# Lagrange对偶函数

## Lagrange${p_{207}}$

$\min \space f_o(x)$

$s.t. \space f_i(x)\le 0,i=1,...,m$

$h_i(x) = 0,i=1,...,p$

Lagrange对偶的基本思想是在目标函数中考虑问题的约束条件，即添加约束条件的加权和，得到目标的增广函数。

$L(x, \lambda, v)=f_{0}(x)+\sum_{i=1}^{m} \lambda_{i} f_{i}(x)+\sum_{i=1}^{p} v_{i} h_{i}(x)$

## Lagrange对偶函数

$g(\lambda, v)=\inf _{x \in D} L(x, \lambda, v)=\inf _{x \in D}\left(f_{0}(x)+\sum_{i=1}^{m} \lambda_{i} f_{i}(x)+\sum_{i=1}^{p} v_{i} h_{i}(x)\right)$

Lagrange函数关于$x$无下界，则对偶函数取值$- \infty$

### 最优值的下界

$g(\lambda,v)\le p^\star$

## 例子

### 线性方程组的最小二乘解${p_{210}}$

$\min \space x^Tx$

$s.t.\space Ax = b$

$L(x,v) = x^Tx + v^T (Ax-b)$

$g(v) = \inf _x L(x,v)$

$\bigtriangledown_xL(x,v) = 2x +A^Tv = 0$

### 标准形式的线性规划

$\min c^Tx$

$s.t. \space Ax = b$

$x \succeq 0$

$L(x,\lambda,v) = c^Tx - \sum\limits_{i=1}^n\lambda_ix_i + v^T(Ax -b) = -b^Tv + (c + A^Tv - \lambda)^Tx$

$g(\lambda,v) = \inf_xL(x,\lambda,v) = -b^Tv + \inf_x(c + A^Tv - \lambda)^Tx$

## Lagrange对偶函数和共轭函数${p_{212}}$

$f^\star(y) = \sup\limits_{x\in dom f} (y^Tx - f(x))$

$\min f_0(x)$

$s.t. \space Ax \preceq b$

$Cx = d$

\begin{aligned} g(\lambda, v) &=\inf _{x}\left(f_{0}(x)+\lambda^{T}(A x-b)+v^{T}(C x-d)\right) \\ &=-b^{T} \lambda-d^{T} v+\inf _{x}\left(f_{0}(x)+\left(A^{T} \lambda+C^{T} v\right)^{T} x\right) \\ &=-b^{T} \lambda-d^{T} v-f_{0}^{\star}\left(-A^{T} \lambda-C^{T} v\right) \end{aligned}

### 熵的最大化${p_{214}}$

$\min \space f_0(x) = \sum\limits_{i=1}^nx_i\log x_i$

$s.t. \space Ax \preceq b$

$1^Tx = 1$

$f^\star _0(y) = \sum\limits_{i=1}^ne^{y_i-1}$

$g(\lambda,v) = -b^T\lambda -v -\sum\limits_{i=1}^n e^{-a_i^T\lambda -v-1}$

# Lagrange对偶问题

## 定义

$\max g(\lambda,v)$

$s.t. \space \lambda \succeq 0$

## 例子

### 标准形式线性规划的Lagrange对偶

$\max -b^Tx$

$s.t. A^Tv - \lambda +c = 0$

$\lambda \succeq 0$

$\max -b^Tx$

$A^Tv + c \succeq 0$

### 不等式形式的线性规划的Lagrange对偶

$\min c^Tx$

$s.t. Ax \preceq b$

Lagrange函数为：

$L(x,\lambda) = c^Tx + \lambda^T(Ax - b) = -b^T\lambda +(A^T\lambda + c)^Tx$

$g(\lambda) = \inf_x L(x,\lambda) = -b^T\lambda +\inf _x(A^T\lambda + c)^Tx$

$\max -b^T\lambda$

$s.t. A^T\lambda +c = 0$

$\lambda \succeq 0$

## 弱对偶性

$d^\star$表示Lagrange对偶问题的最优值，原问题的最优值用$p^\star$表示，很容易，我们可以有以下不等式：

$d^\star \le p^\star$

## 强对偶性与Slater准则

### 凸函数

$\min f_0(x)$

$s.t. f_i(x) \le 0$

$Ax = b$

### Slater条件

$f_i(x) < 0, i =1,...,m, \space Ax =b$

Slater定理表明，当条件成立且原问题为凸问题时，强对偶性成立。

$f_i(x)\le 0, i=1,...,k \space f_i(x)<0,i=k+1,...,m \space Ax =b$

### 例子

#### 二次约束二次规划QCQP${p_{220}}$

$\min (1/2)x^TP_0x + q_0^Tx + r_0$

