Convex Optimization

A Subgradient Projection Method with Outer Approximation for Solving Semidefinite Programming Problems

  • Nagisa Sugishita
  • Miguel F. Anjos
    • Categories Convex Optimization, Semi-definite Programming Tags , ,

    We explore the combination of subgradient projection with outer approximation to solve semidefinite programming problems. We compare several ways to construct outer approximations using the problem structure. The resulting approach enjoys the strengths of both subgradient projection and outer approximation methods. Preliminary computational results on the semidefinite programming relaxations of graph partitioning and max-cut show … Read more

    Projection onto hyperbolicity cones and beyond: a dual Frank-Wolfe approach

  • Takayuki Nagano
  • Bruno F. Lourenço
  • Akiko Takeda
    • Categories Cone Programming, Convex Optimization, Linear, Cone and Semidefinite Programming Tags , , , ,

    We discuss the problem of projecting a point onto an arbitrary hyperbolicity cone from both theoretical and numerical perspectives. While hyperbolicity cones are furnished with a generalization of the notion of eigenvalues, obtaining closed form expressions for the projection operator as in the case of semidefinite matrices is an elusive endeavour. To address that we … Read more

    Composite optimization models via proximal gradient method with increasing adaptive stepsizes

  • Pham Thi Hoai
    • Categories Constrained Nonlinear Optimization, Convex and Nonsmooth Optimization, Convex Optimization, Nonlinear Optimization, Nonsmooth Optimization Tags , , , ,

    We first consider the convex composite optimization models without globally Lipschitz condition imposed on the gradient of the differentiable term. The classical method which is proximal gradient will be studied with our new strategy of stepsize selection. The idea for constructing such a stepsize is motivated by the one in \cite{hoai} that used for gradient … Read more

    Accelerated Fully First-Order Methods for Bilevel and Minimax Optimization

  • Chris Junchi Li
    • Categories Convex Optimization, Nonlinear Optimization Tags ,

    We present in this paper novel accelerated fully first-order methods in \emph{Bilevel Optimization} (BiO). Firstly, for BiO under the assumption that the lower-level functions admit the typical strong convexity assumption, the \emph{(Perturbed) Restarted Accelerated Fully First-order methods for Bilevel Approximation} (\PRAFFBA) algorithm leveraging \emph{fully} first-order oracles is proposed, whereas the algorithm for finding approximate first-order … Read more

    Recognizing weighted means in geodesic spaces

  • Adrian Lewis
    • Categories Convex Optimization Tags , , , , ,

    Geodesic metric spaces support a variety of averaging constructions for given finite sets. Computing such averages has generated extensive interest in diverse disciplines. Here we consider the inverse problem of recognizing computationally whether or not a given point is such an average, exactly or approximately. In nonpositively curved spaces, several averaging notions, including the usual … Read more

    The Role of Level-Set Geometry on the Performance of PDHG for Conic Linear Optimization

  • Zikai Xiong
  • Robert M. Freund
    • Categories Convex Optimization, Linear Programming, Linear, Cone and Semidefinite Programming Tags , , ,

    We consider solving huge-scale instances of (convex) conic linear optimization problems, at the scale where matrix-factorization-free methods are attractive or necessary. The restarted primal-dual hybrid gradient method (rPDHG) — with heuristic enhancements and GPU implementation — has been very successful in solving huge-scale linear programming (LP) problems; however its application to more general conic convex … Read more

    Convex optimization on CAT(0) cubical complexes

  • Adrian Lewis
    • Categories Convex Optimization Tags , , , ,

    We consider geodesically convex optimization problems involving distances to a finite set of points A in a CAT(0) cubical complex. Examples include the minimum enclosing ball problem, the weighted mean and median problems, and the feasibility and projection problems for intersecting balls with centers in A. We propose a decomposition approach relying on standard Euclidean … Read more

    Faster Convergence of Stochastic Accelerated Gradient Descent under Interpolation

  • Aaron Mishkin
  • Mert Pilanci
  • Mark Schmidt
    • Categories Convex Optimization, Stochastic Programming Tags , , ,

    \(\) We prove new convergence rates for a generalized version of stochastic Nesterov acceleration under interpolation conditions. Unlike previous analyses, our approach accelerates any stochastic gradient method which makes sufficient progress in expectation. The proof, which proceeds using the estimating sequences framework, applies to both convex and strongly convex functions and is easily specialized to … Read more

    Slow convergence of the moment-SOS hierarchy for an elementary polynomial optimization problem

  • Didier Henrion
  • Adrien Le Franc
  • Victor Magron
    • Categories Convex Optimization, Nonlinear Optimization Tags , ,

    We describe a parametric univariate quadratic optimization problem for which the moment-SOS hierarchy has finite but increasingly slow convergence when the parameter tends to its limit value. We estimate the order of finite convergence as a function of the parameter. Article Download View Slow convergence of the moment-SOS hierarchy for an elementary polynomial optimization problem

    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