Convex Optimization

Convergence analysis for a primal-dual monotone + skew splitting algorithm with applications to total variation minimization

  • Radu Ioan Bot
  • Christopher Hendrich
    • Categories Convex Optimization Tags , , ,

    In this paper we investigate the convergence behavior of a primal-dual splitting method for solving monotone inclusions involving mixtures of composite, Lipschitzian and parallel sum type operators proposed by Combettes and Pesquet in [7]. Firstly, in the particular case of convex minimization problems, we derive convergence rates for the sequence of objective function values by … Read more

    AN INEXACT PERTURBED PATH-FOLLOWING METHOD FOR LAGRANGIAN DECOMPOSITION IN LARGE-SCALE SEPARABLE CONVEX OPTIMIZATION

  • Moritz Diehl
  • Ion Necoara
  • Carlo Savorgnan
  • Quoc Tran-Dinh
    • Categories Convex and Nonsmooth Optimization, Convex Optimization, Parallel Algorithms Tags , , , , ,

    This paper studies an inexact perturbed path-following algorithm in the framework of Lagrangian dual decomposition for solving large-scale separable convex programming problems. Unlike the exact versions considered in the literature, we propose to solve the primal subproblems inexactly up to a given accuracy. This leads to an inexactness of the gradient vector and the Hessian … Read more

    COMPUTATIONAL COMPLEXITY OF INEXACT GRADIENT AUGMENTED LAGRANGIAN METHODS: APPLICATION TO CONSTRAINED MPC

  • Ion Necoara
  • Quoc Tran-Dinh
  • Valentin Nedelcu
    • Categories Control Applications, Convex and Nonsmooth Optimization, Convex Optimization Tags , , , , ,

    We study the computational complexity certification of inexact gradient augmented Lagrangian methods for solving convex optimization problems with complicated constraints. We solve the augmented Lagrangian dual problem that arises from the relaxation of complicating constraints with gradient and fast gradient methods based on inexact first order information. Moreover, since the exact solution of the augmented … Read more

    Efficient parallel coordinate descent algorithm for convex optimization problems with separable constraints: application to distributed MPC

  • Dragos Clipici
  • Ion Necoara
    • Categories Control Applications, Convex Optimization, Parallel Algorithms Tags , , , ,

    In this paper we propose a parallel coordinate descent algorithm for solving smooth convex optimization problems with separable constraints that may arise e.g. in distributed model predictive control (MPC) for linear network systems. Our algorithm is based on block coordinate descent updates in parallel and has a very simple iteration. We prove (sub)linear rate of … Read more

    Hardness and Approximation Results for hBcBall Constrained Homogeneous Polynomial Optimization Problems

  • Ke Hou
  • Anthony Man-Cho So
    • Categories Constrained Nonlinear Optimization, Convex Optimization

    In this paper, we establish hardness and approximation results for various $L_p$-ball constrained homogeneous polynomial optimization problems, where $p \in [2,\infty]$. Specifically, we prove that for any given $d \ge 3$ and $p \in [2,\infty]$, both the problem of optimizing a degree-$d$ homogeneous polynomial over the $L_p$-ball and the problem of optimizing a degree-$d$ multilinear … Read more

    Minimal Representation of Insurance Prices

  • Alois Pichler
  • Alexander Shapiro
    • Categories Convex Optimization, Finance and Economics, Statistics Tags , , ,

    This paper addresses law invariant coherent risk measures and their Kusuoka representations. By elaborating the existence of a minimal representation we show that every Kusuoka representation can be reduced to its minimal representation. Uniqueness — in a sense specified in the paper — of the risk measure’s Kusuoka representation is derived from this initial result. … Read more

    Solving large scale polynomial convex problems on \ell_1/nuclear norm balls by randomized first-order algorithms

  • Aharon Ben-Tal
  • Arkadi Nemirovski
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming Tags , , ,

    One of the most attractive recent approaches to processing well-structured large-scale convex optimization problems is based on smooth convex-concave saddle point reformulation of the problem of interest and solving the resulting problem by a fast First Order saddle point method utilizing smoothness of the saddle point cost function. In this paper, we demonstrate that when … Read more

    The Spectral Bundle Method with Second-Order Information

  • Christoph Helmberg
  • Michael L. Overton
  • Franz Rendl
    • Categories Convex Optimization, Semi-definite Programming Tags ,

    The spectral bundle method was introduced by Helmberg and Rendl to solve a class of eigenvalue optimization problems that is equivalent to the class of semidefinite programs with the constant trace property. We investigate the feasibility and effectiveness of including full or partial second-order information in the spectral bundle method, building on work of Overton … Read more

    Rate analysis of inexact dual first order methods: Application to distributed MPC for network systems

  • Ion Necoara
  • Valentin Nedelcu
    • Categories Convex Optimization, Distributed Control, Parallel Algorithms Tags , , , , ,

    In this paper we propose two dual decomposition methods based on inexact dual gradient information for solving large-scale smooth convex optimization problems. The complicating constraints are moved into the cost using the Lagrange multipliers. The dual problem is solved by inexact first order methods based on approximate gradients and we prove sublinear rate of convergence … Read more

    Convergence rate and iteration complexity on the alternating direction method of multipliers with a substitution procedure for separable convex programming

  • Bingsheng He
  • Tao Min
  • Xiao-Ming Yuan
    • Categories Convex Optimization Tags , , , ,

    Recently, in [17] we have showed the first possibility of combining the Douglas-Rachford alternating direction method of multipliers (ADMM) with a Gaussian back substitution procedure for solving a convex minimization model with a general separable structure. This paper is a further study on theoretical aspects of this theme. We first derive a general algorithmic framework … Read more