Convex Optimization

New results on subgradient methods for strongly convex optimization problems with a unified analysis

  • Masaru Ito
    • Categories Constrained Nonlinear Optimization, Convex Optimization, Nonsmooth Optimization Tags , , , , , ,

    We develop subgradient- and gradient-based methods for minimizing strongly convex functions under a notion which generalizes the standard Euclidean strong convexity. We propose a unifying framework for subgradient methods which yields two kinds of methods, namely, the Proximal Gradient Method (PGM) and the Conditional Gradient Method (CGM), unifying several existing methods. The unifying framework provides … Read more

    Lower Bounds on Complexity of Lyapunov Functions for Switched Linear Systems

  • Amir Ali Ahmadi
  • Raphaël Jungers
    • Categories Convex Optimization, Semi-definite Programming, Systems governed by Differential Equations Optimization Tags , , ,

    We show that for any positive integer $d$, there are families of switched linear systems—in fixed dimension and defined by two matrices only—that are stable under arbitrary switching but do not admit (i) a polynomial Lyapunov function of degree $\leq d$, or (ii) a polytopic Lyapunov function with $\leq d$ facets, or (iii) a piecewise … Read more

    Convergence rates for forward-backward dynamical systems associated with strongly monotone inclusions

  • Radu Ioan Bot
  • Ernö Robert Csetnek
    • Categories Convex Optimization, Nonsmooth Optimization, Systems governed by Differential Equations Optimization Tags , , , ,

    We investigate the convergence rates of the trajectories generated by implicit first and second order dynamical systems associated to the determination of the zeros of the sum of a maximally monotone operator and a monotone and Lipschitz continuous one in a real Hilbert space. We show that these trajectories strongly converge with exponential rate to … Read more

    An optimal subgradient algorithm with subspace search for costly convex optimization problems

  • Masoud Ahookhosh
  • Arnold Neumaier
    • Categories Convex and Nonsmooth Optimization, Convex Optimization, Nonsmooth Optimization Tags , , , , , ,

    This paper presents an acceleration of the optimal subgradient algorithm OSGA \cite{NeuO} for solving convex optimization problems, where the objective function involves costly affine and cheap nonlinear terms. We combine OSGA with a multidimensional subspace search technique, which leads to low-dimensional problem that can be solved efficiently. Numerical results concerning some applications are reported. A … Read more

    Active-Set Methods for Convex Quadratic Programming

  • Anders Forsgren
  • Philip E. Gill
  • Elizabeth Wong
    • Categories Convex Optimization, Quadratic Programming Tags , , , , , ,

    Computational methods are proposed for solving a convex quadratic program (QP). Active-set methods are defined for a particular primal and dual formulation of a QP with general equality constraints and simple lower bounds on the variables. In the first part of the paper, two methods are proposed, one primal and one dual. These methods generate … Read more

    A forward-backward-forward differential equation and its asymptotic properties

  • Sebastian Banert
  • Radu Ioan Bot
    • Categories Convex Optimization, Dynamic Programming, Nonsmooth Optimization Tags , , , ,

    In this paper, we approach the problem of finding the zeros of the sum of a maximally monotone operator and a monotone and Lipschitz continuous one in a real Hilbert space via an implicit forward-backward-forward dynamical system with nonconstant relaxation parameters and stepsizes of the resolvents. Besides proving existence and uniqueness of strong global solutions … Read more

    A strong polynomial gradient algorithm in Linear Programming

  • Peter A. Bruijs
    • Categories Convex Optimization, Linear Programming

    It has been an open question whether the Linear Programming (LP) problem can be solved in strong polynomial time. The simplex algorithm does not offer a polynomial bound, and polynomial algorithms by Khachiyan and Karmarkar don’t have the strong characteristic. The curious fact that non-linear algorithms would be needed to deliver the strongest complexity result … Read more

    A Flexible ADMM Algorithm for Big Data Applications

  • Daniel P. Robinson
  • Rachael Tappenden
    • Categories Convex Optimization

    We present a flexible Alternating Direction Method of Multipliers (F-ADMM) algorithm for solving optimization problems involving a strongly convex objective function that is separable into $n \geq 2$ blocks, subject to (non-separable) linear equality constraints. The F-ADMM algorithm uses a \emph{Gauss-Seidel} scheme to update blocks of variables, and a regularization term is added to each … Read more

    A weighted Mirror Descent algorithm for nonsmooth convex optimization problem

  • Duy V.N. Luong
  • Panos Parpas
  • Berc Rustem
  • Daniel Rueckert
    • Categories Convex Optimization, Nonsmooth Optimization Tags , , ,

    Large scale nonsmooth convex optimization is a common problem for a range of computational areas including machine learning and computer vision. Problems in these areas contain special domain structures and characteristics. Special treatment of such problem domains, exploiting their structures, can significantly improve the the computational burden. We present a weighted Mirror Descent method to … Read more

    A Framework for Applying Subgradient Methods to Conic Optimization Problems (version 2)

  • James Renegar
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming Tags ,

    A framework is presented whereby a general convex conic optimization problem is transformed into an equivalent convex optimization problem whose only constraints are linear equations and whose objective function is Lipschitz continuous. Virtually any subgradient method can be applied to solve the equivalent problem. Two methods are analyzed. (In version 2, the development of algorithms … Read more