convex optimization

Understanding the Acceleration Phenomenon via High-Resolution Differential Equations

  • Simon Du
  • Michael I. Jordan
  • Bin Shi
  • Weijie Su
    • Categories Convex Optimization, Global Optimization Theory, Unconstrained Optimization Tags ,

    Gradient-based optimization algorithms can be studied from the perspective of limiting or- dinary differential equations (ODEs). Motivated by the fact that existing ODEs do not distin- guish between two fundamentally different algorithms—Nesterov’s accelerated gradient method for strongly convex functions (NAG-SC) and Polyak’s heavy-ball method—we study an alter- native limiting process that yields high-resolution ODEs. We … Read more

    Exploiting Low-Rank Structure in Semidefinite Programming by Approximate Operator Splitting

  • Joaquim Dias Garcia
  • Mario Souto
  • Alvaro Viega
    • Categories Convex Optimization, Optimization Software and Modeling Systems, Semi-definite Programming Tags , , , , ,

    In contrast with many other convex optimization classes, state-of-the-art semidefinite programming solvers are yet unable to efficiently solve large scale instances. This work aims to reduce this scalability gap by proposing a novel proximal algorithm for solving general semidefinite programming problems. The proposed methodology, based on the primal-dual hybrid gradient method, allows the presence of … Read more

    A proximal ADMM with the Broyden family for Convex Optimization Problems

  • Yan Gu
  • Nobuo Yamashita
    • Categories Convex Optimization Tags , , ,

    Alternating direction methods of multipliers (ADMM) have been well studied and effectively used in various application fields. The classical ADMM must solve two subproblems exactly at each iteration. To overcome the difficulty of computing the exact solution of the subproblems, some proximal terms are added to the subproblems. Recently, Gu and Yamashita studied a special … Read more

    A Partial PPA block-wise ADMM for Multi-Block Constrained Separable Convex Optimization

  • Yuan Shen
    • Categories Applications - OR and Management Sciences, Unconstrained Optimization Tags , , ,

    The alternating direction method of multipliers(ADMM) has been proved to be effective for solving two-block separable convex optimization subject to linear constraints. However, it is not necessarily convergent when it is extended to multiple-block case directly. One remedy could be regrouping multiple-block variables into two groups firstly and then adopting the classic ADMM to the … Read more

    Accelerated Bregman Proximal Gradient Methods for Relatively Smooth Convex Optimization

  • Filip Hanzely
  • Peter Richtarik
  • Lin Xiao
    • Categories Convex Optimization, Nonlinear Optimization Tags , , , ,

    We consider the problem of minimizing the sum of two convex functions: one is differentiable and relatively smooth with respect to a reference convex function, and the other can be nondifferentiable but simple to optimize. The relatively smooth condition is much weaker than the standard assumption of uniform Lipschitz continuity of the gradients, thus significantly … Read more

    Convex computation of extremal invariant measures of nonlinear dynamical systems and Markov processes

  • Didier Henrion
  • Milan Korda
  • Igor Mezic
    • Categories Semi-definite Programming, Systems governed by Differential Equations Optimization Tags , , ,

    We propose a convex-optimization-based framework for computation of invariant measures of polynomial dynamical systems and Markov processes, in discrete and con- tinuous time. The set of all invariant measures is characterized as the feasible set of an infinite-dimensional linear program (LP). The objective functional of this LP is then used to single-out a specific measure … Read more

    Efficient Solution of Maximum-Entropy Sampling Problems

  • Kurt M. Anstreicher
    • Categories (Mixed) Integer Nonlinear Programming, Convex Optimization, Statistics Tags , ,

    We consider a new approach for the maximum-entropy sampling problem (MESP) that is based on bounds obtained by maximizing a function of the form ldet M(x) over linear constraints, where M(x)is linear in the n-vector x. These bounds can be computed very efficiently and are superior to all previously known bounds for MESP on most … Read more

    Finite convergence and weak sharpness for solutions of nonsmooth variational inequalities in Hilbert spaces

  • Qamrul Hasan Ansari
  • Luong Nguyen
  • Xiaolong Qin
    • Categories Convex and Nonsmooth Optimization, Nonlinear Optimization Tags , , , , ,

    This paper deals with the study of weak sharp solutions for nonsmooth variational inequalities and finite convergence property of the proximal point method. We present several characterizations for weak sharpness of the solutions set of nonsmooth variational inequalities without using the gap functions. We show that under weak sharpness of the solutions set, the sequence … Read more

    On the Complexity of Detecting Convexity over a Box

  • Amir Ali Ahmadi
  • Georgina Hall
    • Categories Convex Optimization, Global Optimization, Nonlinear Optimization Tags , , ,

    It has recently been shown that the problem of testing global convexity of polynomials of degree four is {strongly} NP-hard, answering an open question of N.Z. Shor. This result is minimal in the degree of the polynomial when global convexity is of concern. In a number of applications however, one is interested in testing convexity … Read more

    Efficient Optimization Algorithms for Robust Principal Component Analysis and Its Variants

  • Necdet Serhat Aybat
  • Shiqian Ma
    • Categories Convex and Nonsmooth Optimization, Nonlinear Optimization Tags , , , , , ,

    Robust PCA has drawn significant attention in the last decade due to its success in numerous application domains, ranging from bio-informatics, statistics, and machine learning to image and video processing in computer vision. Robust PCA and its variants such as sparse PCA and stable PCA can be formulated as optimization problems with exploitable special structures. … Read more