convex optimization

Performance Estimation for Smooth and Strongly Convex Sets

  • Alan Luner
  • Benjamin Grimmer
    • 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 Slater points and bounded diameter, showing a wide range of extremal questions amount to structured mathematical programs. Prior function interpolation theorems are recovered … Read more

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

  • Arnesh Sujanani
  • Renato D.C. Monteiro
    • 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

  • Jianchao Bai
    • Categories Complementarity and Variational Inequalities, Convex and Nonsmooth Optimization, Global Optimization Tags , , , ,

    In this paper, we consider a family of linearly constrained convex minimization problems whose objective function is not necessarily smooth. A basic double-proximal augmented Lagrangian method (DP-ALM) is developed, which enjoys a flexible dual stepsize and a proximal subproblem with relatively smaller proximal parameter. By a novel prediction-correction reformulation for the proposed DP-ALM and by … Read more

    Scalable Projection-Free Optimization Methods via MultiRadial Duality Theory

  • Thabo Samakhoana
  • Benjamin Grimmer
    • 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

  • Tejas Natu
  • Camille Castera
  • Jalal Fadili
  • Peter Ochs
    • 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

  • Camille Castera
  • Peter Ochs
    • 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 for Large-Scale Convex Composite Optimization

  • Adeyemi D. Adeoye
  • Alberto Bemporad
    • 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 may be nonsmooth. The key highlight of our approach is in a natural property of the resulting problem’s structure which provides us with a variable-metric selection method and a step-length selection … Read more

    Information Complexity of Mixed-integer Convex Optimization

  • Amitabh Basu
  • Hongyi Jiang
  • Phillip Kerger
  • Marco Molinaro
    • 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

  • Moslem Zamani
  • François Glineur
    • 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 … Read more

    Convergence Analysis on A Data-deriven Inexact Proximal-indefinite Stochastic ADMM

  • Jianchao Bai
    • 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