Wolfe duality

From HandWiki
Revision as of 20:35, 6 March 2023 by Wikisleeper (talk | contribs) (add)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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

For a minimization problem with inequality constraints,

[math]\displaystyle{ \begin{align} &\underset{x}{\operatorname{minimize}}& & f(x) \\ &\operatorname{subject\;to} & &g_i(x) \leq 0, \quad i = 1,\dots,m \end{align} }[/math]

the Lagrangian dual problem is

[math]\displaystyle{ \begin{align} &\underset{u}{\operatorname{maximize}}& & \inf_x \left(f(x) + \sum_{j=1}^m u_j g_j(x)\right) \\ &\operatorname{subject\;to} & &u_i \geq 0, \quad i = 1,\dots,m \end{align} }[/math]

where the objective function is the Lagrange dual function. Provided that the functions [math]\displaystyle{ f }[/math] and [math]\displaystyle{ g_1, \ldots, g_m }[/math] are convex and continuously differentiable, the infimum occurs where the gradient is equal to zero. The problem

[math]\displaystyle{ \begin{align} &\underset{x, u}{\operatorname{maximize}}& & f(x) + \sum_{j=1}^m u_j g_j(x) \\ &\operatorname{subject\;to} & & \nabla f(x) + \sum_{j=1}^m u_j \nabla g_j(x) = 0 \\ &&&u_i \geq 0, \quad i = 1,\dots,m \end{align} }[/math]

is called the Wolfe dual problem.[2] This problem employs the KKT conditions as a constraint. Also, the equality constraint [math]\displaystyle{ \nabla f(x) + \sum_{j=1}^m u_j \nabla g_j(x) }[/math] is nonlinear in general, so the Wolfe dual problem may be a nonconvex optimization problem. In any case, weak duality holds.[3]

See also

  • Lagrangian duality
  • Fenchel duality

References

  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". October 30, 2011. http://wwwhome.math.utwente.nl/~stillgj/conopt/chap3.pdf. 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.