OPTIMIZATION SEMINAR

For convex constrained optimization problems, Lagrange multipliers are informative in the sense that they identifying constraints whose relaxation, at rates proportional to the multipliers, strictly improves the primal optimal value. However, existence of Lagrange multipliers requires assumptions such as no duality gap and existence of a primal optimal solution. What if these assumptions are relaxed? We prove that, in this general case, there still exists certain Fritz John multipliers that are informative. Moreover, there is a dual version of this result, involving the dual optimal value and dual optimal solutions.

This work is jointly with Dimitri Bertsekas and Asuman Ozdaglar at MIT.

Mathematics Department University of Washington