convex optimization

Performance Estimation for Smooth and Strongly Convex Sets

Categories Convex Optimization, Semi-definite Programming Tags , , , , ,

We extend recent computer-assisted design and analysis techniques for first-order optimization over structured functions—known as performance estimation—to apply to structured sets. We prove “interpolation theorems” for smooth and strongly convex sets with interior point conditions and bounded diameter, showing a wide range of extremal questions amount to structured mathematical programs. Prior function interpolation theorems are … Read more

Efficient parameter-free restarted accelerated gradient methods for convex and strongly convex optimization

Categories Convex and Nonsmooth Optimization, Convex Optimization, Nonlinear Optimization Tags , , , , ,

This paper develops a new parameter-free restarted method, namely RPF-SFISTA, and a new parameter-free aggressive regularization method, namely A-REG, for solving strongly convex and convex composite optimization problems, respectively. RPF-SFISTA has the major advantage that it requires no knowledge of both the strong convexity parameter of the entire composite objective and the Lipschitz constant of … Read more

Double-proximal augmented Lagrangian methods with improved convergence condition

Categories Complementarity and Variational Inequalities, Convex and Nonsmooth Optimization, Global Optimization Tags , , , ,

In this paper, we propose a novel double-proximal augmented Lagrangian method(DP-ALM) for solving a family of linearly constrained convex minimization problems whose objective function is not necessarily smooth. This DP-ALM not only enjoys a flexible dual stepsize, but also contains a proximal subproblem with relatively smaller proximal parameter. By a new prediction-correction reformulation for this … Read more

Scalable Projection-Free Optimization Methods via MultiRadial Duality Theory

Categories Convex and Nonsmooth Optimization, Convex Optimization, Nonsmooth Optimization Tags , , ,

Recent works have developed new projection-free first-order methods based on utilizing linesearches and normal vector computations to maintain feasibility. These oracles can be cheaper than orthogonal projection or linear optimization subroutines but have the drawback of requiring a known strictly feasible point to do these linesearches with respect to. In this work, we develop new … Read more

Accelerated Gradient Dynamics on Riemannian Manifolds: Faster Rate and Trajectory Convergence

Categories Convex Optimization, Optimization in Data Science Tags , , ,

In order to minimize a differentiable geodesically convex function, we study a second-order dynamical system on Riemannian manifolds with an asymptotically vanishing damping term of the form \(\alpha/t\). For positive values of \(\alpha\), convergence rates for the objective values and convergence of trajectory is derived. We emphasize the crucial role of the curvature of the … Read more

Near-optimal closed-loop method via Lyapunov damping for convex optimization

Categories Convex Optimization, Systems governed by Differential Equations Optimization, Unconstrained Optimization Tags , , ,

We introduce an autonomous system with closed-loop damping for first-order convex optimization. While, to this day, optimal rates of convergence are only achieved by non-autonomous methods via open-loop damping (e.g., Nesterov’s algorithm), we show that our system is the first one featuring a closed-loop damping while exhibiting a rate arbitrarily close to the optimal one. … Read more

Self-concordant smoothing in proximal quasi-Newton algorithms for large-scale convex composite optimization

Categories Convex Optimization, Nonsmooth Optimization Tags , , , , , , ,

We introduce a notion of self-concordant smoothing for minimizing the sum of two convex functions, one of which is smooth and the other nonsmooth. The key highlight is a natural property of the resulting problem’s structure that yields a variable metric selection method and a step length rule especially suited to proximal quasi-Newton algorithms. Also, … Read more

Information Complexity of Mixed-integer Convex Optimization

Categories (Mixed) Integer Nonlinear Programming, Convex and Nonsmooth Optimization, Convex Optimization Tags , , ,

We investigate the information complexity of mixed-integer convex optimization under different types of oracles. We establish new lower bounds for the standard first-order oracle, improving upon the previous best known lower bound. This leaves only a lower order linear term (in the dimension) as the gap between the lower and upper bounds. This is derived … Read more

Exact convergence rate of the last iterate in subgradient methods

Categories Convex Optimization, Nonsmooth Optimization Tags , , , , , , ,

We study the convergence of the last iterate in subgradient methods applied to the minimization of a nonsmooth convex function with bounded subgradients. We first introduce a proof technique that generalizes the standard analysis of subgradient methods. It is based on tracking the distance between the current iterate and a different reference point at each … Read more

Convergence analysis on a data-driven inexact proximal-indefinite stochastic ADMM

Categories Convex Optimization, Stochastic Approaches Tags , , , , ,

In this paper, we propose an Inexact Proximal-indefinite Stochastic ADMM (abbreviated as IPS-ADMM) to solve a class of separable convex optimization problems whose objective functions consist of two parts: one is an average of many smooth convex functions and the other is a convex but potentially nonsmooth function. The involved smooth subproblem is tackled by … Read more