Article Contents

2017, Volume 13, Issue 1: 47-62. Doi: 10.3934/jimo.2016003

This issue Previous Article Consumption-portfolio optimization and filtering in a hidden Markov-modulated asset price model Next Article The stable duality of DC programs for composite convex functions

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
* Corresponding author

Received: May 2014

Published: August 2017

Abstract / Introduction Full Text(HTML) Figure(2) / Table(2) Related Papers Cited by

Abstract

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:

Full Text(HTML)

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$

Download: Full-size image 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$

Download: Full-size image 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

| Show Table

DownLoad: CSV

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

| Show Table

DownLoad: CSV

Related Papers

Cited by

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.