最优化：建模、算法与理论

目前在学习 最优化：建模、算法与理论这本书，来此记录一下，顺便做一些笔记，在其中我也会加一些自己的理解，尽量写的不会那么的条条框框（当然最基础的还是要有）

第三章 优化建模

本章将从常用的建模技巧开始，接着介绍统计学、信号处理、图像处理以及机器学习中常见的优化模型，我们会侧重于解释优化建模背后的思想和实际含义。

3.1 建模技术

3.1.1 目标函数的设计

1. 最小二乘法

最小二乘法，依我之见，应该很少有初学者来直接学习这本书，所以这个东西大家应该已经司空见惯了。
设${\varphi }_i(x):R^n\to R,i=1,2,\cdots ,m$为$n$元函数，且有如下方程组
$$b_i={\varphi }_i(x),i=1,2,\cdots ,m\text{\hspace{1em}(3.1.1)}$$
其中$b_i$是已知的实数，我们知道，这个问题并不总是可解的，首先，如果方程组的个数$m$超过自变量个数$n$，因此方程组的解可能不存在，其次，由于测量误差等因素，方程组的等式关系可能不是精确成立的，为了能实际情况下求解，最小二乘法的思想是极小化误差的$l_2$范数平方，即
$$\underset{x\in R^n}{\min }\sum _{i=1}^m(b_i-{\varphi }_i(x){)}^2\text{\hspace{1em}(3.1.2)}$$
如果${\varphi }_i(x)$为线性函数，那么就称之为线性最小二乘，否则称为非线性最小二乘
最小二乘的思想很直观的，如果方程（3.1.1）存在解，则求解问题（3.1.2）的全局最优解为0，就相当于求出了方程的解，如果方程的解不存在的话，问题（3.1.2）给出了某种程度上误差最小的解。

最小二乘法使用了$l_2$范数来度量误差大小，其主要优点有两个
（1）$l_2$范数平方是光滑可微的，它会给目标函数带来较好的性质
（2）$l_2$范数对于某种误差的处理有最优性，后续会给出解答

当然，最小二乘并不总是最合理的，No free lunch theorem，根据实际问题，我们还经常建立最小一乘模型以及最大最小模型，其思想是使用不同的范数代替$l_2$范数，如果要保证偏差和绝对值之和最小回归，相应的模型为：
$$\underset{x\in R^n}{\min }\sum _{i=1}^m|b_i-{\varphi }_i(x)|\text{\hspace{1em}(3.1.3)}$$
如果要最小化最大偏差，其对应的优化模型为：
$$\underset{x\in R^n}{\min }\underset{i}{\max }|b_i-{\varphi }_i(x)|\text{\hspace{1em}(3.1.4)}$$

2. 正则化

在建模时，我们往往需要借助于想要得到的解的性质，例如当最优解不止一个的时候，并不一定所有的解都是我们想要的，为了让解具有光滑性以及克服问题的病态性质，亦或者为了解决过拟合的问题（更具光滑性实际上就是变相解决过拟合），那么改进的模型为
$$\underset{x\in R^n}{\min }\sum _{i=1}^m(b_i-{\varphi }_i(x){)}^2+\mu ||x|{|}_2^2\text{\hspace{1em}(3.1.5)}$$
其中$\mu >0$是个平衡参数，如果想要得到一个稀疏的解，可以借助$l_0$范数构造如下模型($l_0$范数定义为向量中非零元素的个数)
$$\underset{x\in R^n}{\min }\sum _{i=1}^m(b_i-{\varphi }_i(x){)}^2+\mu ||x|{|}_0\text{\hspace{1em}(3.1.6)}$$
其中$\mu >0$用来控制解的稀疏度，但由于$l_0$范数在实际中难以处理，我们往往使用$l_1$范数来保证稀疏性，模型如下
$$\underset{x\in R^n}{\min }\sum _{i=1}^m(b_i-{\varphi }_i(x){)}^2+\mu ||x|{|}_1\text{\hspace{1em}(3.1.7)}$$

