We describe an algorithm based on a logarithmic barrier function, Newton's method, and linear conjugate gradients, that obtains an approximate minimizer of a smooth function over the nonnegative orthant. We develop a bound on the complexity of the approach, stated in terms of the required accuracy and the cost of a single gradient evaluation of the objective function and or a matrix-vector multiplication involving the Hessian of the objective. The approach can be implemented without explicit calculation or storage of the Hessian.
A number of algorithms have also been proposed for constrained optimization problems which require at most @math iterations to find a point which satisfies some first-order (and sometimes second-order) optimality condition(s). Although the optimality conditions vary between papers, @cite_16 @cite_2 @cite_1 all achieve this iteration complexity bound for some first order optimality condition by solving a constrained cubic regularization subproblem at each iteration. Another recent work finds a first-order point in @math iterations for linear equality and bound constraints through the use of an active set method @cite_13 . When optimizing on a single face of the polytope, this method also uses a cubic regularization model. However, these papers do not account for the cost of solving the subproblem at each iteration, noting either that this subproblem may be NP-hard, or suggesting that a simple first-order, gradient- based method can solve it reliably.
@cite_13 @cite_16 @cite_1 @cite_2
2801742348 2133068139 2898652568 2018738327
The main objective of this research is to introduce a practical method for smooth bound-constrained optimization that possesses worst-case evaluation complexity @math for finding an @math -approximate first-order stationary point when the Hessian of the objective function is Lipschitz continuous. As other well-established algorithms for optimization with box constraints, the algorithm proceeds visiting the different faces of the domain aiming to reduce the norm of an internal projected gradient and abandoning active constraints when no additional progress is expected in the current face. The introduced method emerges as a particular case of a method for minimization with linear constraints. Moreover, the linearly constrained minimization algorithm is an instance of a minimization algorithm with general constraints whose implementation may be unaffordable when the constraints are complicated. As a procedure for leaving faces, a different method is employed that may be regarded as a... The adaptive cubic overestimation algorithm described in Cartis, Gould and Toint (2007) is adapted to the problem of minimizing a nonlinear, possibly nonconvex, smooth objective function over a convex domain. Convergence to first-order critical points is shown under standard assumptions, but without any Lipschitz continuity requirement on the objective’s Hessian. A worst-case complexity analysis in terms of evaluations of the problem’s function and derivatives is also presented for the Lipschitz continuous case and for a variant of the resulting algorithm. This analysis extends the best known bound for general unconstrained problems to nonlinear problems with convex constraints. We provide sharp worst-case evaluation complexity bounds for nonconvex minimization problems with general inexpensive constraints, i.e. problems where the cost of evaluating enforcing of the (possibly nonconvex or even disconnected) constraints, if any, is negligible compared to that of evaluating the objective function. These bounds unify, extend or improve all known upper and lower complexity bounds for unconstrained and convexly-constrained problems. It is shown that, given an accuracy level @math , a degree of highest available Lipschitz continuous derivatives @math and a desired optimality order @math between one and @math , a conceptual regularization algorithm requires no more than @math evaluations of the objective function and its derivatives to compute a suitably approximate @math -th order minimizer. With an appropriate choice of the regularization, a similar result also holds if the @math -th derivative is merely H "older rather than Lipschitz continuous. We provide an example that shows that the above complexity bound is sharp for unconstrained and a wide class of constrained problems, we also give reasons for the optimality of regularization methods from a worst-case complexity point of view, within a large class of algorithms that use the same derivative information. 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 @math can be obtained by a second-order method using cubic regularization in at most @math 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 least-squares. 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 ( @math ) evaluation-complexity bound for solving general nonconvexly constrained optimization problems.