Home
Wikimization
Contact Us
Accumulator error feedback
CVX Download
Calculus of Inequalities
Rick Chartrand
Chromosome Structure EDM
Complementarity problem
Compressive Sampling
Compressed Sensing
Conic Independence
Convex Cones
Convex Functions
Convex Geometry
Convex, Affine, Conic: Hulls
Convex Iteration
Convex Optimization
Convex Optimization Group
Dattorro PC Optimization
Dattorro Supercomputer
Distance Geometry
Distance Matrix Cone
Dual Cones
Duality Gap
Eigenvalues/Eigenvectors
Elliptope and Fantope
Euclidean Distance Matrices
EDM cone faces
Extreme Directions
Face Recognition
Farkas Lemma
Fermat point
Fifth Metric Property
Jensen's Inequality
Jobs in Optimization
Kissing Number
Harold W. Kuhn
Linear Algebra
Linear Matrix Inequality
Manifold Learning
MATLAB for Optimization
Matrix Calculus
Molecular Conformation
Moreau's theorem
Isaac Newton
Angelia Nedic
Open Problems
Positive Matrix Factorization
Positive Semidefinite Cone
Projection
Projection on Cone
Proximity Problems
PY4SCIENCE
Quasiconvex Functions
Rank Constraint
Rockafellar
Justin Romberg
Michael Saunders
Schoenberg Criterion
Semidefinite Programming
Sensor Network Localization
Smallest Simplex
Systems Optimization Lab
Stanford SOL
Talks on Optimization
Joshua Trzasko
Video
Wikimization     Meboo     SOL      Video     CVX     Contact     
Felice crystal
Home arrow Duality Gap
Duality Gap

"Duality is a powerful and widely employed tool in applied mathematics for a number of reasons.  First, the dual program is always convex even if the primal is not.  Second, the number of variables in the dual is equal to the number of constraints in the primal which is often less than the number of variables in the primal program.  Third, the maximum value achieved by the dual problem is often equal to the minimum of the primal."


dual programs

 

Essentially, duality theory concerns representation of a given optimization problem as half a minimax problem.  Given any real function f(x,z)

minimize_x maximize_z  f (x,z) >= maximize_z minimize_x  f (x,z)

always holds.  When

minimize_x maximize_z  f (x,z) = maximize_z minimize_x  f (x,z)

we have strong duality and then a saddle value exists, as depicted, and the duality gap is 0 (g(z) kisses f(x)).

Read more...

 
Course,   Video
Convex Optimization
     convex optimization
Stephen Boyd 
L. Vandenberghe 


Dattorro      convex optimization Euclidean distance geometry 2ε
Dattorro


Course
Bertsekas
     books by Bertsekas
Dimitri Bertsekas 


See Inside Hiriart-Urruty & Lemaréchal
Hiriart-Urruty
& Lemaréchal


See Inside
Rockafellar Rockafellar