American Institute of Mathematical Sciences

Advanced
January  2017, 13(1): 47-62. doi: 10.3934/jimo.2016003

Line search globalization of a semismooth Newton method for operator equations in Hilbert spaces with applications in optimal control

Matthias Gerdts , Stefan Horn and  Sven-Joachim Kimmerle ,

Institut für Mathematik und Rechneranwendung (LRT-1), Universität der Bundeswehr München, Werner-Heisenberg-Weg 39, 85577 Neubiberg/München, Germany

* Corresponding author

Received  May 2014 Published  March 2016

We consider the numerical solution of nonlinear and nonsmooth operator equations in Hilbert spaces. A semismooth Newton method is used for search direction generation. The operator equation is solved by a globalized semismooth Newton method that is equipped with an Armijo linesearch using a semismooth merit function. We prove that an accumulation point of the globalized algorithm is a solution and transition to fast local convergence under a directional Hadamard-like continuity assumption on the Newton matrix. In particular, no auxiliary descent directions or smoothing steps are required. Finally, we apply this method to a control-constrained and also to a regularized state-constrained optimal control problem subject to partial differential equations.

Keywords: Semismooth Newton method, line search globalization, superlinear convergence, optimal control of partial differential equations, control constraints, state constraints.
Mathematics Subject Classification: Primary: 49J20, 49J52, 49M15; Secondary: 90C56, 65K10, 65N12.
Citation: Matthias Gerdts, Stefan Horn, Sven-Joachim Kimmerle. Line search globalization of a semismooth Newton method for operator equations in Hilbert spaces with applications in optimal control. Journal of Industrial & Management Optimization, 2017, 13 (1) : 47-62. doi: 10.3934/jimo.2016003
References:
[1]

J. F. Bonnans and A. Shapiro, Perturbation Analysis of Optimization Problems, Springer Series in Operations Research, Springer, New York, 2000. doi: 10.1007/978-1-4612-1394-9.  Google Scholar

[2]

E. Casas, Using piecewise linear functions in the numerical approximation of semilinear elliptic control problems, Adv. Comput. Math., 26 (2007), 137-153.  doi: 10.1007/s10444-004-4142-0.  Google Scholar

[3]

E. Casas and F. Tröltzsch, Second order optimality conditions and their role in PDE control, Jahresber. Dtsch. Math.-Ver., 117 (2015), 3-44.  doi: 10.1365/s13291-014-0109-3.  Google Scholar

[4]

X. Chen, Z. Nashed and L. Qi, Smoothing methods and semismooth methods for nondifferentiable operator equations, SIAM J. Numer. Anal., 38 (2000), 1200-1216.  doi: 10.1137/S0036142999356719.  Google Scholar

[5]

R. Correa and A. Joffre, Tangentially continuous directional derivatives in nonsmooth analysis, J. Optim. Theory Appl., 61 (1989), 1-21.  doi: 10.1007/BF00940840.  Google Scholar

[6]

M. Gerdts, Global convergence of a nonsmooth Newton's method for control-state constrained optimal control problems, SIAM J. Optim., 19 (2008), 326{350; M. Gerdts and B. Hüpping, Erratum: Global convergence of a nonsmooth Newton's method for control-state constrained optimal control problems, Technical report, Universität der Bundeswehr München, Neubiberg (2011). Available online: http://www.unibw.de/lrt1/gerdts/forschung/publikationen/erratum-siam-19-1-2008-326-350-full.pdf. doi: 10.1137/060657546.  Google Scholar

[7]

M. Gerdts and M. Kunkel, A nonsmooth Newton's method for discretized optimal control problems with state and control constraints, J. Ind. Manag. Opt., 4 (2008), 247-270.  doi: 10.3934/jimo.2008.4.247.  Google Scholar

[8]

M. Hintermüller, K. Ito and K. Kunisch, The primal-dual active set strategy as a semismooth Newton method, SIAM J. Optim., 13 (2003), 865-888.  doi: 10.1137/S1052623401383558.  Google Scholar

[9]

M. Hintermüller, F. Tröltzsch and I. Yousept, Mesh-independence of semismooth Newton methods for Lavrentiev-regularized state constrained nonlinear optimal control problems, Numer. Math., 108 (2008), 571-603.  doi: 10.1007/s00211-007-0134-6.  Google Scholar

