Convex Optimization

Adaptive Sampling Quasi-Newton Methods for Zeroth-Order Stochastic Optimization

  • Raghu Bollapragada
  • Stefan M. Wild
    • Categories Convex Optimization, Nonlinear Optimization, Stochastic Programming Tags , ,

    We consider unconstrained stochastic optimization problems with no available gradient information. Such problems arise in settings from derivative-free simulation optimization to reinforcement learning. We propose an adaptive sampling quasi-Newton method where we estimate the gradients of a stochastic function using finite differences within a common random number framework. We develop modified versions of a norm … Read more

    A Local MM Subspace Method for Solving Constrained Variational Problems in Image Recovery

  • Émilie Chouzenoux
  • Ségolène Martin
  • Jean-Christophe Pesquet
    • Categories Constrained Nonlinear Optimization, Convex Optimization, Nonsmooth Optimization Tags , , , , , ,

    This article introduces a new Penalized Majorization-Minimization Subspace algorithm (P-MMS) for solving smooth, constrained optimization problems. In short, our approach consists of embedding a subspace algorithm in an inexact exterior penalty procedure. The subspace strategy, combined with a Majoration-Minimization step-size search, takes great advantage of the smoothness of the penalized cost function, while the penalty … Read more

    A simple Introduction to higher order liftings for binary problems

  • Florian Jarre
    • Categories 0-1 Programming, Convex Optimization Tags ,

    A short, simple, and self-contained proof is presented showing that $n$-th lifting for the max-cut-polytope is exact. The proof re-derives the known observations that the max-cut-polytope is the projection of a higher-dimensional regular simplex and that this simplex coincides with the $n$-th semidefinite lifting. An extension to reduce the dimension of higher order liftings and … Read more

    SABRINA: A Stochastic Subspace Majorization-Minimization Algorithm

  • Jean-Baptiste Fest
  • Émilie Chouzenoux
    • Categories Convex Optimization, Nonlinear Optimization Tags , , , , ,

    A wide class of problems involves the minimization of a coercive and differentiable function $F$ on $\mathbb{R}^N$ whose gradient cannot be evaluated in an exact manner. In such context, many existing convergence results from standard gradient-based optimization literature cannot be directly applied and robustness to errors in the gradient is not necessarily guaranteed. This work … Read more

    A Derivation of Nesterov’s Accelerated Gradient Algorithm from Optimal Control Theory

  • Isaac Ross
    • Categories Convex Optimization Tags , , ,

    Nesterov’s accelerated gradient algorithm is derived from first principles. The first principles are founded on the recently-developed optimal control theory for optimization. The necessary conditions for optimal control generate a controllable dynamical system for accelerated optimization. Stabilizing this system via a control Lyapunov function generates an ordinary differential equation. An Euler discretization of the differential … Read more

    A New Insight on Augmented Lagrangian Method with Applications in Machine Learning

  • Jianchao Bai
    • Categories Convex Optimization Tags , , , ,

    By exploiting double-penalty terms for the primal subproblem, we develop a novel relaxed augmented Lagrangian method for solving a family of convex optimization problems subject to equality or inequality constraints. This new method is then extended to solve a general multi-block separable convex optimization problem, and two related primal-dual hybrid gradient algorithms are also discussed. … Read more

    Accelerated Stochastic Peaceman-Rachford Method for Empirical Risk Minimization

  • Jianchao Bai
  • Fengmiao Bian
  • Xiaokai Chang
  • Lin Du
    • Categories Convex Optimization, Stochastic Programming Tags , , , ,

    This work is devoted to studying an Accelerated Stochastic Peaceman-Rachford Splitting Method (AS-PRSM) for solving a family of structural empirical risk minimization problems. The objective function to be optimized is the sum of a possibly nonsmooth convex function and a finite-sum of smooth convex component functions. The smooth subproblem in AS-PRSM is solved by a stochastic gradient method using variance reduction … Read more

    Exact Convergence Rates of Alternating Projections for Nontransversal Intersections

  • Hiroyuki Ochiai
  • Yoshiyuki Sekiguchi
  • Hayato Waki
    • Categories Convex Optimization Tags , , , , ,

    We study the exact convergence rate of the alternating projection method for the nontransversal intersection of a semialgebraic set and a linear subspace. If the linear subspace is a line, the exact rates are expressed by multiplicities of the defining polynomials of the semialgebraic set, or related power series. Our methods are also applied to … Read more

    An optimization problem for dynamic OD trip matrix estimation on transit networks with different types of data collection units

  • Esteve Codina
  • Lídia Montero
    • Categories Convex Optimization, Nonlinear Optimization, Transportation Tags , ,

    Dynamic O-D trip matrices for public transportation systems provide a valuable source of information of the usage of public transportation system that may be used either by planners for a better design of the transportation facilities or by the administrations in order to characterize the efficiency of the transport system both in peak hours and … Read more

    Rank computation in Euclidean Jordan algebras

  • Michael Orlitzky
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming Tags , , , ,

    Euclidean Jordan algebras are the abstract foundation for symmetriccone optimization. Every element in a Euclidean Jordan algebra has a complete spectral decomposition analogous to the spectral decomposition of a real symmetric matrix into rank-one projections. The spectral decomposition in a Euclidean Jordan algebra stems from the likewise-analogous characteristic polynomial of its elements, whose degree is … Read more