Wolfe duality

This article needs additional citations for verification. Please help by adding citations to reliable sources. Unsourced material may be challenged and removed. Find sources:  –  ·  ·  · scholar · JSTOR (May 2012) (Learn how and when to remove this template message)

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,

${\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]

See also[]

• Lagrangian duality
• Fenchel duality

References[]

This applied mathematics-related article is a stub. You can help Wikipedia by .

• v
• t