Month: June 2026

Lower Bounds for Feasibility and Stationarity in First-Order Nonconvex Constrained Optimization

  • Qiankun Shi
  • Xiao Wang
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization

    We study oracle-complexity lower bounds for first-order methods applied to smooth equality-constrained nonconvex optimization, separating two components of approximate KKT accuracy: feasibility and stationarity. Under iteration-wise Jacobian regularity, we prove a lower bound of order \(\Omega(\frac{L_c\Delta_c}{\sigma^2}+\log\log(\frac{\sigma^2}{L_c\epsilon}))\) to achieve \(\epsilon\)-feasibility. For stationarity, we construct a nonlinear equality-constrained hard instance whose multiplier-minimized stationarity residual reduces exactly to … Read more

    A Fletcher’s Augmented Lagrangian-Based Stochastic First-Order Method for Nonconvex Equality-Constrained Optimization

  • Yawen Cui
  • Qiankun Shi
  • Xiao Wang
  • Xiantao Xiao
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization

    In this paper, we study nonconvex equality-constrained optimization problems in which only stochastic first-order approximations of the objective and constraint functions are available. Owing to the stochasticity in both objective and constraints, most existing stochastic first-order methods incur relatively high oracle complexity, particularly in terms of stochastic constraint function evaluations. To address this issue, we … Read more

    Constrained Variable Projection for Structured Problems

  • Francesco Rinaldi
    • Categories Bilevel Optimization, Nonlinear Optimization, Optimization in Data Science Tags , ,

    Variable projection is a classical technique for separable nonlinear least-squares problems, in which variables that enter linearly are eliminated exactly, yielding a reduced nonlinear problem. By expressing this framework as a particular instance of a broader class of bilevel optimization problems, we develop a constrained variable-projection framework for data-science models, where the remaining variables are … Read more

    Skip or Insert? A Priori Optimization for the Vehicle Routing Problem with Time Windows and Stochastic Customers

  • Yulin Han
  • Hande Yaman
    • Categories Combinatorial Optimization, Production and Logistics, Stochastic Programming Tags , , , , , , ,

    We study an extension of the vehicle routing problem with time windows by incorporating stochastic customers, i.e., ad-hoc service requests. The uncertainty in stochastic customers is captured through scenarios. Two a priori optimization approaches, a classical and a new one lead to two different problems, both of which are modeled as scenario-based two-stage stochastic programs. … Read more

    Neural Assortment Optimization

  • Zhen Yang
    • Categories Combinatorial Optimization, Nonsmooth Optimization, Yield Management

    Assortment optimization selects a subset of items to maximize expected revenue under a discrete choice model and is widely used in revenue management and online platforms. Its combinatorial nature creates a practical tension among generality, scalability, and provable guarantees: model-specific algorithms can be strong when their structural assumptions hold, but are hard to adapt across … Read more

    Optimal Macroitem Sequences in the Precedence Constrained Knapsack Problem

  • Valerio Dose
  • Fabio Furini
  • Marco Locatelli
    • Categories Combinatorial Optimization, Graphs and Matroids, Linear Programming Tags , , ,

    The Precedence Constrained Knapsack Problem (PCKP) asks for a maximum-profit subset of items, subject to a knapsack capacity constraint and precedence constraints encoded by a directed acyclic graph. We study the structure of optimal solutions of the Linear Programming (LP) relaxation of the natural Integer Linear Programming formulation of the PCKP. We introduce the notion … Read more

    Local-to-Global Exactness of SDP Relaxations for Sparse QCQPs

  • Masakazu Kojima
  • Sunyoung Kim
  • Naohiko Arima
    • Categories Global Optimization Theory, Quadratic Programming, Semi-definite Programming Tags , , , , , , , ,

    We study exact semidefinite programming (SDP) relaxation for a given sparse quadratically constrained quadratic program (QCQP). The SDP relaxation is exact if, whenever it has an optimal solution, it admits a rank-at-most-one optimal solution that corresponds to an optimal solution of the QCQP. Using the maximal cliques of a chordal extension of the aggregate sparsity … Read more

    Quadratic Quasi-Newton Optimization – An Interpolated Hybrid Method

  • Andrew Charneski
    • Categories Nonlinear Optimization, Unconstrained Optimization Tags ,

    We present the Quadratic-Quasi-Newton (QQN) algorithm, a novel optimization method that combines gradient descent and quasi-Newton directions through quadratic interpolation. QQN constructs a parametric path d(t) = t(1 − t)(−∇f) + t 2 d L-BFGS and performs univariate optimization along this path, creating an adaptive interpolation that requires no additional hyperparameters beyond those of its … Read more

    Designing Autonomous Aerial Cable Car Networks for Sustainable Urban Logistics

  • Zeynep Çınar
  • Mehmet Ali Silgu
  • Barış Yıldız
    • Categories Network Optimization, Other Topics, Transportation Tags , , , ,

    This paper investigates the emerging autonomous aerial cableway technology to reduce the negative impacts of urban freight transportation. We focus on the infrastructure design problem to minimize the road-transportation externalities, taking pricing, investment costs, and the physical footprint into account. The network design problem is formulated as a mixed-integer linear programming (MILP) model that explicitly … Read more