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

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.

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. ChenZ. 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üllerK. 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üllerF. 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önerK. 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. ChenZ. 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üllerK. 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üllerF. 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önerK. 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 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$
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
$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
$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]

Zuliang Lu, Fei Huang, Xiankui Wu, Lin Li, Shang Liu. Convergence and quasi-optimality of $ L^2- $norms based an adaptive finite element method for nonlinear optimal control problems. Electronic Research Archive, 2020, 28 (4) : 1459-1486. doi: 10.3934/era.2020077

[2]

Lars Grüne, Matthias A. Müller, Christopher M. Kellett, Steven R. Weller. Strict dissipativity for discrete time discounted optimal control problems. Mathematical Control & Related Fields, 2020  doi: 10.3934/mcrf.2020046

[3]

Lorenzo Zambotti. A brief and personal history of stochastic partial differential equations. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 471-487. doi: 10.3934/dcds.2020264

[4]

Yueyang Zheng, Jingtao Shi. A stackelberg game of backward stochastic differential equations with partial information. Mathematical Control & Related Fields, 2020  doi: 10.3934/mcrf.2020047

[5]

Youming Guo, Tingting Li. Optimal control strategies for an online game addiction model with low and high risk exposure. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020347

[6]

José Madrid, João P. G. Ramos. On optimal autocorrelation inequalities on the real line. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020271

[7]

Bernard Bonnard, Jérémy Rouot. Geometric optimal techniques to control the muscular force response to functional electrical stimulation using a non-isometric force-fatigue model. Journal of Geometric Mechanics, 2020  doi: 10.3934/jgm.2020032

[8]

Tommi Brander, Joonas Ilmavirta, Petteri Piiroinen, Teemu Tyni. Optimal recovery of a radiating source with multiple frequencies along one line. Inverse Problems & Imaging, 2020, 14 (6) : 967-983. doi: 10.3934/ipi.2020044

[9]

Awais Younus, Zoubia Dastgeer, Nudrat Ishaq, Abdul Ghaffar, Kottakkaran Sooppy Nisar, Devendra Kumar. On the observability of conformable linear time-invariant control systems. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020444

[10]

Hua Qiu, Zheng-An Yao. The regularized Boussinesq equations with partial dissipations in dimension two. Electronic Research Archive, 2020, 28 (4) : 1375-1393. doi: 10.3934/era.2020073

[11]

Fabio Camilli, Giulia Cavagnari, Raul De Maio, Benedetto Piccoli. Superposition principle and schemes for measure differential equations. Kinetic & Related Models, , () : -. doi: 10.3934/krm.2020050

[12]

Li-Bin Liu, Ying Liang, Jian Zhang, Xiaobing Bao. A robust adaptive grid method for singularly perturbed Burger-Huxley equations. Electronic Research Archive, 2020, 28 (4) : 1439-1457. doi: 10.3934/era.2020076

[13]

Thabet Abdeljawad, Mohammad Esmael Samei. Applying quantum calculus for the existence of solution of $ q $-integro-differential equations with three criteria. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020440

[14]

Fathalla A. Rihan, Hebatallah J. Alsakaji. Stochastic delay differential equations of three-species prey-predator system with cooperation among prey species. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020468

[15]

Marion Darbas, Jérémy Heleine, Stephanie Lohrengel. Numerical resolution by the quasi-reversibility method of a data completion problem for Maxwell's equations. Inverse Problems & Imaging, 2020, 14 (6) : 1107-1133. doi: 10.3934/ipi.2020056

[16]

Thierry Horsin, Mohamed Ali Jendoubi. On the convergence to equilibria of a sequence defined by an implicit scheme. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020465

[17]

Andy Hammerlindl, Jana Rodriguez Hertz, Raúl Ures. Ergodicity and partial hyperbolicity on Seifert manifolds. Journal of Modern Dynamics, 2020, 16: 331-348. doi: 10.3934/jmd.2020012

[18]

Soniya Singh, Sumit Arora, Manil T. Mohan, Jaydev Dabas. Approximate controllability of second order impulsive systems with state-dependent delay in Banach spaces. Evolution Equations & Control Theory, 2020  doi: 10.3934/eect.2020103

[19]

Siyang Cai, Yongmei Cai, Xuerong Mao. A stochastic differential equation SIS epidemic model with regime switching. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020317

[20]

Zexuan Liu, Zhiyuan Sun, Jerry Zhijian Yang. A numerical study of superconvergence of the discontinuous Galerkin method by patch reconstruction. Electronic Research Archive, 2020, 28 (4) : 1487-1501. doi: 10.3934/era.2020078

2019 Impact Factor: 1.366

Metrics

  • PDF downloads (142)
  • HTML views (349)
  • Cited by (0)

[Back to Top]