Convex Optimization

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

    Gauge optimization, duality, and applications

  • Michael P. Friedlander
  • Ives Macêdo
  • Ting Kei Pong
    • Categories Convex Optimization Tags , , ,

    Gauge functions significantly generalize the notion of a norm, and gauge optimization, as defined by Freund (1987), seeks the element of a convex set that is minimal with respect to a gauge function. This conceptually simple problem can be used to model a remarkable array of useful problems, including a special case of conic optimization, … Read more

    Completely Positive Reformulations for Polynomial Optimization

  • Javier F. Peña
  • Juan C. Vera
  • Luis F. Zuluaga
    • Categories Convex Optimization, Global Optimization Theory Tags , , ,

    Polynomial optimization encompasses a very rich class of problems in which both the objective and constraints can be written in terms of polynomials on the decision variables. There is a well stablished body of research on quadratic polynomial optimization problems based on reformulations of the original problem as a conic program over the cone of … Read more

    The Direct Extension of ADMM for Multi-block Convex Minimization Problems is Not Necessarily Convergent

  • Caihua Chen
  • Bingsheng He
  • Yinyu Ye
  • Xiao-Ming Yuan
    • Categories Convex Optimization, Statistics Tags , , , , , , ,

    The alternating direction method of multipliers (ADMM) is now widely used in many fields, and its convergence was proved when two blocks of variables are alternatively updated. It is strongly desirable and practically valuable to extend ADMM directly to the case of a multi-block convex minimization problem where its objective function is the sum of … Read more

    Convex Quadratic Relaxations for Mixed-Integer Nonlinear Programs in Power Systems

  • Carleton Coffrin
  • Hassan L. Hijazi
  • Pascal Van Hentenryck
    • Categories Basic Sciences Applications, Convex Optimization, Global Optimization Applications Tags , , , , ,

    This paper presents a set of new convex quadratic relaxations for nonlinear and mixed-integer nonlinear programs arising in power systems. The considered models are motivated by hybrid discrete/continuous applications where existing approximations do not provide optimality guarantees. The new relaxations offer computational efficiency along with minimal optimality gaps, providing an interesting alternative to state-of-the-art semi-definite … Read more

    Smooth minimization of nonsmooth functions with parallel coordinate descent methods

  • Olivier Fercoq
  • Peter Richtarik
    • Categories Convex Optimization, Parallel Algorithms Tags , , , ,

    We study the performance of a family of randomized parallel coordinate descent methods for minimizing the sum of a nonsmooth and separable convex functions. The problem class includes as a special case L1-regularized L1 regression and the minimization of the exponential loss (“AdaBoost problem”). We assume the input data defining the loss function is contained … Read more