Optimization: Problems, Vector Norms, and Convex Sets

绪论

介绍最优化问题和补充一些最基础的知识储备

关于最优化问题

最优化问题是数学建模的相当重要的一个部分 往往结合数学和计算机数值方法进行处理 一般最优化问题会体现为 目标函数在约束条件下的极值问题 并且数学分析中的手段往往无法处理 我们需要数值方法来解决 在最优化问题的最开始 我们往往会见到一些被不等式约束的极值问题 当然后面会介绍更多的其他东西

基本概念

常用概念

等式约束以及不等式约束下的集合是这个问题的 可行集 全局最优解 是目标函数的最大或者最小值 如果这个点唯一 那么称为 严格全局最优解 局部最优解 某一个邻域下的最大或者最小值 而不是整个可行集下的 研究全局最优解往往是有难度的，后面很多方法都是只能研究局部最优解

$z=min{f(x_{1},x_{2})}$ 这种二维的最优化问题 往往体现为曲面的极值问题 这是一个几何上的描述

定理：任意全局最优解集合是闭集合 定理：如果目标函数 等式约束 不等式约束 都是连续函数 则可行域也是闭集合

知识补充

向量范数

定义：一种度量结构 是模长这个概念的推广 符号 $||x||$

范数的性质：

1. 正定 $||x||>0$
2. 正齐次 $||cx||=c||x||$
3. 三角不等式 $||x+y|| \ge ||x||+||y||$

各种不同的向量范数定义 他只是一种度量结构，并不唯一

1. 欧式范数

$$\|x\|_2 = \sqrt{\sum_{i=1}^{n} x_i^2}$$

2. 1范数

$$\|x\|_1 = \sum_{i=1}^{n} |x_i|$$

3. 无穷范数

$$\|x\|_{\infty} = \max_{i=1,...,n} |x_i|$$

我们最常用的还是在分析学里面就使用的欧式范数 他也叫做2范数

向量序列的收敛

• 依范数收敛 $||x^{b}-x^{k}||$ 极限为0
• 依坐标收敛 各个坐标序列是收敛数列
• 两个收敛本质上是等价的

Hessian矩阵

多元函数的梯度是一个向量 其中向量的各个分量也是多元函数 所谓的Hessian矩阵 就是对这个向量再进行求梯度 就能得到一个矩阵了 在最优化理论中 符号$\nabla$ 一般表示梯度算子 他有线性性质 几个特殊的例子

$$\bigtriangledown (b^{T}x)=b$$ $$\bigtriangledown (x^{T}x)=2x$$ $$\bigtriangledown (x^{T}Ax)=2Ax$$

凸集 凸函数 凸规划

这是研究线性和非线性的规划都非常重要的基本概念，这里进行非常必要的知识补充，但是并不会非常深刻

凸集

基本概念

定义：$C$是一个几何 $\forall~x,y\in C~ if~\lambda x+(1-\lambda)y\in C~\lambda\in[0,1]$ 则称C是一个凸集 对应的概念有凸组合 对于凸集的验证，直接采用定义来完成 容易验证以下几个命题 其中涉及的集合是凸集 涉及的数字是实数

$$\beta S_{1}=\{\beta x|x\in S_{1} \}是凸集$$ $$S_{1}\cap S_{2}是凸集$$ $$S_{1}+S_{2}=\{x^{1}+x^{2}|x^{1}\in S_{1}~~~x^{2\in}S_{2}\}$$ $$S_{1}-S_{2}=\{x^{1}-x^{2}|x^{1}\in S_{1}~~~x^{2\in}S_{2}\}$$

凸锥和多面集

极点和极方向

定义：如果S为非空的凸集，$x\in S$ 如x不能表示为S中两个不同点的凸组合 称x为凸集S的极点 多边形的顶点都是极点 圆周上的每一点都是极点 推论：对于紧凸集 任意一点都能表示为极点的凸组合 对于无界集合 不成立 定义：设$S$是$R^{n}$上的闭凸集 $d$是非零向量 如果对于$S$的每一个$x$ 都有射线

$$\{x+\lambda d|~\lambda \ge0\}\in S$$

则称$d$是$S$的方向 如果有一个方向不能表示为其他的两个方向的和 则称这个方向$d$是$S$的极方向 非常明显的，只有无界的集合才会有方向的概念，因此只有无界才有极方向 推论：任意的方向都能表示为极方向的正线性组合

凸集分离定理

凸集分离定理的直观意义是，在很弱的条件下，两个不相交的凸集，总可以用一个超平面分离，也就是对于超平面 $p^{T}x=a$ 两个集合的点分别全部满足 $p^{T}x_{1}\ge a$ 和$p^{T}x_{2}\le a$ 此时就称为 超平面$H$ 分离 两个集合

