Nonlinear Optimization

Tilt Stability on Riemannian Manifolds with Application to Convergence Analysis of Generalized Riemannian Newton Method

  • Zijian Shi
  • Miantao Chao
    • Categories Nonlinear Optimization, Nonsmooth Optimization Tags , , ,

    We generalize tilt stability, a fundamental concept in perturbation analysis of optimization problems in Euclidean spaces, to the setting of Riemannian manifolds. We prove the equivalence of the following conditions: Riemannian tilt stability, Riemannian variational strong convexity, Riemannian uniform quadratic growth, local strong monotonicity of Riemannian subdifferential, strong metric regularity of Riemannian subdifferential, and positive … Read more

    An efficient penalty decomposition algorithm for minimization over sparse symmetric sets

  • Ahmad Mousavi
  • Morteza Kimiaei
  • Saman Babaie-Kafaki
  • Vyacheslav Kungurtsev
    • Categories Nonlinear Optimization, Nonsmooth Optimization Tags , , , ,

    This paper proposes an improved quasi-Newton penalty decomposition algorithm for the minimization of continuously differentiable functions, possibly nonconvex, over sparse symmetric sets. The method solves a sequence of penalty subproblems approximately via a two-block decomposition scheme: the first subproblem admits a closed-form solution without sparsity constraints, while the second subproblem is handled through an efficient … Read more

    Projected Stochastic Momentum Methods for Nonlinear Equality-Constrained Optimization for Machine Learning

  • Qi Wang
  • Yunlang Zhu
  • Frank E. Curtis
  • Christian Piermarini
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization, Stochastic Programming Tags , , , , ,

    Two algorithms are proposed, analyzed, and tested for solving continuous optimization problems with nonlinear equality constraints. Each is an extension of a stochastic momentum-based method from the unconstrained setting to the setting of a stochastic Newton-SQP-type algorithm for solving equality-constrained problems. One is an extension of the heavy-ball method and the other is an extension … Read more

    A single loop method for quadratic minmax optimization

  • Stefano Cipolla
  • Oliver Stein
  • Alain Zemkoho
    • Categories Linear Programming, Quadratic Programming, Robust Optimization Tags

    We consider a quadratic minmax problem with coupled inner constraints and propose a method to compute a class of stationary points. To motivate the need to compute such stationary points, we first show that they are meaningful, in the sense that they can be locally optimal for our problem under suitable linear independence and second-order … Read more

    First-order Methods for Unconstrained Vector Optimization Problems: A Unified Majorization-Minimization Perspective

  • Jian Chen
    • Categories Multi-Criteria Optimization, Nonlinear Optimization, Stochastic Programming Tags , , , ,

    In this paper, we develop a unified majorization-minimization scheme and convergence analysis with first-order surrogate functions for unconstrained vector optimization problems (VOPs). By selecting different surrogate functions, the unified method can be reduced to various existing first-order methods. The unified convergence analysis reveals that the slow convergence of the steepest descent method is primarily attributed … Read more

    Global Optimization for Combinatorial Geometry Problems Revisited in the Era of LLMs

  • Timo Berthold
  • Dominik Kamp
  • Gioni Mexi
  • Sebastian Pokutta
  • Imre Pólik
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization, Optimization Software and Modeling Systems Tags , , ,

    Recent progress in LLM-driven algorithm discovery, exemplified by DeepMind’s AlphaEvolve, has produced new best-known solutions for a range of hard geometric and combinatorial problems. This raises a natural question: to what extent can modern off-the-shelf global optimization solvers match such results when the problems are formulated directly as nonlinear optimization problems (NLPs)? We revisit a … Read more

    A Majorization-Minimization approach for multiclass classification in a big data scenario

  • Giorgia Franchini
  • Federica Porta
  • Émilie Chouzenoux
  • Jean-Christophe Pesquet
  • Filippo Camellini
    • Categories Convex Optimization, Data Science Algorithms, Unconstrained Optimization Tags , , , , ,

    This work presents a novel optimization approach for training linear classifiers in multiclass classification tasks, when focusing on a regularized and smooth Weston-Watkins support vector machine (SVM) model. We propose a Majorization-Minimization (MM) algorithm to solve the resulting, Lipschitz-differentiable, optimization problem. To enhance scalability of the algorithm when tackling large datasets, we introduce an incremental … Read more

    The Maximum Clique Problem under Adversarial Uncertainty: a min-max approach

  • Giovanni Spisso
  • Immanuel M. Bomze
  • Francesco Rinaldi
  • Chiara Faccio
    • Categories Nonlinear Optimization, Nonsmooth Optimization, Other Topics Tags , , ,

    We analyze the problem of identifying large cliques in graphs that are affected by adversarial uncertainty. More specifically, we consider a new formulation, namely the adversarial maximum clique problem, which extends the classical maximum-clique problem to graphs with edges strategically perturbed by an adversary. The proposed mathematical model is thus formulated as a two-player zero-sum … Read more

    A speed up strategy for gradient methods

  • Anna De Magistris
  • Serena Crisci
  • Valentina De Simone
  • Gerardo Toraldo
    • Categories Convex Optimization, Quadratic Programming Tags , , ,

    In this paper, we propose a new acceleration strategy for gradient-based methods applied to strictly convex Quadratic Programming (QP) problems. The strategy consists in performing, at selected iterations, minimization steps along alternative descent directions or even within low-dimensional affine subspaces. In particular, considering the contribution of the linear and quadratic part of the objective function … Read more

    An Inexact Modified Quasi-Newton Method for Nonsmooth Regularized Optimization

  • Nathan Allaire
  • Sébastien Le Digabel
  • Dominique Orban
    • Categories Data Science Algorithms, Nonlinear Optimization, Nonsmooth Optimization Tags , , , , , , , ,

    We introduce method iR2N, a modified proximal quasi-Newton method for minimizing the sum of a \(C^1\) function \(f\) and a lower semi-continuous prox-bounded \(h\) that permits inexact evaluations of \(f\), \(\nabla f\) and of the relevant proximal operators. Both \(f\) and \(h\) may be nonconvex. In applications where the proximal operator of \(h\) is not … Read more