Philippe L. Toint – Page 8 – Optimization Online

Nonlinear Optimization, Nonlinear Systems and Least-Squares, Unconstrained Optimization evaluation complexity, nonconvex optimization, second order optimality conditions, worst-case analysis

This paper examines worst-case evaluation bounds for finding weak minimizers in unconstrained optimization. For the cubic regularization algorithm, Nesterov and Polyak (2006) and Cartis, Gould and Toint (2010) show that at most O(epsilon^{-3}) iterations may have to be performed for finding an iterate which is within epsilon of satisfying second-order optimality conditions. We first show … Read more

Preconditioning and Globalizing Conjugate Gradients in Dual Space for Quadratically Penalized Nonlinear-Least Squares Problems

Published: 2010/12/16

Serge Gratton

Nonlinear Systems and Least-Squares, Optimization of Simulated Systems, Optimization of Systems modeled by PDEs conjugate-gradient methods, data assimilation, dual-space minimization, globalization, preconditioning, trust-region methods

Selime Gürol

When solving nonlinear least-squares problems, it is often useful to regularize the problem using a quadratic term, a practice which is especially common in applications arising in inverse calculations. A solution method derived from a trust-region Gauss-Newton algorithm is analyzed for such applications, where, contrary to the standard algorithm, the least-squares subproblem solved at each … Read more

Solving structured nonlinear least-squares and nonlinear feasibility problems with expensive functions

Published: 2010/12/14

Constrained Nonlinear Optimization, Nonlinear Optimization, Nonlinear Systems and Least-Squares derivative-free, feasibility problem, global convergence, multidimensional filter, nonlinear least squares, nonlinear systems, structured problems, trust-region methods

We present an algorithm for nonlinear least-squares and nonlinear feasibility problems, i.e. for systems of nonlinear equations and nonlinear inequalities, which depend on the outcome of expensive functions for which derivatives are assumed to be unavailable. Our algorithm combines derivative-free techniques with filter trust-region methods to keep the number of expensive function evaluations low and … Read more

Evaluation complexity of adaptive cubic regularization methods for convex unconstrained optimization

Published: 2010/11/05

Convex and Nonsmooth Optimization, Nonlinear Optimization convex optimization, cubic regularization

The adaptive cubic regularization algorithms described in Cartis, Gould & Toint (2009, 2010) for unconstrained (nonconvex) optimization are shown to have improved worst-case efficiency in terms of the function- and gradient-evaluation count when applied to convex and strongly convex objectives. In particular, our complexity upper bounds match in order (as a function of the accuracy … Read more

On the oracle complexity of first-order and derivative-free algorithms for smooth nonconvex minimization

Published: 2010/10/19

Nonlinear Systems and Least-Squares, Unconstrained Optimization derivative-free optimization, finite differences, first-order methods, nonconvex optimization, oracle complexity, worst-case analysis

The (optimal) function/gradient evaluations worst-case complexity analysis available for the Adaptive Regularizations algorithms with Cubics (ARC) for nonconvex smooth unconstrained optimization is extended to finite-difference versions of this algorithm, yielding complexity bounds for first-order and derivative free methods applied on the same problem class. A comparison with the results obtained for derivative-free methods by Vicente … Read more

Using approximate secant equations in limited memory methods for multilevel unconstrained optimization

Published: 2009/12/01

Serge Gratton

Vincent Malmedy

Optimization of Systems modeled by PDEs, Unconstrained Optimization limited-memory algorithms, multiobjective optimization, nonlinear conjugate gradient methods, nonlinear optimization, quasi-newton methods

The properties of multilevel optimization problems defined on a hierarchy of discretization grids can be used to define approximate secant equations, which describe the second-order behaviour of the objective function. Following earlier work by Gratton and Toint (2009), we introduce a quasi-Newton method (with a linesearch) and a nonlinear conjugate gradient method that both take … Read more

On the complexity of steepest descent, Newton’s and regularized Newton’s methods for nonconvex unconstrained optimization

Published: 2009/10/16

Unconstrained Optimization complexity, nonconvex unconstrained optimization, steepest descent

It is shown that the steepest descent and Newton’s method for unconstrained nonconvex optimization under standard assumptions may be both require a number of iterations and function evaluations arbitrarily close to O(epsilon^{-2}) to drive the norm of the gradient below epsilon. This shows that the upper bound of O(epsilon^{-2}) evaluations known for the steepest descent … Read more

Stopping rules and backward error analysis for bound-constrained optimization

Published: 2009/10/15

Serge Gratton

Bound-constrained Optimization, Optimization Software Design Principles backward error, bound constraints, multicriteria optimization, nonlinear optimization, stopping criterion

Mélodie Mouffe

Termination criteria for the iterative solution of bound-constrained optimization problems are examined in the light of backward error analysis. It is shown that the problem of determining a suitable perturbation on the problem’s data corresponding to the definition of the backward error is analytically solvable under mild assumptions. Moreover, a link between existing termination criteria … Read more

An adaptive cubic regularisation algorithm for nonconvex optimization with convex constraints and its function-evaluation complexity

Published: 2009/02/20