[10]

M. Hintermüller and M. Ulbrich, A mesh-independence result for semismooth Newton methods, Math. Program., Ser. B, 101 (2004), 151-184.  doi: 10.1007/s10107-004-0540-9.  Google Scholar

[11]

M. Hinze, R. Pinnau, M. Ulbrich and S. Ulbrich, Optimization with PDE Constraints, Math. Modelling: Theory and Applications, Vol. 23, Springer, New York, 2009. doi: 10.1007/978-1-4020-8839-1.  Google Scholar

[12]

M. Hinze and M. Vierling, The semi-smooth Newton method for variationally discretized control constrained elliptic optimal control problems; implementation, convergence and globalization, Optim. Methods Softw., 27 (2012), 933-950.  doi: 10.1080/10556788.2012.676046.  Google Scholar

[13]

M. Hinze and M. Vierling, A globalized semi-smooth Newton method for variational discretization of control constrained elliptic optimal control problems, in Constrained Optimization and Optimal Control for Partial Differential Equations (eds. G. Leugering et al.), Int. Ser. Numer. Math., 160, Birkhäuser/Springer, Basel, 2012,171-182. doi: 10.1007/978-3-0348-0133-1_9.  Google Scholar

[14]

S. Horn, Fixpunktiterationsverfahren für PDE-restringierte Optimalsteuerungsverfahren, Master thesis, Universität der Bundeswehr München, Neubiberg, 2012. Google Scholar

[15]

K. Ito and K. Kunisch, Applications of semi-smooth Newton methods to variational inequalities, in Control of Coupled Partial Differential Equations (eds. K. Kunisch, G. Leugering, J. Sprekels and F. Tröltzsch), Internat. Ser. Numer. Math., 155, Birkhäuser, Basel, 2007, 175-192. doi: 10.1007/978-3-7643-7721-2_8.  Google Scholar

[16]

K. Ito and K. Kunisch, On a semi-smooth Newton method and its globalization, Math. Program., Ser. A, 118 (2009), 347-370.  doi: 10.1007/s10107-007-0196-3.  Google Scholar

[17]

A. Kröner, K. Kunisch and B. Vexler, Semismooth Newton methods for optimal control of the wave equation with control constraints, SIAM J. Control Optim., 49 (2011), 830-858.  doi: 10.1137/090766541.  Google Scholar

[18]

B. Kummer, Newton's method for non-differentiable functions, in Advances in Mathematical Optimization (eds. J. Guddat, et al.), Math. Res., 45, Akademie-Verlag, Berlin, 1988,114-125.  Google Scholar

[19]

B. Kummer, Newton's method based on generalized derivatives for nonsmooth functions: Convergence analysis, in Advances in Optimization (Lambrecht 1991) (eds. W. Oettli and D. Pallaschke), Lecture Notes in Econom. and Math. Systems, 382, Springer, Berlin, 1992, 171-194. doi: 10.1007/978-3-642-51682-5_12.  Google Scholar

[20]

A. Rösch and D. Wachsmuth, Semi-smooth Newton's method for an optimal control problem with control and mixed control-state constraints, Optim. Methods Softw., 26 (2011), 169-186.  doi: 10.1080/10556780903548257.  Google Scholar

[21]

A. Schiela, A simplified approach to semismooth Newton methods in function space, SIAM J. Optim., 19 (2008), 1417-1432.  doi: 10.1137/060674375.  Google Scholar

[22]

M. Ulbrich, Nonsmooth Newton-like Methods for Variational Inequalities and Constrained Optimization Problems in Function Spaces, Habilitation thesis, Technical University Munich, München, 2001. Google Scholar

[23]

M. Ulbrich, Semismooth Newton methods for operator equations in function spaces, SIAM J. Optim., 13 (2003), 805-842.  doi: 10.1137/S1052623400371569.  Google Scholar

[24]

M. Ulbrich, Semismooth Newton Methods for Variational Inequalities and Constrained Optimization Problems in Function Spaces, MOS-SIAM Series on Optimization, 11, SIAM/MOS, Philadelphia, 2011. doi: 10.1137/1.9781611970692.  Google Scholar

