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$
-
Previous Article
The stable duality of DC programs for composite convex functions
- JIMO Home
- This Issue
-
Next Article
Consumption-portfolio optimization and filtering in a hidden Markov-modulated asset price model
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 |
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 and 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. |
| [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. |
| [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. |
| [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. |
| [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. |
| [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. |
| [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. |
| [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. |
| [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. |
| [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. |
| [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. |
| [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. |
| [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. |
| [14] |
S. Horn, Fixpunktiterationsverfahren für PDE-restringierte Optimalsteuerungsverfahren, Master thesis, Universität der Bundeswehr München, Neubiberg, 2012. |
| [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. |
| [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. |
| [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. |
| [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. |
| [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. |
| [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. |
| [21] |
A. Schiela,
A simplified approach to semismooth Newton methods in function space, SIAM J. Optim., 19 (2008), 1417-1432.
doi: 10.1137/060674375. |
| [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. |
| [23] |
M. Ulbrich,
Semismooth Newton methods for operator equations in function spaces, SIAM J. Optim., 13 (2003), 805-842.
doi: 10.1137/S1052623400371569. |
| [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. |
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. |
| [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. |
| [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. |
| [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. |
| [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. |
| [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. |
| [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. |
| [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. |
| [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. |
| [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. |
| [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. |
| [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. |
| [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. |
| [14] |
S. Horn, Fixpunktiterationsverfahren für PDE-restringierte Optimalsteuerungsverfahren, Master thesis, Universität der Bundeswehr München, Neubiberg, 2012. |
| [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. |
| [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. |
| [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. |
| [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. |
| [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. |
| [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. |
| [21] |
A. Schiela,
A simplified approach to semismooth Newton methods in function space, SIAM J. Optim., 19 (2008), 1417-1432.
doi: 10.1137/060674375. |
| [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. |
| [23] |
M. Ulbrich,
Semismooth Newton methods for operator equations in function spaces, SIAM J. Optim., 13 (2003), 805-842.
doi: 10.1137/S1052623400371569. |
| [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. |
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
| 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 |
| 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
| 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 |
| 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 and 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 and 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 and Management Optimization, 2015, 11 (3) : 733-746. doi: 10.3934/jimo.2015.11.733 |
| [4] |
Nidhal Gammoudi, Hasnaa Zidani. A differential game control problem with state constraints. Mathematical Control and Related Fields, 2022 doi: 10.3934/mcrf.2022008 |
| [5] |
Eduardo Casas, Fredi Tröltzsch. Sparse optimal control for the heat equation with mixed control-state constraints. Mathematical Control and Related Fields, 2020, 10 (3) : 471-491. doi: 10.3934/mcrf.2020007 |
| [6] |
Elimhan N. Mahmudov. Optimal control of second order delay-discrete and delay-differential inclusions with state constraints. Evolution Equations and Control Theory, 2018, 7 (3) : 501-529. doi: 10.3934/eect.2018024 |
| [7] |
Vincenzo Basco, Piermarco Cannarsa, Hélène Frankowska. Necessary conditions for infinite horizon optimal control problems with state constraints. Mathematical Control and Related Fields, 2018, 8 (3&4) : 535-555. doi: 10.3934/mcrf.2018022 |
| [8] |
Luís Tiago Paiva, Fernando A. C. C. Fontes. Adaptive time--mesh refinement in optimal control problems with state constraints. Discrete and Continuous Dynamical Systems, 2015, 35 (9) : 4553-4572. doi: 10.3934/dcds.2015.35.4553 |
| [9] |
Theodore Tachim-Medjo. Optimal control of a two-phase flow model with state constraints. Mathematical Control and Related Fields, 2016, 6 (2) : 335-362. doi: 10.3934/mcrf.2016006 |
| [10] |
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 and Control Theory, 2022, 11 (2) : 347-371. doi: 10.3934/eect.2020110 |
| [11] |
Thomas Lorenz. Partial differential inclusions of transport type with state constraints. Discrete and Continuous Dynamical Systems - B, 2019, 24 (3) : 1309-1340. doi: 10.3934/dcdsb.2019018 |
| [12] |
Piermarco Cannarsa, Hélène Frankowska, Elsa M. Marchini. On Bolza optimal control problems with constraints. Discrete and Continuous Dynamical Systems - B, 2009, 11 (3) : 629-653. doi: 10.3934/dcdsb.2009.11.629 |
| [13] |
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 and Related Fields, 2012, 2 (1) : 61-80. doi: 10.3934/mcrf.2012.2.61 |
| [14] |
Alexander Tyatyushkin, Tatiana Zarodnyuk. Numerical method for solving optimal control problems with phase constraints. Numerical Algebra, Control and Optimization, 2017, 7 (4) : 481-492. doi: 10.3934/naco.2017030 |
| [15] |
Changjun Yu, Shuxuan Su, Yanqin Bai. On the optimal control problems with characteristic time control constraints. Journal of Industrial and Management Optimization, 2022, 18 (2) : 1305-1320. doi: 10.3934/jimo.2021021 |
| [16] |
Xiaojiao Tong, Felix F. Wu, Yongping Zhang, Zheng Yan, Yixin Ni. A semismooth Newton method for solving optimal power flow. Journal of Industrial and Management Optimization, 2007, 3 (3) : 553-567. doi: 10.3934/jimo.2007.3.553 |
| [17] |
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 |
| [18] |
M. Arisawa, P.-L. Lions. Continuity of admissible trajectories for state constraints control problems. Discrete and Continuous Dynamical Systems, 1996, 2 (3) : 297-305. doi: 10.3934/dcds.1996.2.297 |
| [19] |
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 and Optimization, 2012, 2 (3) : 571-599. doi: 10.3934/naco.2012.2.571 |
| [20] |
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 and Management Optimization, 2018, 14 (2) : 427-446. doi: 10.3934/jimo.2017054 |
2021 Impact Factor: 1.411
Tools
Metrics
Other articles
by authors
[Back to Top]