We consider a bi-level optimization problem of finding, among all optimal solutions of a convex program, one that minimizes a second convex objective function. Special cases of interest include bi-level shortest path and linear programs, which are solvable in "one pass" by modifying Dijkstra's method and simplex method. In general, we show that the bi-level problem is equivalent to a regularized convex program if and only if the bi-level problem has a Lagrange multiplier. This result is related to the existence of multipliers for exact penalization of convex programs. Time permitting, open questions and error bounds will be discussed.
Part of the work is joint with Michael Friedlander, UBC.