Constrained 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

    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

    Almost-sure convergence of iterates and multipliers in stochastic sequential quadratic optimization

  • Frank E. Curtis
  • Xin Jiang
  • Qi Wang
    • Categories Constrained Nonlinear Optimization, Data Science Applications, Stochastic Programming Tags , , ,

    Stochastic sequential quadratic optimization (SQP) methods for solving continuous optimization problems with nonlinear equality constraints have attracted attention recently, such as for solving large-scale data-fitting problems subject to nonconvex constraints. However, for a recently proposed subclass of such methods that is built on the popular stochastic-gradient methodology from the unconstrained setting, convergence guarantees have been … Read more

    On the Computation of Restricted Normal Cones

  • Mario Jelitte
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization, Nonsmooth Optimization Tags , , ,

    Restricted normal cones are of interest, for instance, in the theory of local error bounds, where they have recently been used to characterize the exis- tence of a constrained Lipschitzian error bound. In this paper, we establish rela- tions between two concepts for restricted normals. The first of these concepts was introduced in the late … Read more

    Constraint qualifications and strong global convergence properties of an augmented Lagrangian method on Riemannian manifolds

  • Roberto Andreani
  • Kelvin Rodrigues Couto
  • Orizon Pereira Ferreira
  • Gabriel Haeser
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization Tags , , ,

    In the past years, augmented Lagrangian methods have been successfully applied to several classes of non-convex optimization problems, inspiring new developments in both theory and practice. In this paper we bring most of these recent developments from nonlinear programming to the context of optimization on Riemannian manifolds, including equality and inequality constraints. Many research have … Read more

    Unboundedness and Infeasibility in Linear Bilevel Optimization: How to Overcome Unbounded Relaxations

  • Bárbara Rodrigues
  • Miguel F. Anjos
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization Tags , ,

    Bilevel optimization problems are known to be challenging to solve in practice. In particular, the feasible set of a bilevel problem is, in general, non-convex, even for linear bilevel problems. In this work, we aim to develop a better understanding of the feasible set of linear bilevel problems. Specifically, we develop means by which to … Read more

    Adaptive Importance Sampling Based Surrogation Methods for Bayesian Hierarchical Models, via Logarithmic Integral Optimization

  • Ziyu He
  • Junyi Liu
  • Jong-Shi Pang
    • Categories Constrained Nonlinear Optimization, Nonsmooth Optimization, Stochastic Programming Tags , ,

    We explore Maximum a Posteriori inference of Bayesian Hierarchical Models (BHMs) with intractable normalizers, which are increasingly prevalent in contemporary applications and pose computational challenges when combined with nonconvexity and nondifferentiability. To address these, we propose the Adaptive Importance Sampling-based Surrogation method, which efficiently handles nonconvexity and nondifferentiability while improving the sampling approximation of the … Read more

    First-Order Methods for Nonsmooth Nonconvex Functional Constrained Optimization with or without Slater Points

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

    Constrained optimization problems where both the objective and constraints may be nonsmooth and nonconvex arise across many learning and data science settings. In this paper, we show a simple first-order method finds a feasible, ϵ-stationary point at a convergence rate of O(ϵ−4) without relying on compactness or Constraint Qualification (CQ). When CQ holds, this convergence is measured by … Read more

    A Stochastic-Gradient-based Interior-Point Algorithm for Solving Smooth Bound-Constrained Optimization Problems

  • Qi Wang
  • Frank E. Curtis
  • Daniel P. Robinson
  • Vyacheslav Kungurtsev
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization, Optimization in Data Science Tags , ,

    A stochastic-gradient-based interior-point algorithm for minimizing a continuously differentiable objective function (that may be nonconvex) subject to bound constraints is presented, analyzed, and demonstrated through experimental results. The algorithm is unique from other interior-point methods for solving smooth (nonconvex) optimization problems since the search directions are computed using stochastic gradient estimates. It is also unique … Read more

    A descent method for nonsmooth multiobjective optimization problems on Riemannian manifolds

  • Chunming Tang
  • Hao He
  • Jinbao Jian
  • Miantao Chao
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization, Nonsmooth Optimization Tags

    In this paper, a descent method for nonsmooth multiobjective optimization problems on complete Riemannian manifolds is proposed. The objective functions are only assumed to be locally Lipschitz continuous instead of convexity used in existing methods. A necessary condition for Pareto optimality in Euclidean space is generalized to the Riemannian setting. At every iteration, an acceptable … Read more