最优化方法例题解法

简略记录了例题以及解法，没事，李老师会预判你的预判，自求多福

Chapter1

利润最大化问题(没考)

步骤如下：

1. 将最大化问题与条件转换为矩阵形式，如：

$$max \space 40x_1+50x_2 \space s.t. \space x_1 + 2x_2 \le 40$$

变成

$$令x=\begin{bmatrix} x_1 \\ x_2\end{bmatrix}, a=\begin{bmatrix} 40 \\ 50\end{bmatrix}, b=\begin{bmatrix} 1 \\ 2 \end{bmatrix}$$

$$max \space a^T x \space s.t. \space b^Tx \le 40$$

2. 使用线性规划法求解问题，画出坐标图

3. 最大化$y=a^Tx$即最大化该直线的截距，找到直线经过的最高点并计算出此时的最优解。

Chapter2

判断是否为线性函数(没考)

两条性质：

• 齐次性（homogeneity）：$f(kx)=kf(x)$

• 叠加性（Additivity）：$f(x+y)=f(x)+f(y)$

验证或找到反例即可

反例可先判断其不为仿射函数（一个线性函数加上常数）：

$$f(\alpha x + \beta y)=\alpha f(x) + \beta f(y), \space \alpha + \beta =1,\alpha, \beta \in \mathbb{R},x,y \in \mathbb{R} ^n$$

求一阶泰勒近似(考了)

代公式就好

$$\hat{f}(x)=f(z)+\nabla f(z)^T(x-z) \\ \nabla f(z)=\begin{bmatrix} \frac{\partial f}{\partial x_1}(z) \\ \vdots \\ \frac{\partial f}{\partial x_n}(z) \end{bmatrix}$$

Chapter3

写出各种范数(考了，送分)

$\ell_1$-范数（曼哈顿范数）

$$||x||_1=|x_1|+|x_2|+ \cdots +|x_n|,x,y \in \bold{R}^n,\alpha \in \bold{R}$$

$\ell_2$-范数（欧几里得范数，一般的$||\cdot||$也是）

$$||x||_2=\sqrt{(x_1^2+x_2^2+ \cdots +x_n^2)}=\sqrt{x^Tx}=(\langle x,x \rangle )^\frac{1}{2}$$

$\ell_p$-范数

$$||x||_p=(|x_1|^p+|x_2|^p+\cdots+|x_n|^p)^\frac{1}{p},x \in \mathbb{R}^n$$

$\ell_\infin$-范数

$$||x||_\infin = \max_{1 \le i \le n} |x_i|,x \in \bold{R}^n$$

$\ell_0$-范数 （非0元素的个数）

$$||x||_0=nnz(x)$$

柯西-施瓦茨不等式

可用于证明$\ell_2$-范数的三角不等性

$$|\langle x,y \rangle |^2 \le \langle x,x \rangle \langle y,y \rangle = ||x||_2^2 ||y||_2^2$$

Minkowshi不等式

可用于证明$\ell_p$-范数的三角不等性

$$(\sum_{i=1}^n |x_i+y_i|^p)^\frac{1}{p} \le (\sum_{i=1}^n|x_i|^p)^\frac{1}{p} + (\sum_{i=1}^n|y_i|^p)^\frac{1}{p},p \ge 1, x,y \in \bold{R}^n$$

Hölder不等式

$$\sum_{i=1}^n |x_iy_i| \le (\sum_{i=1}^n|x_i|^p)^\frac{1}{p} (\sum_{i=1}^n|y_i|^p)^\frac{1}{p},\frac{1}{p}+\frac{1}{q}=1,1$$

判断是否为范数

• 非负性：$||x|| \ge 0,x\in \mathbb{R}^n 且 ||x||=0 \Leftrightarrow x=0$

• 齐次性：$||\alpha x||=|\alpha|||x||,\alpha \in \mathbb{R}且x \in \mathbb{R}^n$

• 三角不等性：$||x+y|| \le ||x||+||y||,x,y \in \mathbb{R}^n$

特殊范数的三角不等性

• $\ell_2$-范数需要使用柯西-施瓦茨不等式

$$\begin{aligned}||x+y||_2^2 &=\langle x+y,x+y \rangle \\ &= \langle x,x \rangle + \langle x,y \rangle + \langle y,x \rangle + \langle y,y \rangle \\ &= ||x||_2^2 + 2 \red {\langle x,y \rangle} + ||y||_2^2 \\ & \le ||x||_2^2 + 2\red{||x||_2||y||_2}+ ||y||_2^2 \\ &= (||x||_2+||y||_2)^2\end{aligned}$$

• 则$||x+y||_2 \le ||x||_2+||y||_2$得证

