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{array}{rlrl}& \underset{x}{\mathrm{minimize}}& & f(x)\\ & \mathrm{s}\mathrm{u}\mathrm{b}\mathrm{j}\mathrm{e}\mathrm{c}\mathrm{t}\mathrm{t}\mathrm{o}& & g_i(x)\le 0,i=1,\dots ,m\end{array}$

the Lagrangian dual problem is

$\begin{array}{rlrl}& \underset{u}{\mathrm{maximize}}& & \underset{x}{\inf }(f(x)+\sum _{j=1}^m{u}_j{g}_j(x))\\ & \mathrm{s}\mathrm{u}\mathrm{b}\mathrm{j}\mathrm{e}\mathrm{c}\mathrm{t}\mathrm{t}\mathrm{o}& & u_i\ge 0,i=1,\dots ,m\end{array}$

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

$\begin{array}{rlrl}& \underset{x,u}{\mathrm{maximize}}& & f(x)+\sum _{j=1}^m{u}_j{g}_j(x)\\ & \mathrm{s}\mathrm{u}\mathrm{b}\mathrm{j}\mathrm{e}\mathrm{c}\mathrm{t}\mathrm{t}\mathrm{o}& & \mathrm{\nabla }f(x)+\sum _{j=1}^m{u}_j\mathrm{\nabla }{g}_j(x)=0\\ & & & u_i\ge 0,i=1,\dots ,m\end{array}$

is called the Wolfe dual problem. This problem employs the KKT conditions as a constraint. Also, the equality constraint $\mathrm{\nabla }f(x)+\sum _{j=1}^m{u}_j\mathrm{\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