凸函数

定义：对于定义在凸集 C 上的函数 $f(x)$ 若对于$\forall x,y\in~C~\forall \lambda \in[0,1]$有$f(\lambda x+(1-\lambda)y)\le \lambda f(x)+(1-\lambda)f(y)$ 则称这个函数是凸函数 如果$x\ne y$时不取等 则称其为严格凸函数 （所谓的凸函数是下凸的） 下面的这些推论和定理也是用定义完成证明 定义：如果上面的不等号方向反过来 则称其凹函数 （这和一元的凹凸性定义一致） 定义：$f(x)$是凸函数 则$-f(x)$是凹函数 两个定义等价 定义：取$\lambda=1/2$ 则称为中点凸 推论：线性函数既是凸函数又是凹函数 定理：两个凸函数的和是凸函数 凸函数的正数乘是凸函数 推论：$f(x)$是凸函数$\Longrightarrow$ $\Omega_{c}=\{x|x\in \Omega,f(x)<c\}$是凸集 定理：凸集上的凸函数连续 定理：定义在开凸集$C$上的可微函数$f(x)$是凸函数$\Leftrightarrow$ $\forall x,y\in C,f(y)\ge f(x)+\nabla f(x)^{T}(y-x)$ 如要求严格 则等号删掉 定理：从一元函数凸性推广 定义在开凸集$C$上的可微函数$f(x)$是凸函数 $\Leftrightarrow$ $f(x)$的Hessian矩阵半正定（$\nabla^{2}f(x)\ge 0$）严格凸同理 只是从充要条件变为充分非必要条件

凸规划

定义：目标函数和约束函数都是凸函数的规划问题称为凸规划 推论：线性规划问题是凸规划 推论：凸规划的可行集是凸集 最优解是凸集 任意的局部最优解是全局最优解 定理：对于凸规划 如果目标函数是严格凸函数 且最优解存在 则最优解存在并唯一 所谓的最优解不唯一，是多个点达到了同一个最优函数值，要不然谈不了最优解的概念 定理：设$x^{*}$是凸规划$(P)$的可行解 则其是最优解的充要条件是 $x^{*}$ 是规划$min_{x\in S }\nabla f(x^{*})^{T}x$的最优解 其中S是$(P)$的可行域

线性规划的基本性质

线性规划 Linear Programming 他的约束条件和目标函数都是线性的 这是优化问题中较为简单的一类 也是最基本的一类问题 我们在会研究线性规划的一般性解法 在研究他们之前 给出一些线性规划的基本内容和特殊解法 也是重要的

线性规划的标准形式

标准形式

线性规划有所谓的标准形式 约束函数可以是等式和不等式混杂 目标函数可以求最大可以求最小 但是线性规划具有标准的形式 研究标准形式有利于后面各个解法的描述 定理：一切的线性规划都可以化为以下的形式 称为线性规划的标准形式 线性规划的标准形式可以用方程的形式表示为：$$\begin{aligned} \min_{x_1,x_2,\cdots,x_n} \quad & c_1 x_1+c_2 x_2+\cdots+c_n x_n \\ \text{s.t.} \quad & a_{11}x_1+a_{12}x_2+\cdots+a_{1n}x_n= b_1 \\ & a_{21}x_1+a_{22}x_2+\cdots+a_{2n}x_n= b_2 \\ & \cdots \\ & a_{m1}x_1+a_{m2}x_2+\cdots+a_{mn}x_n= b_m \\ & x_1,x_2,\cdots,x_n\geq 0 \end{aligned}$$ 其中，$x_i$ 表示第 $i$ 个决策变量，$c_i$ 表示第 $i$ 个决策变量的系数，$a_{ij}$ 表示第 $i$ 个约束条件中第 $j$ 个决策变量的系数，$b_i$ 表示第 $i$ 个约束条件的右端常数。 如果用矩阵表示则为

$$\begin{aligned} \min_{x} \quad & c^T x \\ \text{s.t.} \quad & A x = b \\ & x \geq 0 \end{aligned}$$

其中，$x$ 是 $n$ 维向量，$c$ 是 $n$ 维向量，$A$ 是 $m\times n$ 的矩阵，$b$ 是 $m$ 维向量。这里的 $\max$ 表示最大化目标函数 $c^T x$，$\text{s.t.}$ 表示约束条件。第一行是目标函数，第二行是约束条件

