Nonlinear Optimization

Zeroth-order Riemannian Averaging Stochastic Approximation Algorithms

  • Jiaxiang Li
  • Krishnakumar Balasubramanian
  • Shiqian Ma
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization, Stochastic Programming

    We present Zeroth-order Riemannian Averaging Stochastic Approximation (\texttt{Zo-RASA}) algorithms for stochastic optimization on Riemannian manifolds. We show that \texttt{Zo-RASA} achieves optimal sample complexities for generating $\epsilon$-approximation first-order stationary solutions using only one-sample or constant-order batches in each iteration. Our approach employs Riemannian moving-average stochastic gradient estimators, and a novel Riemannian-Lyapunov analysis technique for convergence analysis. … Read more

    On Tractable Convex Relaxations of Standard Quadratic Optimization Problems under Sparsity Constraints

  • Immanuel M. Bomze
  • Bo Peng
  • Yuzhou Qiu
  • E. Alper Yildirim
    • Categories (Mixed) Integer Nonlinear Programming, Quadratic Programming, Semi-definite Programming Tags , , , ,

    Standard quadratic optimization problems (StQPs) provide a versatile modelling tool in various applications. In this paper, we consider StQPs with a hard sparsity constraint, referred to as sparse StQPs. We focus on various tractable convex relaxations of sparse StQPs arising from a mixed-binary quadratic formulation, namely, the linear optimization relaxation given by the reformulation-linearization technique, … Read more

    Goldstein Stationarity in Lipschitz Constrained Optimization

  • Benjamin Grimmer
  • Zhichao Jia
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization Tags , , , ,

    We prove the first convergence guarantees for a subgradient method minimizing a generic Lipschitz function over generic Lipschitz inequality constraints. No smoothness or convexity (or weak convexity) assumptions are made. Instead, we utilize a sequence of recent advances in Lipschitz unconstrained minimization, which showed convergence rates of $O(1/\delta\epsilon^3)$ towards reaching a “Goldstein” stationary point, that … Read more

    Analysis of a Class of Minimization Problems Lacking Lower Semicontinuity

  • Shaoning Han
  • Ying Cui
  • Jong-Shi Pang
    • Categories Nonlinear Optimization, Nonsmooth Optimization, Optimization in Data Science Tags , , ,

    The minimization of non-lower semicontinuous functions is a difficult topic that has been minimally studied. Among such functions is a Heaviside composite function that is the composition of a Heaviside function with a possibly nonsmooth multivariate function. Unifying a statistical estimation problem with hierarchical selection of variables and a sample average approximation of composite chance … Read more

    On achieving strong necessary second-order properties in nonlinear programming

  • Gabriel Haeser
  • Andreas Fischer
  • Thiago P. Silveira
    • Categories Nonlinear Optimization

    Second-order necessary or sufficient optimality conditions for nonlinear programming are usually defined by means of the positive (semi-)definiteness of a quadratic form, or a maximum of quadratic forms, over the critical cone. However, algorithms for finding such second-order stationary points are currently unknown. Typically, an algorithm with a second-order property approximates a primal-dual point such … Read more

    Full-low evaluation methods for bound and linearly constrained derivative-free optimization

  • Clément W. Royer
  • Oumaima Sohab
  • Luis Nunes Vicente
    • Categories Bound-constrained Optimization, Nonlinear Optimization Tags , , ,

    Derivative-free optimization (DFO) consists in finding the best value of an objective function without relying on derivatives. To tackle such problems, one may build approximate derivatives, using for instance finite-difference estimates. One may also design algorithmic strategies that perform space exploration and seek improvement over the current point. The first type of strategy often provides … Read more

    Eigenvalue programming beyond matrices

  • Masaru Ito
  • Bruno F. Lourenço
    • Categories Nonlinear Optimization Tags , , ,

    In this paper we analyze and solve eigenvalue programs, which consist of the task of minimizing a function subject to constraints on the “eigenvalues” of the decision variable. Here, by making use of the FTvN systems framework introduced by Gowda, we interpret “eigenvalues” in a broad fashion going beyond the usual eigenvalues of matrices. This … Read more

    Cone product reformulation for global optimization

  • Danique de Moor
  • Dick den Hertog
  • Dimitris Bertsimas
  • Jianzhe Zhen
  • Thodoris Koukouvinos
    • Categories Cone Programming, Global Optimization, Nonlinear Optimization

    In this paper, we study nonconvex optimization problems involving sum of linear times convex (SLC) functions as well as conic constraints belonging to one of the five basic cones, that is, linear cone, second order cone, power cone, exponential cone, and semidefinite cone. By using the Reformulation Perspectification Technique, we can obtain a convex relaxation … Read more

    Range of the displacement operator of PDHG with applications to quadratic and conic programming

  • Tao Jiang
  • Walaa M. Moursi
  • Stephen A. Vavasis
    • Categories Generalized Convexity/Monoticity, Quadratic Programming, Second-Order Cone Programming Tags , , , , ,

    Primal-dual hybrid gradient (PDHG) is a first-order method for saddle-point problems and convex programming introduced by Chambolle and Pock. Recently, Applegate et al. analyzed the behavior of PDHG when applied to an infeasible or unbounded instance of linear programming, and in particular, showed that PDHG is able to diagnose these conditions. Their analysis hinges on … Read more

    A Criterion Space Search Feasibility Pump Heuristic for Solving Maximum Multiplicative Programs

  • Ashim Khanal
  • Hadi Charkhgard
    • Categories Game Theory, Multi-Criteria Optimization, Nonlinear Optimization Tags , , , ,

    We study a class of nonlinear optimization problems with diverse practical applications, particularly in cooperative game theory. These problems are referred to as Maximum Multiplicative Programs (MMPs), and can be conceived as instances of “Optimization Over the Frontier” in multiobjective optimization. To solve MMPs, we introduce a feasibility pump-based heuristic that is specifically designed to … Read more