在图像处理中，$x$本身可能不是稀疏的，但是其在变换域中是稀疏的，相应的模型为
$$\underset{x\in R^n}{\min }\sum _{i=1}^m(b_i-{\varphi }_i(x){)}^2+\mu ||W(x)|{|}_0\text{\hspace{1em}(3.1.8)}$$
以及
$$\underset{x\in R^n}{\min }\sum _{i=1}^m(b_i-{\varphi }_i(x){)}^2+\mu ||W(x)|{|}_1\text{\hspace{1em}(3.1.9)}$$
其中$W:R^n\to R^p$表示某种变换，常用的有全变差以及小波变换

正则项在目标函数的意义是很明显的，我们要同时满足误差尽量小以及它的系数相对来说不能太大，如果系数太大那么他的正则项惩罚就会很高，而当所有的系数都减少下来，那么模型自然而然也就平滑了。

3.最大似然估计

在实际问题中有许多数据来自未知的分布，从数据反推分布的具体形式是非常虫咬的，最大似然估计就是统计中常用的一种估计概率分布的方法，且通过最大似然函数，使得观测数据尽可能地服从假定的模型。

这里我们考虑一种简单的情况，假设已经知道数据来自某种特定的分布，但不知道分布具体的参数，为了方便起见，令$p(a;x)$是其分布律或概率密度函数，其中$x$是未知参数，为了估计$x$，我们选取一列独立同分布的样本点$a_1,a_2,\cdots ,a_n$，似然函数定义为在参数$x$下，数据集{$a_i,i=1,2,\cdots ,n$}发生的概率，即
$$L(x)=\prod _{i=1}^{n}p(a_i;x)$$
$L(x)$实际上就是这$n$个点的联合概率（联合密度），但此时自变变为了参数$x$
那么现在就很明显了，参数的最大似然估计定义为
$$\hat{x}\in \underset{x\in \chi }{\mathrm{argmax}}L(x)$$
其实就是求能让$L(x)$最大的那个x，就是通过参数$x$让发生这件事情的概率最大
其中$\chi$为参数空间，假设最大似然估计存在，则求解最大似然估计本质上是在一族分布中找寻最有可能产生该样本的参数（跟我上面说的差不多），实际中，似然函数的对数的最大值更容易求解，即考虑最大化问题
$$\underset{x\in \chi }{\max }l(x)=\ln L(x)\text{\hspace{1em}(3.1.10)}$$
因为$ln(x)$是严格单调递增的，实际计算中我觉得最大的原因可能是因为相乘可以转化成相加，更容易操作

4.代价、损失、收益函数

运筹学中的很多问题就算极小化代价（损失）并极大化收益的过程，比如，我们在玩游戏的时候，每走一步都会有相应的分数奖励，我们期望自然是最后的得分越高越好，旅游时，我们希望在游览所有城市的情况下路径最短或者差旅费最少，在超市物品定价的时候，我们一般会根据价格与其对应可能的销售数，来确定一个最大利益的定价，在这些实际问题中，都可以写成优化问题的形式，其目标函数或者是最小化损失，或者是最大化收益，亦或者二者兼顾（风险最小，收益最大）

5.泛函，变分

物理、化学中很多问题都可以表述成能量极小化的形式，比如，在电子结构计算中，我们通过极小化原子和电子之间的相互作用能量来计算稳定态，一般来说，能量泛函是定义在函数空间上的，即相应优化问题的自变量是无穷维空间中的函数，我们可以通过变分来得到其相应的最优性条件等，实际中常用的另一种办法，是利用合适的离散化，将能量泛函的极小化问题从无穷维空间中拉回到有限空间中，从而得到相应问题的离散解，注意，不同的离散化一般对应于不同的目标函数以及不同的优化问题。
PS：这一块我也还没学，不太能深入理解

6.松弛问题

