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.^[1]

Mathematical formulation

For a minimization problem with inequality constraints,

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

{\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 $f$ and $g_{1},\ldots ,g_{m}$ are continuously differentiable, the infimum occurs where the gradient is equal to zero. The problem

{\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. This problem may be difficult to deal with computationally, because the objective function is not concave in the joint variables $(u,x)$ . Also, the equality constraint $\nabla f(x)+\sum _{j=1}^{m}u_{j}\nabla g_{j}(x)$ is nonlinear in general, so the Wolfe dual problem is typically a nonconvex optimization problem. In any case, weak duality holds.^[3]

References

↑ Philip Wolfe (1961). "A duality theorem for non-linear programming". Quarterly of Applied Mathematics. 19: 239–244.
↑ "Chapter 3. Duality in convex optimization" (pdf). October 30, 2011. Retrieved May 20, 2012.
↑ Geoffrion, Arthur M. (1971). "Duality in Nonlinear Programming: A Simplified Applications-Oriented Development". SIAM Review. 13 (1): 1–37. doi:10.1137/1013001. JSTOR 2028848.

This article is issued from Wikipedia - version of the 4/9/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.

Wolfe duality

Mathematical formulation

See also

References