From: hwolkowi@orion.math.uwaterloo.ca (Henry Wolkowicz) Subject: Re: URGENT: Duality gap in optimization Date: 25 Nov 1999 17:51:55 GMT Newsgroups: sci.math.num-analysis In article , thomas floeck wrote: >Hi there, > >anybody able to give me a verbatim definition on what "gap of duality" >in nonlinear optimization is all about. > >In german it is called "Dualitaetsluecke" > >TIA, I appreciate > >Cheers > >Thomas Given a NLP p^*=min_x f(x) s.t. g(x) <=0 then the dual problem is d^*= max_{y>=0} min_x f(x) + where <.,.> is the appropriate inner product and y is the dual or Lagrange multiplier vector. A duality gap exists if p^* > d^* (primal opt value is > dual opt value) Note that weak duality p^* >= d^* is always true. ---------------------------- P.S. Some confusion may have arisen since the popularization of primal-dual interior-point methods for linear programming and other convex programming problems. In those algorithms, one often refers to closing the duality gap to find the optimal solution. That refers to individual iterations in the algorithm, i.e. the gap between objective values of feasible primal and dual points gets smaller. -- ||Prof. Henry Wolkowicz |Fax: (519) 725-5441 ||University of Waterloo |Tel: (519) 888-4567, 1+ext. 5589 ||Dept of Comb and Opt |email: hwolkowicz@orion.math.uwaterloo.ca ||Waterloo, Ont. CANADA N2L 3G1 |URL: http://orion.math.uwaterloo.ca/~hwolkowi