Convex and Nonsmooth Optimization

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

    POLO: a POLicy-based Optimization library

  • Arda Aytekin
  • Martin Biel
  • Mikael Johansson
    • Categories Convex and Nonsmooth Optimization, Optimization Software Design Principles, Parallel Algorithms Tags , , , ,

    We present POLO — a C++ library for large-scale parallel optimization research that emphasizes ease-of-use, flexibility and efficiency in algorithm design. It uses multiple inheritance and template programming to decompose algorithms into essential policies and facilitate code reuse. With its clear separation between algorithm and execution policies, it provides researchers with a simple and powerful … Read more

    Low-M-Rank Tensor Completion and Robust Tensor PCA

  • Bo Jiang
  • Shiqian Ma
  • Shuzhong Zhang
    • Categories Applications - Science and Engineering, Convex and Nonsmooth Optimization, Nonlinear Optimization

    In this paper, we propose a new approach to solve low-rank tensor completion and robust tensor PCA. Our approach is based on some novel notion of (even-order) tensor ranks, to be called the M-rank, the symmetric M-rank, and the strongly symmetric M-rank. We discuss the connections between these new tensor ranks and the CP-rank and … Read more

    Analysis of Limited-Memory BFGS on a Class of Nonsmooth Convex Functions

  • Azam Asl
  • Michael L. Overton
    • Categories Nonsmooth Optimization

    The limited memory BFGS (L-BFGS) method is widely used for large-scale unconstrained optimization, but its behavior on nonsmooth problems has received little attention. L-BFGS can be used with or without “scaling”; the use of scaling is normally recommended. A simple special case, when just one BFGS update is stored and used at every iteration, is … Read more

    Hamiltonian Descent Methods

  • Arnaud Doucet
  • Chris J. Maddison
  • Brendan O'Donoghue
  • Daniel Paulin
  • Yee Whye Teh
    • Categories Convex Optimization

    We propose a family of optimization methods that achieve linear convergence using first-order gradient information and constant step sizes on a class of convex functions much larger than the smooth and strongly convex ones. This larger class includes functions whose second derivatives may be singular or unbounded at their minima. Our methods are discretizations of … Read more

    An inertial extrapolation method for convex simple bilevel optimization

  • Yekini Shehu
  • Alain Zemkoho
  • Phan Tu Vuong
    • Categories Constrained Nonlinear Optimization, Convex and Nonsmooth Optimization Tags , ,

    We consider a scalar objective minimization problem over the solution set of another optimization problem. This problem is known as simple bilevel optimization problem and has drawn a significant attention in the last few years. Our inner problem consists of minimizing the sum of smooth and nonsmooth functions while the outer one is the minimization … Read more

    Projective Splitting with Forward Steps only Requires Continuity

  • Jonathan Eckstein
  • Patrick R. Johnstone
    • Categories Complementarity and Variational Inequalities, Convex and Nonsmooth Optimization

    A recent innovation in projective splitting algorithms for monotone operator inclusions has been the development of a procedure using two forward steps instead of the customary proximal steps for operators that are Lipschitz continuous. This paper shows that the Lipschitz assumption is unnecessary when the forward steps are performed in finite-dimensional spaces: a backtracking linesearch … Read more

    An Inexact First-order Method for Constrained Nonlinear Optimization

  • Yuyang Rong
  • Jiashan Wang
  • Hao Wang
  • Hudie Zhou
    • Categories Constrained Nonlinear Optimization, Convex and Nonsmooth Optimization, Nonlinear Optimization Tags , , , , ,

    The primary focus of this paper is on designing inexact first-order methods for solving large-scale constrained nonlinear optimization problems. By controlling the inexactness of the subproblem solution, we can significantly reduce the computational cost needed for each iteration. A penalty parameter updating strategy during the subproblem solve enables the algorithm to automatically detect infeasibility. Global … Read more

    Universal Barrier is n-Self-Concordant

  • Yin Tat Lee
  • Man-Chung Yue
    • Categories Constrained Nonlinear Optimization, Convex Optimization Tags , , ,

    This paper shows that the self-concordance parameter of the universal barrier on any n-dimensional proper convex domain is upper bounded by n. This bound is tight and improves the previous O(n) bound by Nesterov and Nemirovski. The key to our main result is a pair of new, sharp moment inequalities for s-concave distributions, which could … Read more

    Deep Neural Network Structures Solving Variational Inequalities

  • Patrick L. Combettes
  • Jean-Christophe Pesquet
    • Categories Complementarity and Variational Inequalities, Convex Optimization Tags , , , ,

    We propose a novel theoretical framework to investigate deep neural networks using the formalism of proximal fixed point methods for solving variational inequalities. We first show that almost all activation functions used in neural networks are actually proximity operators. This leads to an algorithmic model alternating firmly nonexpansive and linear operators. We derive new results … Read more