Interior-point algorithms with full Newton steps for nonsymmetric convex conic optimization

  • Dávid Papp
  • Anita Varga
    • Categories Cone Programming, Convex Optimization Tags , , ,

    We design and analyze primal-dual, feasible interior-point algorithms (IPAs) employing full Newton steps to solve convex optimization problems in standard conic form. Unlike most nonsymmetric cone programming methods, the algorithms presented in this paper require only a logarithmically homogeneous self-concordant barrier (LHSCB) of the primal cone, but compute feasible and \(\varepsilon\)-optimal solutions to both the … Read more

    Constructing QCQP Instances Equivalent to Their SDP Relaxations

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

    General quadratically constrained quadratic programs (QCQPs) are challenging to solve as they are known to be NP-hard. A popular approach to approximating QCQP solutions is to use semidefinite programming (SDP) relaxations. It is well-known that the optimal value η of the SDP relaxation problem bounds the optimal value ζ  of the QCQP from below, i.e., … Read more

    A Study of First-Order Methods with a Probabilistic Relative-Error Gradient Oracle

  • Nadav Hallak
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization Tags , , , , ,

    This paper investigates the problem of minimizing a smooth function over a compact set with a probabilistic relative-error gradient oracle. The oracle succeeds with some probability, in which case it provides a relative-error approximation of the true gradient, or fails and returns an arbitrary vector, while the optimizer cannot distinguish between successful and failed queries … Read more

    A Two-stage Stochastic Programming Approach for CRNA Scheduling with Handovers

  • Ankit Bansal
  • Osman Y. Ozaltin
    • Categories (Mixed) Integer Linear Programming, Scheduling, Stochastic Programming Tags , , ,

    We present a two-stage stochastic integer program for assigning Certified Registered Nurse Anesthetists (CRNAs) to Operating Rooms (ORs) under surgery duration uncertainty. The proposed model captures the trade-offs between CRNA staffing levels, CRNA handovers and under-staffing in the ORs. Since the stochastic program includes binary variables in both stages, we present valid inequalities to tighten … Read more

    Solving Decision-Dependent Robust Problems as Bilevel Optimization Problems

  • Henri Lefebvre
  • Martin Schmidt
  • Simon Stevens
  • Johannes Thürauf
    • Categories Bilevel Optimization, Robust Optimization Tags , , ,

    Both bilevel and robust optimization are established fields of mathematical optimization and operations research. However, only until recently, the similarities in their mathematical structure has neither been studied theoretically nor exploited computationally. Based on the recent results by Goerigk et al. (2025), this paper is the first one that reformulates a given strictly robust optimization … Read more

    MIP-DD: Delta Debugging for Mixed Integer Programming Solvers

  • Alexander Hoen
  • Dominik Kamp
  • Ambros Gleixner
    • Categories (Mixed) Integer Linear Programming, Integer Programming Tags ,

    The recent performance improvements in mixed-integer programming (MIP) have been accompanied by a significantly increased complexity of the codes of MIP solvers, which poses challenges in fixing implementation errors. In this paper, we introduce MIP-DD, a solver-independent tool, which to the best of our knowledge is the first open-source delta debugger for MIP. Delta debugging … Read more

    On liftings that improve convergence properties of Newton’s Method for Boundary Value Optimization Problems

  • Robert Lampel
  • Sebastian Sager
    • Categories Dynamic Programming, Nonlinear Optimization Tags , , ,

    The representation of a function in a higher-dimensional space is often referred to as lifting. Liftings can be used to reduce complexity. We are interested in the question of how liftings affect the local convergence of Newton’s method. We propose algorithms to construct liftings that potentially reduce the number of iterations via analysis of local … Read more

    Integrated Schedule Planning for Regional Airlines Using Column Generation

  • Alberto Santini
    • Categories (Mixed) Integer Linear Programming, Airline Optimization, Combinatorial Optimization Tags , , , ,

    Problem definition: More than one-third of US domestic flights are operated by regional airlines. This paper focuses on optimizing medium-term schedule planning decisions for a network of regional airlines through the joint optimization of frequency planning, timetable development, fleet assignment, and some limited aspects of route planning, while capturing passengers’ travel decisions through a general … Read more

    A Sound Local Regret Methodology for Online Nonconvex Composite Optimization

  • Nadav Hallak
    • Categories Applications - OR and Management Sciences, Constrained Nonlinear Optimization, Nonlinear Optimization Tags , , ,

    Online nonconvex optimization addresses dynamic and complex decision-making problems arising in real-world decision-making tasks where the optimizer’s objective evolves with the intricate and changing nature of the underlying system. This paper studies an online nonconvex composite optimization model with limited first-order access, encompassing a wide range of practical scenarios. We define local regret using a … Read more

    An Interior-Point Algorithm for Continuous Nonlinearly Constrained Optimization with Noisy Function and Derivative Evaluations

  • Frank E. Curtis
  • Shima Dezfulian
  • Andreas Wächter
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization, Optimization of Simulated Systems Tags , , , ,

    An algorithm based on the interior-point methodology for solving continuous nonlinearly constrained optimization problems is proposed, analyzed, and tested. The distinguishing feature of the algorithm is that it presumes that only noisy values of the objective and constraint functions and their first-order derivatives are available. The algorithm is based on a combination of a previously … Read more