• $\ell_p$-范数使用Minkowshi不等式可直接证明

$$(\sum_{i=1}^n |x_i+y_i|^p)^\frac{1}{p} \le (\sum_{i=1}^n|x_i|^p)^\frac{1}{p} + (\sum_{i=1}^n|y_i|^p)^\frac{1}{p},p \ge 1, x,y \in \bold{R}^n$$

Chapter4

证明一个函数是凸函数(考了复合函数，做不出来)

证明：

$$f(\alpha x + (1-\alpha )y) \le \alpha f(x) + (1-\alpha) f(y), \\ \forall x,y \in \Omega,\alpha \in \bold R, 0\le\alpha\le 1$$

证明引理(好像是附加题，反正做不到)

可微函数$f$是凸函数的充要条件：

$$f(y) \ge f(x) + \langle \nabla f(x), y-x \rangle , \forall x,y$$

n=1(一维情况)

可微函数$f$是凸函数是式子的充分条件：

根据函数$f$是凸函数可得：

$$f(x+t(y-x))=f((1-t)x+ty) \le (1-t)f(x)+tf(y)$$

上式两端同除$t$可得：

$$f(y) \ge f(x) + \frac{f(x+t(y-x))-f(x)}{t}$$

令$t\to 0$，得证(得到式子)

可微函数$f$是凸函数是式子的必要条件：

令$z=\alpha x + (1-\alpha)x,0\le \alpha \le 1$，根据式子可得：

$$f(x) \ge f(z)+f'(z)(x-z), \ f(y) \ge f(z)+f'(z)(y-z)$$

将第一个不等式乘以$\alpha$，第二个不等式乘以$1-\alpha$，并将两者相加即可得：

$$\alpha f(x) + (1-\alpha)f(y) \ge f(z)$$

即可得到函数$f$是凸的

n>1(一般情况)

令

$$g(t)=f(ty+(1-t)x), \\ g'(t)=\nabla f(ty+(1-t)x)^T(y-x)$$

可微函数$f$是凸函数是式子的充分条件：

由于函数$f$是凸的，所以函数$g$是凸的。满足

$$g(1) \ge g(0) + g'(0)(1-0)$$

即

$$f(y)\ge f(x)+\nabla f(x)^T(y-x)$$

可微函数$f$是凸函数是式子的必要条件：

令$ty+(1-t)x \in \bold{dom} f,\bar ty+(1-\bar t)x \in \bold{dom} f$，根据式子可得：

$$f(ty+(1-t)x)\ge f(\bar ty+(1-\bar t)x) + \nabla f(\bar ty+(1-\bar t)x)^T(y-x)(t-\bar t)$$

即$g(t)\ge g(\bar t) + g'(\bar t)(t-\bar t)$，说明函数$g$是凸的

Chapter5

标准正交分解

$a_1,\cdots, a_n$是n维向量的一个标准正交基，对于任意n维向量x：

$$x=(a_1^Tx)a_1+\cdots+(a_n^Tx)a_n$$

则称其为x在标准正交基下的标准正交分解

Gram-Schmidt(正交化)算法(考了)

反复操作直到$i=n$

$$\tilde{q_i}=a_i-(q_1^Ta_i)q_1-\cdots-(q_{i-1}^Ta_i)q_{i-1}$$

$$q_i=\frac{\tilde{q_i}}{||\tilde{q_i}||_2}$$

Chapter6

主要是矩阵运算，注意定义与维度以及有时需要将矩阵拆成向量进行运算即可

Chapter7

是否存在左逆(考了)

若矩阵$A$的列向量线性无关(先看维度)，则存在左逆：

$$A^+=(A^TA)^{-1}A^T$$

使得

$$A^+A=(A^TA)^{-1}A^TA=(A^TA)^{-1}(A^TA)=I$$

是否存在右逆(考了)

若矩阵$A$的行向量线性无关(先看维度)，则存在右逆：

$$A^\dagger=A^T(AA^T)^{-1}$$

使得

$$AA^\dagger=AA^T(AA^T)^{-1}=(AA^T)^{-1}(AA^T)=I$$

是否存在逆(考了)

存在左逆(或右逆)，若矩阵为方阵，则存在逆矩阵

Chapter8

判断是否为正交矩阵(算考了)

矩阵A需满足：

$$\left. \begin{aligned} A^TA=I \\ A是方的 \end{aligned}\right \} \Rightarrow AA^T=I$$

Chapter9

QR分解(考了)

如果矩阵$A\in \R^{m\times n}$的列向量线性无关，则可以分解为一组标准正交向量$Q$与上三角矩阵$R$

