minimax problem

Efficiently Escaping Saddle Points in Bilevel Optimization

  • Minhui Huang
  • Kaiyi Ji
  • Lifeng Lai
  • Shiqian Ma
    • Categories Nonlinear Optimization Tags , , ,

    Bilevel optimization is one of the fundamental problems in machine learning and optimization. Recent theoretical developments in bilevel optimization focus on finding the first-order stationary points for nonconvex-strongly-convex cases. In this paper, we analyze algorithms that can escape saddle points in nonconvex-strongly-convex bilevel optimization. Specifically, we show that the perturbed approximate implicit differentiation (AID) with … Read more

    Robust Sensitivity Analysis of the Optimal Value of Linear Programming

  • Samuel Burer
  • Guanglin Xu
    • Categories Quadratic Programming, Robust Optimization, Semi-definite Programming Tags , , , , ,

    We propose a framework for sensitivity analysis of linear programs (LPs) in minimiza- tion form, allowing for simultaneous perturbations in the objective coefficients and right-hand sides, where the perturbations are modeled in a compact, convex uncertainty set. This framework unifies and extends multiple approaches for LP sensitivity analysis in the literature and has close ties … Read more