$s.t. \space (1/2)x^TP_ix + q_i^Tx + r_i \le0$

Lagrange函数为：

$L(x,\lambda) = (1/2 )x^TP(\lambda)x + q(\lambda)^Tx + r(\lambda)$

$\max -(1/2)q(\lambda)^TP(\lambda)^{-1}q(\lambda) + r(\lambda)$

$s.t. \lambda \succeq 0$

$(1/2)x^TP_ix + q_i^Tx + r_i <0$

## 小结

Lagrange对偶问题则进一步，将最小化最大值问题转化为最大化最小值问题，即最大化Lagrange对偶函数来求得原问题的解的下界（在Slater条件下相等），而对偶函数的好处是它始终是一个凸函数。

对偶性我们可以从之前线性规划的对偶问题看出眉目。

# 最优性条件${p_{233}}$

## 互补松弛性

\begin{aligned} f_{0}\left(x^{\star}\right) &=g\left(\lambda^{\star}, v^{\star}\right) \\ &=\inf _{x}\left(f_{0}(x)+\sum \lambda_{i}^{\star} f_{i}(x)+\sum v_{i}^{\star} h_{i}(x)\right) \\ & \leq f_{0}\left(x^{\star}\right)+\sum \lambda_{i}^{\star} f_{i}\left(x^{\star}\right)+\sum v_{i}^{\star} h_{i}\left(x^{\star}\right) \\ & \leq f_{0}\left(x^{\star}\right) \end{aligned} 可以得到一个重要的结论：

$\lambda_i^\star f_i(x^\star) = 0$

$\lambda ^\star > 0 \Rightarrow f_i(x^\star) =0$

$f_i(x^\star) < 0 \Rightarrow \lambda^\star = 0$

## KKT最优性条件

### 非凸问题的KKT条件${p_{235}}$

$\triangledown f_0(x^\star)+\sum\lambda_i^\star\triangledown f_i(x^\star) + \sum v_i^\star\triangledown h_i(x^\star) = 0$

$f_i(x^\star) \le 0$

$h_i(x^\star) = 0$

$\lambda_i^\star \ge 0$

$\lambda_i^\star f_i(x^\star )= 0$

$\triangledown f_0(x^\star)+\sum\lambda_i^\star\triangledown f_i(x^\star) + \sum v_i^\star\triangledown h_i(x^\star) = 0$

### 凸问题的KKT条件

$f_i(\tilde{x}) \le 0$

$h_i(\tilde{x}) = 0$

$\tilde{\lambda_i} \ge 0$

$\tilde{\lambda_i} f_i(\tilde{x})= 0$

$\triangledown f_0(\tilde{x})+\sum\tilde{\lambda_i}\triangledown f_i(\tilde{x}) + \sum \tilde{v_i}\triangledown h_i(\tilde{x}) = 0$

# 扰动及灵敏度分析

## 扰动问题${p_{241}}$

$\min f_0(x)$

$s.t.\space f_i(x)\le u_i$

$h_i(x)=v_i$

$u_i$大于0，则我们放松了第$i$个不等式约束；若$u_i$小于0，则我们加强了第$i$个不等式约束。

$p^\star(u,v) = \inf\{f_o(x)| \exists x\in D ,f_i(x)\le u_i,h_i(x) = v_i\}$

## 全局不等式

\begin{aligned} p^{\star}(0,0) &=g\left(\lambda^{\star}, v^{\star}\right) \\ & \leq f_{0}(x)+\sum \lambda_{i}^{\star} f_{i}(x)+\sum v_{i}^{\star} h_{i}(x) \\ & \leq f_{0}(x)+\lambda^{\star T} u+v^{\star T} v \end{aligned} 因此，对于任意扰动问题的可行解$x$

$f_0(x) \ge p^\star (0,0) - {\lambda^\star}^T u - {v^\star}^T v$

$p^\star(u,v) \ge p^\star (0,0) - {\lambda^\star}^T u - {v^\star}^T v$

### 解释

• 如果$\lambda^\star$较大，我们加强第$i$个约束(选择$u_i < 0$)，则最优值$p^\star(\lambda^\star ,v^\star)$会大幅增加；
• 如果$v^\star$较大且大于0，选择$v< 0$；或者如果$v^\star$较大且小于0，我们选择$v_i > 0$，这两种情况下最优值也会大幅增加；
• 类似，如果$\lambda^\star$较小，我们放松第$i$个约束(选择$u_i > 0$)，则最优值$p^\star(\lambda^\star ,v^\star)$不会减小太多；

## 局部灵敏度分析${p_{243}}$

$\lambda^\star_i = -\frac{\partial p^\star(0,0)}{\partial u_i} \quad v^\star_i = -\frac{\partial p^\star(0,0)}{\partial v_i}$