Constrained Nonlinear Optimization

Curvature-oriented variance reduction methods for nonconvex stochastic optimization

  • Qiankun Shi
  • Shiji Zuo
  • liuyx
  • Xiao Wang
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization Tags , , , ,

    When pursuing an approximate second-order stationary point in nonconvex constrained stochastic optimization, is it possible to design a stochastic second-order method that achieves the same sample complexity order as in the unconstrained setting? To address this question in this paper, we first introduce Carme, a curvature-oriented variance reduction method designed for unconstrained nonconvex stochastic optimization. … Read more

    Voronoi Conditional Gradient Method for Constrained Nonconvex Optimization

  • Abbas Khademi
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization Tags , , , ,

    The Conditional Gradient method offers a computationally efficient, projection-free framework for constrained problems; however, in nonconvex settings it may converge to stationary points of low quality. We propose the Voronoi Conditional Gradient (VCG) method, a geometric heuristic that systematically explores the feasible region by constructing adaptive Voronoi partitions from previously discovered stationary points. VCG incrementally … Read more

    An objective-function-free algorithm for general smooth constrained optimization

  • Stefania Bellavia
  • Serge Gratton
  • Benedetta Morini
  • Philippe L. Toint
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization Tags , ,

    A new algorithm for smooth constrained optimization is proposed that never computes the value of the problem’s objective function and that handles both equality and inequality constraints. The algorithm uses an adaptive switching strategy between a normal step aiming at reducing constraint’s infeasibility and a tangential step improving dual optimality, the latter being inspired by … Read more

    Learning to Choose Branching Rules for Nonconvex MINLPs

  • Timo Berthold
  • Fritz Geis
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization

    Outer-approximation-based branch-and-bound is a common algorithmic framework for solving MINLPs (mixed-integer nonlinear programs) to global optimality, with branching variable selection critically influencing overall performance. In modern global MINLP solvers, it is unclear whether branching on fractional integer variables should be prioritized over spatial branching on variables, potentially continuous, that show constraint violations, with different solvers … 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

    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

    The Convexity Zoo: A Taxonomy of Function Classes in Optimization

  • Abbas Khademi
    • Categories Constrained Nonlinear Optimization, Generalized Convexity/Monoticity, Nonlinear Optimization Tags , , , ,

    The tractability of optimization problems depends critically on structural properties of the objective function. Convexity guarantees global optimality of local solutions and enables polynomial-time algorithms under mild assumptions, but many problems arising in modern applications—particularly in machine learning—are inherently nonconvex. Remarkably, a large class of such problems remains amenable to efficient optimization due to additional … Read more

    A Proximal-Gradient Method for Solving Regularized Optimization Problems with General Constraints

  • Daniel P. Robinson
  • Frank E. Curtis
  • Xiaoyi Qu
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization, Nonsmooth Optimization Tags , , , , , ,

    We propose, analyze, and test a proximal-gradient method for solving regularized optimization problems with general constraints. The method employs a decomposition strategy to compute trial steps and uses a merit function to determine step acceptance or rejection. Under various assumptions, we establish a worst-case iteration complexity result, prove that limit points are first-order KKT points, … Read more

    Robust optimality for nonsmooth mathematical programs with equilibrium constraints under data uncertainty

  • Vivek Laha
    • Categories Applications - OR and Management Sciences, Constrained Nonlinear Optimization, Convex and Nonsmooth Optimization, Convex Optimization, Nonlinear Optimization, Nonsmooth Optimization, Robust Optimization Tags

    We develop a unified framework for robust nonsmooth optimization problems with equilibrium constraints (UNMPEC). As a foundation, we study a robust nonsmooth nonlinear program with uncertainty in both the objective function and the inequality constraints (UNP). Using Clarke subdifferentials, we establish Karush–Kuhn–Tucker (KKT)–type necessary optimality conditions under an extended no–nonzero–abnormal–multiplier constraint qualification (ENNAMCQ). When the … Read more

    Subsampled cubic regularization method with distinct sample sizes for function, gradient, and Hessian

  • Max L. N. Gonçalves
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization, Nonsmooth Optimization Tags , , ,

    We develop and study a subsampled cubic regularization method for finite-sum composite optimization problems, in which the function, gradient, and Hessian are estimated using possibly different sample sizes. By allowing each quantity to have its own sampling strategy, the proposed method offers greater flexibility to control the accuracy of the model components and to better … Read more