show all references

References:
[1]

J. F. Bonnans and A. Shapiro, Perturbation Analysis of Optimization Problems, Springer Series in Operations Research, Springer, New York, 2000. doi: 10.1007/978-1-4612-1394-9.  Google Scholar

[2]

E. Casas, Using piecewise linear functions in the numerical approximation of semilinear elliptic control problems, Adv. Comput. Math., 26 (2007), 137-153.  doi: 10.1007/s10444-004-4142-0.  Google Scholar

[3]

E. Casas and F. Tröltzsch, Second order optimality conditions and their role in PDE control, Jahresber. Dtsch. Math.-Ver., 117 (2015), 3-44.  doi: 10.1365/s13291-014-0109-3.  Google Scholar

[4]

X. Chen, Z. Nashed and L. Qi, Smoothing methods and semismooth methods for nondifferentiable operator equations, SIAM J. Numer. Anal., 38 (2000), 1200-1216.  doi: 10.1137/S0036142999356719.  Google Scholar

[5]

R. Correa and A. Joffre, Tangentially continuous directional derivatives in nonsmooth analysis, J. Optim. Theory Appl., 61 (1989), 1-21.  doi: 10.1007/BF00940840.  Google Scholar

[6]

M. Gerdts, Global convergence of a nonsmooth Newton's method for control-state constrained optimal control problems, SIAM J. Optim., 19 (2008), 326{350; M. Gerdts and B. Hüpping, Erratum: Global convergence of a nonsmooth Newton's method for control-state constrained optimal control problems, Technical report, Universität der Bundeswehr München, Neubiberg (2011). Available online: http://www.unibw.de/lrt1/gerdts/forschung/publikationen/erratum-siam-19-1-2008-326-350-full.pdf. doi: 10.1137/060657546.  Google Scholar

[7]

M. Gerdts and M. Kunkel, A nonsmooth Newton's method for discretized optimal control problems with state and control constraints, J. Ind. Manag. Opt., 4 (2008), 247-270.  doi: 10.3934/jimo.2008.4.247.  Google Scholar

[8]

M. Hintermüller, K. Ito and K. Kunisch, The primal-dual active set strategy as a semismooth Newton method, SIAM J. Optim., 13 (2003), 865-888.  doi: 10.1137/S1052623401383558.  Google Scholar

[9]

M. Hintermüller, F. Tröltzsch and I. Yousept, Mesh-independence of semismooth Newton methods for Lavrentiev-regularized state constrained nonlinear optimal control problems, Numer. Math., 108 (2008), 571-603.  doi: 10.1007/s00211-007-0134-6.  Google Scholar

[10]

M. Hintermüller and M. Ulbrich, A mesh-independence result for semismooth Newton methods, Math. Program., Ser. B, 101 (2004), 151-184.  doi: 10.1007/s10107-004-0540-9.  Google Scholar

[11]

M. Hinze, R. Pinnau, M. Ulbrich and S. Ulbrich, Optimization with PDE Constraints, Math. Modelling: Theory and Applications, Vol. 23, Springer, New York, 2009. doi: 10.1007/978-1-4020-8839-1.  Google Scholar

[12]

M. Hinze and M. Vierling, The semi-smooth Newton method for variationally discretized control constrained elliptic optimal control problems; implementation, convergence and globalization, Optim. Methods Softw., 27 (2012), 933-950.  doi: 10.1080/10556788.2012.676046.  Google Scholar

[13]

M. Hinze and M. Vierling, A globalized semi-smooth Newton method for variational discretization of control constrained elliptic optimal control problems, in Constrained Optimization and Optimal Control for Partial Differential Equations (eds. G. Leugering et al.), Int. Ser. Numer. Math., 160, Birkhäuser/Springer, Basel, 2012,171-182. doi: 10.1007/978-3-0348-0133-1_9.  Google Scholar

[14]

S. Horn, Fixpunktiterationsverfahren für PDE-restringierte Optimalsteuerungsverfahren, Master thesis, Universität der Bundeswehr München, Neubiberg, 2012. Google Scholar

[15]

