Global Optimization

Efficient Warm-Start Strategies for Nash-based Linear Complementarity Problems via Bilinear Approximation

  • Dominic C. Flocco
  • Steven A. Gabriel
    • Categories Complementarity and Variational Inequalities, Constrained Nonlinear Optimization, Global Optimization Applications Tags , , ,

    We present an effective warm-starting scheme for solving large linear complementarity problems (LCPs) arising from Nash equilibrium problems. The approach generates high-quality starting points that, when passed to the PATH solver, yield substantial reductions in computational time and variance. Our warm-start routine reformulates each agent’s LP using strong duality, leading to a master problem with … Read more

    Modeling Binary Relations in Piecewise-Linear Approximations

  • Kristin Braun
  • Robert Burlacu
  • Tobias Kuen
  • kristinarolsing
    • Categories Combinatorial Optimization, Global Optimization Theory, Nonlinear Optimization Tags , , , , ,

    Over the last decades, using piecewise-linear mixed-integer relaxations of nonlinear expressions has become a strong alternative to spatial branching for solving mixed-integer nonlinear programs. Since these relaxations give rise to large numbers of binary variables that encode interval selections, strengthening them is crucial. We investigate how to exploit the resulting combinatorial structure by integrating cutting-plane … Read more

    On Approximate Computation of Critical Points

  • Amir Ali Ahmadi
  • Georgina Hall
    • Categories Global Optimization, Unconstrained Optimization Tags , ,

    We show that computing even very coarse approximations of critical points is intractable for simple classes of nonconvex functions. More concretely, we prove that if there exists a polynomial-time algorithm that takes as input a polynomial in \(n\) variables of constant degree (as low as three) and outputs a point whose gradient has Euclidean norm … Read more

    A Geometric Perspective on Polynomially Solvable Convex Maximization

  • Shaoning Han
  • Yongchun Li
    • Categories Global Optimization, Integer Programming, Optimization in Data Science Tags

    Convex maximization arises in many applications but is generally NP-hard, even for low-rank objectives. This paper introduces a set of broadly applicable conditions that certify when such problems are polynomially solvable. Our main condition is a new property of the feasible set, which we term co-monotonicity. We show that this property holds for two important … Read more

    AI for Enhancing Operations Research of Agriculture and Energy

  • Morteza Kimiaei
  • Anshu Kumar
  • Vyacheslav Kungurtsev
    • Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences, Global Optimization Tags , , , , , , ,

    This paper surveys optimization problems arising in agriculture, energy systems, and water-energy coordination from an operations research perspective. These problems are commonly formulated as integer nonlinear programs, mixed-integer nonlinear programs, or combinatorial set optimization models, characterized by nonlinear physical constraints, discrete decisions, and intertemporal coupling. Such structures pose significant computational challenges in large-scale and repeated-solution … Read more

    Global optimization of low-rank polynomials

  • Llorenç Balada Gaggioli
  • Didier Henrion
  • Milan Korda
    • Categories Global Optimization, Semi-definite Programming

    This work considers polynomial optimization problems where the objective admits a low-rank canonical polyadic tensor decomposition. We introduce LRPOP (low-rank polynomial optimization), a new hierarchy of semidefinite programming relaxations for which the size of the semidefinite blocks is determined by the canonical polyadic rank rather than the number of variables. As a result, LRPOP can … Read more

    Solving the Heilbronn Triangle Problem using Global Optimization Methods

  • Burak Kocuk
  • Amirali Modir
  • Amirhossein Monji
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Applications Tags , , , ,

    We study the Heilbronn triangle problem, which involves placing \(n\) points in the unit square such that the minimum area of any triangle formed by these points is maximized. A straightforward maximin formulation of this problem is highly non-linear and non-convex due to the existence of bilinear terms and absolute value equations. We propose two … Read more

    Inexact subgradient algorithm with a non-asymptotic convergence guarantee for copositive programming problems

  • Mitsuhiro Nishijima
  • Pierre-Louis Poirion
  • Akiko Takeda
    • Categories Convex and Nonsmooth Optimization, Global Optimization, Linear, Cone and Semidefinite Programming Tags , , , ,

    In this paper, we propose a subgradient algorithm with a non-asymptotic convergence guarantee to solve copositive programming problems. The subproblem to be solved at each iteration is a standard quadratic programming problem, which is NP-hard in general. However, the proposed algorithm allows this subproblem to be solved inexactly. For a prescribed accuracy $\epsilon > 0$ … Read more

    Extreme Strong Branching for QCQPs

  • Santanu S. Dey
  • Dahye Han
  • Yang Wang
    • Categories (Mixed) Integer Nonlinear Programming, Applications - OR and Management Sciences, Global Optimization

    For mixed-integer programs (MIPs), strong branching is a highly effective variable selection method to reduce the number of nodes in the branch-and-bound algorithm. Extending it to nonlinear problems is conceptually simple but practically limited. Branching on a binary variable fixes the variable to 0 or 1, whereas branching on a continuous variable requires an additional … Read more