Strict Complementarity and a Tale of Two Errors in Optimization

About this event

Harvard John A. Paulson School of

Engineering and Applied Sciences

ELECTRICAL & Computer ENGINEERING SEMINAR

Friday, November 13

11:00 AM - 12:00 PM

SEC LL2.221

"Strict Complementarity and a Tale of Two Errors in Optimization"

Gabor Pataki

Professor, Department of Statistics & Operations Research, University of North Carolina - Chapel Hill

Abstract : In an optimization problem, how close is a computed solution to a true optimal solution? Small constraint violations and a tiny optimality gap can suggest high accuracy. Yet even then, the computed point can be very far from every optimal solution. This is the distinction between the backward error, which is easy to compute, and the forward “true” error, i.e., the distance to the optimal solution set.

I will discuss this discrepancy in semidefinite programming, a generalization of linear programming. A central issue is strict complementarity, a condition that connects optimal solutions and Lagrange multipliers.

We describe all semidefinite programs that lack strict complementarity by a simple normal form obtained using elementary row operations and rotations. The normal form makes failure of strict complementarity visible and gives an algorithm to construct every such problem. Thus, it parametrizes semidefinite programs that lack strict complementarity similarly to how the Jordan normal form parametrizes matrices with given eigenvalues.

Our computational study shows that large discrepancies arise even in small problems: with matrices of order at most 20, the forward error can exceed the backward error by eight orders of magnitude. Thus, solvers computed solutions which appear numerically optimal, yet are far from any true optimal solution.

The talk is intended for a general audience and requires only a basic background in optimization and linear algebra.

Speaker Bio : Gábor Pataki is a Professor in the Department of Statistics & Operations Research at University of North Carolina at Chapel Hill (UNC-CH). He earned his Ph.D. in Algorithms, Combinatorics, and Optimization from Carnegie Mellon University, then held a visiting position at Columbia University.

His research centers on convex analysis and conic linear optimization, especially semidefinite programming (SDP), with an emphasis on geometry, duality, and computational complexity. Some of his recent, representative publications are:

Bad semidefinite programs: they all look the same, SIAM Journal on Optimization, 27(3), 146–172, 2017.

Characterizing bad semidefinite programs: normal forms and short proofs, SIAM Review, 61(4), 2019.

How do exponential size solutions arise in semidefinite programming? (with Aleksandr Touzov), SIAM Journal on Optimization, 34(1), 2024.