最优化：建模、算法与理论（典型优化问题

第四章 典型优化问题

4.1 线性规划

4.1.1 基本形式和应用背景

再次说明一下，其实这本书很多的内容之前肯定大家都学过，但是我觉得这本书和我们之前学的东西的出发角度不一样，他更偏向数学，也多一个角度让我们去理解

线性规划问题的一般形式如下：
$$\begin{gathered} \underset{x\in R^n}{\min }{c}^{T}x \\ s.t.Ax=b \\ Gx\le e\text{\hspace{1em}(4.1.1)} \end{gathered}$$
其中$c\in R^n,A\in R^{m\times n},b\in R^m,G\in R^{p\times n},e\in R^p$是给定的矩阵和向量，$x\in R^n$是决策变量，在实际中，我们考虑问题（4.1.1）的两种特殊形式（其他形式都可以转化为这两种形式），标准型（等式约束和决策变量非负）：
$$\begin{gathered} \underset{x\in R^n}{\min }{c}^{T}x, \\ s.t.Ax=b, \\ x\ge 0,\text{\hspace{1em}(4.1.2)} \end{gathered}$$
以及不等式型（没有等式约束）：
$$\begin{gathered} \underset{x\in R^n}{\min }{c}^{T}x \\ s.t.Ax\le b\text{\hspace{1em}(4.1.3)} \end{gathered}$$
线性规划最先在第二次世界大战时被提出（了解一下也蛮有意思的哈哈）

4.1.2 应用举例

1.运输问题

有$I$个港口$P_1,P_2,\cdots ,P_I$提供某种商品，有$J$个市场$M_1,M_2,\cdots ,M_J$需要这种商品，假设港口$P_i$有$s_i$单位的这种商品，市场$M_j$需要$r_j$单位的这种商品，且总供应和总需求相等，即${\sum }_{i=1}^I{s}_i={\sum }_{j=1}^J{r}_j$，令$b_{ij}$为从港口$P_i$运输单位数量商品到市场$M_j$的成本，运输问题是在满足市场需求下使得运输成本最低
令$x_{i}j$为从港口$P_i$运输到市场$M_j$的商品数量，总运输代价为
$$\sum _{i=1}^I\sum _{j=1}^J{x}_{ij}{b}_{ij}\text{\hspace{1em}(4.1.4)}$$
港口$P_i$总输出量为${\sum }_{j=1}^J{x}_{ij}$，因为港口$P_i$存有的商品总量为$s_i$，所以
$$\sum _{j=1}^J{x}_{ij}=s_i,i=1,2,\cdots ,I\text{\hspace{1em}(4.1.5)}$$
市场$M_j$总输入量为${\sum }_{i=1}^I{x}_{ij}$，因为市场$M_j$的需求量为$r_j$，所以
$$\sum _{i=1}^I{x}_{ij}=r_j,j=1,2,\cdots ,J\text{\hspace{1em}(4.1.6)}$$
因为运输是非负的，所以
$$x_{ij}\ge 0,i=1,2,\cdots ,I,j=1,2,\cdots ,J\text{\hspace{1em}(4.1.7)}$$
所以我们只需要极小化总运输代价和满足约束条件就好了，整理一下就是
$$\begin{gathered} \underset{x}{\min }\sum _{i=1}^I\sum _{j=1}^J{x}_{ij}{b}_{ij} \\ s.t.\sum _{j=1}^J{x}_{ij}=s_i,i=1,2,\cdots ,I \\ \sum _{i=1}^I{x}_{ij}=r_j,j=1,2,\cdots ,J \\ {x}_{ij}\ge 0,i=1,2,\cdots ,I,j=1,2,\cdots ,J \end{gathered}$$
这个问题还有更一般的版本，即最优运输问题，它是关心两个（离散、连续）测度的对应关系，也就是距离嘛，这个具体问题具体分析把，大差不差的

2.马尔可夫决策过程

在马尔可夫决策过程中，考虑终止时间$T=\infty$的情形，因为折现因子$0<\gamma <1$，所以如果单步奖励是有界的，则策略对应的奖励和是有界的，否则，如果奖励和无界，任何一个策略的奖励和都可以是无限的，就失去了研究价值。$Bellman$方程（3.13.2）可以转化为如下线性规划模型
$$\begin{gathered} \underset{V\in R^{|S|}}{\max }\sum _{i}V(i) \\ s.t.V(i)\ge \sum _j{P}_a(i,j)(r(i,a)+\gamma V(j)),\forall i\in S,\forall a\in A \end{gathered}$$
其中$V(i)$是向量$V$的第$i$个向量，表示从状态$i$出发得到的累计奖励。这个意思我看的就是，从i出发，选择一个策略，让从$i$出来到所有的$j$的奖励和最大（为什么不是到奖励最大的$j$最大我到现在也没有想明白）

3.基追踪问题

基追踪问题是压缩感知的一个基本问题，可以为写
$$\begin{gathered} \underset{x\in R^n}{\min }||x|{|}_1, \\ s.t.Ax=b\text{\hspace{1em}(4.1.8)} \end{gathered}$$
对每个$|x_i|$引入一个新的变量$z_i$，可以将问题（4.1.8）转化为
$$\begin{gathered} \underset{z\in R^n}{\min }\sum _{i=1}^n{z}_i, \\ s.t.Ax=b, \\ -z_i\le x_i\le z_i,i=1,2,\cdots ,n \end{gathered}$$
这是一个线性规划问题，另外，我们也可以引入$x_i$的正部和负部$x_i^{+},x_i^{-}\ge 0$，利用$x_i=x_i^{+}-x_i^{-},|x_i|=x_i^{+}+x_i^{-}$，（这里我搜了一下不知道实数的正部负部什么意思，我觉得是不是如果$x_i$为正，$x_i^{+}=x_i,x_i^{-}=0$，反之亦然）问题（4.1.8）的另外一种等价的线性规划形式可以写成
$$\begin{gathered} \underset{x^{+},x^{-}\in R^n}{\min }\sum _{i=1}^n(x_i^{+}+x_i^{-}), \\ s.t.A{x}^{+}-A{x}^{-}=b, \\ {x}_{+},x_{-}\ge 0 \end{gathered}$$

4.数据拟合