$$\begin{aligned} A&=\begin{bmatrix}a_1& a_2& \cdots & a_n\end{bmatrix} \\ &=\begin{bmatrix}q_1& q_2& \cdots & q_n \end{bmatrix} \begin{bmatrix} R_{11}& R_{12}& \cdots & R_{1n} \\ 0& R_{22} & \cdots & R_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & R_{nn} \end{bmatrix} \\ &= QR \end{aligned}$$

Gram-Schmidt正交化

$$\tilde{q_i}=a_-(q_1^Ta_i)q_1-\cdots-(q_{i-1}^Ta_i)q_{i-1}$$

$$R_{ji}=(q_j^Ta_i)$$

一般要求$R_{ii}>0$使得$Q$和$R$是唯一的

使用QR分解求逆(考了)

具有线性无关列向量的矩阵$A$的伪逆为

$$A^+=(A^TA)^{-1}A^T$$

将$A$的伪逆表示为QR因子：

$$\begin{aligned} A^+&= \left( (QR)^T(QR) \right)^{-1}(QR)^T \\ &= (R^TQ^TQR)^{-1}R^TQ^T \\ &= (R^TR)^{-1}R^TQ^T \\ &= R^{-1}R^{-T}R^TQ^T \\ &= R^{-1}Q^T \end{aligned}$$

对于方阵非奇异矩阵$A$，其逆为：

$$A^{-1}=(QR)^{-1}=R^{-1}Q^T$$

矩阵$R$为上三角矩阵，设$x=R^{-1}$，使用前向回代法求解$xR=I$或使用后向回代法求解$Rx=I$

Chapter10

LU分解(可能考了，但我没用)

$L$为上三角矩阵且对角线元素全为1，$U$为上三角矩阵

$$A=LU$$

1. 矩阵$U$的第一行元素：

$$u_{1j}=a_{1j},j=1,\cdots,n$$

2. 矩阵$L$的第一列元素：

$$l_{i1}=\frac{a_{i1}}{u_{11}},i=2,3,\cdots,n$$

从$r=2$开始直到$r=n$

3. 矩阵$U$第r行主对角线以右元素$u_{rj}$

$$u_{rj}=a_{rj}-\sum_{k=1}^{r-1}l_{rk}u_{kj},j=r,\cdots,n$$

4. 矩阵$L$第r列主对角线以下元素$l_{ir}$

$$l_{ir}=\left(a_{ir}- \sum_{k=1}^{r-1} l_{ik}u_{kr} \right)/u_{rr},i=r+1,\cdots,n$$

LU分解求解方程组

例：

$$\begin{pmatrix} 2 & 10 &0 & -3 \\ -3 & -4 & -12 & 13 \\ 1 & 2 &3 & -4 \\ 4 & 14 & 9 &-13 \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \end{pmatrix}=\begin{pmatrix} 10 \\ 5 \\ -2 \\ 7 \end{pmatrix}$$

解：

对矩阵$A$进行$LU$分解：

$$A=\begin{pmatrix} 2 & 10 &0 & -3 \\ -3 & -4 & -12 & 13 \\ 1 & 2 &3 & -4 \\ 4 & 14 & 9 &-13 \end{pmatrix}$$

$$L=\begin{pmatrix} 1 & 0 & 0 & 0 \\ -\frac 3 2 & 1 & 0 & 0 \\ \frac 1 2 & -\frac 3 {11}& 1 & 0 \\ 2 &-\frac 6 {11} & -9 & 1 \end{pmatrix}, \ U = \begin{pmatrix} 2 & 10 & 0 & -3 \\ 0 & 11 & -12 & \frac {17} 2 \\ 0 & 0 & -\frac 3 {11} & -\frac 2 {11} \\ 0 & 0 & 0 & -4 \end{pmatrix}$$

前向回代法求解$y$：

$$LUx=Ly=b=\begin{pmatrix} 10 \\ 5 \\ -2 \\ 7 \end{pmatrix} \Rightarrow y=\begin{pmatrix} 10 \\ 20 \\ -\frac{17}{11} \\ -16\end{pmatrix}$$

后向回代法求解$x$：

$$Ux=y \Rightarrow x= \begin{pmatrix} 1 \\ 2 \\ 3 \\ 4 \end{pmatrix}$$

Chapter11

最小二乘法的性质(考了，跟投影一起考)

要求：

$$\hat x = \argmin_x ||Ax-b||_2^2$$

当矩阵$A$列线性无关时，有

$$A^TA\hat x=A^Tb$$

不能直接得出$\hat x = A^{-1}b$，$A$很多时候不可右逆(因为可能是高矩阵)：

$$\hat x = A^+ b = (A^TA)^{-1}A^Tb$$

QR分解求解正规方程(考了)

若矩阵$A$列向量线性无关，则最小二乘法问题的解：

