109_Duality

When a nonlinear programming problem is given, there exists another similar nonlinear programming problem. The former is referred to as the primal problem, and the latter as the dual problem. Under certain convexity assumptions, since the primal and dual problems have the same optimal objective function values, solving the dual problem can indirectly solve the primal problem.

 

 

To consider the local duality theory, take an example of problem with equality constraints. Assume that the function $f$ and ${h_i}$ are twice differentiable. ${h_i}(x)=0$ represents the equality constraint. The Lagrangian function and its Hessian are as follows.

 

 

${\bf{v}}$ is the $p$-dimensional vector of Lagrange multipliers for the equality constraints. If ${x^*}$ is a local minimum and a regular point of the feasible set, there exists a unique Lagrange multiplier $v_i^*$ for each constraint, satisfying the first-order necessary conditions.

 

 

If assume that the Hessian of the Lagrangian function at the minimum point ${\bf{{x^*}}}$ is positive definite, it guarantees that the Lagrangian function is locally convex at ${\bf{{x^*}}}$ . Additionally, it satisfies the sufficient conditions for ${\bf{{x^*}}}$ to be a local minimum. Therefore, ${\bf{{x^*}}}$ also becomes the local minimum for the following inequality problem.

 

 

For any ${\bf{v}}$ colse to ${\bf{{v^*}}}$, the Lagrangian function will have a local minimum around ${\bf{{x^*}}}$. The necessary conditions at the point ${\bf{(x,v)}}$ near $({{\bf{x}}^{\bf{*}}},{{\bf{v}}^{\bf{*}}})$ are as follows.

 

 

Since ${{\text{H}}_x}({{\bf{x}}^*},{{\bf{v}}^*})$ is positive definite, it is nonsingular. Consequently, ${{\text{H}}_x}({{\bf{x}}},{{\bf{v}}})$ remains positive definite and hence nonsingular in the near of $({{\bf{x}}^*},{{\bf{v}}^*})$. Therefore, locally, there is a unique correspondence between ${\bf{v}}$ and ${\bf{x}}$ through the solution of the equality problem.

 

By using this definition of the dual function, we can show that locally, the original problem with constriants is equivalent to the local maximization of the dual function with respect to ${\bf{v}}$. Therefore, we can establish the equivalence between the problem with constraints at ${\bf{x}}$ and the unconstrained problem at ${\bf{v}}$