A new direct accelerated Newton method for minimizing convex functions with Lipschitz continuous Hessian that achieves the global convergence rate of $O(1/k^3)$ in terms of the functional residual, the first second-order method for this problem class attaining this rate.
Abstract
We develop a new direct accelerated Newton method for minimizing convex functions with Lipschitz continuous Hessian. The algorithm uses only primal variables and performs just one linear solve per iteration. With a simple predetermined choice of parameters, it achieves the global convergence rate of $O(1/k^3)$ in terms of the functional residual. To the best of our knowledge, this is the first second-order method for this problem class attaining this rate while relying solely on one linear system solve per iteration (without solving auxiliary nonlinear regularized subproblems, such as cubic regularization, performing nonlinear parameter searches, or using dual extragradient corrections). Our method can be implemented in a Hessian-free way, using an inexact linear system solver, while preserving the fast global rate. We further extend our construction to arbitrary geometry through Bregman divergence, and to composite optimization problems.
This paper proposes a general line-search Newton framework for unconstrained optimization that avoids repeated Hessian regularization by exploiting the Newton direction only when it is well-defined and suitable and provides the first Newton-type algorithm together with a comprehensive convergence analysis for this important class of nonconvex optimization problems.
In this work, we present a novel dynamic proximal point algorithm for unconstrained optimization. The method generates a sequence of proximal subproblems, where the quadratic regularization term is weighted by a diagonal matrix that is updated adaptively at each iteration. Each subproblem is solved using an inner Newton's method combined with a line search, which provides a global convergence mechanism for the nonlinear solver. At the outer level, the algorithm updates the reference point and adjusts the regularization parameter based on the performance of the inner Newton solver. We derive the reduced linear system used to compute the Newton step, define the corresponding merit function, and discuss practical approaches for constructing the diagonal scaling matrix from derivative information. The paper also provides implementation-oriented pseudocode and stopping criteria that are consistent with the proposed method.
E. Bertolazzi, A. Marchi, Davide Stocco· 0 citations
As an extension of convex quadratic optimization (CQO) problems, the weighted convex quadratic optimization (WCQO) plays an important role in the domain of mathematical programming and engineering. In this paper, we propose a short-step primal-dual interior-point algorithm for solving WCQO based on the strategy of weighted-path. The latter generates only full-Newton steps and requires no line search. Under appropriate conditions, the algorithm converges locally quadratically to an optimal solution of WCQO. Moreover, it has the best well-known polynomial complexity, namely, O(√n log(n/ϵ)).
Finally, some numerical results are reported to confirm the efficiency of our proposed algorithm.
Rima Hamadouche, L. Derbal, M. Achache· Reserche operationelle· 0 citations
This work proposes a nonlinear-residual linearized augmented Lagrangian method (NR-LALM) that replaces this subproblem by a regularized Gauss-Newton-type step while retaining the classical multiplier update based on the nonlinear constraint residual.
Benqi Liu, Kangkang Deng, Zichen Wang et al.· 0 citations
For solving nonconvex equality-constrained optimization problems, a recent Gradient-Eigenstep Algorithm by Goyens et al.~is an iteration-efficient approach, based on minimizing Fletcher's augmented Lagrangian function, for finding an approximate second-order stationary point from an arbitrary starting point. In this paper, the analysis of this algorithm is extended, offering a two-fold contribution. First, it is shown that a local-linear rate of convergence can be obtained by this method if it is initiated sufficiently close to a strong second-order stationary point and employs a sufficiently small step-size parameter and sufficiently large penalty parameter. In this case, the algorithm reduces to a gradient descent algorithm applied to minimize Fletcher's augmented Lagrangian. Second, as a particularly useful application of the first result, it is shown that the Gradient-Eigenstep algorithm can be used as an iteration-efficient subproblem solver in the context of a progressive sampling strategy for solving equality-constrained optimization problems when the objective and constraint functions are defined by large sample averages, ultimately offering an algorithm with an improved worst-case sample complexity when compared to an approach that solves a full-sample problem directly.
F. Curtis, Ling-Jun Guo, Daniel P. Robinson· 0 citations
Augmented Lagrangian methods are among the most effective approaches for solving constrained convex optimization problems. However, classical complexity analyses of first-order methods applied within the augmented Lagrangian framework usually rely on the assumption that the objective function has a Lipschitz continuous gradient. This assumption excludes an important class of generalized smooth functions whose gradients may grow unboundedly. In this paper, we study an inexact augmented Lagrangian method for solving linearly constrained convex optimization problems with $(L_0,L_1)$-smooth objective functions. We show that the augmented Lagrangian subproblems preserve the $(L_0,L_1)$-smooth structure, with parameters depending on the penalty coefficient. This property allows us to employ recent accelerated first-order schemes designed for generalized smooth optimization instead of classical smooth optimization methods. In particular, we combine the inexact augmented Lagrangian framework with a two-stage acceleration procedure based on clipped gradient descent and accelerated optimization.
A. Vyguzov, F. Stonyakin· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