K. Ito and K. Kunisch, Applications of semi-smooth Newton methods to variational inequalities, in Control of Coupled Partial Differential Equations (eds. K. Kunisch, G. Leugering, J. Sprekels and F. Tröltzsch), Internat. Ser. Numer. Math., 155, Birkhäuser, Basel, 2007, 175-192. doi: 10.1007/978-3-7643-7721-2_8.  Google Scholar

[16]

K. Ito and K. Kunisch, On a semi-smooth Newton method and its globalization, Math. Program., Ser. A, 118 (2009), 347-370.  doi: 10.1007/s10107-007-0196-3.  Google Scholar

[17]

A. Kröner, K. Kunisch and B. Vexler, Semismooth Newton methods for optimal control of the wave equation with control constraints, SIAM J. Control Optim., 49 (2011), 830-858.  doi: 10.1137/090766541.  Google Scholar

[18]

B. Kummer, Newton's method for non-differentiable functions, in Advances in Mathematical Optimization (eds. J. Guddat, et al.), Math. Res., 45, Akademie-Verlag, Berlin, 1988,114-125.  Google Scholar

[19]

B. Kummer, Newton's method based on generalized derivatives for nonsmooth functions: Convergence analysis, in Advances in Optimization (Lambrecht 1991) (eds. W. Oettli and D. Pallaschke), Lecture Notes in Econom. and Math. Systems, 382, Springer, Berlin, 1992, 171-194. doi: 10.1007/978-3-642-51682-5_12.  Google Scholar

[20]

A. Rösch and D. Wachsmuth, Semi-smooth Newton's method for an optimal control problem with control and mixed control-state constraints, Optim. Methods Softw., 26 (2011), 169-186.  doi: 10.1080/10556780903548257.  Google Scholar

[21]

A. Schiela, A simplified approach to semismooth Newton methods in function space, SIAM J. Optim., 19 (2008), 1417-1432.  doi: 10.1137/060674375.  Google Scholar

[22]

M. Ulbrich, Nonsmooth Newton-like Methods for Variational Inequalities and Constrained Optimization Problems in Function Spaces, Habilitation thesis, Technical University Munich, München, 2001. Google Scholar

[23]

M. Ulbrich, Semismooth Newton methods for operator equations in function spaces, SIAM J. Optim., 13 (2003), 805-842.  doi: 10.1137/S1052623400371569.  Google Scholar

[24]

M. Ulbrich, Semismooth Newton Methods for Variational Inequalities and Constrained Optimization Problems in Function Spaces, MOS-SIAM Series on Optimization, 11, SIAM/MOS, Philadelphia, 2011. doi: 10.1137/1.9781611970692.  Google Scholar

Figure 1.  Discrete solution of (P2) for $h=1/64$. Left-hand side: Optimal state $y^h(x_1, x_2)$ on $x_3$ axis vs. $x_1$ and $x_2$. Right-hand side: Optimal control $u^h(x_1, x_2)$ on $x_3$ axis vs. $x_1$ and $x_2$
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 2.  Discrete solution of (P3) for $h=1/32$. Left-hand side: Optimal state $y^h(x_1, x_2)$ on $x_3$ axis vs. $x_1$ and $x_2$. Right-hand side: Optimal control $u^h(x_1, x_2)$ on $x_3$ axis vs. $x_1$ and $x_2$
Figure Options

Download full-size image

Download as PowerPoint slide

Table 1.  Iteration history for the solution of problem (P2) for $h=1/256$. Step size $\alpha_k$, norm $\Vert f(z_k)\Vert_{Z^*}$ and norm of the search direction $\Vert s_k\Vert_Z$ for the $k$-th iterate. These numerical results exhibit the superlinear convergence
$k$ $\alpha_k$ $\left\Vert f(z_k)\right\Vert_{Z^*}$ $\left\Vert s_k\right\Vert_Z$
0- 5.43111E-02 -
1 9.76563E-04 5.43015E-02 5.00085E+00
2 3.12500E-02 5.36304E-02 1.82556E+00
3 5.00000E-01 2.91839E-02 1.55585E+00
4 6.25000E-02 2.75202E-02 3.87423E-01
┆
16 0.25000E+00 1.65715E-02 2.48095E-02
17 0.50000E+00 1.38976E-02 1.28644E-02
18 1.00000E+00 1.24060E-02 6.81858E-03
19 1.00000E+00 9.44693E-03 1.63072E-03
20 1.00000E+00 5.60965E-06 4.47294E-05
21 1.00000E+00 2.27743E-15 1.57318E-11
Table Options

