EUROPT 2025
Abstract Submission

258. Solving a convex quadratic maximization problem appearing in some distributionally robust problem

Invited abstract in session MC-12: Robust optimisation and its applications, stream Applications: AI, uncertainty management and sustainability.

Monday, 14:00-16:00
Room: B100/8009

Authors (first author is the speaker)

1. Mathis Azema
CERMICS, ENPC
2. Wim van Ackooij
OSIRIS, EDF R&D
3. vincent leclere
CERMICS, Ecole des Ponts

Abstract

The distributionally robust optimization (DRO) framework has emerged as a powerful approach for dealing with uncertainty. In the context of Unit Commitment, where demand uncertainty affects the right-hand side of constraints, we investigate a DRO approach based on the Wasserstein distance with the $L^2$-norm. This method can be addressed using Benders' Decomposition (BD) as in the risk-neutral approach. However, the key difference lies in the oracle problem that generates valid cuts for the master problem: while the risk-neutral approach requires solving a linear oracle problem at each iteration and for each scenario, the DRO formulation leads to a quadratic convex maximization oracle problem. This problem has been proven to be NP-hard, and directly solving it with a commercial solver like Gurobi may be inefficient, significantly slowing down the BD.

Since BD only requires a valid cut to progress toward convergence, solving the oracle problem to optimality at each iteration is unnecessary. However, computing an optimal solution is essential for determining an upper bound, which is needed to certify whether the BD has reached optimality.

Thus, we first propose to use the Frank-Wolfe algorithm to generate non-optimal but valid cuts by solving only linear programs. Second, we develop slower but exact methods to solve the problem to optimality, ensuring an accurate computation of the optimality gap at the end of the BD.

Keywords

Status: accepted

Back to the list of papers