Convex and Nonsmooth 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

    Condition Number Analysis of Logistic Regression, and its Implications for Standard First-Order Solution Methods

  • Robert M. Freund
  • Rahul Mazumder
  • Paul Grigas
    • Categories Convex Optimization, Data-Mining, Statistics Tags , , ,

    Logistic regression is one of the most popular methods in binary classification, wherein estimation of model parameters is carried out by solving the maximum likelihood (ML) optimization problem, and the ML estimator is defined to be the optimal solution of this problem. It is well known that the ML estimator exists when the data is … 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

    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