Wolfe duality

From Wikipedia, the free encyclopedia
  (Redirected from Wolfe dual problem)
Jump to: navigation, search

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[edit]

For a minimization problem with inequality constraints,

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

the Lagrangian dual problem is

\begin{align}
&\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{align}

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{align}
&\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{align}

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]

See also[edit]

References[edit]

  1. ^ Philip Wolfe (1961). "A duality theorem for non-linear programming". Quarterly of Applied Mathematics 19: 239–244. 
  2. ^ "Chapter 3. Duality in convex optimization" (pdf). October 30, 2011. Retrieved May 20, 2012. 
  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.