Month: March 2024

Stochastic Aspects of Dynamical Low-Rank Approximation in the Context of Machine Learning

  • Arsen Hnatiuk
  • Lisa Kusch
  • Jonas Kusch
  • Nicolas R. Gauger
  • Andrea Walther
    • Categories Data Science Theory, Nonlinear Optimization, Optimization in Data Science Tags , , , ,

    The central challenges of today’s neural network architectures are the prohibitive memory footprint and the training costs associated with determining optimal weights and biases. A large portion of research in machine learning is therefore dedicated to constructing memory-efficient training methods. One promising approach is dynamical low-rank training (DLRT) which represents and trains parameters as a … Read more

    Fast convergence of the primal-dual dynamical system and algorithms for a nonsmooth bilinearly coupled saddle point problem

  • Kewei Ding
  • Jörg Fliege
  • Phan Vuong
    • Categories Game Theory, Nonsmooth Optimization Tags , , , ,

    This paper is devoted to study the convergence rates of a second-order dynamical system and its corresponding discretizations associated with a nonsmooth bilinearly coupled convex-concave saddle point problem. We derive the convergence rate of the primal-dual gap for the second-order dynamical system with asymptotically vanishing damping term. Based on the implicit discretization, we propose a … Read more

    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

    On the Out-of-Sample Performance of Stochastic Dynamic Programming and Model Predictive Control

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

    Sample average approximation-based stochastic dynamic programming (SDP) and model predictive control (MPC) are two different methods for approaching multistage stochastic optimization. In this paper we investigate the conditions under which SDP may be outperformed by MPC. We show that, depending on the presence of concavity or convexity, MPC can be interpreted as solving a mean-constrained … 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 the … 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