Model Construction for Convex-Constrained Derivative-Free Optimization

  • Lindon Roberts
    • Categories Bound-constrained Optimization, Constrained Nonlinear Optimization, Nonlinear Optimization Tags , ,

    We develop a new approximation theory for linear and quadratic interpolation models, suitable for use in convex-constrained derivative-free optimization (DFO). Most existing model-based DFO methods for constrained problems assume the ability to construct sufficiently accurate approximations via interpolation, but the standard notions of accuracy (designed for unconstrained problems) may not be achievable by only sampling … Read more

    Certified Constraint Propagation and Dual Proof Analysis in a Numerically Exact MIP Solver

  • Sander Borst
  • Leon Eifler
  • Ambros Gleixner
    • Categories Integer Programming, Optimization Software and Modeling Systems Tags , ,

    This paper presents the integration of constraint propagation and dual proof analysis in an exact, roundoff-error-free MIP solver. The authors employ safe rounding methods to ensure that all results remain provably correct, while sacrificing as little computational performance as possible in comparison to a pure floating-point implementation. The study also addresses the adaptation of certification … Read more

    Similarity-based Decomposition Algorithm for Two-stage Stochastic Scheduling

  • Daniel Montes
  • José Luis Pitarch
  • Cesar de Prada
    • Categories Parallel Algorithms, Scheduling, Stochastic Programming Tags , ,

    This paper presents a novel decomposition method for two-stage stochastic mixed-integer optimization problems. The algorithm builds upon the idea of similarity between finite sample sets to measure how similar the first-stage decisions are among the uncertainty realization scenarios. Using such a Similarity Index, the non-anticipative constraints are removed from the problem formulation so that the … Read more

    Using Disjunctive Cuts in a Branch-and-Cut Method to Solve Convex Integer Nonlinear Bilevel Problems

  • Horländer Andreas
  • Ivana Ljubić
  • Martin Schmidt
    • Categories (Mixed) Integer Nonlinear Programming, Cutting Plane Approaches Tags , , ,

    We present a branch-and-cut method for solving convex integer nonlinear bilevel problems, i.e., bilevel models with nonlinear but convex objective functions and constraints in both the upper and the lower level. To this end, we generalize the idea of using disjunctive cuts to cut off integer-feasible but bilevel-infeasible points. These cuts can be obtained by … Read more

    Scalable Projection-Free Optimization Methods via MultiRadial Duality Theory

  • Thabo Samakhoana
  • Benjamin Grimmer
    • Categories Convex and Nonsmooth Optimization, Convex Optimization, Nonsmooth Optimization Tags , , ,

    Recent works have developed new projection-free first-order methods based on utilizing linesearches and normal vector computations to maintain feasibility. These oracles can be cheaper than orthogonal projection or linear optimization subroutines but have the drawback of requiring a known strictly feasible point to do these linesearches with respect to. In this work, we develop new … Read more

    Sample Average Approximation and Model Predictive Control for Multistage Stochastic Optimization

  • Dominic S. T. Keehan
  • Andrew B. Philpott
  • Edward Anderson
    • Categories Robust Optimization, Stochastic Programming Tags , , ,

    Sample average approximation-based stochastic dynamic programming and model predictive control are two different methods of approaching multistage stochastic optimization. Model predictive control—despite a lack of theoretical backing—is often used instead of stochastic dynamic programming due to computational necessity. For settings where the stage reward is a convex function of the random terms, the stage dynamics … Read more

    A Unified Approach for Maximizing Continuous $\gamma$-weakly DR-submodular Functions

  • Mohammad Pedramfar
  • Christopher Quinn
  • Vaneet Aggarwal
    • Categories Constrained Nonlinear Optimization, Stochastic Programming Tags , ,

    \(\) This paper presents a unified approach for maximizing continuous \(\gamma\)-weakly DR-submodular functions that encompasses a range of settings and oracle access types. Our approach includes a Frank-Wolfe type offline algorithm for both monotone and non-monotone functions, with different restrictions on the convex feasible region. We consider settings where the oracle provides access to either … Read more

    Neur2BiLO: Neural Bilevel Optimization

  • Justin Dumouchelle
  • Esther Julien
  • Jannis Kurtz
  • Elias B. Khalil
    • Categories (Mixed) Integer Linear Programming, (Mixed) Integer Nonlinear Programming Tags , ,

    Bilevel optimization deals with nested problems in which a leader takes the first decision to minimize their objective function while accounting for a follower best-response reaction. Constrained bilevel problems with integer variables are particularly notorious for their hardness.  While exact solvers have been proposed for mixed-integer~linear bilevel optimization, they tend to scale poorly with problem … Read more

    ε-Optimality in Reverse Optimization

  • Mounir El Maghri
    • Categories Convex and Nonsmooth Optimization, Global Optimization Tags , , , ,

    The purpose of this paper is to completely characterize the global approximate optimality (ε-optimality) in reverse convex optimization under the general nonconvex constraint “h(x) ≥ 0”. The main condition presented is obtained in terms of Fenchel’s ε-subdifferentials thanks to El Maghri’s ε-efficiency in difference vector optimization [J. Glob. Optim. 61 (2015) 803–812], after converting the … Read more

    Managing Distributional Ambiguity in Stochastic Optimization through a Statistical Upper Bound Framework

  • Shixin Liu
  • Jian Hu
    • Categories Robust Optimization, Stochastic Programming

    Stochastic optimization is often hampered by distributional ambiguity, where critical probability distributions are poorly characterized or unknown. Addressing this challenge, we introduce a new framework that targets the minimization of a statistical upper bound for the expected value of uncertain objectives, facilitating more statistically robust decision-making. Central to our approach is the Average Percentile Upper … Read more