Wolfe duality

For a minimization problem with inequality constraints,

${\displaystyle {\begin{aligned}&{\underset {x}{\operatorname {minimize} }}&&f(x)\\&\operatorname {subject\;to} &&g_{i}(x)\leq 0,\quad i=1,\dots ,m\end{aligned}}}$

the Lagrangian dual problem is

${\displaystyle {\begin{aligned}&{\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{aligned}}}$

where the objective function is the Lagrange dual function. Provided that the functions ${\displaystyle f}$ and ${\displaystyle g_{1},\ldots ,g_{m}}$ are convex and continuously differentiable, the infimum occurs where the gradient is equal to zero. The problem

${\displaystyle {\begin{aligned}&{\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{aligned}}}$

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

• Lagrangian duality
• Fenchel duality