Download as excel

$k$ $\alpha_k$ $\left\Vert f(z_k)\right\Vert_{Z^*}$ $\left\Vert s_k\right\Vert_Z$
0- 5.43111E-02 -
1 9.76563E-04 5.43015E-02 5.00085E+00
2 3.12500E-02 5.36304E-02 1.82556E+00
3 5.00000E-01 2.91839E-02 1.55585E+00
4 6.25000E-02 2.75202E-02 3.87423E-01
┆
16 0.25000E+00 1.65715E-02 2.48095E-02
17 0.50000E+00 1.38976E-02 1.28644E-02
18 1.00000E+00 1.24060E-02 6.81858E-03
19 1.00000E+00 9.44693E-03 1.63072E-03
20 1.00000E+00 5.60965E-06 4.47294E-05
21 1.00000E+00 2.27743E-15 1.57318E-11
Table 2.  Iteration history for the solution of problem (P3) for $h=1/128$. Step size $\alpha_k$, norm $\Vert f(z_k)\Vert_{Z^*}$ and norm of the search direction $\Vert s_k\Vert_Z$ for the $k$-th iterate. We observe transition to local superlinear convergence
$k$ $\alpha$ $\left\Vert f(z_k)\right\Vert_{Z^*}$ $\left\Vert s_k\right\Vert_{Z^*}$
0 - 7.59736E+05 -
1 1.00000E+00 1.14024E+05 1.93458E+03
2 1.00000E+00 3.61620E+04 7.83427E+02
3 1.00000E+00 1.59280E+04 1.62132E+03
┆
9 2.50000E-01 3.03640E-02 1.48894E-01
10 1.00000E+00 9.69843E-03 3.23249E-02
11 1.00000E+00 2.42234E-05 9.90030E-06
12 1.00000E+00 3.15754E-06 2.56947E-07
13 1.00000E+00 1.14583E-07 1.59876E-09
14 1.00000E+00 1.70426E-13 5.17916e-13
Table Options

Download as excel

$k$ $\alpha$ $\left\Vert f(z_k)\right\Vert_{Z^*}$ $\left\Vert s_k\right\Vert_{Z^*}$
0 - 7.59736E+05 -
1 1.00000E+00 1.14024E+05 1.93458E+03
2 1.00000E+00 3.61620E+04 7.83427E+02
3 1.00000E+00 1.59280E+04 1.62132E+03
┆
9 2.50000E-01 3.03640E-02 1.48894E-01
10 1.00000E+00 9.69843E-03 3.23249E-02
11 1.00000E+00 2.42234E-05 9.90030E-06
12 1.00000E+00 3.15754E-06 2.56947E-07
13 1.00000E+00 1.14583E-07 1.59876E-09
14 1.00000E+00 1.70426E-13 5.17916e-13
[1]

Matthias Gerdts, Martin Kunkel. A nonsmooth Newton's method for discretized optimal control problems with state and control constraints. Journal of Industrial & Management Optimization, 2008, 4 (2) : 247-270. doi: 10.3934/jimo.2008.4.247
[2]

Xiaojiao Tong, Shuzi Zhou. A smoothing projected Newton-type method for semismooth equations with bound constraints. Journal of Industrial & Management Optimization, 2005, 1 (2) : 235-250. doi: 10.3934/jimo.2005.1.235
[3]

Shuang Chen, Li-Ping Pang, Dan Li. An inexact semismooth Newton method for variational inequality with symmetric cone constraints. Journal of Industrial & Management Optimization, 2015, 11 (3) : 733-746. doi: 10.3934/jimo.2015.11.733
[4]

Eduardo Casas, Fredi Tröltzsch. Sparse optimal control for the heat equation with mixed control-state constraints. Mathematical Control & Related Fields, 2020, 10 (3) : 471-491. doi: 10.3934/mcrf.2020007
[5]

