On Solving Chance-Constrained Models with Gaussian Mixture Distribution

  • Shibshankar Dey
  • Sanjay Mehrotra
  • Anirudh Subramanyam
    • Categories Nonlinear Optimization, Stochastic Programming, Yield Management Tags , , , , , ,

    We study linear chance-constrained problems where the coefficients follow a Gaussian mixture distribution. We provide mixed-binary quadratic programs that give inner and outer approximations of the chance constraint based on piecewise linear approximations of the standard normal cumulative density function. We show that $O\left(\sqrt{\ln(1/\tau)/\tau} \right)$ pieces are sufficient to attain $\tau$-accuracy in the chance constraint. … Read more

    On the Convergence of Constrained Gradient Method

  • Danqing Zhou
  • Hongmei Chen
  • Shiqian Ma
  • Junfeng Yang
    • Categories Constrained Nonlinear Optimization, Convex Optimization Tags ,

    The constrained gradient method (CGM) has recently been proposed to solve convex optimization and monotone variational inequality (VI) problems with general functional constraints. While existing literature has established convergence results for CGM, the assumptions employed therein are quite restrictive; in some cases, certain assumptions are mutually inconsistent, leading to gaps in the underlying analysis. This … Read more

    Supermodularity, Curvature, and Convex Relaxations in a Class of Quadratic Binary Optimization Problems

  • Bismark Singh
    • Categories Combinatorial Optimization, Convex and Nonsmooth Optimization Tags , , ,

    We study the combinatorial structure of a quadratic set function $F(S)$ arising from a class of binary optimization models within the family of undesirable facility location problems. Despite strong empirical evidence of nested optimal solutions in previously studied real-world instances, we show that $F(S)$ is, in general, neither submodular nor supermodular. To quantify deviation from … Read more

    Stochastic Mixed-Integer Programming: A Survey

  • Ward Romeijnders
  • Yihang Zhang
  • Suvrajeet Sen
    • Categories Stochastic Programming Tags ,

    The goal of this survey is to provide a road-map for exploring the growing area of stochastic mixed-integer programming (SMIP) models and algorithms. We provide a comprehensive overview of existing decomposition algorithms for two-stage SMIPs, including Dantzig-Wolfe decomposition, dual decomposition, Lagrangian cuts, and decomposition approaches using parametric cutting planes and scaled cuts. Moreover, we explicitly … Read more

    Structure-Preserving Symmetry Presolving for Mixed-Binary Linear Problems

  • Annika Jaeger
  • Marc E. Pfetsch
    • Categories (Mixed) Integer Linear Programming, 0-1 Programming Tags , ,

    This paper investigates a presolving method for handling symmetries in mixed-binary programs, based on inequalities computed from so-called Schreier-Sims tables. We show that an iterative application of this method together with merging variables will produce an instance for which the symmetry group is trivial. We then prove that the problem structure can be preserved for … Read more

    An alternating optimization approach for robust optimal control in chromatography

  • Dominik H. Cebulla
  • Andrea Gilch
  • Jan Hendrik Rolfes
  • Christian Kirches
  • Frauke Liers
    • Categories Optimization of Systems modeled by PDEs, Robust Optimization Tags , ,

    Chromatographic separation plays a vital role in various areas, as this technique can deliver high-quality products both in lab- and industrial-scale processes. Economical and also ecological benefits can be expected when optimizing such processes with mathematical methods. However, even small perturbations in the operating conditions can result in significantly altered results, which may lead to … Read more

    The Decentralized Trust-Region Method with Second-Order Approximations

  • Hong Wang
    • Categories Parallel Algorithms Tags , ,

    This paper presents a novel decentralized trust-region framework that systematically incorporates second-order information to solve general nonlinear optimization problems in multi-agent networks. Our approach constructs local quadratic models that simultaneously capture objective curvature and enforce consensus through penalty terms, while supporting multiple Hessian approximation strategies including exact Hessians, limited-memory quasi-Newton methods, diagonal preconditioners, and matrix-free … Read more

    Min-Max Optimization Is Strictly Easier Than Variational Inequalities

  • Henry Shugart
  • Jason M. Altschuler
    • Categories Convex Optimization

    Classically, a mainstream approach for solving a convex-concave min-max problem is to instead solve the variational inequality problem arising from its first-order optimality conditions. Is it possible to solve min-max problems faster by bypassing this reduction? This paper initiates this investigation. We show that the answer is yes in the textbook setting of unconstrained quadratic … Read more