Convex Optimization

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

    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

    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

    Large-scale optimization with the primal-dual column generation method

  • Jacek Gondzio
  • Pedro Munari
  • Pablo Gonzalez-Brevis
    • Categories Convex Optimization, Linear Programming, Optimization Software and Modeling Systems Tags , , , , , ,

    The primal-dual column generation method (PDCGM) is a general-purpose column generation technique that relies on the primal-dual interior point method to solve the restricted master problems. The use of this interior point method variant allows to obtain suboptimal and well-centered dual solutions which naturally stabilizes the column generation. A reduction in the number of calls … Read more

    On the Coupled Continuous Knapsack Problems: Projection Onto the Volume Constrained Gibbs N-Simplex

  • Rouhollah Tavakoli
    • Categories Applications - OR and Management Sciences, Convex Optimization Tags , , ,

    Coupled continuous quadratic knapsack problems (CCK) are introduced in the present study. The solution of a CCK problem is equivalent to the projection of an arbitrary point onto the volume constrained Gibbs N-simplex, which has a wide range of applications in computational science and engineering. Three algorithms have been developed in the present study to … Read more

    Stability of Polynomial Differential Equations: Complexity and Converse Lyapunov Questions

  • Amir Ali Ahmadi
  • Pablo A. Parrilo
    • Categories Control Applications, Convex Optimization, Semi-definite Programming Tags , , , ,

    We consider polynomial differential equations and make a number of contributions to the questions of (i) complexity of deciding stability, (ii) existence of polynomial Lyapunov functions, and (iii) existence of sum of squares (sos) Lyapunov functions. (i) We show that deciding local or global asymptotic stability of cubic vector fields is strongly NP-hard. Simple variations … Read more

    Separable Approximations and Decomposition Methods for the Augmented Lagrangian

  • Burak Buke
  • Peter Richtarik
  • Rachael Tappenden
    • Categories Convex Optimization, Nonsmooth Optimization, Stochastic Programming Tags , , , , , , , , ,

    In this paper we study decomposition methods based on separable approximations for minimizing the augmented Lagrangian. In particular, we study and compare the Diagonal Quadratic Approximation Method (DQAM) of Mulvey and Ruszczy\'{n}ski and the Parallel Coordinate Descent Method (PCDM) of Richt\'{a}rik and Tak\'{a}\v{c}. We show that the two methods are equivalent for feasibility problems up … Read more

    Inexact Coordinate Descent: Complexity and Preconditioning

  • Jacek Gondzio
  • Peter Richtarik
  • Rachael Tappenden
    • Categories Convex Optimization, Nonlinear Systems and Least-Squares, Nonsmooth Optimization Tags , , , , ,

    In this paper we consider the problem of minimizing a convex function using a randomized block coordinate descent method. One of the key steps at each iteration of the algorithm is determining the update to a block of variables. Existing algorithms assume that in order to compute the update, a particular subproblem is solved exactly. … Read more

    String-Averaging Projected Subgradient Methods for Constrained Minimization

  • Yair Censor
  • Alexander J. Zaslavski
    • Categories Constrained Nonlinear Optimization, Convex Optimization Tags , , , , , , , , ,

    We consider constrained minimization problems and propose to replace the projection onto the entire feasible region, required in the Projected Subgradient Method (PSM), by projections onto the individual sets whose intersection forms the entire feasible region. Specifically, we propose to perform such projections onto the individual sets in an algorithmic regime of a feasibility-seeking iterative … Read more

    Composite Self-concordant Minimization

  • Volkan Cevher
  • Quoc Tran-Dinh
  • Anastasios Kyrillidis
    • Categories Convex and Nonsmooth Optimization, Convex Optimization, Statistics Tags , , , ,

    We propose a variable metric framework for minimizing the sum of a self-concordant function and a possibly non-smooth convex function endowed with a computable proximal operator. We theoretically establish the convergence of our framework without relying on the usual Lipschitz gradient assumption on the smooth part. An important highlight of our work is a new … Read more