Elimhan N. Mahmudov. Optimal control of second order delay-discrete and delay-differential inclusions with state constraints. Evolution Equations & Control Theory, 2018, 7 (3) : 501-529. doi: 10.3934/eect.2018024
[6]

Vincenzo Basco, Piermarco Cannarsa, Hélène Frankowska. Necessary conditions for infinite horizon optimal control problems with state constraints. Mathematical Control & Related Fields, 2018, 8 (3&4) : 535-555. doi: 10.3934/mcrf.2018022
[7]

Luís Tiago Paiva, Fernando A. C. C. Fontes. Adaptive time--mesh refinement in optimal control problems with state constraints. Discrete & Continuous Dynamical Systems - A, 2015, 35 (9) : 4553-4572. doi: 10.3934/dcds.2015.35.4553
[8]

Theodore Tachim-Medjo. Optimal control of a two-phase flow model with state constraints. Mathematical Control & Related Fields, 2016, 6 (2) : 335-362. doi: 10.3934/mcrf.2016006
[9]

Stefan Doboszczak, Manil T. Mohan, Sivaguru S. Sritharan. Pontryagin maximum principle for the optimal control of linearized compressible navier-stokes equations with state constraints. Evolution Equations & Control Theory, 2020  doi: 10.3934/eect.2020110
[10]

Thomas Lorenz. Partial differential inclusions of transport type with state constraints. Discrete & Continuous Dynamical Systems - B, 2019, 24 (3) : 1309-1340. doi: 10.3934/dcdsb.2019018
[11]

Piermarco Cannarsa, Hélène Frankowska, Elsa M. Marchini. On Bolza optimal control problems with constraints. Discrete & Continuous Dynamical Systems - B, 2009, 11 (3) : 629-653. doi: 10.3934/dcdsb.2009.11.629
[12]

Huaiqiang Yu, Bin Liu. Pontryagin's principle for local solutions of optimal control governed by the 2D Navier-Stokes equations with mixed control-state constraints. Mathematical Control & Related Fields, 2012, 2 (1) : 61-80. doi: 10.3934/mcrf.2012.2.61
[13]

Alexander Tyatyushkin, Tatiana Zarodnyuk. Numerical method for solving optimal control problems with phase constraints. Numerical Algebra, Control & Optimization, 2017, 7 (4) : 481-492. doi: 10.3934/naco.2017030
[14]

Changjun Yu, Shuxuan Su, Yanqin Bai. On the optimal control problems with characteristic time control constraints. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021021
[15]

M. Arisawa, P.-L. Lions. Continuity of admissible trajectories for state constraints control problems. Discrete & Continuous Dynamical Systems - A, 1996, 2 (3) : 297-305. doi: 10.3934/dcds.1996.2.297
[16]

Mikhail Gusev. On reachability analysis for nonlinear control systems with state constraints. Conference Publications, 2015, 2015 (special) : 579-587. doi: 10.3934/proc.2015.0579
[17]

Ryan Loxton, Qun Lin, Volker Rehbock, Kok Lay Teo. Control parameterization for optimal control problems with continuous inequality constraints: New convergence results. Numerical Algebra, Control & Optimization, 2012, 2 (3) : 571-599. doi: 10.3934/naco.2012.2.571
[18]

Xiaojiao Tong, Felix F. Wu, Yongping Zhang, Zheng Yan, Yixin Ni. A semismooth Newton method for solving optimal power flow. Journal of Industrial & Management Optimization, 2007, 3 (3) : 553-567. doi: 10.3934/jimo.2007.3.553
[19]

IvÁn Area, FaÏÇal NdaÏrou, Juan J. Nieto, Cristiana J. Silva, Delfim F. M. Torres. Ebola model and optimal control with vaccination constraints. Journal of Industrial & Management Optimization, 2018, 14 (2) : 427-446. doi: 10.3934/jimo.2017054
[20]

Maria do Rosário de Pinho, Ilya Shvartsman. Lipschitz continuity of optimal control and Lagrange multipliers in a problem with mixed and pure state constraints. Discrete & Continuous Dynamical Systems - A, 2011, 29 (2) : 505-522. doi: 10.3934/dcds.2011.29.505

2019 Impact Factor: 1.366

Tools

Metrics

  • PDF downloads (160)
  • HTML views (351)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences