On the use of the energy norm in trust-region and adaptive cubic regularization subproblems.

*(English)*Zbl 1390.90511Summary: We consider solving unconstrained optimization problems by means of two popular globalization techniques: trust-region (TR) algorithms and adaptive regularized framework using cubics (ARC). Both techniques require the solution of a so-called “subproblem” in which a trial step is computed by solving an optimization problem involving an approximation of the objective function, called “the model”. The latter is supposed to be adequate in a neighborhood of the current iterate. In this paper, we address an important practical question related with the choice of the norm for defining the neighborhood. More precisely, assuming here that the Hessian \(B\) of the model is symmetric positive definite, we propose the use of the so-called “energy norm” – defined by \(\| x\| _B= \sqrt{x^TBx}\) for all \(x \in \mathbb {R}^n\) – in both TR and ARC techniques. We show that the use of this norm induces remarkable relations between the trial step of both methods that can be used to obtain efficient practical algorithms. We furthermore consider the use of truncated Krylov subspace methods to obtain an approximate trial step for large scale optimization. Within the energy norm, we obtain line search algorithms along the Newton direction, with a special backtracking strategy and an acceptability condition in the spirit of TR/ARC methods. The new line search algorithm, derived by ARC, enjoys a worst-case iteration complexity of \(\mathcal {O}(\epsilon ^{-3/2})\). We show the good potential of the energy norm on a set of numerical experiments.

##### MSC:

90C30 | Nonlinear programming |

##### Keywords:

nonlinear optimization; unconstrained optimization; trust-region algorithm; adaptive regularized framework using cubics; line search algorithm; energy norm; Krylov subspace methods; conjugate gradient
PDF
BibTeX
XML
Cite

\textit{E. Bergou} et al., Comput. Optim. Appl. 68, No. 3, 533--554 (2017; Zbl 1390.90511)

Full Text:
DOI

##### References:

[1] | Arioli, M; Loghin, D; Wathen, AJ, Stopping criteria for iterations in finite element methods, Numer. Math., 99, 381-410, (2005) · Zbl 1069.65124 |

[2] | Arioli, M; Noulard, E; Russo, A, Stopping criteria for iterative solvers, Calcolo, 38, 97-112, (2001) · Zbl 1072.65045 |

[3] | Bellavia, S; Morini, B; Cartis, C; Gould, NIM; Toint, PhL, Convergence of a regularized Euclidean residual algorithm for nonlinear least-squares, SIAM J. Numer. Anal., 48, 1-29, (2010) · Zbl 1218.90182 |

[4] | Bianconcini, T; Liuzzi, G; Morini, B; Sciandrone, M, On the use of iterative methods in cubic regularization for unconstrained optimization, Comput. Optim. Appl., 60, 35-57, (2014) · Zbl 1308.90166 |

[5] | Cartis, C; Gould, NIM; Toint, PhL, Adaptive cubic overestimation methods for unconstrained optimization. part II: worst-case function- and derivative-evaluation complexity, Math. Program., 130, 295-319, (2011) · Zbl 1229.90193 |

[6] | Cartis, C; Gould, NIM; Toint, PhL, Adaptive cubic regularisation methods for unconstrained optimization. part I: wotivation, convergence and numerical results, Math. Program., 127, 245-295, (2011) · Zbl 1229.90192 |

[7] | Conn, A.R., Gould, N.I.M., Toint, PhL: Trust-Region Methods. SIAM, Philadelphia (2000) · Zbl 0958.65071 |

[8] | Courtier, P; Thépaut, J-N; Hollingsworth, A, A strategy for operational implementation of 4D-var, using an incremental approach, Q. J. R. Meteorol. Soc., 120, 1367-1388, (1994) |

[9] | Curtis, FE; Robinson, DP; Samadi, M, A trust region algorithm with a worst-case iteration complexity of \(O(ϵ ^{-3/2})\) for nonconvex optimization, Math. Program., 162, 1-32, (2017) · Zbl 1360.49020 |

[10] | Dolan, ED; Moré, JJ, Benchmarking optimization software with performance profiles, Math. Program., 91, 201-213, (2002) · Zbl 1049.90004 |

[11] | Gould, NIM; Lucidi, S; Roma, M; Toint, PhL, Solving the trust-region subproblem using the Lanczos method, SIAM J. Optim., 9, 504-525, (1999) · Zbl 1047.90510 |

[12] | Gould, NIM; Orban, D; Toint, PhL, GALAHAD, a library of thread-safe Fortran 90 packages for large-scale nonlinear optimization, ACM Trans. Math. Softw., 29, 353-372, (2003) · Zbl 1068.90525 |

[13] | Gratton, S; Mouffe, M; Sartenaer, A; Toint, PhL; Tomanos, D, Numerical experience with a recursive trust-region method for multilevel nonlinear bound-constrained optimization, Optim. Methods Softw., 25, 359-386, (2010) · Zbl 1190.90209 |

[14] | Griewank, A.: The modification of Newton’s method for unconstrained optimization by bounding cubic terms. Technical Report NA/12, Department of Applied Mathematics and Theoretical Physics, University of Cambridge (1981) |

[15] | Moré, JJ; Garbow, BS; Hillstrom, KE, Testing unconstrained optimization software, ACM Trans. Math. Softw., 7, 17-41, (1981) · Zbl 0454.65049 |

[16] | Nesterov, Y; Polyak, BT, Cubic regularization of newton’s method and its global performance, Math. Program., 108, 177-205, (2006) · Zbl 1142.90500 |

[17] | Nocedal, J., Wright, S.J.: Numerical Optimization, 2nd edn. Springer, New York (2006) · Zbl 1104.65059 |

[18] | Powell, MJD; Rosen, JB (ed.); Mangasarian, OL (ed.); Ritter, K (ed.), A new algorithm for unconstrained optimization, 31-65, (1970), New York |

[19] | Trémolet, Y, Model error estimation in 4D-var, Q. J. R. Meteorol. Soc., 133, 1267-1280, (2007) |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.