Primal Problem

For optimize problem in convex set $\mathcal{X}$

$$\begin{align} \mathop{\arg\min}\limits_{x\in\mathcal{X}}\quad &f(x)\tag{P}\\ s.t.\quad &g_i(x)\leq 0,\quad i=1,2,\ldots,k\\ & h_j(x)=0,\quad j=1,2,\ldots,l \end{align}$$

which is called the primal problem for optimization.

The generalized Lagrange function for primal problem is defined as

$$\begin{align} \mathcal{L}(x,\kappa ,\lambda )\equiv& f(x)+\sum_{i=1}^k\kappa _ig_i(x)+\sum_{j=1}^l\lambda _jh_j(x) \\ w.r.t. \quad&\kappa _i\geq 0,\quad i=1,2,\ldots,k \end{align}$$

Comment: here the constraint $\kappa _i\geq 0$ suggest that, if $g_i(x)<0$, then a $\kappa_i\to\infty$ would result in $\mathcal{L}\to -\infty$, which cannot be minimized. This is how $\kappa _i\geq 0$ helps keep the constraints.

and we could further define a function of $x$:

$$\begin{align} \theta _P(x)\equiv& \mathop{\max}\limits_{\kappa ,\lambda :\kappa _i\geq 0}\mathcal{L}(x,\kappa ,\lambda ) =\begin{cases} f(x)&\text{constraint } g,\,h \text{ satisfied}\\ +\infty &\text{contraint unsatisfied} \end{cases} \end{align}$$

which means we can give the solution value of primal problem (P) simply by minimizing $\theta _P(x)$, minimum denoted $p^*$

$$\begin{align} p^* \equiv \mathop{\min}\limits_{x}\theta _P(x)=\mathop{\min}\limits_{x} \mathop{\max}\limits_{\kappa ,\lambda :\kappa _i\geq 0}\mathcal{L}(x,\kappa ,\lambda ) \end{align}$$

Dual problem

Similar to primal problem, we can define a function of $\kappa ,\lambda$:

$$\begin{align} \theta _D(\kappa ,\lambda )\equiv&\mathop{\min}\limits_{x} \mathcal{L}(x,\kappa ,\lambda ) \end{align}$$

and similarly get the dual problem of primal, value denoted $d^*$

$$\begin{align} d^*\equiv\max_{\kappa ,\lambda :\kappa \geq 0}\theta _D(\kappa ,\lambda )=\max_{\kappa ,\lambda :\kappa \geq 0}\mathop{\min}\limits_{x} \mathcal{L}(x,\kappa ,\lambda ) \end{align}$$

it is obvious that

$$\begin{align} d^*= \max_{\kappa ,\lambda :\kappa \geq 0}\mathop{\min}\limits_{x} \mathcal{L}(x,\kappa ,\lambda ){\color{red}\leq }\mathop{\min}\limits_{x} \mathop{\max}\limits_{\kappa ,\lambda :\kappa _i\geq 0}\mathcal{L}(x,\kappa ,\lambda )=p^* \end{align}$$

Karush-Kuhn-Tucker Condition (KKT Condition)

KKT condition to allow $d^*=p^*$ at $(x^*,\kappa ^*,\lambda ^*)$: in the case that

• $f(x)$ and $g_i(x)$ are convex
• $h_j(x)$ in the form of affine function $A_jx+b$
• $g_i(x)$ are feasible constraints

then $\mathrm{KKT}\,\Leftrightarrow\, p^*=d^*=\mathcal{L}(x^*,\kappa ^*,\lambda ^*)$. The KKT conditions are:

$$\begin{align} &\nabla_x\mathcal{L}(x^*,\kappa ^*,\lambda ^*)=0&\\ &\kappa ^*_ig_i(x^*)=0&i=1,2,\ldots,k\\ &g_i(x^*)\leq 0&i=1,2,\ldots,k\\ &\kappa _i\geq 0&i=1,2,\ldots,k\\ &\lambda _j(x^*)=0&j=1,2,\ldots,l \end{align}$$