Convex Optimization

On the Convergence of Alternating Minimization for Convex Programming with Applications to Iteratively Reweighted Least Squares and Decomposition Schemes

  • Amir Beck
    • Categories Convex Optimization

    This paper is concerned with the alternating minimization (AM) for solving convex minimization problems where the decision variables vector is split into two blocks. The objective function is a sum of a differentiable convex function and a separable (possible) nonsmooth extended real-valued convex function, and consequently constraints can be incorporated. We analyze the convergence rate … Read more

    On the Proximal Jacobian Decomposition of ALM for Multiple-block Separable Convex Minimization Problems and its Relationship to ADMM

  • Bingsheng He
  • Xiao-Ming Yuan
  • Hong-Kun Xu
    • Categories Convex Optimization Tags , , , , , ,

    The augmented Lagrangian method (ALM) is a benchmark for solving convex minimization problems with linear constraints. When the objective function of the model under consideration is representable as the sum of some functions without coupled variables, a Jacobian or Gauss-Seidel decomposition is often implemented to decompose the ALM subproblems so that the functions’ properties could … Read more

    Practical Inexact Proximal Quasi-Newton Method with Global Complexity Analysis

  • Katya Scheinberg
  • Xiaocheng Tang
    • Categories Convex Optimization, Nonsmooth Optimization Tags , , ,

    Recently several methods were proposed for sparse optimization which make careful use of second-order information [11, 30, 17, 3] to improve local convergence rates. These methods construct a composite quadratic approximation using Hessian information, optimize this approximation using a first-order method, such as coordinate descent and employ a line search to ensure sufficient descent. Here … Read more

    An inexact proximal path-following algorithm for constrained convex minimization

  • Volkan Cevher
  • Quoc Tran-Dinh
  • Anastasios Kyrillidis
    • Categories Convex and Nonsmooth Optimization, Convex Optimization, Linear, Cone and Semidefinite Programming Tags , , , ,

    Many scientific and engineering applications feature large-scale non-smooth convex minimization problems over convex sets. In this paper, we address an important instance of this broad class where we assume that the non-smooth objective is equipped with a tractable proximity operator and that the convex constraints afford a self-concordant barrier. We provide a new joint treatment … Read more

    A First-Order Algorithm for the A-Optimal Experimental Design Problem: A Mathematical Programming Approach

  • Selin Damla Ahipasaoglu
    • Categories Convex Optimization, Semi-definite Programming, Statistics Tags , ,

    We develop and analyse a first-order algorithm for the A-optimal experimental design problem. The problem is first presented as a special case of a parametric family of optimal design problems for which duality results and optimality conditions are given. Then, two first-order (Frank-Wolfe type) algorithms are presented, accompanied by a detailed time-complexity analysis of the … Read more

    Accelerating block-decomposition first-order methods for solving composite saddle-point and two-player Nash equilibrium problems

  • Yunlong He
  • Renato D.C. Monteiro
    • Categories Convex Optimization, Generalized Convexity/Monoticity, Nonsmooth Optimization Tags , , , , , ,

    This article considers the two-player composite Nash equilibrium (CNE) problem with a separable non-smooth part, which is known to include the composite saddle-point (CSP) problem as a special case. Due to its two-block structure, this problem can be solved by any algorithm belonging to the block-decomposition hybrid proximal-extragradient (BD-HPE) framework. The framework consists of a … Read more

    On the Convergence of Decentralized Gradient Descent

  • Qing Ling
  • Wotao Yin
  • Kun Yuan
    • Categories Convex Optimization Tags ,

    Consider the consensus problem of minimizing $f(x)=\sum_{i=1}^n f_i(x)$ where each $f_i$ is only known to one individual agent $i$ out of a connected network of $n$ agents. All the agents shall collaboratively solve this problem and obtain the solution subject to data exchanges restricted to between neighboring agents. Such algorithms avoid the need of a … Read more

    Iteration-Complexity of a Generalized Forward Backward Splitting Algorithm

  • Jalal Fadili
  • Jingwei Liang
  • Gabriel Peyré
    • Categories Convex Optimization Tags , , ,

    In this paper, we analyze the iteration-complexity of a generalized forward-backward (GFB) splitting algorithm, recently proposed in~\cite{gfb2011}, for minimizing the large class of composite objectives $f + \sum_{i=1}^n h_i$ on a Hilbert space, where $f$ has a Lipschitz-continuous gradient and the $h_i$’s are simple (i.e. whose proximity operator is easily computable ). We derive iteration-complexity … Read more

    A feasible active set method for strictly convex problems with simple bounds

  • Philipp Hungerländer
  • Franz Rendl
    • Categories Convex Optimization, Quadratic Programming Tags , , ,

    A primal-dual active set method for quadratic problems with bound constraints is presented which extends the infeasible active set approach of [K. Kunisch and F. Rendl. An infeasible active set method for convex problems with simple bounds. SIAM Journal on Optimization, 14(1):35-52, 2003]. Based on a guess of the active set, a primal-dual pair (x,α) … Read more

    Bundle methods in the XXIst century: A bird’s-eye view

  • Welington de Oliveira
  • Claudia Sagastizábal
    • Categories Convex Optimization Tags , ,

    Bundle methods are often the algorithms of choice for nonsmooth convex optimization, especially if accuracy in the solution and reliability are a concern. We review several algorithms based on the bundle methodology that have been developed recently and that, unlike their forerunner variants, have the ability to provide exact solutions even if most of the … Read more