Wolfe duality

(Redirected from Wolfe dual problem)

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{align} &\underset{x}{\operatorname{minimize}}& & f(x) \\ &\operatorname{subject\;to} & &g_i(x) \leq 0, \quad i = 1,\dots,m \end{align}
\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]