Convex Optimization

New Computational Guarantees for Solving Convex Optimization Problems with First Order Methods, via a Function Growth Condition Measure

  • Robert M. Freund
  • Haihao Lu
    • Categories Convex Optimization, Nonsmooth Optimization Tags , , ,

    Motivated by recent work of Renegar, we present new computational methods and associated computational guarantees for solving convex optimization problems using first-order methods. Our problem of interest is the general convex optimization problem f^* = \min_{x \in Q} f(x), where we presume knowledge of a strict lower bound f_slb < f^*. [Indeed, f_slb is naturally ... Read more

    Noisy Euclidean distance realization: robust facial reduction and the Pareto frontier

  • Dmitriy Drusvyatskiy
  • Nathan Krislock
  • Henry Wolkowicz
  • Y.-L. Voronin
    • Categories Convex Optimization, Semi-definite Programming Tags , , , , ,

    We present two algorithms for large-scale low-rank Euclidean distance matrix completion problems, based on semidefinite optimization. Our first method works by relating cliques in the graph of the known distances to faces of the positive semidefinite cone, yielding a combinatorial procedure that is provably robust and parallelizable. Our second algorithm is a first order method … Read more

    Uniqueness of Market Equilibrium on a Network: A Peak-Load Pricing Approach

  • Veronika Grimm
  • Lars Schewe
  • Martin Schmidt
  • Gregor Zöttl
    • Categories Convex Optimization, Finance and Economics, Network Optimization Tags , , ,

    In this paper we establish conditions under which uniqueness of market equilibrium is obtained in a setup where prior to trading of electricity, transmission capacities between different market regions are fixed. In our setup, firms facing fluctuating demand decide on the size and location of production facilities. They make production decisions constrained by the invested … Read more

    Inertial Proximal ADMM for Linearly Constrained Separable Convex Optimization

  • Raymond Chan
  • Caihua Chen
  • Shiqian Ma
  • Junfeng Yang
    • Categories Convex Optimization Tags , , , ,

    The \emph{alternating direction method of multipliers} (ADMM) is a popular and efficient first-order method that has recently found numerous applications, and the proximal ADMM is an important variant of it. The main contributions of this paper are the proposition and the analysis of a class of inertial proximal ADMMs, which unify the basic ideas of … Read more

    A general inertial proximal point algorithm for mixed variational inequality problem

  • Caihua Chen
  • Shiqian Ma
  • Junfeng Yang
    • Categories Convex Optimization Tags , , ,

    In this paper, we first propose a general inertial \emph{proximal point algorithm} (PPA) for the mixed \emph{variational inequality} (VI) problem. Based on our knowledge, without stronger assumptions, convergence rate result is not known in the literature for inertial type PPAs. Under certain conditions, we are able to establish the global convergence and nonasymptotic $O(1/k)$ convergence … Read more

    Low-rank spectral optimization

  • Michael P. Friedlander
  • Ives Macêdo
    • Categories Convex Optimization

    Various applications in signal processing and machine learning give rise to highly structured spectral optimization problems characterized by low-rank solutions. Two important examples that motivate this work are optimization problems from phase retrieval and from blind deconvolution, which are designed to yield rank-1 solutions. An algorithm is described based solving a certain constrained eigenvalue optimization … Read more

    On the Convergence of Multi-Block Alternating Direction Method of Multipliers and Block Coordinate Descent Method

  • Caihua Chen
  • Xin Liu
  • Yinyu Ye
  • Min Li
    • Categories Convex Optimization, Nonsmooth Optimization Tags , , , , ,

    The paper answers several open questions of the alternating direction method of multipliers (ADMM) and the block coordinate descent (BCD) method that are now wildly used to solve large scale convex optimization problems in many fields. For ADMM, it is still lack of theoretical understanding of the algorithm when the objective function is not separable … Read more

    A survey on operator splitting and decomposition of convex programs

  • Arnaud Lenoir
  • Philippe Mahey
    • Categories Convex Optimization Tags , ,

    Many structured convex minimization problems can be modeled by the search of a zero of the sum of two monotone operators. Operator splitting methods have been designed to decompose and regularize at the same time these kind of models. We review here these models and the classical splitting methods. We focus on the numerical sensitivity … Read more

    Bounded perturbation resilience of projected scaled gradient methods

  • Yair Censor
  • Ming Jiang
  • Wenma Jin
    • Categories Constrained Nonlinear Optimization, Convex Optimization Tags , , ,

    We investigate projected scaled gradient (PSG) methods for convex minimization problems. These methods perform a descent step along a diagonally scaled gradient direction followed by a feasibility regaining step via orthogonal projection onto the constraint set. This constitutes a generalized algorithmic structure that encompasses as special cases the gradient projection method, the projected Newton method, … Read more

    Vanishing Price of Anarchy in Large Coordinative Nonconvex Optimization

  • Mengdi Wang
    • Categories Convex Optimization, Global Optimization Theory Tags , , , ,

    We focus on a class of nonconvex cooperative optimization problems that involve multiple participants. We study the duality framework and provide geometric and analytic character- izations of the duality gap. The dual problem is related to a market setting in which each participant pursuits self interests at a given price of common goods. The duality … Read more