MB8 - Optimisation non linéaire / Nonlinear Optimization

We propose a single-level convex reformulation of a class of bilevel optimization problems in which the lower level is a mixed-integer quadratic program (MIQP). Exploiting the completely positive representation of binary and continuous quadratic programs, we lift the lower-level MIQP into a linear program over the completely positive cone and derive its copositive dual. We employ strong duality and replace the lower-level optimality condition with a primal feasibility constraint, a dual feasibility constraint, and a single scalar strong duality equality, yielding a single-level formulation. The resulting single-level program is a convex cone program whenever the upper-level objective and constraints are convex. To address the computational intractability of exact copositive optimization, we further develop a semidefinite programming (SDP) relaxation based on standard inclusions as well as a submatrix restriction exploiting the exactness result for copositive matrices of order at most four. The proposed hierarchy of relaxations provides computable lower bounds on the bilevel optimal value. Our reformulation is validated numerically on synthetic MIQPs and we benchmark its performance against established bilevel solution methods from the literature, including Karush-Kuhn-Tucker single-level reformulations and branch-and-bound schemes.

The set of copositive matrices constitutes a proper cone. A copositive program (COP) is a linear optimization problem over this cone, and is therefore convex. Completely positive programs (CPPs) are the duals of COPs, and under standard constraint qualifications, strong duality holds. Many nonconvex and combinatorial optimization problems can be reformulated as COPs. For instance, mixed-binary quadratic programs, can be reformulated as CPPs, whose duals are COPs. These properties enabled COPs to find a wide range of applications across various fields, particularly in graph and network problems as well as discrete market pricing. However, the existing literature offers only a limited number of algorithmic approaches for solving COPs, and to date, no industrial-grade software is capable of directly solving COPs. In this work, we consider a recent iterative cutting-plane algorithm that relies on a mixed-integer linear program (MILP) formulation to test the copositivity of the incumbent solution and make a cut otherwise. We propose a divide-and-conquer extension leveraging the properties of copositive matrices to improve the resolution process. Specifically, we exploit the relationship between copositive matrices and their associated graphs to first decompose the MILP solved at each iteration into smaller subproblems, and second, to generate stronger cuts when combining the outputs of these MILPs. Our process further enables parallel execution and reduces the size of the copositive validation MILP to be solved at each iteration. We evaluate the performance in terms of optimality gap and computation time on both synthetic and engineering-motivated instances. To this end, we construct a new COP benchmark based on quadratic programming instances from the QPLIB library and compare our algorithm with the original iterative cutting-plane algorithm. Finally, we illustrate the practical benefits of
our solver through an application to pricing in unit commitment problems for electric power systems.

L-natural-convex functions encompass a large class of nonlinear functions over general integer domains and arise in a wide range of real-world applications. We explore the minimization of L-natural-convex functions, of multiple L-natural-convex functions with common variables, and of a mixed-integer extension of L-natural-convex functions—functions defined over a mixed-integer domain with properties that resemble L-natural- convexity. For each of these families of minimization problems, we propose valid linear inequalities and provide convex hull descriptions for the corresponding epigraphs. For all classes of proposed inequalities, we discuss their facet conditions, develop exact separation methods, and analyze the complexity of the separation problem. We discover hidden L-natural-convexity in well-known mixed-integer structures in the integer programming literature, namely the (general integer) mixing set and the continuous mixing set. We show that our findings subsume the existing polyhedral results for these sets and establish new results for the multi-capacity variant of the continuous mixing set.

We present an algorithm for calibrating parameters of a short-term electricity demand forecasting model in Québec. The calibration problem is formulated as nonlinear least-squares optimization subject to mixed constraints. Nonlinear constraints are handled via an augmented Lagrangian reformulation of the objective while linear feasibility is maintained by gradient projection. We exploit the least-squares structure through a structured Hessian approximation. Implemented in Julia, numerical experiments demonstrate the method's efficiency and accuracy.