Wolfe Duality

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.

Mathematical formulation

For a minimization problem with inequality constraints,

: $\begin &\underset& & f(x) \\ &\operatorname & &g_i(x) \leq 0, \quad i = 1,\dots,m \end$

the Lagrangian dual problem is

: $\begin &\underset& & \inf_x \left(f(x) + \sum_^m u_j g_j(x)\right) \\ &\operatorname & &u_i \geq 0, \quad i = 1,\dots,m \end$

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

: $\begin &\underset& & f(x) + \sum_^m u_j g_j(x) \\ &\operatorname & & \nabla f(x) + \sum_^m u_j \nabla g_j(x) = 0 \\ &&&u_i \geq 0, \quad i = 1,\dots,m \end$

is called the Wolfe dual problem. This problem employs the KKT conditions as a constraint. Also, the equality constraint $\nabla f(x) + \sum_^m u_j \nabla g_j(x)$ is nonlinear in general, so the Wolfe dual problem may be a nonconvex optimization problem. In any case, weak duality holds.

See also

* Lagrangian duality
* Fenchel duality

References

Convex optimization

{{applied-math-stub