变量的个数$n$称为$LP$问题的维数 方程的个数$m$称为$LP$问题的阶数 一般$n>m$ 一些无关的约束的对应的矩阵称为线性规划的基 基矩阵对应的方程得到的解称为矩阵对应的基本解 约束条件允许的称为可行解 满足我们的目标函数条件的称为最优解 明显的，对于$m$阶$n$维的$LP$问题，最多有$C_{n}^{m}$个基本可行解，每个矩阵形式对应一个基本可行解

化为标准形式

首先 我们需要处理目标函数的 min max 差别 实际上 当求目标函数的max 就是其相反数的min 非常容易简化 对于 把下面的不等式 化为等式的问题 需要引入松弛变量来实现 如下

$$a_{11}x_1+a_{12}x_2+\cdots+a_{1n}x_n \ge b_1$$

引入松弛变量 化为

$$a_{11}x_1+a_{12}x_2+\cdots+a_{1n}x_n -x_{n+1}= b_1~~~~x_{n+1}\ge 0$$

同理的

$$a_{11}x_1+a_{12}x_2+\cdots+a_{1n}x_n\le b_1$$

化为

$$a_{11}x_1+a_{12}x_2+\cdots+a_{1n}x_n+x_{n+1}= b_1~~~~~x_{n+1}\ge 0$$

请注意 每个新的不等式都要引入新的松弛变量 不要重复 并且松弛变量一定要大于0 自行调整正负号

对于自由变量的处理

我们的标准形式是要求所有变量都是正的，不允许自由变量的出现，下面是一个处理的示例，核心就是通过解出某个方程，来实现自由变量的消失

$$\begin{aligned} \min_{x_1,x_2,\cdots,x_3} \quad & x_1+3 x_2+4 x_3 \\ \text{s.t.} \quad & x_1+2x_2+x_3= 5 \\ & 2x_1+3x_2+x_3= 6 \\ & x_2,x_3\geq 0 \end{aligned}$$

目前这个问题中$x_{1}$是自由变量，明显这不符合我们的需求，所以我们解第一个等式方程得到

$$x_{1}=5-2x_{2}-x{3}$$

代入前面的表达式得到

$$\begin{aligned} \min_{x_1,x_2,\cdots,x_3} \quad & 5-2 x_2- x_3 \\ \text{s.t.} \quad & x_2+x_3= 4 \\ & x_2,x_3\geq 0 \end{aligned}$$

此时标准化就顺利的实现了，这里标准化的所有内容就结束了

图解法

对于比较简单的线性规划 图解法就可以处理的 我们画出约束条件的图形 和 待求的线性函数 通过移动直线的方法 就可以找到最大值 明显的 图解法 只能处理2维（最高3维）的问题 更高维度的处理并不现实 推论： 对于二维的线性规划问题 最优解一定在凸集的极点（多边形顶点）上取到 推论： 如果两个顶点同时是最优解 那么意味着最优解不唯一 而是一条线 推论： 当集合是无限集合的时候，最优解可能不存在 需要画图考虑了

线性规划基本定理

线性规划的基本定理由两个核心定理构成，他是我们后面研究线性规划的求解的基础

$$定理：矢量x是凸集Ax=b的极点的充要条件是x是Ax=b的一个基本可行解$$ $$定理：对于一个标准的LP问题。如果存在可行解，就一定存在基本可行解， 如果存在最优可行解，就一定存在最优的基本可行解$$

两个定理能够告诉我们，研究LP问题的最优解，就是研究基本可行解，就是研究可行集的极点，这给我们后面的求解方法给出了最基础且核心的东西，也是对图解法一些内容的回顾

$$推论：只要可行集非空，至少有一个极点$$ $$推论：只要有限的最优解存在，那一定在一个极点上$$ $$推论：极点的数量至多为有限个$$

基本单纯型方法

这里我们来介绍最为核心的一个LP问题求解的方法 根据基本定理，只要我们研究所有的极点就一定能够求出所有基本可行解，此时就能找到最优解；但是对于超大规模的LP问题，这是非常不现实的，所以我们需要给出单纯形法； 他是一种转换的方法，从一个基本可行解转换到另一个，并且保证目标函数值的减少，经过不断的迭代，来用更少的次数来找到最优基本可行解 我们会分别介绍三个迭代思路的产生，最后合并起来进行使用单纯型表的练习

基本解的转换

对于一个$LP$问题 如下所示

$$\begin{aligned} \min_{x} \quad & c^T x \\ \text{s.t.} \quad & A x = b \\ & x \geq 0 \end{aligned}$$

由于我们的原始问题是通过引入松弛变量实现的标准化，所以我们认为系数矩阵中一定存在一个标准阵$E$ 即如下的形式

$$\left\{\begin{array}{ll} x_{1}+ & +y_{1, m+1} x_{m+1}+\cdots+y_{1 n} x_{11}=y_{10} \\ x_{2}+\cdots \\ & x_{m}+y_{m,m+1} x_{m+1}+\cdots+y_{m n} x_{\eta}=y_{m 0} \end{array}\right.$$

此时很容易找到一个基本解 怎么找到另一个基本解呢？ 假设我们想要把基本变量xp去掉 引入新的基本变量xq 我们的操作是

$p$行 $x_{q}$的系数化为1 (乘常数)

其他行 $x_{q}$的系数化为0 (加减$p$行)

可行性的保证

研究在转换的过程中 保证解的可行性

判别数与目标函数值减少

研究在转换的过程中 保证解的目标函数值的减少

单纯性表的使用

我们用一个例子来说明这个问题

改进的单纯性方法

大M法

为了处理没有单位矩阵的情况 我们引入了大M法 思路如下 对于原本的线性规划问题 我们引入人工变量$y=(y_{1},y_{1}...y_{m})$ 构造线性规划问题

$$\begin{aligned} \min_{x} \quad & c^T x+ME^{T}y\\ \text{s.t.} \quad & A x+y = b \\ & x \geq 0~x \geq 0\end{aligned}$$

此时我们的修正问题存在一个单位矩阵可以使用单纯形方法求解 定理：设$(x^{*},y^{*})$ 是修正问题的最优解 那么如果$y^{*}$为0 $x^{*}$就是原始问题的最优解 否则原问题没有可行解 反之同理 M确定为一个确定的数是没有意义的 我们认为他非常大代入后面的运算就好了

两阶段法

还是对于原始问题 我们引入人工变量$y=(y_{1},y_{1}...y_{m})$ 构造修正问题如下

$$\begin{aligned} \min_{y} \quad & \sum y_{i}\\ \text{s.t.} \quad & A x+y = b \\ & x \geq 0 ~y \geq 0\end{aligned}$$

定理：设$(x^{*},y^{*})$ 是修正问题的最优解 那么如果$y^{*}$为0 $x^{*}$就是原始问题的最优解 否则原问题没有可行解 反之同理

退化和循环

如果计算进基变量时出现min=0 则新解和旧解的目标函数值一致 导致迭代循环不止 我们这里并不会给出处理退化和循环的方法 只是为了尽可能的避免出现这样的问题 我们规定

• 有多个$r_{i}<0$时（确定多个进基） 我们选最小的那一个为进基变量
• 如果确定了多个离基变量时 还是选择$min~r_{k}$对应了那个

一维搜索

最优化问题的构造原理

这里是对最优化问题整体原理的一个阐述，我们后面的研究都是他的细节与拓展 取无约束极小化问题$min(f(x))$ 对于给定的初值$x^{0}$ 我们的某一次迭代过程如下

1. 按照一定规则获得在$x_{k}$下降方向$d_{k}$
2. 按照一定规则确定步长$\lambda _{k}$ 一般是$min[f(x^{k}+\lambda_{k}d_{k})]$
3. 令$x^{k+1}=x^{k}+\lambda_{k}d_{k}$
4. 按照一定规则确定是否需要结束迭代，循环或者输出结果 根据以上的方法可以得到一个序列$x^{k}$ 他的极限点就是极小化问题的极小点 如果对于多个初始点 都有共同的极小值 则成为全局收敛 否则是局部的

收敛性分析

算法的收敛性分析是一个复杂的工作，很多算法并不能确定是否收敛，但是不耽误我们使用它，考虑执行效率是算法设计工作中更为重要的一个问题，下面是对收敛性的一些讨论

对于依范数收敛的序列$x^{k}$ 如果存在实数$\alpha$ 和常数 $k$ 满足

$$\lim _{k \rightarrow \infty} \frac{\left\|x^{k+1}-x^{*}\right\|}{\left\|x^{k}-x^{*}\right\|^{\alpha}}=q$$

• $\alpha=1~q>0$ 称为线性收敛速度
• $1<\alpha<2~q>0~or~\alpha=1~q=0$ 称为超线性收敛
• $\alpha=2$ 称为二阶收敛速度

根据收敛性分析给出一些常用的迭代终止条件 他们多用于上面的最优化问题

• $||x^{k+1}-x^{k}||<\varepsilon$
• $||\bigtriangledown f(x^{k})||<\varepsilon$

精确一维搜索

在前面的最优化问题构造中 步长$\lambda$是根据一个一维的极小值问题研究的，这本质上就是一维基础的最优化问题，我们在这里专门研究一下这个问题的计算方法，也就是一维搜索；我们只会介绍一部分方法，因为方法是给不完的；

借助分析学性质的求解

对于一维的极小值问题，我们可以直接通过求导的方式来研究

$f^{'}(x)=0$的就是极值点，求解对应的值就可以了

成功-失败法

取一维无约束极小化问题$min(f(x))$ 对于给定的初值$x^{0}$ 计算方法如下

1. 给定初始点$x^{0}$ 搜索步长$h>0$ 精度$\varepsilon$
2. 计算$x^{1}=x^{0}+h;f_{1}=f(x^{1})$
3. 如果$f_{1}<f_{0}$ 搜索成功 加大步长搜索 $x^{0}=x^{1},f_{0}=f_{1},h=2h$
4. 反之，搜索失败，如果$|h|<\varepsilon$ 找到极小，搜索结束 否则缩小步长后退搜索$x^{0}=x^{1},f_{0}=f_{1},h=-1/4*h$ 这就是成功失败法的完整迭代过程 对于求搜索区间的问题，题目不用给出$\varepsilon$ 我们的目的是找到最优解大概存在的一个区间，不是找具体值，迭代原理是完全一致的

0.618法

借助黄金分割原理进行迭代的一种手段 考虑以下一维极小化问题 $min(f(x))~st~a_{1}\le \lambda\le b_{1}$ 这里需要一个基本范围了 我们预先需要知道 $\varepsilon,\alpha=0.618$

1. 计算$\lambda_{1}=a_{1}+(1-\alpha)(b_{1}-a_{1})~\mu_{1}=a_{1}+\alpha (b_{1}-a_{1})$ $f(\lambda_{1})~f(\mu_{1})$
2. 如果$b_{k}-a_{k}<\varepsilon$ 迭代结束 最优解为$(b_{k}+a_{k})/2$ 如果$f(\lambda_{1})>f(\mu_{1})$ 转3 否则转4
3. $a_{k+1}=\lambda_{k},b_{k+1}=b_{k}$ 在这个范围内再次进行上面从1开始
4. $a_{k+1}=a_{k},b_{k+1}=\mu_{k}$ 在这个范围内再次进行上面从1开始
5. 迭代角标 0.618法需要的迭代次数往往比较高，原因是他的收敛速度非常慢

二分法

这里的二分法和求根的二分法完全一致，我们借助介值定理和导数判断根的具体位置；这里就不再继续赘述了，我们只是需要注意截止条件，一般采用$||x^{k+1}-x^{k}||<\varepsilon$ 这和newton迭代有一个非常相似的核心思路 就是把原函数的最小值问题转为了导函数的零点问题 然后使用求根的方法进行了求解

Newton迭代法

他的核心思想是借助二阶的Taylor展开式来近似原本的函数，用近似的函数的分析性质研究极小值的位置，迭代思路如下 对于给定的初值$x^{0}$ 我们进行如下迭代过程

$$x^{k+1}=x^{k}-f^{'}(x^{k})/f^{''}(x^{k})$$

直到 $|f^{'}(x^{k}|<\varepsilon$ 这个方法的优势就是非常快的收敛速度

抛物线法

用一个非Taylor的二阶函数来实现近似，也就是插值多项式的思路，我们选择三插值构造二阶函数 对于二阶函数 求最小值应该是一个非常容易的操作 我们需要初始的插值点$x_{0}~x_{1}~x_{2}~$ 一般默认$x_{0}$在中间 通过解我们构造的插值方程组可以得到二阶函数的系数 迭代一次产生的结果是

$$\bar{x}=1/2[x_{1}+x_{0}-b_{1}/a_{2}]$$

其中

$$(f_{1}-f_{0})/(x_{1}-x_{0})=b_{1}~~(f_{2}-f_{0})/(x_{2}-x_{0})=b_{2}~(b_{2}-b_{1})/(x_{2}-x_{0})=a_{2}$$

理解一下就好了，最好记一下公式

非精确一维搜索

在某些情况下，非精确的一维搜索可以起到更好的加速收敛的作用，并且精确的一维搜索实现难度有时候有点过高，所以非精确的一维搜索现在应用非常的广泛 这里就略去具体的方法了，在需要的时候补充

无约束优化方法

无约束优化的极值条件

一般情况下，无约束优化问题是通过一系列一维搜索实现的，如何选择这一系列一维搜索是我们需要考虑的问题； 定理：曲线在负梯度方向下降最快 在极小值点梯度为0 定理：局部最优解的充要条件还需要加上Hessian矩阵正定 定理：对于凸函数，全局最优解只需要梯度为0就可保证 有了这些理论，我们知道梯度是研究无约束极值问题的核心

最速下降法

最速下降法的核心就是负梯度方向下降最快的原理来选择搜索方向；然后根据一维搜索来确定每次的步长，最后根据某个截止条件完成截止，下面是详细的运算步骤

1. 给定初始点$x^{0}$ 精度$\varepsilon$ 令$k=0$
2. 计算$d^{k}=-\bigtriangledown f(x^{k})$ 如果$d^{k}<\varepsilon$搜索停止，返回现在的$x^{k}$作为$x^{*}$
3. 从$x^{k}$ 出发，作一维搜索$min\{f(x^{k}+\lambda d^{k}\}$
4. 找到$\lambda$，找到新的$x^{k+1}$ 进行下一次迭代 在手工的运算中，一维搜索往往可以使用最简单的分析学性质来实现搜索，而不是那些复杂的搜索算法，那更适合计算机使用 算法优劣

• 对初始点没什么要求，前期迭代很快
• 在接近最优解的时候迭代速度很慢，对扰动不稳定，收敛速度受变量的尺度影响，导致初始点选取还是大问题，不好的初始点选择会导致复杂的计算过程
• 对于确定全局最优解，往往是多个点求局部最优解，如果一致，就认定全局最优解
• 为了避免锯齿状的下降，我们采用修正搜索方向$d^{k}=x^{k}-x^{k-2}$ 这应该是很好理解的，他可以避免正交的锯齿下降

Newton法

Newton方法借助二次近似来实现搜索方向的确定，过程如下

1. 给定初始点$x^{0}$ 精度$\varepsilon$ 令$k=0$
2. 计算$g^{k}=\bigtriangledown f(x^{k})$如果$g^{k}<\varepsilon$搜索停止,返回现在的$x^{k}$作为$x^{*}$
3. 计算$d^{k}=-[\bigtriangledown ^{2} f(x^{k})]^{-1}g^{k}=-H_{k}^{-1}g^{k}$ 作为下降方向
4. 作一维搜索$min\{f(x^{k}+\lambda d^{k}\}$
5. 找到$\lambda$，找到新的$x^{k+1}$ 进行下一次迭代

$H^{-1}$ 是求逆矩阵

为了保证矩阵$Hk$和$gk$可以进行矩阵的乘法，我们要对让梯度向量是一个列向量 算法优劣

• 局部收敛速度非常好，二次终止性，对于二次凸函数一步到达最优解
• Newton方向不一定下降，受限于Hessian矩阵的奇异性，需要非奇异的矩阵，否则方向计算困难

共轭梯度法

计算二阶Hessian矩阵和他的逆矩阵并不是一件容易的事情；最速下降的后期迭代效果不好，我们希望结合两者的优点，也就是我们这里介绍的共轭梯度法 定义：向量$d_{1}~d_{2}$ 关于某个矩阵共轭意味着$d_{1}^{T}Ad_{2}=0$ 这个矩阵退化为单位的时候意味着正交

$$定理：设A_{n*n}>0,d^{1},d^{2}...d^{n}是一组A-共轭的向量；f(x)=1/2x^{T}Ax+b^{T}+c只需要从任意初始点出发，从每一个共轭方向进行精确一维搜索就可以找到最优解，至多需要n次$$

有了前面的定理；问题变成了生成一组共轭方向，事实上，共轭方向的生成最好结合函数本身，下面我们直接给出最为经典的共轭梯度方法算法步骤

1. 给定初始点$x^{1}$ 令$k=1$
2. 计算$d^{k}=-g^{k}=-\bigtriangledown f(x^{k})$ 梯度足够小终止迭代
3. 根据负梯度方向进行一维搜索，给出一个辅助公式$\lambda _{k}=\frac{(g^{k})^{T}g^{k}}{(d^{k})^{T}Ad^{k}}$ (分析学计算也可)
4. 令 $x^{k+1}=x^{k}+\lambda_{k}d^{k};g^{k+1}=\bigtriangledown f(x^{k+1});\alpha_{k}=\frac{(g^{k+1})^{T}g^{k+1}}{(g^{k})^{T}g^{k}};d^{k+1}=-g^{k+1}+\alpha_{k}d^{k}$
5. 迭代的次数为变量的个数，从初始点开始算一次迭代 请注意，我们需要保证第一次采用负梯度方向进行计算，才能保证构造的方向是共轭的

$A$是初始量的Hessian矩阵

变尺度的DFP方法（拟Newton法）

拟Newton方程

拟newton方法是newton方法的改进 希望用迭代的方法来找到可以取代Hessian矩阵的方法 如果找到了满足拟newton方程

$$H_{k+1}g_{k}=s_{k}$$

也就是 迭代矩阵$\times$目前梯度=下降方向 这就是满足拟newton方程

拟Newton法

拟newton法的思想是用其他的手段来取代Newton方法中Hessian矩阵的问题，这是newton法的一个巨大缺点

1. 给定初始点$x^{0}$ 精度$\varepsilon$
2. 令$H_{1}=E$ 计算$g^{1}=\bigtriangledown f(x^{1})$ 如果$g^{1}<\varepsilon$搜索停止,返回现在的$x^{1}$作为$x^{*}$
3. 令$d_{k}=-H_{k}g^{k}$
4. 一维搜索求出$\lambda_{k}$ 计算$x^{k+1},g^{k+1}$
5. 重复运算过程，利用DFP修正公式求出新的$H_{k}$ 直到找到最优解

$$DFP修正公式： {H}_{k+1}={H}_{k}+\frac{\Delta x^{k}\left(\Delta x^{k}\right)^{T}}{\left(\Delta x^{k}\right)^{T} \Delta g^{k}}-\frac{{H}_{k} \Delta g^{k}\left({H}_{k} \Delta g^{k}\right)^{T}}{\left(\Delta g^{k}\right)^{T} {H}_{k} \Delta g^{k}}~~其中的\Delta意味着k+1和k的差值$$

约束优化方法

约束极值条件

一个约束优化问题应该表示为以下的形式 整体分为了目标函数，不等式约束，等式约束三个部分

$$\left\{\begin{array}{l} \min _{x \in \mathbb{R}^{n}} f(x) \\ \text { s.t. } g_{i}(x) \geq 0, i=1, \cdots, m, \\ h_{j}(x)=0, j=1, \cdots, n . \end{array}\right. 集合 S=\left\{\begin{array}{l|l} x \in \mathbb{R}^{n} & \begin{array}{l} g_{i}(x) \geq 0, i=1, \cdots, m, \\ h_{j}(x)=0, j=1, \cdots, n . \end{array} \end{array}\right\} 为问题(1)的可行集.$$

对于存在约束的优化问题，目标函数无约束的驻点很可能不在可行集$S$内，所以直接使用无约束方法进行研究是不可行的，我们需要变通 定义：下降方向，目标函数值在走向这个方向的时候下降 定义：可行方向，在走向这个方向的时候，我们能保证只走一定的长度一直在可行集内 定义：某点的线性化可行方向集为

$${LFD}(\bar{x}, S):=\left\{\begin{array}{l|l} d \neq 0 \in \mathbb{R}^{n} & \begin{array}{l} d^{T} \nabla g_{i}(\bar{x}) \geq 0, i \in I, \\ d^{T} \nabla h_{j}(\bar{x})=0, j=1, \cdots, n . \end{array} \end{array}\right\}$$

定义：对于可行集$S$中的一点，不等式约束条件分为了两个状态，满足$g(x_{i})=0$的时候 称为积极约束 对应的$g(x_{i})>0$ 称为非积极约束，记$I=\{i|g_{i}(\bar{x})=0,i=1,2,...,m\}$称为某点的积极约束指标集

$$Kuhn-Tucker极值条件：设目标函数和约束函数均可微，向量集CQ\{\bigtriangledown g_{i}(\bar{x}),\bigtriangledown h_{j}(\bar{x})\}线性无关；如果\bar{x}是局部最优解，则存在数w_{i}~v_{j}使得~\bigtriangledown f(\bar{x})=\sum w_{i}\bigtriangledown g_{i}(\bar{x})+\sum v_{i}\bigtriangledown h_{j}(\bar{x});其中w_{i}\ge0~ ~i \in I~I是约束指标集$$

让KT极值条件成立的点$\bar{x}$称为$K-T$点 定理：凸规划问题的$K-T$点是全局最优解

$K-T$点的验证和计算

事实上对于K-T点的验证，我们也完全采用定义进行，请练习后深刻理解我们需要计算的过程，我们需要处理一个线性方程组就可以得到K-T点的位置；同理我们可以进行验证的操作 理解这个计算过程还是有一定难度的 只有等式约束的问题就是数学分析的拉格朗日乘子法 所以我们KT方法就是为了处理不等式约束和综合两种约束情况 先从只有一个不等式约束入手

1. 构造拉格朗日函数 $L(x,\lambda)=f(x)+\lambda g(x)$
2. 求梯度构造方程 $\nabla f(x^{*})+\lambda \nabla g(x^{*})=0$
3. 分别讨论$\lambda=0~and\nabla g(x^{*})=0$
4. 验证得到的解是否满足梯度方程和 $\lambda\ge 0~g(x^{*})\le0$ 这样我们就可以知道到底哪些点是我们需要知道的KT点了 综合情况
5. 构造拉格朗日函数 $L(x,\lambda)=f(x)+\sum\limits\lambda_{i} g_{i}(x)+\sum\limits\mu_{j}h_{j}(x)$
6. 求梯度构造方程 $\nabla f(x)+\sum\limits\lambda_{i} \nabla g_{i}(x)+\sum\limits\mu_{j} \nabla h_{j}(x)=0$
7. 分别讨论$\lambda_{i}=0~and\nabla g_{i}(x^{*})=0$
8. 我们独立的讨论每一个$\lambda_{i}$ 当它为0的时候，对应的$g_{i}(x)$不为0，否则对应的$g_{i}(x)$为0
9. 验证得到的解是否满足梯度方程和 $\lambda_{i}\ge 0~g(x^{*})\le0~h_{i}(x^{*})=0$ 注意约束问题的标准形式，不好化错

SUMT外点法

SUMT是序列无约束极小化方法 我们的主要方法就是它 也就是惩罚函数法 其思想是构造惩罚函数项 让我们的自变量偏离可行域后函数值快速的增大 借此改变成无约束优化的问题 第一步 构造惩罚函数项$p(x)$ 得$F(x,M)=f(x)+Mp(x)$

$p(x)$需要满足连续 恒正 仅当$x\in S,p(x)=0$

第二步 构造这个$p(x)$项是很容易的 我们有以下的思路 等式约束$p(x)=h^{2}(x)$ 不等式约束$p(x)=0 if x\in S else~ ~p(x)=g^{2}(x)$ 对于多个约束的情况 把所有的$p(x)$加起来就好了 第三步 求解无约束优化问题 如果需要迭代$M$ 则使用$M_{k+1}=M_{k}c;c\in[4,10]$ 初始的$M$需要指定 在分析学计算时 我们要记住 M非常大 就好了

SUMT内点法

也就是碰壁函数法 其思想是构造碰壁函数项 让我们的自变量接近可行域边界后函数值快速的增大 借此改变成无约束优化的问题 第一步 构造惩罚函数项$B(x)$ 得$F(x,r)=f(x)+rB(x)$

$B(x)$需要满足连续 恒正 x逼近S边界的时候 B(x)趋于无穷大

第二步 构造这个$B(x)$项是很容易的 我们有以下的思路 哪个好算用哪个 注意标准形式的不等号是大于0

$B(x)=\sum\limits g_{i}^{+}(x);g_{i}^{+}(x)=-\frac{1}{g_{i}(x)}or-ln(-g_{i}(x))$

第三步 求解无约束优化问题 如果需要迭代$r$ 则使用$r_{k+1}=\frac{r_{k}}{c};c\in[4,10]$ 初始的$r$需要指定 在分析学计算时 我们要记住 r接近0 就好了

SUMT混合法

综合惩罚和碰壁 可以加速迭代进度

多目标规划

多目标规划的定义是非常明确且清楚地；此时我们有多个$min~max$的目标函数；

很明显的，如果所有的目标函数都能在同一个点达到最优解（绝对最优解），这当然是很好的，不过这太理想了，很难实现；

事实上，我们在这里往往会给出有效解的概念；意味着，不存在绝对比他更好的解（实现一个目标函数一定会另一个目标函数偏离最优），核心点在于矢量的大小我们这里无法比较，最后多目标规划问题就称为了在有效解中根据自己的偏好情况进行选择的问题，具体怎么选择，没有优劣的区分

我们的多目标规划是寻找有效解的过程，而不是寻找最优解，具体的最优解要根据偏好来决定；

下面介绍一些经典的求有效解的方法，核心思想都是把多目标降为单目标进行思考；

极小极大法

$$h(x)=min/max~\{h_{1}(x),h_{2}(x)...h_{n}(x)\}$$

缺点，只能找到一个有效解，后续生成的函数失去了可微性

线性加权和

$$h(x)=\sum \theta_{i}h_{i}(x)$$

平方加权和

$$h(x)=\sum \theta_{i}(h_{i}(x)-h_{min}(x))~~~h_{min}(x)=min~\{h_{1}(x),h_{2}(x)...h_{n}(x)\}$$

乘除法

另一种构造的方法，以后学习的时候研究

约束法

只保留一个目标函数，把其余目标函数转化为约束条件的求解方法