当原始问题不容易求解时，优化中一个常用的技巧是松弛，这一技巧的基本思想是：在保留原问题部分性质的条件下，使用简单的项替代目标函数中难以处理的项，进而使得问题更容易求解。例如，$l_0$范数是不可微且非凸的，由于$l_1$范数是$l_0$范数在某种程度上的近似，实际中往往用$l_1$范数代替$l_0$范数，因为$l_1$范数是凸 的，其相应模型的理论分析以及算法设计会更简单。
对于低秩优化问题，秩对应矩阵奇异值中非零元的个数，其也是非凸且不可微的，常用方式是将其用矩阵的核范数（矩阵奇异值组成的向量的$l_1$范数）代替，得到一个更容易处理的凸松弛项

另一种松弛的策略是例如处理一个$minf(x)$问题，使用目标函数的一个下界$f_R(x)$来替换$f(x)$进行求解，其中$f_R(x)$应该满足：
（1）$f_R(x)\le f(x),\forall x\in \chi$
（2）$f_R(x)$具有简单结构
后续介绍的拉格朗日函数，实际上就可以看成是原问题目标函数的松弛
需要注意的是，松弛之后的问题未必与原问题等价，之前我们反复提到$l_0$范数可替换为$l_1$范数均是在一定条件下进行的，$l_2$范数一般不能作为$l_0$范数的松弛

3.1.2 约束的设计

1. 问题本身的物理性质

根据问题的实际意义，优化问题的决策变量需要满足各种各样的约束，比如，在电子结构设计中，我们假设轨道函数之间是相互正交的；还例如在飞机机翼的设计中，受机翼周围的气流影响，机翼形状的改变对应于一个微分方程，很多情况下还有非负约束。当线性或者一般的等式观测带有噪声或者需要更多的鲁棒性时，我们也将等时约束放宽为不等式约束。

2.等价代换

对于一个优化问题，如果目标函数是复合函数的形式，如：
$$\underset{x}{\min }f(Ax+b)$$
我们经常引入变量$y$和等式约束$y=Ax+b$而考虑带约束的等价问题就变为：
$$\underset{x}{\min }f(y)s.t.y=Ax+b$$
对于优化问题${\min }_{x}f(x)=h(x)+r(x)$，我们往往引入$y$以及约束$x=y$,将其转化为
$$\underset{x}{\min }h(x)+r(y)s.t.x=y$$
通过这种方式，将目标函数进行拆分，对于不等式约束，我们也可以通过引入松弛变量将其转变为等式约束和简单的非负或非正约束，例如考虑约束$c(x)\le 0$，引入$y\ge 0$，可将其等价转化为
$$c(x)+y=0,y\ge 0$$
另外，我们还可以利用上方图来得到问题的等价形式，对于优化问题${\min }_{x}f(x)$，根据上方图的定义，可知等价于优化问题
$$\underset{x,t}{\min }t,s.t.f(x)\le t$$
将优化问题的约束进行等价的转换有助于我们进行更方便的研究该问题的数学性质，等价转化后可能许多问题都会变成同一类型的问题，然后我们就可以找到统一的算法或模型去求解。

3.松弛

当原始优化模型的约束过于复杂时，我们同样可以采用松弛的技巧将难处理的约束替换为容易处理的约束。松弛后的问题的可行域会比原始问题大，例如可以用盒约束$x\in [0,1]$来代替整数约束 x ∈ { 0 , 1 } x{\in}\{0,1\} x∈{0,1}，或使用不等式约束$c(x)\ge 0$来代替等式约束$c(x)=0$
放大可行域要遵守两点基本原则：
（1）将原有约束进行简化，即松弛后的问题一定要更容易处理，要不然松弛的干嘛
（2）也别将可行域放的过大了，过分放大可行域会丢失原问题的关键信息，进行求解就没有意义了

有一个很自然的问题，松弛问题的解和原问题的解存在什么联系？一般情况下，松弛问题和原问题不等价，但在一定条件下可以证明松弛问题的解就是原问题的解。

3.2 回归分析

3.2.1 概述

