Search

Adaptive cubic regularization methods have emerged as a credible alternative to linesearch and trust-region for smooth nonconvex optimization, with optimal complexity amongst second-order methods. Here we consider a general/new class of adaptive regularization methods that use first- or higher-order local Taylor models of the objective regularized by a(ny) power of the step size and applied to convexly constrained optimization problems. We investigate the worst-case evaluation complexity/global rate of convergence of these algorithms, when the level of sufficient smoothness of the objective may be unknown or may even be absent. We find that the methods accurately reflect in their complexity the degree of smoothness of the objective and satisfy increasingly better bounds with improving model accuracy. The bounds vary continuously and robustly with respect to the regularization power and accuracy of the model and the degree of smoothness of the objective. [ABSTRACT FROM AUTHOR]

Adaptive cubic regularization methods have emerged as a credible alternative to linesearch and trust-region for smooth nonconvex optimization, with optimal complexity amongst second-order methods. Here we consider a general/new class of adaptive regularization methods that use first- or higher-order local Taylor models of the objective regularized by a(ny) power of the step size and applied to convexly constrained optimization problems. We investigate the worst-case evaluation complexity/global rate of convergence of these algorithms, when the level of sufficient smoothness of the objective may be unknown or may even be absent. We find that the methods accurately reflect in their complexity the degree of smoothness of the objective and satisfy increasingly better bounds with improving model accuracy. The bounds vary continuously and robustly with respect to the regularization power and accuracy of the model and the degree of smoothness of the objective. [ABSTRACT FROM AUTHOR]

When solving the general smooth nonlinear and possibly nonconvex optimization problem involving equality and/or inequality constraints, an approximate first-order critical point of accuracy ∊ can be obtained by a second-order method using cubic regularization in at most O(∊-3/2) evaluations of problem functions, the same order bound as in the unconstrained case. This result is obtained by first showing that the same result holds for inequality constrained nonlinear leastsquares. As a consequence, the presence of (possibly nonconvex) equality/inequality constraints does not affect the complexity of finding approximate first-order critical points in nonconvex optimization. This result improves on the best known (O(∊-2)) evaluation-complexity bound for solving general nonconvexly constrained optimization problems. [ABSTRACT FROM AUTHOR]

The complexity of finding $$\epsilon $$-approximate first-order critical points for the general smooth constrained optimization problem is shown to be no worse that $$O(\epsilon ^{-2})$$ in terms of function and constraints evaluations. This result is obtained by analyzing the worst-case behaviour of a first-order short-step homotopy algorithm consisting of a feasibility phase followed by an optimization phase, and requires minimal assumptions on the objective function. Since a bound of the same order is known to be valid for the unconstrained case, this leads to the conclusion that the presence of possibly nonlinear/nonconvex inequality/equality constraints is irrelevant for this bound to apply. [ABSTRACT FROM AUTHOR]

We propose a new termination criterion suitable for potentially singular, zero or nonzero residual, least-squares problems, with which cubic regularization variants take at most O(∈3/2) residual- and Jacobian-evaluations to drive either the Euclidean norm of the residual or its gradient below e; this is the best known bound for potentially rank-deficient nonlinear least-squares problems. We then apply the new optimality measure and cubic regularization steps to a family of least-squares merit functions in the context of a target-following algorithm for nonlinear equality-constrained problems; this approach yields the first evaluation complexity bound of order ∈3/2 for nonconvexly constrained problems when higher accuracy is required for primal feasibility than for dual first-order criticality. [ABSTRACT FROM AUTHOR]

This short note considers and resolves the apparent contradiction between known worst-case complexity results for first- and second-order methods for solving unconstrained smooth nonconvex optimization problems and a recent note by Jarre [On Nesterov's smooth Chebyshev–Rosenbrock function, Optim. Methods Softw. (2011)] implying a very large lower bound on the number of iterations required to reach the solution's neighbourhood for a specific problem with variable dimension. [ABSTRACT FROM AUTHOR]