在数据拟合中，除了常用的最小二乘模型外，还有最小$l_1$范数模型
$$\underset{x\in R^n}{\min }||Ax-b|{|}_1\text{\hspace{1em}(4.1.9)}$$
和最小$l_{\infty }$范数模型
$$\underset{x\in R^n}{\min }||Ax-b|{|}_{\infty }\text{\hspace{1em}(4.1.10)}$$
这两个问题都可以转化为线性规划的形式，通过引入变量$y=Ax-b$，可以得到如下等价问题
$$\begin{gathered} \underset{x,y\in R^n}{\min }||y|{|}_1, \\ s.t.y=Ax-b \end{gathered}$$
利用基追踪的类似的技巧，可以转化为线性规划问题。
对于问题4.1.10，令$t=||Ax-b|{|}_{\infty }$，则得到等价问题
$$\begin{gathered} \underset{x\in R^n,t\in R}{\min }t, \\ s.t.||Ax-b||\le t \end{gathered}$$

4.2 最小二乘问题

4.2.1 基本形式和应用背景

最小二乘问题的一般形式如下
$$\underset{x\in R^n}{\min }\sum _{i=1}^m{r}_i^2(x),\text{\hspace{1em}(4.2.1)}$$
其中$r_i:R^n\to R$为实值函数，如果所有的$r_i$都是线性函数，我们称问题(4.2.1)为线性最小二乘为，否则称其为非线性最小二乘问题，最小二乘问题是线性回归和非线性回归的基础
最小二乘问题也常用于线性（非线性）方程组问题中（见第三章最小二乘建模），当线性（非线性）观测带有噪声时，我们一般会基于该线性（非线性）系统建议最小二乘模型，特别的，如果噪声服从高斯分布，最小二乘问题的解对应原问题的极大似然解

4.2.2 应用举例

1.线性最小二乘问题

线性最小二乘问题是回归分析中的一个基本模型，它可以表示为
$$\underset{x\in R^n}{\min }\sum _{i=1}^m(a_i^{T}x-b)$$

记$A=[a_1,a_2,\cdots ,a_m{]}^T$,那么线性最小二乘问题可以等价于如下形式：
$$\underset{x\in R^n}{\min }f(x)=\frac{1}{2}||Ax-b|{|}_2^2$$
这是一个无约束二次目标函数的优化问题，因为二次函数是凸的，所以$x\in R^n$为其全局最小解当且仅当$x$满足方程
$$\nabla f(x)=A^T(Ax-b)=0$$
因为$f$是二次的，我们有
$$\begin{gathered} f(y)=f(x)+\nabla f(x{)}^T(y-x)+\frac{1}{2}(y-x{)}^T{\nabla }^{2}f(x)(y-x) \\ =f(y)=f(x)+\nabla f(x{)}^T(y-x)+\frac{1}{2}(y-x{)}^T{A}^{T}A(y-x) \end{gathered}$$
因此，如果$\nabla f(x)=0$根据$A^{T}A$的正定性
$$f(y)\ge f(x),\forall y\in R^n$$
即$x$为$f(x)$的全局最小解

反之，如果$\nabla f(x)\ne 0$，此时我们说明沿着负梯度方向目标函数将减小。

具体的，取$y=x-t\nabla f(x)$，且$t=\frac{1}{{\lambda }_{max}(A^{T}A)}$,其中${\lambda }_{max}{A}^{T}A$表示$A^{T}A$的最大特征值
PS：这里有些奇怪的是$A^{T}A$明明是一个实数，那他的最大特征就是他自己了？感觉有点多此一举
将$y$代入那么
$$\begin{gathered} f(x-t\nabla f(x))=f(x)-t||\nabla f(x)|{|}_2^2+\frac{1}{2}{t}^2{\lambda }_{max}(A^{T}A)||\nabla f(x)|{|}_2^2 \\ =f(x)+(-t+\frac{1}{2}{t}^2{\lambda }_{max}(A^{T}A))||\nabla f(x)|{|}_2^2 \\ =f(x)-\frac{1}{2{\lambda }_{max}(A^{T}A)}||\nabla f(x)|{|}_2^2<f(x) \end{gathered}$$
因此在全局最小解$x$处必有$\nabla f(x)=0$

2.数据插值

