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{matrix} \underset{x}{minimize} & f (x) \\ s u b j e c t t o & g_{i} (x) \leq 0, i = 1, \dots, m \end{matrix}

the Lagrangian dual problem is

\begin{matrix} \underset{u}{maximize} & inf_{x} (f (x) + \sum_{j = 1}^{m} u_{j} g_{j} (x)) \\ s u b j e c t t o & u_{i} \geq 0, i = 1, \dots, m \end{matrix}

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{matrix} \underset{x, u}{maximize} & f (x) + \sum_{j = 1}^{m} u_{j} g_{j} (x) \\ s u b j e c t t o & \nabla f (x) + \sum_{j = 1}^{m} u_{j} \nabla g_{j} (x) = 0 \\ u_{i} \geq 0, i = 1, \dots, m \end{matrix}

is called the Wolfe dual problem.^{[clarification needed]} This problem employs the KKT conditions as a constraint. 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 may be a nonconvex optimization problem. In any case, weak duality holds.

References

↑ Philip Wolfe (1961). "A duality theorem for non-linear programming". Quarterly of Applied Mathematics. 19 (3): 239–244. doi:10.1090/qam/135625.
↑ Eiselt, Horst A. (2019). Nonlinear Optimization: Methods and Applications. International Series in Operations Research and Management Science Ser. Carl-Louis Sandblom. Cham: Springer International Publishing AG. p. 147. ISBN 978-3-030-19462-8.
↑ 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 applied mathematics–related article is a stub. You can help Wikipedia by adding missing information.

[Wolfe-1] Philip Wolfe (1961). "A duality theorem for non-linear programming". Quarterly of Applied Mathematics. 19 (3): 239–244. doi:10.1090/qam/135625.

[2] Eiselt, Horst A. (2019). Nonlinear Optimization: Methods and Applications. International Series in Operations Research and Management Science Ser. Carl-Louis Sandblom. Cham: Springer International Publishing AG. p. 147. ISBN 978-3-030-19462-8.

[3] 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.

Wolfe duality

Mathematical formulation

See also

References