In mathematical optimization, Wolfe duality, named after Philip Wolfe, is type of dual problem in which the objective function and constraints are all differentiable functions. Using this concept a lower bound for a minimization problem can be found because of the weak duality principle.[1]

Mathematical formulation

edit

For a minimization problem with inequality constraints,

 

the Lagrangian dual problem is

 

where the objective function is the Lagrange dual function. Provided that the functions   and   are convex and continuously differentiable, the infimum occurs where the gradient is equal to zero. The problem

 

is called the Wolfe dual problem.[2] This problem employs the KKT conditions as a constraint. Also, the equality constraint   is nonlinear in general, so the Wolfe dual problem may be a nonconvex optimization problem. In any case, weak duality holds.[3]

See also

edit

References

edit
  1. ^ Philip Wolfe (1961). "A duality theorem for non-linear programming". Quarterly of Applied Mathematics. 19 (3): 239–244. doi:10.1090/qam/135625.
  2. ^ "Chapter 3. Duality in convex optimization" (PDF). October 30, 2011. Retrieved May 20, 2012.
  3. ^ Geoffrion, Arthur M. (1971). "Duality in Nonlinear Programming: A Simplified Applications-Oriented Development". SIAM Review. 13 (1): 1–37. doi:10.1137/1013001. JSTOR 2028848.