Nonlinear Optimization

Accuracy and Relationships of Quadratic Models in Derivative-free Optimization

  • Yiwen Chen
  • Warren Hare
  • Lindon Roberts
    • Categories Nonlinear Optimization Tags , ,

    We study three quadratic models in model-based derivative-free optimization: the minimum norm (MN), minimum Frobenius norm (MFN), and quadratic generalized simplex derivative (QS) models. Despite their widespread use, their approximation accuracy and relationships have not been systematically explored. We establish fully linear error bounds for all three models, removing the uniformly bounded model Hessian assumption … Read more

    Supervised feature selection via multiobjective programming and its application in the medical field

  • Pham Thi Hoai
    • Categories Applications - OR and Management Sciences, Constrained Nonlinear Optimization, Convex and Nonsmooth Optimization, Convex Optimization, Other Topics Tags , , , ,

    In this study, we model the supervised feature selection problem using a novel approach: convex bi-objective optimization. Traditional methods have addressed this problem by maximizing relevance to class labels and minimizing redundancy among features. Recently, Wang et al. [30] formulated this problem as a single-objective convex optimization, yielding only a unique solution. Unlike that, we … Read more

    Out-of-the-Box Global Optimization for Packing Problems: New Models and Improved Solutions

  • Timo Berthold
  • Dominik Kamp
  • Gioni Mexi
  • Sebastian Pokutta
  • Imre Pólik
    • Categories Global Optimization, Nonlinear Optimization

    Recent LLM-driven discoveries have renewed interest in geometric packing problems. In this paper, we study several classes of such packing problems through the lens of modern global nonlinear optimization. Starting from comparatively direct nonlinear formulations, we consider packing circles in squares and fixed-perimeter rectangles, packing circles into minimum-area ellipses, packing regular polygons into regular polygons, … Read more

    Stochastic Three Points Method with an Inexact Oracle and Its Application to Steady-State Optimization

  • Geovani Nunes Grapiglia
    • Categories Nonlinear Optimization, Unconstrained Optimization Tags , , ,

    We consider unconstrained derivative-free optimization problems in which only inexact function evaluations are available. Specifically, we study the setting where the oracle returns function values with partially controllable inexactness, with the error bounded linearly by a user-specified accuracy parameter, but with an unknown proportionality constant. This framework captures optimization problems arising from approximate simulations or … Read more

    A unified framework for inexact adaptive stepsizes in the gradient methods, the conjugate gradient methods and the quasi-Newton methods for strictly convex quadratic optimization

  • Zexian Liu
    • Categories Convex Optimization, Quadratic Programming, Unconstrained Optimization Tags , , , ,

    The inexact adaptive stepsizes for the conjugate gradient method and  the quasi-Newton method are very rare. The exact stepsizes in the gradient method, the conjugate gradient method and the  quasi-Newton method for strictly convex quadratic optimization have a unified framework, while the unified framework for inexact adaptive stepsizes  in the gradient method, the conjugate gradient … Read more

    Accuracy Certificates for Convex Optimization at Accelerated Rates via Primal-Dual Averaging

  • Matthew X. Burns
  • Jiaming Liang
    • Categories Convex and Nonsmooth Optimization, Nonlinear Optimization Tags , , , ,

    Many works in convex optimization provide rates for achieving a small primal gap. However, this quantity is typically unavailable in practice. In this work, we show that solving a regularized surrogate with algorithms based on simple primal-dual averaging provides non-asymptotic convergence guarantees for a computable optimality certificate. We first analyze primal and dual methods based … Read more

    A semi-smooth Newton method for the nonlinear conic problem with generalized simplicial cones

  • Nicolas F. Armijo
  • Yunier Bello-Cruz
  • Gabriel Haeser
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization Tags , , , , ,

    In this work we develop and analyze a semi-smooth Newton method for the general non- linear conic programming problem. In particular, we study the problem with a generalized simplicial cone, i.e., the image of a symmetric cone under a linear mapping. We generalize Robinson’s normal equations to a conic setting, yielding what we call the … Read more

    A unified convergence theory for adaptive first-order methods in the nonconvex case, including AdaNorm, full and diagonal AdaGrad, Shampoo and Muon

  • Serge Gratton
  • Philippe L. Toint
    • Categories Data Science Algorithms, Stochastic Programming, Unconstrained Optimization Tags , , ,

    A unified framework for first-order optimization algorithms for nonconvex unconstrained optimization is proposed that uses adaptively preconditioned gradients and includes popular methods such as full and diagonal AdaGrad, AdaNorm, as well as adpative variants of Shampoo and Muon. This framework also allows combining heterogeneous geometries across different groups of variables while preserving a unified convergence … Read more

    Complexity of an inexact stochastic SQP algorithm for equality constrained optimization

  • Michael J. O'Neill
  • Aoji Tang
    • Categories Constrained Nonlinear Optimization, Stochastic Programming Tags , , ,

    In this paper, we consider nonlinear optimization problems with a stochastic objective function and deterministic equality constraints. We propose an inexact two-stepsize stochastic sequential quadratic programming (SQP) algorithm and analyze its worst-case complexity under mild assumptions. The method utilizes a step decomposition strategy and handles stochastic gradient estimates by assigning different stepsizes to different components … Read more

    A flexible block coordinate descent method for unconstrained optimization under Hölder continuity

  • V. S. Amaral
  • Roberto Andreani
  • Leonardo D. Secchin
  • Gilson Silva
    • Categories Nonlinear Optimization, Unconstrained Optimization

    In this work, we propose a flexible block coordinate method for unconstrained optimization problems under Hölder continuity assumptions. The method guarantees convergence to stationary points and has worst-case complexity results comparable to those obtained by single-block methods that assume Lipschitz or Hölder continuity. The approach is based on quadratic models of the objective function combined … Read more