A Newton-CG based barrier method for finding a second-order stationary point of nonconvex conic optimization with complexity guarantees

In this paper we consider finding an approximate second-order stationary point (SOSP) of nonconvex conic optimization that minimizes a twice differentiable function over the intersection of an affine subspace and a convex cone. In particular, we propose a Newton-conjugate gradient (Newton-CG) based barrier method for finding an $(\epsilon,\sqrt{\epsilon})$-SOSP of this problem. Our method is not … Read more

Primal-dual extrapolation methods for monotone inclusions under local Lipschitz continuity with applications to variational inequality, conic constrained saddle point, and convex conic optimization problems

In this paper we consider a class of structured monotone inclusion (MI) problems that consist of finding a zero in the sum of two monotone operators, in which one is maximal monotone while another is locally Lipschitz continuous. In particular, we first propose a primal-dual extrapolation (PDE) method for solving a structured strongly MI problem … Read more

Accelerated first-order methods for convex optimization with locally Lipschitz continuous gradient

In this paper we develop accelerated first-order methods for convex optimization with locally Lipschitz continuous gradient (LLCG), which is beyond the well-studied class of convex optimization with Lipschitz continuous gradient. In particular, we first consider unconstrained convex optimization with LLCG and propose accelerated proximal gradient (APG) methods for solving it. The proposed APG methods are … Read more

Complexity-Optimal and Curvature-Free First-Order Methods for Finding Stationary Points of Composite Optimization Problems

This paper develops and analyzes an accelerated proximal descent method for finding stationary points of nonconvex composite optimization problems. The objective function is of the form f+h where h is a proper closed convex function, f is a differentiable function on the domain of h, and the gradient of f is Lipschitz continuous on the … Read more

FISTA and Extensions – Review and New Insights

The purpose of this technical report is to review the main properties of an accelerated composite gradient (ACG) method commonly referred to as the Fast Iterative Shrinkage-Thresholding Algorithm (FISTA). In addition, we state a version of FISTA for solving both convex and strongly convex composite minimization problems and derive its iteration complexities to generate iterates … Read more

Iteration-complexity of a proximal augmented Lagrangian method for solving nonconvex composite optimization problems with nonlinear convex constraints

This paper proposes and analyzes a proximal augmented Lagrangian (NL-IAPIAL) method for solving smooth nonconvex composite optimization problems with nonlinear K-convex constraints, i.e., the constraints are convex with respect to the order given by a closed convex cone K. Each NL-IAPIAL iteration consists of inexactly solving a proximal augmented Lagrangian subproblem by an accelerated composite … Read more

Iteration-complexity of an inner accelerated inexact proximal augmented Lagrangian method based on the classical Lagrangian function and a full Lagrange multiplier update

This paper establishes the iteration-complexity of an inner accelerated inexact proximal augmented Lagrangian (IAPIAL) method for solving linearly constrained smooth nonconvex composite optimization problems which is based on the classical Lagrangian function and, most importantly, performs a full Lagrangian multiplier update, i.e., no shrinking factor is incorporated on it. More specifically, each IAPIAL iteration consists … Read more

On Inexact Accelerated Proximal Gradient Methods with Relative Error Rules

One of the most popular and important first-order iterations that provides optimal complexity of the classical proximal gradient method (PGM) is the “Fast Iterative Shrinkage/Thresholding Algorithm” (FISTA). In this paper, two inexact versions of FISTA for minimizing the sum of two convex functions are studied. The proposed schemes inexactly solve their subproblems by using relative … Read more

Iteration-complexity of an inexact proximal accelerated augmented Lagrangian method for solving linearly constrained smooth nonconvex composite optimization problems

This paper proposes and establishes the iteration-complexity of an inexact proximal accelerated augmented Lagrangian (IPAAL) method for solving linearly constrained smooth nonconvex composite optimization problems. Each IPAAL iteration consists of inexactly solving a proximal augmented Lagrangian subproblem by an accelerated composite gradient (ACG) method followed by a suitable Lagrange multiplier update. It is shown that … Read more

A proximal bundle variant with optimal iteration-complexity for a large range of prox stepsizes

This paper presents a proximal bundle variant, namely, the relaxed proximal bundle (RPB) method, for solving convex nonsmooth composite optimization problems. Like other proximal bundle variants, RPB solves a sequence of prox bundle subproblems whose objective functions are regularized composite cutting-plane models. Moreover, RPB uses a novel condition to decide whether to perform a serious … Read more