数据插值是数值分析的一个基本问题，给定数据集 { a i ∈ R p , b i ∈ R q } , i = 1 , 2 , ⋯   , m \{a_i{\in}R^p,b_i{\in}R^q\},i=1,2,\cdots,m {ai​∈Rp,bi​∈Rq},i=1,2,⋯,m插值是求一个映射$f$，使得
$$b_i=f(a_i),i=1,2,\cdots ,m$$
(怎么感觉有点像拟合）
在实际中，出于计算上的可行性，我们一般会限制在一个特定函数空间上来求$f$的一个近似解，如果利用线性函数逼近，则$f(a)=Xa+y$，其中$X\in R^{q\times p},y\in R^q$，为了求解$X,y$，可以建立如下最小二乘问题
$$\underset{X\in R^{q\times p}}{\min }\sum _{i=1}^m||X{a}_i+y-b_i|{|}^2$$
一般的，假设 { ϕ i ( a ) } i = 1 n ( n ≤ m ) \{{\phi}_i(a)\}_{i=1}^n(n{\le}m) {ϕi​(a)}i=1n​(n≤m)的为插值空间的一组基，数据插值问题可以写成
$$b_j=f(a_j)=\sum _{i=1}^n{x}_i{\varphi }_i(a_j),j=1,2,\cdots ,m$$
其中$x_i$为待定系数，这是关于$x$的线性方程组，在实际中，我们考虑其替代的最小二乘模型
$$\underset{x\in R}{\min }\sum _{j=1}^m||\sum _{i=1}^n{x}_i{\varphi }_i(a_j)-b_j|{|}^2$$
对于基${\varphi }_i(a)$的选取，一般要求其反应数据的物理性质或者内在性质以及计算比较方便

除了这种基函数的和的方式，深度学习也通过一些简单函数的复合来逼近原未知函数，具体地，假设有一些简单的非线性向量函数${\varphi }_i(\theta ):R^q\to R^q$,并构造如下复合函数
$$f(\theta )={\varphi }_n(X_n{\varphi }_{n-1}(X_{n-1}\cdots {\varphi }_1(X_1\theta +y_1)\cdots +y_{n-1})+y_n)$$
在实际中常用的简单非线性函数有$ReLU$，即
$${\varphi }_i(\theta )=(ReLU({\theta }_1),ReLU({\theta }_2),\cdots ,ReLU({\theta }_q){)}^T,i=1,2,\cdots ,n$$

这样的做法往往会带来更多未知的非线性，因而可能在更大的函数空间中得到未知函数的一个很好的逼近，将点$a_i$处的取值代入，我们得到如下非线性方程组
$$f(a_i)-b_i={\varphi }_n(X_n{\varphi }_{n-1}(X_{n-1}\cdots {\varphi }_1(X_1{a}_i+y_1)\cdots +y_{n-1})+y_n)-b_i=0$$
这里需要求得的是关于$X_1\in R^{q\times p}，X_i\in R^{q\times q},i=2,3,\cdots ,n,y_i\in R^q,i=1,2,\cdots ,n$的非线性方程组，我们一般考虑替代的最小二乘问题
min ⁡ { X i , y i } ∑ i = 1 m ∣ ∣ f ( a i ) − b i ∣ ∣ 2 \min_{\{X_i,y_i\}}\sum_{i=1}^m||f(a_i)-b_i||^2 {Xi​,yi​}min​i=1∑m​∣∣f(ai​)−bi​∣∣2

3.深度Q学习

在强化学习中，为了求解出最优策略及相应的期望奖励，往往需要考虑动作价值函数(action-value function)$Q:S\times A\to R$，注意，我们一般称$V$为价值函数即value function，其表示从状态$s$出发，采取动作$a$可以获得的最大期望奖励，根据最优性，其$Bellman$方程为
$$Q(s,a)=r(s,a)+\gamma \sum _{s^{\prime }}{P}_a(s,s^{\prime })\underset{a^{\prime }}{\max }Q(s^{\prime },a^{\prime })\text{\hspace{1em}(4.2.2)}$$
这个应该很好懂把，就是在状态$s$下做$a$得到的最大期望奖励等于直接得到的reward再加上做了$a$，到达环境$s^{\prime }$后，在$s^{\prime }$处做最优的$a^{\prime }$得到的奖励
对于求解方程（4.2.2），一个常用的迭代算法的格式为
$$Q_{k+1}(s,a)=r(s,a)+\gamma \sum _{s^{\prime }}{P}_a(s,s^{\prime })\underset{a^{\prime }}{\max }{Q}_k(s^{\prime },a^{\prime })\text{\hspace{1em}(4.2.3)}$$
同样的，每一轮更新都需要对所有状态动作对$(s,a)$做一次迭代

然而在实际问题中，我们通常没有模型信息，也就是说，上次涉及的奖励和状态转移都是未知的，为此，我们必须与环境不断进行交互，获取经验来估计这些项的大小，在与环境的交互中，我们可以得到很多形如$(s_t,a_t,r_t,s_{t+1})$的四元组，它记录了智能体在时刻$t$处于状态$s_t$时，选择某个动作$a_t$转移至状态$s_{t+1}$，同时获得奖励$r_t$，算法可以根据这一的小段进行迭代更新
$$Q_{k+1}(s_t,a_t)=(1-\alpha )Q_k(s_t,a_t)+\alpha (r_t+\gamma \underset{a^{\prime }}{\max }{Q}_k(s_{t+1},a^{\prime }))$$
每次迭代更新呢，加法左边是表示上一次的Q表信息，我们迭代更新是一点点迭代的，不能丢掉上次的Q表信息，右边是对(4.2.3)式右端期望值的一个采样，就是通过我们的采样信息，得到$(r_t+\gamma {\max }_{a^{\prime }}{Q}_k(s_{t+1},a^{\prime }))$，然后通过这个跟上一次的Q表一起来更新我们的Q表。为什么要有上次的信息呢？直接用第二项更新不行吗？不行的，因为你智能体每次可能做相同的动作，但到达的$s^{\prime }$和$r_t$都有可能不一样，所以需要这样迭代更新，才能运用到所有的数据。
为了方便计算，我们不会等到所有数据生成后再计算平均值，而是利用凸组合的方式持续不断的将新的计算结果按一定权重加到原有数据上。这是强化学习中的一种常用均值计算技巧。

在实际应用场景中，状态空间非常大，甚至是连续的，当计算所有状态和动作对应的动作价值函数时，会非常难，无论从存储量还是计算量来说。为了解决这个问题，我们引入“归纳”的概念，简单来说，我们只需要学习状态集合中的一部分状态动作的价值函数，然后通过这些动作价值函数去归纳附近其他类似状态的动作价值函数。
这样，只需要学习一部分状态上的动作价值函数，就可以得到整个空间中动作价值函数的估计。
实现归纳这一想法的基本途径是函数近似，我们用$Q_{\theta }(s,a)$来近似动作价值函数，它带有参数$\theta \in R^d$。当参数$\theta$固定时，它就是一个关于状态$s$和动作$a$的二元函数。$Q_{\theta }(s,a)$有很多不同的形式，它可以是最简单的线性函数，也可以是复杂的神经网络（深度Q学习）。其权重矩阵和偏差项作为这里的参数$\theta$。在带函数近似的Q学习方法中，我们不再对动作价值函数列表进行学习，而是学习参数$\theta$，使得近似函数$Q_{\theta }(s,a)$尽可能满足最优$Bellman$方程，参数$\theta$的维数通常要比状态的个数小得多，改变参数中的一个维度，会对动作价值函数估计产生大范围的影响，会做动作价值函数估计产生大范围的影响，由于引入了近似处理，$Q_{\theta }(s,a)$通常不会和真实动作价值函数完全相等，严格来讲，我们希望最小化平方损失，即
$$\underset{\theta }{\min }L(\theta )=E_{(s,a)\sim p(s,a)}[(y_{\theta }(s,a)-Q_{\theta }(s,a){)}^2]\text{\hspace{1em}(4.2.4)}$$
其中$p(s,a)$是状态动作对$(s,a)$出现的概率分布
$$y_{\theta }(s,a)=r(s,a)+\gamma \sum _{s^{\prime }}{P}_a(s,s^{\prime })\underset{a^{\prime }}{\max }{Q}_{\theta }(s^{\prime },a^{\prime })$$
是近似函数希望逼近的目标，问题4.2.4实际上就是在极小化方程4.2.2的残差。但在实际应用中，由于4.2.4比较复杂，深度Q学习采用迭代方式求解，在迭代的第$i$步近似求解如下优化问题
$$\underset{\theta }{\min }{L}_i(\theta )=E_{(s,a)\sim p(s,a)}[(y_i(s,a)-Q_{\theta }(s,a){)}^2]\text{\hspace{1em}(4.2.5)}$$
其中
$$y_i=r(s,a)+\gamma \sum _{s^{\prime }}{P}_a(s,s^{\prime })\underset{a^{\prime }}{\max }{Q}_{{\theta }_{i-1}}(s^{\prime },a^{\prime })$$
参数${\theta }_{i-1}$来自上一步迭代的估计，和问题（4.2.4）不同，$y_i$与待优化的变量$\theta$无关，因此可以认为问题（4.2.5）是随机版本的最小二乘问题。

4.带有微分方程约束优化问题

当约束中含有微分方程时，我们称相应的优化问题为带微分方程约束的优化问题，它在最优控制、形状优化等各种领域中有着广泛应用。这里，我们以瓦斯油催化裂解为例。这个问题求解瓦斯油催化裂解生成气体和其他副产物的反应系数，反应可以由如下非线性常微分方程组表示：
$$\{\begin{array}{c}\dot{y_1}=-({\theta }_1+{\theta }_3)y_1^2\\ {\dot{y}}_2={\theta }_1{y}_1^2-{\theta }_2{y}_2,\end{array}\text{\hspace{1em}(4.2.6)}$$
其中系数${\theta }_i\ge 0,i=1,2,3$,且$y_1,y_2$的初始条件的已知的，我们考虑的问题是
$$\begin{gathered} \underset{\theta \in R^3}{\min }\sum _{j=1}^n||y({\tau }_j,\theta )-z_j|{|}^2 \\ s.t.y(\tau ;\theta )满足方程组（\mathrm{4.2.6}） \end{gathered}$$
这里$z_j$是时刻${\tau }_j$的$y$的测量值，$n$为测量的时刻数量
（什么玩意，没看懂

4.3 复合优化问题

4.3.1 基本形式和应用背景

复合优化问题一般可以表示为如下形式：
$$\underset{x\in R^n}{\min }\psi (x)=f(x)+h(x)$$
其中$f(x)$是光滑函数（比如数据拟合项），$h(x)$可能是非光滑的(比如$l_1$正则项，约束集合的示性函数，或他们的线性组合)，复合优化问题在实际走有着十分重要的应用，并且其中的函数$h(x)$一般是凸的，由于应用问题的驱动，复合优化问题的算法近年来得到了大量的研究，比如次梯度法，近似点梯度法，$Nesterov$加速算法和交替方向乘子法等等，后续会详细介绍。
在下表中，我们总结了实际中常用的复合优化问题的可能形式

1.图像去噪

图像去噪问题是指从一个带噪声的图像中恢复出不带噪声的原图，记带噪声的图像为$y$，噪声为$ϵ$，那么
$$y=x+ϵ$$
其中$x$为要恢复的真实图像，利用全变差模型(3.11.5)，去噪问题可以表示为
$$\underset{x\in R^{n\times n}}{\min }||x-y|{|}_F^2+\lambda ||x|{|}_{TV}$$
这里，离散的线性算子为单位矩阵，我们也可以利用小波框架，小波变换可以很好的保护信号尖峰和突变信号，并且噪声对应的小波系数往往很小，因此，去噪问题的小波分解模型可以写为
$$\underset{x}{\min }||\lambda \odot W(x)|{|}_1+\frac{1}{2}||x-y|{|}_F^2$$
其中$\lambda =({\lambda }_1,{\lambda }_2,\cdots ,{\lambda }_m{)}^T$是给定的

2.盲反卷积

盲反卷积（也叫去模糊）是图像处理中的一个基本问题，其目的是从一个模糊的图像恢复出原来清晰的图像， 导致图像模糊的原因有很多种，比如相机抖动、聚焦不良、相机和拍摄物体所在的非静止环境以及成像设备的内在 缺陷等等，因此一般来说盲反卷积是不容易做到的。

为了让这个复杂的困难变得简单一些，我们做如下假设：模糊是线性的（不做图像变化）以及空间不变的（即与像素位置无关），线性且空间不变的模糊可以表示成一个卷积，令$x$为原始的清晰图像，$a$为未知的卷积核对应的矩阵，$y$为观测到的模糊图像以及$ϵ$为观测噪声，盲反卷积问题可以表示成
$$y=a\ast x+ϵ$$
其中*为卷积算子，假设噪声为高斯噪声，则转化为求解优化问题(前面提到过)
$$\underset{a,x}{\min }||y-a\ast x|{|}_2^2$$
再假设原始图像信号在小波变换下是稀疏的，我们进一步得到如下复合优化问题
$$\underset{a,x}{\min }||y-a\ast x|{|}_2^2+||\lambda \odot Wx|{|}_1$$
其中$W$是小波框架，$\lambda =({\lambda }_1,{\lambda }_2,\cdots ,{\lambda }_m{)}^T$用来控制稀疏度
2023-09-15还不懂小波变换T T

4.4 随机优化问题

4.4.1 基本形式和应用背景

随机优化问题可以表示成以下形式
$$\underset{x\in \chi }{\min }{E}_{\xi }[F(x,\xi )]+h(x)$$
其中$\chi \subseteq R^n$表示决策变量$x$的可行域，$\xi$是一个随机变量（分布一般是未知的）。对于每个固定的$\xi$，$F(x,\xi )$表示样本$\xi$上的损失或者奖励。正则项$h(x)$来保证解的某种性质，由于变量$\xi$分布的未知性，其数学期望$E_{\xi }[F(x,\xi )]$一般是不可计算的，为了得到目标函数值的一个比较好的估计，其实际问题中往往利用$\xi$的经验分布来代替其真实分布，具体地，假设有$N$个样本${\xi }_1,{\xi }_2,\cdots ,{\xi }_N$，令$f_i(x)=F(x,{\xi }_i)$，我们得到优化问题
$$\underset{x\in \chi }{\min }f(x)=\frac{1}{N}\sum _{i=1}^N{f}_i(x)+h(x)\text{\hspace{1em}(4.4.1)}$$
称其为经验风险极小化问题或者采样平均极小化问题，这个问题通常是难以求解的，一方面是因为样本数$N$比较多（因此函数值、梯度计算代价比较高），另一方面是因为优化问题的可行域空间维数$n$比较大

这个问题在统计学、机器学习、计算机科学中有着重要的应用，对于该问题的求解，我们需要在传统的方法上引入随机性以减少算法中目标函数值和梯度等的计算代价。

4.4.2 应用举例

第一、三章中有很多例子都可以写成随机优化的形式，我们这里还将介绍随机优化在随机主成分分析最和分布式鲁棒优化问题中的应用

1.随机主成分分析

在主成分分析中，如果样本点$\xi$服从某个零均值分布$D$，那么找方差最大的$d$维子空间的优化问题可以写成
$$\underset{X\in R^{p\times d}}{\max }Tr(X^T{E}_{\xi \sim D}[\xi {\xi }^T]X)s.t.X^{T}X=I\text{\hspace{1em}(4.4.2)}$$
其中$E_{\xi \sim D}[\xi {\xi }^T]$为$\xi$的协方差矩阵，在实际中，分布$D$是未知的，已知的只是关于分布$D$的采样。（其实就是换了种说法我感觉）大差不差的。
随机主成分分析关心的问题是在求得问题（4.4.2）的高逼近解过程中需要的样本数量以及消耗的时间。受制于计算机内存的限制，我们还需要考虑在有限内存情况下的逼近解的计算与分析。

2.分布式鲁棒优化

为了提高预测期的泛化能力，一种常用的方法是考虑分布式鲁棒优化问题
$$\underset{h}{\min }\underset{z\in I}{\max }{E}_z[F(h,z)]$$
在这里集合$I$中的随机变量的分布与真实数据的分布在一定意义下非常接近。
Wasserstein 距离
wasserstein 距离常常可以被用来计算两个分布之间的差异，相比于 KL，JS散度，它可以计算两个完全不重合的分布之间的差异，并且提供有效的梯度信息。具体的定理推到我们不在这里写了。两个分布间的 wasserstein 距离越大，说明分布的差异越大。
以现有的样本集合构成的分布作为中心，考虑一个 wasserstein 空间球体内的所有分布，这个空间球体的半径为 $ϵ$ ，真实分布理论上应该不会偏离训练样本集合的分布很远，那么只要$ϵ$合理，就可以认为真实分布应该包含在 wasserstein 球中，那么我们只要能保证模型在整个球体内效果最差的分布下得到最好的结果，就可以保证这个结果是真实样本分布下的性能的下界。

4.5 半定规划

半定规划（SDP）是线性规划在矩阵空间中的一种推广，它的目标函数和等式约束均为关于等式的线性函数，而它与线性规划不同的地方是其自变量取值于半正定矩阵空间。作为一种特殊的矩阵优化问题（见4.6节），半定规划在某些结构上和线性规划非常相似，很多研究线性规划的方法都可以作为研究半定规划的基础。
由于半定规划地位的特殊性，我们在本节中单独讨论半定规划的形式和应用，而一般的矩阵优化问题在4.6节讨论

4.5.1 基本形式和应用背景

半定规划问题的一般形式如下
$$\begin{gathered} \min c^{T}x, \\ s.t.x_1{A}_1+x_2{A}_2+\cdots +x_n{A}_n+B⪯0, \\ Gx=h\text{\hspace{1em}(4.5.1)} \end{gathered}$$
其中$c\in R^n,A_i\in S^m,i=1,2,\cdots ,m,B\in S^m,G\in R^{p\times n},h\in R^p$为已知的向量和矩阵，$x=(x_1,x_2,\cdots ,x_n)\in R^n$是自变量，这里，如果矩阵$A,B$是对角的，那么问题（4.5.1）退化为线性规划问题。类似于线性规划问题，我们考虑半定规划的标准形式
$$\begin{gathered} \min <C,X>, \\ s.t.<A_1,X>=b_1, \\ \cdots , \\ <A_m,X>=b_m, \\ X⪰0\text{\hspace{1em}(4.5.2)} \end{gathered}$$
和不等式形式
$$\begin{gathered} \min c^{T}x \\ s.t.x_1{A}_1+x_2{A}_2+\cdots +x_n{A}_n+B⪯0\text{\hspace{1em}(4.5.3)} \end{gathered}$$
任何（4.5.1）式都可以转化为（4.5.2）式或者（4.5.3）式的形式

4.5.2 应用举例

1.二次约束二次规划问题的半定规划松弛

考虑二次约束二次规划问题
$$\begin{gathered} \underset{x\in R^n}{\min }{x}^T{A}_{0}x+2b_0^{T}x+c_0, \\ s.t.x^T{A}_{i}x+2b_i^{T}x+c_i\le 0,i=1,2,\cdots ,m\text{\hspace{1em}(4.5.4)} \end{gathered}$$
其中$A_i$为$n\times n$对称矩阵，当部分$A_i$为对称不定矩阵时，问题（4.5.4）是NP难的非凸优化问题
（不定矩阵：既不是半正定也不是半负定and，这里的x应该默认都是n行1列的）
现在我们写出问题4.5.4的半定规划松弛问题，对任意$x\in R^n$以及$A\in S^n$，有恒等式
$$x^{T}Ax=Tr(x^{T}Ax)=Tr(Ax{x}^T)=<A,x{x}^T>$$
第三个等号可以看一下这个，但是他这个有点小问题，主要用到最后那个$Tr(x_i{x}_j^T)=x_i^T{x}_j$就很好证了，可以自己推一下

因此原始问题等价于
$$\begin{gathered} \underset{x\in R^n}{\min }<A_0,X>+2b_0^{T}x+c_0 \\ s.t.<A_i,X>+2b_i^{T}x+c_i\le 0,i=1,2,\cdots ,m \\ X=x{x}^T\text{\hspace{1em}(4.5.5)} \end{gathered}$$
进一步的
$$x^T{A}_{i}x+2b_i^{T}x+c_i=<\left(\begin{array}{cc}{A}_i& b_i\\ b_i^T& 1\end{array}\right),\left(\begin{array}{cc}X& x^T\\ x& 1\end{array}\right)>=(def)<\overline{A_i},\bar{X}>,i=1,2,\cdots ,m$$
接下来将4.5.5松弛为半定规划问题，在问题（4.5.5）中，唯一的非线性部分是约束$X=x{x}^T$，我们将其松弛为半正定约束$X⪰x{x}^T$，可以证明，$\bar{X}⪰0$与$X⪰x{x}^T$是等价的，因此这个额问题的半定规划松弛可以写为
$$\begin{gathered} \min <\overline{A_0},\bar{X}> \\ s.t.<\overline{A_i,\stackrel{ˉ}{X}}>\le 0,i=1,2,\cdots ,m, \\ X⪰0, \\ {\bar{X}}_{n+1,n+1}=1 \end{gathered}$$
最后一个等式啥意思我也不知道，前面倒是都可以理解

2.最大割问题的半定规划松弛

令$G$为一个无向图，其节点集合为 V = { 1 , 2 , ⋯   , n } V=\{1,2,\cdots,n\} V={1,2,⋯,n}的边的集合为$E$.令$w_{ij}=w_{ji}$为边$i,j\in E$上的权重，并假设$w_{ij}\ge 0$。最大割问题是找到节点集合$V$的一个子集$S$，使得$S$和他的补集$\bar{S}$之间相连边的权重之和最大化，我们可以将最大割问题写成如下整数规划的形式：令$x_j=1,j\in S$和$x_j=-1,j\in \bar{S}$，则
max ⁡ 1 2 ∑ i < j ( 1 − x i x j ) w i j s . t . x j ∈ { − 1 , 1 } , j = 1 , 2 , ⋯   , n (4.5.6) \max{\quad}\frac{1}{2}{\sum_{i<j}}(1-x_ix_j)w_{ij}\\ s.t.{\quad}x_j{\in}\{-1,1\},j=1,2,\cdots,n\tag{4.5.6} max21​i<j∑​(1−xi​xj​)wij​s.t.xj​∈{−1,1},j=1,2,⋯,n(4.5.6)
在问题4.5.6中，只有$x_i$和$x_j$不同时，$w_{ij}$非0，上面的$i<j$是为了不重复。最大割问题是一个离散优化问题，很难再多项式时间内找到他的最优解，接下来介绍如何将4.5.6松弛成一个半定规划问题
令$W=(w_{ij})\in S^n$，并定义$C=-\frac{1}{4}(Diag(W1)-W)$为图$G$的拉普拉斯矩阵的$-\frac{1}{4}$倍，则问题4.5.6可以等价写为
$$\begin{gathered} \min x^{T}Cx \\ s.t.x_i^2=1,i=1,2,\cdots ,n \end{gathered}$$
其中$W1$是加权度矩阵，拉普拉斯矩阵有很多很好的性质，大家可以自行搜索（我不懂他如何变成这种$x^{T}Cx$）想不太到，本质上还是让$x=1和x=-1$的权重之和尽可能的大，并且让$S$或$\bar{S}$之间的权重之和尽可能小，这样去优化问题我不知道是否可以得到最优解，因为原始的问题是不需要考虑$S$和$\bar{S}$内部的。但是不得不承认的是拉普拉斯矩阵是有很好的性质的。

由于目标函数是关于$x$的二次函数，利用前面的技巧可将其等价代换为$<C,x{x}^T>$，接下来令$X=x{x}^T$，注意到约束$x_i^2=1$，这意味着矩阵$X$的对角线元素$X_{ii}=1$（矩阵$X_{ii}=1$就能代表其他位置都会等于1或者-1了），因此我们将最大割问题转化为
$$\begin{gathered} min<C,X> \\ s.t.X_{ii}=1,i=1,2,\cdots ,n \\ X⪰0,rank(X)=1\text{\hspace{1em}(4.5.7)} \end{gathered}$$
问题4.5.6和问题4.5.7是等价的，因为$X=x{x}^T$可以用约束$X⪰0$和$rank(X)=1$等价刻画（自己推一下就知道了）若在问题4.5.7中将秩一约束去掉，我们就可以得到最大割问题的半定规划松弛形式
$$\begin{gathered} \min <C,X> \\ s.t.X_{ii}=1.i=1,2,\cdots ,n \\ X⪰0\text{\hspace{1em}(4.5.8)} \end{gathered}$$
问题4.5.8是原最大问题的一个松弛，因此他们并不等价，文献指出求解问题4.5.8可以给出原最大割问题的一个0.8786-近似解

3.极小化最大特征值

设$M(z)$为一个以$z$为参数的对称矩阵，极小化最大特征值问题的最终目标是选取一个$z$使得$M(z)$的最大特征值最小，即我们要求解问题
$$\underset{z\in R^n}{\min }{\lambda }_{max}(M(z))\text{\hspace{1em}(4.5.9)}$$
利用上方图的等价转换技巧容易将问题4.5.9转化成上方图的形式
$$\begin{gathered} \min t \\ s.t.t\ge {\lambda }_{max}(M(z))\text{\hspace{1em}(4.5.10)} \end{gathered}$$

问题4.5.10中$t$和$z$都是自变量，在实际应用中，$M(z)$线性依赖于$z$的情形比较常见，即
$$M(z)=A_0+\sum _{i=1}^m{z}_i{A}_i$$
其中$A_0,A_1,\cdots ,A_m$为对称矩阵，我们指出，当$M(z)$为$z$的上述线性映射时，问题4.5.10实际上是一个半定规划问题。实际上，可证明${\lambda }_{max}(M(z))\le t$当且仅当$tI-(M(z))\ge 0$,因此我们得到半定规划问题
$$\begin{gathered} \min t \\ s.t.tI-A_0-\sum _{i=1}^m{z}_i{A}_i⪰0 \end{gathered}$$

4.6 矩阵优化

4.6.1 基本形式和应用背景

矩阵优化问题具有如下形式：
$$\underset{X\in \chi }{\min }\psi (X)$$
其中$\chi$为特定的矩阵空间，$\psi (X):\chi \to R$为给定的函数，可能是非光滑的。对于矩阵优化问题，如果决策变量为一个$n\times n$的矩阵，那么我们可能需要确定$n^2$个元素，因此，决策变量的维数过大往往是矩阵优化问题难以快速求解的一个重要因素。

矩阵优化是在近十年来发展起来的一类变量含有矩阵的优化问题。由于矩阵变量函数的导数计算的复杂性，对于某些问题我们也给出其涉及的导数

（1）半定规划问题（4.5.2）：半定规划是一类特殊的矩阵优化问题，它的目标函数和约束均为线性函数，自变量$X$取值于半正定矩阵空间中，在4.5已经讨论了半定规划的具体形式和应用

（2）低秩矩阵恢复问题（1.3.2）：
$$\underset{x\in R^{m\times n}}{\min }\mu ||X|{|}_{\ast }+\frac{1}{2}\sum _{(i,j)\in \Omega }(X_{ij}-M_{ij}{)}^2$$
考虑函数$h(X)=||X|{|}_{\ast }$，其次微分为
∂ h ( X ) = { U V T + W ∣ ∣ ∣ W ∣ ∣ 2 ≤ 1 , U T W = 0 , W V = 0 } \partial{h(X)}=\{UV^T+W|{\quad}||W||_2{\le}1,U^TW=0,WV=0\} ∂h(X)={UVT+W∣∣∣W∣∣2​≤1,UTW=0,WV=0}
其中$X=U\sum V^T$为$X$的约化奇异值分解，对于函数
$$f(X)=\frac{1}{2}{\sum _{(i,j)\in \Omega }(X_{ij}-M_{ij})}^2$$
令矩阵$P\in R^{m\times n}$为
$$P_{ij}=\{\begin{array}{c}1,(i,j)\in \Omega \\ 0,其他\end{array}$$
那么，$f(X)=\frac{1}{2}||P\odot (X-M)|{|}_F^2$，易知其梯度为
$$\nabla f(X)=P\odot (X-M)$$

（3）主成分分析问题（3.7.1）：
$$\underset{X\in R^{p\times d}}{\min }\psi (X)=-Tr(X^{T}A{A}^{T}X),s.t.X^{T}X=I_d$$
通过简单计算，我们有
$$\nabla \psi (X)=-2A{A}^{T}X$$

（4）矩阵分离问题（3.8.2）
$$\begin{gathered} \underset{X,S\in R^{m\times n}}{\min }\psi (X,S)=||X|{|}_{\ast }+\lambda ||S|{|}_1 \\ s.t.X+S=M \end{gathered}$$
在这里自变量$X$与$S$均为矩阵，$\psi (X,S)$关于$X$和$S$均为不可微函数

（5）字典学习问题（3.9.1）
$$\begin{gathered} \underset{D,X}{\min }\frac{1}{2n}||DX-A|{|}_F^2+\lambda ||X|{|}_1, \\ s.t.||D|{|}_F\le 1 \end{gathered}$$
设$f(X,D)=\frac{1}{2n}||DX-A|{|}_F^2$我们有
$$\begin{gathered} {\nabla }_{X}f=\frac{1}{n}{D}^T(DX-A), \\ {\nabla }_{D}f=\frac{1}{n}(DX-A)X^T \end{gathered}$$
这里要注意$f(X,D)$关于两个变量分别求梯度的形式的区别

4.6.2 应用举例

1. 非负矩阵分解

假设$a$为$d$维空间中的非负随机向量，其$n$个观测值为 { a i } i = 1 n \{a_i\}_{i=1}^n {ai​}i=1n​。记矩阵$A=[a_1,a_2,\cdots ,a_n]\in R^{d\times n}$,非负矩阵分解问题是将$A$分解成非负$d\times p$基矩阵$X=[x_1,x_2,\cdots ,x_p]$和非负系数矩阵$Y=[y_1,y_2,\cdots ,y_n]$的乘积，即
$$A=XY$$
可以看出，$y_j$为观测点$a_j$在基矩阵$X$上的权重系数，也就是说，非负矩阵分解把数据分成基向量的线性组合。通常选取$\ast \ast p<<d\ast \ast$,那么得到的基矩阵$X$的列张成了原数据空间的一个子空间。 这本质上是将高维空间中的数据在一个低维空间中表示。当数据点的内蕴结构完全被基矩阵$X$包含时，我们就得到了一个很好的低维表示。

一般情况下，由于观测含有噪声，原始数据矩阵$A$和分解$XY$不会完全吻合，在这种情况下我们应当寻找误差最小的解。利用矩阵的$F$范数可以定义相似性度量
$$||A-XY|{|}_F^2$$

我们考虑如下优化问题
$$\underset{X\in R^{d\times p},Y\in R^{p\times n}}{\min }||A-XY|{|}_F^2,s.t.X\ge 0,Y\ge 0\text{\hspace{1em}(4.6.1)}$$
其中$\ge 0$表示矩阵的每个元素是非负的

从低维空间逼近的角度来看，非负矩阵分解模型和主成分分析模型类似。但在实际问题中，非负矩阵分解模型会比主成分分析模型更有实际意义的解。
比如，给定很多幅人脸图片(都可以用元素值为0~255的矩阵来表示其灰度值)，我们想要提取脸部的特征，利用主成分分析得到的主成分可能包含负数像素值，这是不合理的，但如果使用非负矩阵分解，则可以有效避免这类情形的发生。

我们称问题(4.6.1)为基本的非负矩阵分解模型，根据具体应用的不同，有时候还考虑带正则项的非负矩阵模型

$$\begin{gathered} \underset{X\in R^{d\times p},Y\in R^{p\times n}}{\min }||A-XY|{|}_F^2+\alpha r_1(X)+\beta r_2(Y), \\ s.t.X\ge 0,Y\ge 0 \end{gathered}$$
其中$r_1(X),r_2(Y)$是正则项，$\alpha ,\beta >0$是用来权衡拟合项和正则项的正则化参数。比如，如果$Y$的列是稀疏的，那么每一个观测值都可以用少数几个基向量来表示。相应地，我们可以惩罚$Y$的每一列$l_1$范数，为了保证基向量的线性无关性，往往要求$X$的列之间是相互正交的。
此外，如果数据矩阵$A$分布在一个低维的非线性流形上，则考虑流形或者图上的非负矩阵分解模型。（没懂哈哈，可能还没了解到这块）

2.低秩相关系数矩阵估计

相关系数矩阵是对角元素全为1的半正定矩阵，其第$(i,j)$元素表示随机变量$x_i$和$x_j$之间的相关系数，相关系数矩阵估计问题来自于统计学、金融学等领域中。
给定对称矩阵$C\in S^n$和非负对称权重矩阵$H\in S^n$，低秩相关系数矩阵估计问题是从给定的矩阵$C$出发，求解一个秩小于等于$p$的相关系数矩阵$X$,使得在结合了权重矩阵的某种度量下最小化:
$$\begin{gathered} \underset{X⪰0}{\min }\frac{1}{2}||H\odot (X-C)|{|}_F^2, \\ s.t.X_{ii}=1,i=1,2,\cdots ,n \\ rank(X)\le p\text{\hspace{1em}(4.6.3)} \end{gathered}$$
将$X$上的秩约束$rank(X)\le p$表示为$X=V^{T}V$，其中$V=[V_1,V_2,\cdots ,V_n]\in R^{p\times n}$，问题4.6.3可以转化为多球约束的四次多项式优化问题
$$\begin{gathered} \underset{V\in R^{p\times n}}{\min }\frac{1}{2}||H\odot (V^{T}V-C)|{|}_F^2 \\ s.t.||V_i|{|}_2=1,i=1,2,\cdots ,n \end{gathered}$$
为什么可以转化成这种写法我也不太懂，先记住？感觉这样更简单一点

3.电子结构计算

分子、纳米级材料的性质很大程度上是通过其原子中电子之间的相互作用来确定的。这些相互作用可以通过电子密度定量表征。
令电子的个数是$n_e$，位置是$r_i\in R^3,i=1,2,\cdots ,n_e$，原子核的个数是$n_u$，位置是${\hat{r}}_j\in R^3,j=1,2,\cdots ,n_u$。令$z_j$是第$j$个原子核的电荷，${\Delta }_{r_i}$为第$i$个电子对应的拉普拉斯算子，$\Gamma$为恒等算子，则多电子哈密顿算子可以表示为
$$H=\frac{1}{2}\sum _{i=1}^{n_e}{\Delta }_{r_i}-(\sum _{j=1}^{n_u}\sum _{i=1}^{n_e}\frac{z_j}{||r_i-{\hat{r}}_j||}-\frac{1}{2}\sum _{1\le i,j\le n_e}\frac{1}{||r_i-r_j||})\Gamma$$
后面一堆什么多体薛定谔方程涉及到电子领域了，没太看懂，最后反正是求一个
$$\underset{X\in C^{n\times n_e}}{\min }{E}_{KS}(X),s.t.{\bar{X}}^{T}X=I_{n_e}$$
这是一个正交约束优化问题，所有满足正交约束的矩阵称为$Stiefel$流形，所以该问题是流形约束优化的特例，KS极小化问题对应的最优性条件是一个非线性特征值问题。称为KS方程，基于KS方程，可以将问题化成一个非线性最小二乘问题，电子结构计算还有很多其他变形。例如简化密度矩阵优化问题可以是半定规划问题。

4.7 整数规划

4.7.1 基本形式和应用背景

不同于线性规划，整数规划要求优化变量必须取整数值，而不能是分数值，一般形式如下
$$\begin{gathered} \min c^{T}x \\ s.t.Ax\le b \\ {x}_i\ge 0,i=1,2,\cdots ,n, \\ {x}_i\in Z,i=1,2,\cdots ,n, \end{gathered}$$
其中$A\in R^{m\times n},c\in R^n,b\in R^m$是给定的矩阵和向量，$Z$是整数集合，如果只要求部分$x_i$是整数，该问题被称为混合整数规划问题。

4.7.2 应用举例

1.资本预算

在经典的资本预算问题中，我们需要对一些潜在的投资进行选择，选择合适的工厂位置或者对现有资本进行分配，放弃一些没有意义的项目，也就是决策变量$x_j=0or1$，意味着第$j$个投资被拒绝或者接受，假设$c_j$为投资$j$项目的回报，$a_{ij}$为将资源$i$用在项目$j$上的数量。那么资本预算问题可以表示为
$$\begin{gathered} \max \sum _{j=1}^n{c}_j{x}_j \\ s.t.\sum _{j=1}^n{a}_{ij}{x}_j\le b_i,i=1,2,\cdots ,m \\ {x}_j=0or1 \end{gathered}$$
有限的资源$b_i$找到投资最大化

这里说的太笼统了，没有考虑将多少资源投资到项目上得到的回报是多少，这里没有说明$c_j$是和$a_{ij}$有关的，我需要和读者说明一下。

2.仓库位置选取

在分配系统的建模中，我们需要考虑仓库与消费者之间的运输成本以及仓库自身的运营成本。
例如，一个管理者需要在$m$个可能的位置上修建一些仓库去满足$n$个消费者的需求。需要做的决策是建造哪些仓库以及控制每个仓库到消费者的运输量。仓库位置选取问题是指管理者根据消费者的需求以及仓库到消费者之间的运输成本，来确定所修建的仓库的位置。需要知道如何以最低成本将物资从仓库运输到消费者，令
$$y_i=\{\begin{array}{c}1，如果仓库i被修建\\ 0，如果仓库i未被修建\end{array}$$
以及$x_{ij}$为从仓库$i$运输到消费者$j$的物资数量，相关成本如下
$$\begin{gathered} f_i=仓库i的固定运营成本，比如租赁费 \\ {c}_{ij}=从仓库i运输物资到消费者j的运输成本 \end{gathered}$$
我们需要满足三个条件：
（1）消费者的需求$d_i$必须被满足
（2）只有已修建的仓库才能提供运输物资，如果 $y_i=0$，那么$x_{ij}=0$
（3）每个仓库i（所能提供的物资数量）是有限的，即${\sum }_{j=1}^n{x}_{ij}\le u_i,u_i\ge 0$为仓库的容量，那么仓库位置选取问题可以写成
$$\begin{gathered} \underset{x,y}{\min }\sum _{i=1}^m\sum _{j=1}^n{c}_{ij}{x}_{ij}+\sum _{i=1}^m{f}_i{y}_i \\ s.t.\sum _{i=1}^m{x}_{ij}=d_j,j=1,2,\cdots ,n \\ \sum _{j=1}^n{x}_{ij}\le y_i{u}_i,i=1,2,\cdots ,m \\ {x}_{ij}\ge 0 \\ {y}_i=0或者1,i=1,2,\cdots ,m \end{gathered}$$
这里很多的都很好理解，我主要说一下约束条件的第二条，他的意思就是如果仓库被建了，那么你的运输总量要少于仓库的容量，如果仓库没被建，那么你的运输总量就要小于等于0了，其实也就是0，因为x又是大于等于0的。