这一章开始，进入凸优化的应用。

拟合、逼近、插值

• 拟合
  
  • 一般是对于离散点
  • 用函数代替列表函数使得误差在某种意义下最小
• 插值
  
  • 一般是对于离散点
  • 用一个函数来近似代替列表函数，并要求函数通过列表函数中给定的数据点
• 逼近
  
  • 一般是对于连续函数
  • 为复杂函数寻找近似替代函数，其误差在某种度量下最小

范数逼近

基本问题$_{p_{286}}$

最简单的范数逼近问题具有以下形式的无约束问题：

$$\min ||Ax -b ||$$

向量$r = Ax-b$称为这个问题的残差，其分量称为个体残差。

很明显，范数逼近问题是一个凸问题，也就是说，至少存在一个最优解。

由线性代数的知识，当$b \in C(A)$时，最优值为0，但我们更关心其不为$A$的列空间的情况。

解释

$Ax = x_1a_1 + ... + x_n a_n$

可以看出，范数逼近问题目标是用$A$的列空间的线性组合尽可能的逼近$b$向量，其偏差由范数度量。

在几何上有更好的解释，其中，$x$可认为是向量$b$在$A$的子空间中的投影点，也就是最靠近$b$的点。

最小二乘逼近

最常见的范数逼近是$l_2$范数。其问题描述为：

$$\min ||Ax - b||^2_2 = r_1^2 + ...+r^2_m$$

其目标函数为残差平方和。我们可以将目标函数转化为凸二次函数：

$$f(x) = x^TA^TAx - 2b^TAx + b^Tb$$

可以解析的求解得到：

$$A^TAx = A^Tb$$

这个方程为正规方程，并且总是有解的。

Chebyshev逼近

当使用$l _{\infty}$范数时，逼近问题转化为：

$$\min ||Ax -b||_{\infty} = \min \max \{|r_1|,...,|r_m|\}$$

表示为极小化最大残差。可以将其描述为线性规划问题：

$$\min \quad t$$

$$s.t.\quad -t1 \preceq Ax -b \preceq t1$$

残差绝对值之和逼近

如果使用$l_1$范数，逼近问题表示为：

$$\min ||Ax -b|| = \min |r_1| + ... + |r_m|$$

这是一种鲁棒估计器。也可以表示为线性规划问题：

$$\min \quad 1^Tt$$

$$s.t.\quad -t \preceq Ax -b \preceq t$$

罚函数逼近

我们把范数扩展开来，可以考虑目标函数：

$$(|r_1|^p+ ... + |r_m|^p)^{1/p}$$

我们可以不用管外面的幂次，具体来说，可写成如下罚函数逼近问题：

$$\min \phi(r_1) + ... +\phi(r_m)$$

$$s.t. \quad r = Ax -b$$

其中，$\phi$称为罚函数，若其为凸函数，则该问题为凸优化问题。

我们可以将目标函数理解为总体惩罚：每个残差的罚函数之和。

有一些常见的罚函数$_{p_{288}}$：

• $\phi(u) = |u|^p$，为范数逼近问题
• 带有死区的线性罚函数
• 对数障碍罚函数
• Huber罚函数

对于这些罚函数的解释可以参考书上$_{p_{288}}$。

书中还考虑了野值（很大的噪声值）对用罚函数设计的影响。

最小范数问题

之前我们考虑的是范数逼近问题（在某种度量下残差最小），现在考虑范数最小问题：

$$\min ||x||$$

$$s.t. \quad Ax =b$$

该问题的解为$Ax=b$的最小范数解。

可重构为范数逼近问题，令$x_0$为任意解，$Z$的列是$A$的零空间的基：

$$\min ||x_0 + Zu||$$

几何解释

可行集$\{x |Ax = b\}$是仿射的，最小范数问题是在仿射集合中寻找距离0最近的点，即寻找0向仿射集合的投影。

线性方程组的最小二乘解$_{p_{296}}$

最常见的最小范数问题为$l_2$范数：

$$\min ||x||^2_2$$

$$s.t. \quad Ax = b$$

其唯一解称为方程$Ax= b$的最小二乘解。类似于最小二乘逼近，此问题也可以被解析的求解。我们可以使用对偶问题来解决此凸优化问题，最优性条件为：

$$2x^\star + A^Tv^\star = 0 , \quad Ax^\star = b$$

这很容易求解，不再赘述。

最小罚问题

$$\min \phi (x_1) + ... + \phi (x_n)$$

$$s.t. \quad Ax = b$$

在约束$Ax=b$下，最小罚问题找到了具有最小总惩罚的$x$。

正则化逼近

双准则式

在正则化逼近中，我们的目标是寻找向量$x$使其较小，同时使得残差较小的值。

可以描述为双目标凸向量优化问题：

$$\min (||Ax - b||,||x||)$$

注意，这两个范数可能是不同的，第一个用以度量残差的规模，第二个用于度量$x$的规模。

正则化

正则化是求解双准则问题的一个常用的标量化方法：

$$\min ||Ax -b || + \gamma||x||$$

其中$\gamma> 0$为问题参数。

Tikhonov正则化$_{p_{298}}$

最常见的正则化基于上式并利用Euclid范数，得到一个凸二次优化问题（也称为领回归）：

$$\min ||Ax-b||^2_2 + \delta||x||^2_2 = x^T(A^TA+\delta I)x -2b^TAx + b^Tb$$

这个正则化有解析解：

$$x = (A^TA+\delta I)^{-1} A^Tb$$

鲁棒逼近

随机鲁棒逼近

当矩阵数据$A$允许不确定和可能的变化时，记起均值为$\bar{A}$，$U$为均值为0的随机矩阵，则可以将$A$表示为：

$$A = \bar{A}+U$$

自然的，可以用$||Ax-b||$的期望来作为目标函数：

$$\min E||Ax-b||$$

这种问题被称为随机鲁棒逼近问题。虽然是凸优化，但并不好解。

若$A$仅有有限个可能值（离散点）时，即$P(A = A_i) = p_i$，则问题可以写为：

$$\min p_i||A_1x-b|| + ... + p_k ||A_kx-b||$$

这被称为范数和问题。可以表述为：

$$\min \quad p^Tt$$

$$s.t. \quad ||A_ix -b|| \le t_i$$

可见，若为$l_2$范数，则范数和问题是一个二阶锥规划。

鲁棒最小二乘问题

$$\min E||Ax-b||^2_2$$

由于$A = \bar{A}+ U$，则可以将目标函数改写为：

$$\begin{align}E||Ax-b||^2_2 &= E(\bar{A}x -b +Ux)^T(\bar{A}x-b+Ux) \\&= (\bar{A}x -b)^T(\bar{A}x -b) + E(x^TU^TUx) \\&= ||\bar{A}x -b||^2_2 + x^TPx \end{align}$$

其中$P=E(U^TU)$。因此，可以将该问题化为正则化最小二乘形式：

$$\min ||\bar{A}x-b||^2_2 + ||P^{1/2}x||^2_2$$

不难通过求导可以得到解为：

$$x= (\bar{A}^T\bar{A}+P)^{-1}\bar{A}^Tb$$

最坏鲁棒逼近

我们用$A$的可能值集合$\chi$描述其不确定性，我们定义候选的逼近解$x$的最坏误差为：

$$e_{wc}(x) = \sup\{||Ax-b|| |A\in \chi \}$$

最坏情况鲁棒逼近问题是极小化最差情况的误差：

$$\min \quad e_{wc}(x)$$