# Lagrangian Duality I. Definition

\begin{aligned} &\min; f({\bf x}) \ {\rm s.t.};;c_i({\bf x}) &\leq 0, ; i=1,2,\cdots,n \ h_j({\bf x}) &= 0, ; j = 1,2,\cdots,m\ \end{aligned} \tag{1}

$$\mathcal{L}({\bf x}, \boldsymbol{\alpha},\boldsymbol{\beta})=f({\bf x})+\boldsymbol{\alpha}^\top {\bf c}({\bf x})+\boldsymbol{\beta}^\top{\bf h}({\bf x})$$

$$\theta_P=\max_{\boldsymbol{\alpha}, \boldsymbol{\beta}}\mathcal{L}({\bf x}, \boldsymbol{\alpha}, \boldsymbol{\beta}) \ {\rm s.t.};; \alpha_i \geq 0,;i=1,2,\cdots,n$$

$$\theta_P(\boldsymbol{\alpha}, \boldsymbol{\beta}) = \begin{cases} f(\mathbf{x}) &\begin{cases} c_i(\mathbf{x}) \leq 0 &i = 1,2,\cdots,n \ h_j(\mathbf{x}) = 0 &j = 1,2,\cdots,m \end{cases} \ \infty &\text{others} \end{cases}$$

${\bf P{\scriptsize ROOF}.}$若 $\exists, i\in[1:n]$使得 $c_i({\bf x})\geq0$，则可调整 $\alpha_i$使 $\theta_P \rightarrow +\infty$；同理，若 $\exists, j \in [1:m]$ 使得$h_j({\bf x}) \neq 0$，则可调整$\beta_j h_j({\bf x})$ 使得$\theta_P \rightarrow +\infty$。$\blacksquare$

$$p^* = \min_{\bf x}f({\bf x}) = \min_{\bf x}\max_{\boldsymbol{\alpha},\boldsymbol{\beta}}\mathcal{L}({\bf x},\boldsymbol{\alpha},\boldsymbol{\beta}) \ {\rm s.t.};; \alpha_i \geq 0,; i=1,2,\cdots,n$$

\left{ \begin{aligned} f({\bf x}) &< d^* \ {\bf c}({\bf x}) &\leq {\bf 0} \ {\bf h}({\bf x}) &= {\bf 0} \end{aligned} \right. \tag{2}

$$f({\bf x})+\boldsymbol{\alpha}^\top {\bf c}({\bf x})+\boldsymbol{\beta}^\top{\bf h}({\bf x}) < d^* \tag{3}$$

$$\min_{\bf x} \left( f({\bf x})+\boldsymbol{\alpha ‘}^\top{\bf c}({\bf x})+\boldsymbol{\beta ‘}^\top{\bf h}({\bf x}) \right) \geq d^*$$

\begin{aligned} d^* &= \max_{\boldsymbol{\alpha},\boldsymbol{\beta}}\min_{\bf x} \left( f({\bf x})+\boldsymbol{\alpha}^\top{\bf c}({\bf x})+\boldsymbol{\beta}^\top{\bf h}({\bf x}) \right) \ &= \max_{\boldsymbol{\alpha},\boldsymbol{\beta}}\min_{\bf x}\mathcal{L}({\bf x}, \boldsymbol{\alpha}, \boldsymbol{\beta}) \end{aligned} \tag{4}

$$\theta_D({\bf x}) = \max_{\boldsymbol{\alpha},\boldsymbol{\beta}}\mathcal{L}({\bf x}, \boldsymbol{\alpha}, \boldsymbol{\beta})$$

$$d^* = \max_{\boldsymbol{\alpha},\boldsymbol{\beta}}\min_{\bf x}\mathcal{L}({\bf x}, \boldsymbol{\alpha}, \boldsymbol{\beta}) \ {\rm s.t.};; \boldsymbol{\alpha} \geq {\bf 0}$$

${\bf T{\scriptsize HEOREM};1}.;;{\rm W{\scriptsize EAK};D{\scriptsize UALITY}.}$

$$\boxed{d^* \leq p^*.}$$

${\bf P{\scriptsize ROOF}}.$ 易得

$$\min_{\bf x}\mathcal{L}({\bf x}, \boldsymbol{\alpha}, \boldsymbol{\beta}) \leq ({\bf x}, \boldsymbol{\alpha}, \boldsymbol{\beta}) \leq \max_{\boldsymbol{\alpha},\boldsymbol{\beta}}\mathcal{L}({\bf x}, \boldsymbol{\alpha}, \boldsymbol{\beta})$$

\begin{aligned} d^* &= \max_{\boldsymbol{\alpha},\boldsymbol{\beta}}\min_{x}\mathcal{L}({\bf x}, \boldsymbol{\alpha}, \boldsymbol{\beta}) \ &\leq \min_{\bf x}\max_{\boldsymbol{\alpha},\boldsymbol{\beta}}\mathcal{L}({\bf x}, \boldsymbol{\alpha}, \boldsymbol{\beta}) \ &= p^*;\blacksquare \end{aligned}

${\bf N\scriptsize{OTE}}.$ 注意 Weak Duality 实际上对于一切优化问题均成立，而与原始问题是否为凸无关。

${\bf C{\scriptsize OROLLARY};;1}.$若 $p^$与 $d^$ 均存在且有$p^* = d^$，则 Primal Problem 和 Dual Problem 的可行解$({\bf x}^, \boldsymbol{\alpha}^, \boldsymbol{\beta}^)$ 分别也是对应问题的最优解。