Convex Optimization

An Efficient Augmented Lagrangian Method with Applications to Total Variation Minimization

  • Hong Jiang
  • Wotao Yin
  • Yin Zhang
  • Chengbo Li
    • Categories Convex and Nonsmooth Optimization, Convex Optimization, Nonsmooth Optimization Tags , , , ,

    Based on the classic augmented Lagrangian multiplier method, we propose, analyze and test an algorithm for solving a class of equality-constrained non-smooth optimization problems (chiefly but not necessarily convex programs) with a particular structure. The algorithm effectively combines an alternating direction technique with a nonmonotone line search to minimize the augmented Lagrangian function at each … Read more

    Convex computation of the region of attraction of polynomial control systems

  • Didier Henrion
  • Milan Korda
    • Categories Control Applications, Convex Optimization, Semi-definite Programming Tags , , , , , ,

    We address the long-standing problem of computing the region of attraction (ROA) of a target set (typically a neighborhood of an equilibrium point) of a controlled nonlinear system with polynomial dynamics and semialgebraic state and input constraints. We show that the ROA can be computed by solving a convex linear programming (LP) problem over the … Read more

    Bounds on Eigenvalues of Matrices Arising from Interior-Point Methods

  • Chen Greif
  • Erin Moulding
  • Dominique Orban
    • Categories Convex Optimization, Quadratic Programming Tags , , , , , , ,

    Interior-point methods feature prominently among numerical methods for inequality-constrained optimization problems, and involve the need to solve a sequence of linear systems that typically become increasingly ill-conditioned with the iterations. To solve these systems, whose original form has a nonsymmetric 3×3 block structure, it is common practice to perform block Gaussian elimination and either solve … Read more

    An adaptive accelerated first-order method for convex optimization

  • Renato D.C. Monteiro
  • Camilo Ortiz
  • Benar Fux Svaiter
    • Categories Convex Optimization, Nonsmooth Optimization Tags , , , ,

    This paper presents a new accelerated variant of Nesterov’s method for solving composite convex optimization problems in which certain acceleration parameters are adaptively (and aggressively) chosen so as to substantially improve its practical performance compared to existing accelerated variants while at the same time preserve the optimal iteration-complexity shared by these methods. Computational results are … Read more

    A QCQP Approach to Triangulation

  • Sameer Agarwal
  • Chris Aholt
  • Rekha R. Thomas
    • Categories Convex Optimization, Quadratic Programming Tags , , ,

    Triangulation of a three-dimensional point from $n\ge 2$ two-dimensional images can be formulated as a quadratically constrained quadratic program. We propose an algorithm to extract candidate solutions to this problem from its semidefinite programming relaxations. We then describe a sufficient condition and a polynomial time test for certifying when such a solution is optimal. This … Read more

    Stochastic optimization and sparse statistical recovery: An optimal algorithm for high dimensions

  • Alekh Agarwal
  • Martin J Wainwright
  • Sahand Negahban
    • Categories Convex Optimization, Stochastic Programming Tags , ,

    We develop and analyze stochastic optimization algorithms for problems in which the expected loss is strongly convex, and the optimum is (approximately) sparse. Previous approaches are able to exploit only one of these two structures, yielding an $\order(\pdim/T)$ convergence rate for strongly convex objectives in $\pdim$ dimensions, and an $\order(\sqrt{(\spindex \log \pdim)/T})$ convergence rate when … Read more

    An acceleration procedure for optimal first-order methods

  • Michel Baes
  • Michael Bürgisser
    • Categories Convex Optimization, Semi-definite Programming Tags , ,

    We introduce in this paper an optimal first-order method that allows an easy and cheap evaluation of the local Lipschitz constant of the objective’s gradient. This constant must ideally be chosen at every iteration as small as possible, while serving in an indispensable upper bound for the value of the objective function. In the previously … Read more

    A variable smoothing algorithm for solving convex optimization problems

  • Radu Ioan Bot
  • Christopher Hendrich
    • Categories Applications - Science and Engineering, Convex Optimization, Data-Mining Tags , , ,

    In this article we propose a method for solving unconstrained optimization problems with convex and Lipschitz continuous objective functions. By making use of the Moreau envelopes of the functions occurring in the objective, we smooth the latter to a convex and differentiable function with Lipschitz continuous gradient by using both variable and constant smoothing parameters. … Read more

    A primal-dual splitting algorithm for finding zeros of sums of maximally monotone operators

  • Radu Ioan Bot
  • Ernö Robert Csetnek
  • Andre Heinrich
    • Categories Convex Optimization Tags , , , , ,

    We consider the primal problem of finding the zeros of the sum of a maximally monotone operator with the composition of another maximally monotone operator with a linear continuous operator and a corresponding dual problem formulated by means of the inverse operators. A primal-dual splitting algorithm which simultaneously solves the two problems in finite-dimensional spaces … Read more