In this paper we extend the Lagrangian duality theory for convex optimization problems to incorporate approximate solutions. In particular, we generalize well-known relationships between minimizers of a convex optimization problem, maximizers of its Lagrangian dual, saddle points of the Lagrangian, Kuhn-Tucker vectors, and Kuhn-Ticker conditions to incorporate approximate versions.
C. Scovel, D. Hush, and I. Steinwart, Approximate Duality. Journal of Optimization Theory and Applications, Vol. 135, pp. 429-443, 2007. Los Alamos National Laboratory Technical Report LA-UR-05-6755. [ Abstract | Postscript (153 KB) | PDF (174 KB) ]
