Month: July 2024

A Stochastic Objective-Function-Free Adaptive Regularization Method with Optimal Complexity

  • Serge Gratton
  • Sadok Jerad
  • Philippe L. Toint
    • Categories Data Science Algorithms, Nonlinear Optimization Tags , , , ,

    A fully stochastic second-order adaptive-regularization method for unconstrained nonconvex optimization is presented which never computes the objective-function value, but yet achieves the optimal $\mathcal{O}(\epsilon^{-3/2})$ complexity bound for finding first-order critical points. The method is noise-tolerant and the inexactness conditions required for convergence depend on the history of past steps. Applications to cases where derivative evaluation … Read more

    S2MPJ and CUTEst optimization problems for Matlab, Python and Julia

  • Serge Gratton
  • Philippe L. Toint
    • Categories Nonlinear Optimization, Optimization Software Benchmark Tags , , , , ,

    A new decoder for the SIF test problems of the \cutest\ collection is described, which produces problem files allowing the computation of values and derivatives of the objective function and constraints of most \cutest\ problems directly within “native” Matlab, Python or Julia, without any additional installation or interfacing with MEX files or Fortran programs. When … Read more

    A progressive decoupling algorithm for minimizing the difference of convex and weakly convex functions over a linear subspace

  • Welington de Oliveira
  • João Carlos Souza
    • Categories Nonlinear Optimization, Nonsmooth Optimization Tags , ,

    Commonly, decomposition and splitting techniques for optimization problems strongly depend on convexity. Implementable splitting methods for nonconvex and nonsmooth optimization problems are scarce and often lack convergence guarantees. Among the few exceptions is the Progressive Decoupling Algorithm (PDA), which has local convergence should convexity be elicitable. In this work, we furnish PDA with a descent … Read more

    Toll Setting with Robust Wardrop Equilibrium Conditions Under Budgeted Uncertainty

  • Yasmine Beck
  • Martine Labbé
  • Martin Schmidt
    • Categories (Mixed) Integer Nonlinear Programming, Robust Optimization, Transportation Tags , , , ,

    We consider two variants of the toll-setting problem in which a traffic authority uses tolls either to maximize revenue or to alleviate bottlenecks in the traffic network. The users of the network are assumed to act according to Wardrop’s user equilibrium so that the overall toll-setting problems are modeled as mathematical problems with equilibrium constraints. … Read more

    Factorized binary polynomial optimization

  • Alberto Del Pia
    • Categories (Mixed) Integer Nonlinear Programming, 0-1 Programming, Integer Programming Tags , , , , ,

    In binary polynomial optimization, the goal is to find a binary point maximizing a given polynomial function. In this paper, we propose a novel way of formulating this general optimization problem, which we call factorized binary polynomial optimization. In this formulation, we assume that the variables are partitioned into a fixed number of sets, and … Read more

    A General Framework for Sequential Batch-Testing

  • Rayen Tan
  • Alex Xu
  • Viswanath Nagarajan
    • Categories Approximation Algorithms, Combinatorial Optimization

    We consider sequential testing problems that involve a system of \(n\) stochastic components, each of which is either working or faulty with independent probability. The overall state of the system is a function of the state of its individual components, and the goal is to determine the system state by testing its components at the … Read more

    A Facial Reduction Algorithm for Standard Spectrahedra

  • Haesol Im
    • Categories Convex Optimization, Semi-definite Programming

    Facial reduction is a pre-processing method aimed at reformulating a problem to ensure strict feasibility. The importance of constructing a robust model is widely recognized in the literature, and facial reduction has emerged an attractive approach for achieving robustness. In this note, we outline a facial reduction algorithm for a standard spectrahedra, the intersection of … Read more