一般的回归模型可以写成如下形式
$$b=f(a)+ϵ\text{\hspace{1em}(3.2.1)}$$
其中$a\in R^d$为自变量，$b\in R$为响应变量，$ϵ\in R$是模型的误差（噪声）。在实际问题中，我们一般只知道$a$和$b$的观测值，而误差是未知的，建立回归模型是利用$m$个观测值($a_i,b_i$)求出$f$的具体形式，然后通过新观测的自变量对响应变量做出预测。

如何选取$f$是很重要的，诚然，我们当然可以做到一个模型让$f(a_i)=b_i$各个都正确，但这样如果$f$十分复杂的话，泛化能力会比较差，这就过拟合了。当然也不能差太多，一个好的模型需要兼顾两方面，在观测的数据上有较小的误差，同时又有简单的形式。

3.2.2 线性回归模型

设$(x_i,y_i),i=1,2,\cdots ,m$为观测到的自变量和响应变量，且不同数据点相互独立，则对每个数据点（书里的自变量和响应变量老是写成a,b,w等形式，让我看的难受，我按照自己之前的习惯写了）这里非常数项系数弄成$n-1$个是为了方便加上常数项后，总共为$n$个好看一点
$$y=w_1{x}_{i1}+w_2{x}_{i2}+\cdots +w_{n-1}{x}_{in-1}+b+ϵ,i=1,2,\cdots ,m$$
其中$w_i$是需要确定的参数，输入特征加上常数项$x_i=(x_{i}1{)}^T$，令$w=(w_1,w_2,\cdots ,w_{n-1},b{)}^T\in R^n$，则线性回归的模型可以写成
$$y_i=w^T{x}_i+{ϵ}_i\text{\hspace{1em}(3.2.2)}$$
如果要写成矩阵形式呢，我们设
$$X=\left[\begin{array}{c}{x}_1^T\\ x_2^T\\ x_3^T\\ ⋮\\ x_m^T\end{array}\right]$$
$$y=\left[\begin{array}{c}{y}_1\\ y_2\\ y_3\\ ⋮\\ y_m\end{array}\right]$$
$$ϵ=\left[\begin{array}{c}{ϵ}_1\\ {ϵ}_2\\ {ϵ}_3\\ ⋮\\ {ϵ}_m\end{array}\right]$$
(目前我不知道如何把他们并在一起，抱歉)
$X$是$m\ast n$的矩阵，$y和ϵ$是$m\ast 1$，$w$是$n\ast 1$则得到矩阵形式
$$y=Xw+ϵ\text{\hspace{1em}(3.2.3)}$$
现在我们要考虑如何求解这个线性回归模式，我们这里就不想当然的去说让误差最小什么的，我们用最大似然来做，更有数学原理一点

假设${ϵ}_i$是高斯白噪声，即${ϵ}_i\sim N（0，{\sigma }^2）$，那么根据${ϵ}_i=y_i-w^T{x}_i$，我们有
$$p({ϵ}_i)=p(y_i|x_i;w)=\frac{1}{\sqrt{2\pi {\sigma }^2}}exp(-\frac{(y_i-w^T{x}_i{)}^2}{2{\sigma }^2})$$
其对数似然函数为
$$l(x)=ln\prod _{i=1}^{m}p(y_i|x_i;w)=-\frac{m}{2}ln(2\pi )-mln\sigma -\sum _{i=1}^m\frac{(y_i-w^T{x}_i{)}^2}{2{\sigma }^2}$$
最大似然估计就是极大化似然函数嘛，去掉常数项后我们得到了如下最小二乘问题
$$\underset{x\in R^n}{\min }\frac{1}{2}||Ax-b|{|}_2^2$$
注意，在构建最大似然估计的时候并不需要知道${ϵ}_i$的方差
以上最重要的就是建立了求解回归模型和最小二乘法的联系，当假设误差是高斯白噪声时，你求解最小二乘解就是线性回归模型的解
当然如果${ϵ}_i$不是服从高斯白噪声的话，求解线性回归模型的解就不是最小二乘模型的解了，可能在某些噪声下他是最小一乘问题的解等等，不知道这样说大家能否清楚明了