Duality

Definition

Optimization problems may be viewed from either the primal problem or the dual problem.

Properties

Consider the following optimization problem

The original problem is called a Primal problem $\underset{x}{\min }f(x)$ subject to $g(x)\le 0,h(x)=0$ Let a $\mathcal{D}$ be the domain of the problem and the $\mathcal{X}\in \mathcal{D}$ be its feasible set

The Lagrangian function corresponding to the primal problem is called a Lagrangian primal function $\mathcal{L}(x,\mu ,\lambda )=f(x)+\mu g(x)+\lambda h(x)$ where the variable $x$ is called a Primal variable, and $\mu ,\lambda$ are called Dual variables

Since $\forall x\in \mathcal{X}\Rightarrow g(x)\le 0\wedge h(x)=0$ by the constraints, the Lagrangian primal function is always lower than or equal to the $f(x)$ for all $x$ in the feasible set $L(x,\lambda ,\mu )=f(x)+\mu g(x)+\lambda h(x)\le f(x),\forall x\in \mathcal{X}$

Let a primal optimal value $f(x^{\ast })$ be the feasible optimal value of the primal problem $f(x^{\ast })=\underset{x\in \mathcal{X}}{\min }f(x)$

Let a Lagrange dual function $q(\mu ,\lambda )$ be the minimum of the Lagrangian primal function for all $x$ in the domain $q(\mu ,\lambda ):=\underset{x\in \mathcal{D}}{\min }\mathcal{L}(x,\mu ,\lambda )=\underset{x\in \mathcal{D}}{\min }\left(f(x)+\lambda h(x)+\mu g(x)\right),\forall \mu >0,\forall \lambda$

We say another optimization problem for the Lagrange dual function $q(\mu ,\lambda )$ a Dual problem $\max q(\mu ,\lambda )$ subject to $\mu \ge 0$

Since the Lagrange dual function minimize the Lagrangian primal function $\forall x\in \mathcal{D}$, it is always lower than or equal to the primal optimal value that minimizes that $\forall x\in \mathcal{X}$ $q(\mu ,\lambda )=\underset{x\in \mathcal{D}}{\min }\mathcal{L}(x,\mu ,\lambda )\le \underset{x\in \mathcal{X}}{\min }\mathcal{L}(x,\mu ,\lambda )=\mathcal{L}(x^{\ast },\mu ,\lambda )=f(x^{\ast })+\lambda h(x^{\ast })+\mu g(x^{\ast })\le f(x^{\ast })\forall \mu >0,\forall \lambda$

Let a dual optimal value be the maximum of the dual problem $q(\mu ,\lambda )$ $q({\mu }^{\ast },{\lambda }^{\ast }):=\underset{\mu ,\lambda }{\max }q(\mu ,\lambda )=\underset{\mu ,\lambda }{\max }(\underset{x\in \mathcal{D}}{\min }\mathcal{L}(x,\mu ,\lambda ))\forall \mu >0,\forall \lambda$

Then, by the above inequality, $q({\mu }^{\ast },{\lambda }^{\ast })$ become the lower bound of $f(x^{\ast })$ $q(\mu ,\lambda )\le q({\mu }^{\ast },{\lambda }^{\ast })\le f(x^{\ast })$ This property is called a Weak Duality $q({\mu }^{\ast },{\lambda }^{\ast })\le f(x^{\ast })$

and the difference between the dual optimal value and the primal optimal value is called a Duality Gap $f(x^{\ast })-q({\mu }^{\ast },{\lambda }^{\ast })$

If the dual optimal value and the primal optimal value are the same, then this property is called a Strong Duality $q({\mu }^{\ast },{\lambda }^{\ast })=f(x^{\ast })$

Solution for the Problem Satisfying Strong Duality