$$\begin{aligned} \hat x &= (A^TA)^{-1}A^Tb \\ &= (R^TQ^TQR)^{-1} R^TQ^Tb \\ &= (R^TR)^{-1}R^TQ^Tb \\ &= R^{-1}Q^Tb \end{aligned}$$

可能会用式子$\hat x = R^{-1} Q^Tb$进行计算

流程：

• 对矩阵$A$进行QR分解

• 计算矩阵向量乘积$d=Q^Tb$

• 通过回代法求解$Rx=d$

Chapter13

KKT条件(利润最大化)(考了等式约束)

如果是max的话，式子化为$g(x)\le0$的形式，min的话式子化为$g(x)\ge0$，拉格朗日函数用减号：$-$

$$\max_{x_1,x_2}\left \{40x_1+50x_2 \right \}\\ s.t. \quad x_1+2x_2 \le 40,4x_1+3x_2\le120,x_1\ge0,x_2\ge0$$

构造$f(x)$与$g(x)$(注意$g(x)\le0$)：

$$x=\begin{bmatrix} x_1 \\ x_2 \end{bmatrix} , \max_x \left \{ f(x) = 40x_1+50x_2 \right \} \\ \begin{aligned} s.t.\quad &g_1(x)=x_1+2x_2-40\le 0, g_2(x)=4x_1+3x_2-120 \le 0, \\ & g_3(x)=-x_1 \le 0,g_4(x)=-x_2 \le 0 \end{aligned}$$

引入拉格朗日函数：

$$L(x,u)=f(x)-u_1g_1(x)-u_2g_2(x)-u_3g_3(x)-u_4g_4(x)$$

对拉格朗日函数求偏导：

$$\begin{aligned} &\nabla_xL(x,u)=\nabla_xf(x)-u_1\nabla_xg_1(x)-u_2\nabla_xg_2(x)-u_3\nabla_xg_3(x)-u_4\nabla_xg_4(x)=0,u_j\ge0 \\ &\nabla_xf(x)=\begin{bmatrix} 40 \\ 50 \end{bmatrix}, \nabla_xg_1(x)=\begin{bmatrix}1 \\ 2 \end{bmatrix}, \nabla_xg_2(x)=\begin{bmatrix}4 \\ 3 \end{bmatrix}, \nabla_xg_3(x)=\begin{bmatrix}-1 \\ 0 \end{bmatrix}, \nabla_xg_4(x)=\begin{bmatrix}0 \\ -1 \end{bmatrix} \end{aligned}$$

对x求偏导，得到KKT方程组：

$$\begin{cases} \frac{\partial L}{\partial x_1} = 40 - u_1 - 4u_2 + u_3 = 0 \\ \frac{\partial L}{\partial x_2} = 50 - 2u_1 - 3u_2 + u_4 = 0 \\ x_1+2x_2-40\le 0 \\ 4x_1+3x_2-120 \le 0 \\ -x_1 \le 0 \\-x_2 \le 0 \\ u_{j=1,2,3,4} \ge 0 \\ \sum_{j=1,2,3,4} u_jg_j(x) = 0 \end{cases}$$

综上所述，只有一种情况满足条件

$$\begin{cases}x_1=24 \\ x_2=8 \end{cases}, f(x)=40x_1+50x_2=1360 \\$$

$\therefore$最优解为$x_1=24,x_2=8$，最大利润为1360

最小范数优化问题(考了)

一般为单个$x$，否则用$y$换元，一般系数不为$\frac 1 2$，以下仅为一般形式

$$\min_x \frac 1 2||x||_2^2 \quad s.t. \quad Cx=d$$

矩阵$C$行向量线性无关，存在右逆$C^\dagger$，要求$\hat x$

引入拉格朗日函数：

$$L(x,\lambda)=\frac 1 2||x||_2^2-\lambda^T(Cx-d)$$

对拉格朗日函数求偏导得到KKT条件：

$$\begin{cases} \nabla_xL(x,\lambda)=x-C^T\lambda=0 \\ \nabla_\lambda L(x,\lambda)=Cx-d=0 \end{cases}$$

由矩阵$C$行向量线性无关可得：

$$Cx=CC^T\lambda=d,\lambda = (CC^T)^{-1}d$$

则有：

$$\hat x = C^T \lambda = C^T (CC^T)^{-1} d = C^\dagger d$$

如果要求确切值需要进行对矩阵$C^T$进行QR分解：

$$\begin{aligned} \hat x &= C^T(CC^T)^{-1}d \\ &= QR(R^TQ^TQR)^{-1}d \\ &= QR(R^TR)^{-1}d \\ &= QR^{-T}d \end{aligned}$$

回代法求解$R^Tz=d$，再计算$\hat x=Qz$