Global Optimization

Decomposition-Based Reformulation of Nonseparable Quadratic Expressions in Convex MINLP

  • Joakim Blomqvist
  • etamm
  • Jan Kronqvist
  • Andreas Lundell
    • Categories (Mixed) Integer Nonlinear Programming, Convex Optimization, Global Optimization Tags , , , , , ,

    In this paper, we present a reformulation technique for convex mixed-integer nonlinear programming (MINLP) problems with nonseparable quadratic terms. For each convex non-diagonal matrix that defines quadratic expressions in the problem, we show that an eigenvalue or LDLT decomposition can be performed to transform the quadratic expressions into convex additively separable constraints. The reformulated problem … Read more

    Separable QCQPs and Their Exact SDP Relaxations

  • Masakazu Kojima
  • Sunyoung Kim
  • Naohiko Arima
    • Categories Global Optimization Theory, Quadratic Programming, Semi-definite Programming Tags , , , , ,

    This paper studies exact semidefinite programming relaxations (SDPRs) for separable quadratically constrained quadratic programs (QCQPs). We consider the construction of a larger separable QCQP from multiple QCQPs with exact SDPRs. We show that exactness is preserved when such QCQPs are combined through a separable horizontal connection, where the coupling is induced through the right-hand-side parameters … Read more

    Hardness of some optimization problems over correlation polyhedra

  • Alberto Caprara
  • Fabio Furini
  • Claudio Gentile
  • Leo Liberti
  • Andrea Lodi
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Theory, Polyhedra Tags , , ,

    We prove the NP-hardness, using Karp reductions, of some problems related to the correlation polytope and its corresponding cone, spanned by all of the n×n rank-one matrices over {0, 1}. The problems are: membership, rank of the decomposition, and a “relaxed rank” obtained from relaxing the zero-norm expression for the rank to an ℓ1 norm. … Read more

    Modeling Network Congestion under Demand Uncertainty Using Wardrop Principles

  • Yasmine Beck
  • Francesca Giancola
  • Ivana Ljubić
  • Sara Mattia
    • Categories (Mixed) Integer Nonlinear Programming, Bilevel Optimization, Global Optimization Tags , , ,

    Motivated by the need for reliable traffic management under fluctuating travel demand, we study the problem of determining the worst-case congestion in a multi-commodity traffic network subject to demand uncertainty. To this end, we stress-test a given network by identifying demand realizations and corresponding travelers’ route choices that maximize congestion. The users of the traffic … Read more

    A Successive Proximal DC Penalty Method with an Application to Mathematical Programs with Complementarity Constraints

  • Dominic C. Flocco
  • Steven A. Gabriel
  • Trine Krogh Boomsma
  • Martin Schmidt
  • Miguel A. Lejeune
    • Categories Bilevel Optimization, Constrained Nonlinear Optimization, Global Optimization Tags , , , ,

    We develop a successive, proximal difference-of-convex (DC) function penalty method for solving DC programs with DC constraints. The proposed approach relies on a DC penalty function that measures the violation of constraints and leads to a penalty reformulation sharing the same solution set as the original problem. The resulting penalty problem is a DC program … Read more

    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
  • Kristina Rolsing
    • 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 encompasses a broad class of optimization problems and is generally $\mathsf{NP}$-hard, even for low-rank objectives. While polynomial solvability has been established for several important special cases, a broader structural understanding for mixed-integer settings remains limited. In this paper, we study this question from a geometric perspective and identify a structural property of the … 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