Find the Lagrange dual function $q(\mu ,\lambda ):=\underset{x\in \mathcal{D}}{\min }\mathcal{L}(x,\mu ,\lambda )$ by using the gradient condition ${\nabla }_x\mathcal{L}(x,\mu ,\lambda )=0$ find the dual optimal variables ${\mu }^{\ast },{\lambda }^{\ast }$ from the dual problem $\underset{\mu ,\lambda }{\max }q(\mu ,\lambda )$ by using the gradient condition ${\nabla }_{\mu ,\lambda }q(\mu ,\lambda )=0$ obtain the primal optimal variable $x^{\ast }$ using the dual optimal variables ${\mu }^{\ast },{\lambda }^{\ast }$

Visual Explanation of Duality

Consider an optimization problem $\underset{x}{\min }f(x)$ subject to $g(x)\le 0$

Let a set $\mathcal{G}$ where $\mathcal{G}=\{(g(x),f(x))|x\in \mathcal{D}\}$

And let $p^{\ast }$ be the primal optimal solution $p^{\ast }=\inf (\{t|(u,t)\in \mathcal{G},u\le 0\})$

By definition of Lagrange dual function, $g(\lambda )=\underset{x\in \mathcal{D}}{\inf }(f(x)+\lambda g(x))=\underset{x\in \mathcal{D}}{\inf }(t+\lambda u)=\inf (\{(\lambda ,1{)}^{⊺}(u,t)|(u,t)\in \mathcal{G}\})$ where $\lambda \ge 0$

Consider $u-t$ plane Where the feasible region is of $\mathcal{G}\cap u\le 0$

The optimal value $p^{\ast }$ is given by the tangent horizontal line that indicates the minimum value when $u\le 0$

Since $\lambda \ge 0$, the line always has negative slope. So, for a given $\lambda$, the line $t=-\lambda u+g(\lambda )$ provides the lower bound of the objective function $t=f(x)$

The figure shows the hyperplanes for different values $\lambda$ We see that ${\lambda }^{\ast }$ gives the best lower bound $d^{\ast }$, also see that Strong Duality does not hold because $p^{\ast }\ne d^{\ast }$

Optimality Property

$\exists \bar{x},\exists \bar{\lambda },\exists \bar{\mu },q(\bar{\mu },\bar{\lambda })=f(\bar{x})\Rightarrow q(\bar{\mu },\bar{\lambda })=q({\mu }^{\ast },{\lambda }^{\ast })\wedge f(\bar{x})=f(x^{\ast })$ If we have feasible solutions to the primal and dual problems such that their respective objective functions are equal, then these solutions are optimal to their respective problems

Proof Let a prime variable be $\bar{x}$ and dual variables be $\bar{\lambda },\bar{\mu }$ satisfying $q(\mu ,\lambda )=f(x)$

Since the primal optimal $x^{\ast }$ minimize $f(x^{\ast })$, the value $f(\bar{x})$ with the prime variable $\bar{x}$ always greater than or equal to the $f(x^{\ast })$ $q(\mu ,\lambda )\le q({\mu }^{\ast },{\lambda }^{\ast })\le f(x^{\ast })\le f(\bar{x})$

And by the assumption, the first term and the last term of the inequality become the same. $q(\bar{\mu },\bar{\lambda })=q({\mu }^{\ast },{\lambda }^{\ast })=f(x^{\ast })=f(\bar{x})$

Then, by the equality $q(\bar{\mu },\bar{\lambda })=q({\mu }^{\ast },{\lambda }^{\ast })$, the dual variable $\bar{\lambda },\bar{\mu }$ are the dual optimal, and by the equality $f(x^{\ast })=f(\bar{x})$, the primal variable $\bar{x}$ is the primal optimal And the two are the same.

Therefore, values $\bar{x},\bar{\lambda },\bar{\mu }$ are optimal.

Facts

If the primal is a minimization problem, then the dual is a maximization problem, and vice versa

The solution to the primal is an upper bound to the solution of the dual, and the solution of the dual is a lower bound to the solution of the primal, and vice versa

For the minimization primal problem, the dual optimal is a lower bound of the primal optimal