最优化方法

极小点判定条件

凸函数：Hessen矩阵半正定（正定时为严格凸函数）

凹函数：Hessen矩阵半负定

线性规划

线性规划的目标函数等值面是平行平面。

标准线性规划

主约束都是右端项非负的等式约束

结果要不是最优解要不是解无界。（不会出现无解）

标准线性规划有容许解，则必有基本容许解。

若有最优解，则必有最优基本容许解。

典范线性规划

I阶段线性规划或存在最优基本容许解(W=0)，或原问题无解(W>0)。

典范线性规划或者解无界或者有最优解 不会出现无解的情况。

第一阶段

解辅助线性规划，目的是求标准线性规划主约束的一个 G-J方程组
第二阶段

解标准线性规划，即解原线性规划

单纯形

本质上是解典范线性规划的算法

根本目标是让人工变量全部退基

具有有限终止性

自由变量 $x_1 = x_2 -x_3$

最优性检验

最大判别数$\delta _l$

最优解 $\delta _l \leq 0$
无界 $\delta _l \gt 0 $ $a_l \leq0$ 异号
无解 第一阶段 最优值 $w>0$

$\delta _l \gt 0 $ $a_l \nleq0 $ 可以继续迭代，典范线性规划不会出现无解的情况。

特殊情况

若所有判别数都 <0 但是人工变量没有退基，任选一个非人工变量系数的非0元素作为主元，在进行一次换基运算，得到标准线性规划主约束的G-J方程组。
若基变量中有人工变量，但非人工变量变量的系数都为0，b也为0，可以直接划掉，进入第二阶段。
没有约束的变量是自由变量，变为$x_1 = x_2 -x_3$

直线搜索

区间收缩法（黄金分割法用于任何单谷函数求极小值）
函数逼近法（抛物线插值法适用于连续单谷函数）

最速下降法

不具备二次终止性，线性收敛算法，无限次迭代。

如果初始点选在椭球等值面（椭圆等值线）上，迭代一次就会得到极小点，否则会无限次迭代。

优点：直观简单

缺点：收敛速度慢实用性差锯齿现象

基本思想：在点$x_k$处沿负梯度方向$p_k$进行直线搜索。

直线搜索的性质：$g_{k+1}·g_k = 0$ 相邻迭代点梯度正交。

锯齿现象：最速下降法的迭代点在向极小点靠近的过程中，走的是曲折的路线，后一次搜索方向$p_{k+1}$与前一次搜索方向$p_k$垂直，称之为锯齿现象。

牛顿法

基本思想：从$xk$到$x{k+1}$的迭代过程中，在点$x_k$处对$f(x)$按Taylor级数展开到第三项，解出极小点。当目标函数$f(x)$是正定二次函数的时候，牛顿法迭代一次就会得到最优解。

几何解释：在函数$f(x)$过点$x_k$的等值面方程，用一个与曲面最密切的二次曲面代替他。

Taylor展开

$f(x)=f(x_k)+g_x^T(x-x_k)+\frac{1}{2}(x-x_k)^TG_{x_k}(x-x_k)$

修正牛顿

对于非正定二次函数，牛顿法一般不会有限步终止，原因：

1.Hesse矩阵奇异

$p_k = -g_k$

直线搜索

$x_{k+1}=x_k+t_k·p_k$

2.Hesse矩阵可逆

牛顿方向不存在（垂直）
```
1.    $p_k = -g_k$
1.    直线搜索
```
步长为1不合适（下降方向）
1. 直线搜索
牛顿方向不是下降方向（上升方向）
1. $p_k = G_k^{-1}·g_k$
2. 直线搜索

共轭方向法

优点：克服了最速下降法的锯齿现象，从而提高了收敛速度，迭代公式简单，不必计算目标函数的二阶导数。与牛顿法相比，减少了计算量和存储量。

二次终止性：对于n元正定二次函数，从任意点出发，顺次沿着n个共轭方向作最多n次直线搜索，就可以求得目标函数的极小点。

共轭梯度法：初始共轭梯度向量$p0$恰好取为初始点$x_0$的负梯度$-g_0$，而其余共轭向量$p_k$，由第$k$个迭代点$x_k$处的负梯度$-g_k$与已经得到的向量$p{k-1}$的线性组合来确定，那么这个共轭方向法就称为共轭梯度法。

DFP算法

性质：若初始矩阵$H_0$对称正定，则$H_k$中每一个都对称正定。

步长加速法

不要求目标函数可导或可微。

基本思想：步长加速法主要由交替进行的“探测搜索”和“模式移动”组成。

探测搜索：为了寻找当前迭代点的下降方向
模式移动：沿着下降方向寻找新的迭代点

探测的出发点：参考点

周围比他更好的点：基点

得到的下降方向：模式

从基点沿模式作直线搜索：模式移动

I型探测：

在基点周围构造一个模式

失败缩小步长

II型探测：

判别上次的模式移动是否成功

失败撤销上次模式移动，将上次的基点作为参考点，开始I型探测

失败原因：前一次模式移动过大，离开了极小点所在区域

最小二乘法

$y=x_1t+x_2$

线性模型

$min ||Ax-b||^2$ $min s(x_1,x_2) = \sum(x_1t+x_2-y)^2$

等价于解法方程组

$A^TAX=A^Tb$

最优解：$x^* = (A^TA)^{-1}A^Tb$

检验

约束规划问题

等式约束

Lagrange函数

Lagrange乘子，使得求解等式约束问题，等价于求解无约束问题。

几何表示：

拉格朗日函数关于x的Hesse矩阵在$x^$的约束曲面切平面的交集上正定，则$x^$是等式约束问题的严格局部极小点。

不等式约束

不等式约束关于容许集的任意内点都是不起作用的约束，只有容许集的边界点才能使某个或某些不等式约束变成起作用约束。

容许方向向量：

对于起作用的约束

$\nabla s_i(x)^Tp>0$

几何最优性条件

判断x* 是否为局部极小点：

若$x^$是局部最优点，则在点$x^$处的容许方向锥和下降方向锥的交集是空集。

$\nabla s_i(x)^Tp>0 \\ \nabla f(x)^Tp<0$

K-T条件

几何表示：

若$x^$是最优点，则目标函数在该点的梯度必位于由*起作用约束函数的梯度张成的凸锥中。

凸规划问题的最优性充分条件：

$f$是可微凸函数，$s_i$是可微凹函数，$h_i$是线性函数，如果$x^*$是K-T点，那么是全局最优点。

$u_0$不为0的充要条件：

在$x^*$处，起作用的约束函数，梯度全都线性无关。

Z-容许方向法

终止条件：

$x^*$为K-T点的充要条件：

$\nabla f(x)^Tp^*=0$

并且：A’ 和 C的行向量线性无关。

继续迭代，仍然是一个下降方向向量

$\nabla f(x)^Tp^*<0$

换点

$\nabla f(x)^Tp^*>0$

算法：

确定当前迭代点的下降容许方向
通过直线搜索确定下一个迭代点（在下降容许方向作ls 最佳步长因子有上界）
判定新的迭代点是否为问题的解

判断容许方向：

非线性约束

$s(x)$为起作用的约束

$\nabla s(x)^Tp>0$

线性约束

$A'p \geq 0$ $Cp=0$

外部罚函数法

惩罚策略：对容许点不予惩罚，对于非容许点给予无穷大的惩罚，将约束问题转化为无约束问题。

惩罚项特点：

包含有取值越来越大的正因子 $\mu$
对于容许点，惩罚项取值为0，对于非容许点，惩罚项取值为正

H-乘子法

H-乘子法罚因子不必趋于无穷大，而外部罚函数的罚因子要趋于无穷大，本质是为了防止Hesse矩阵条件数变得越来越坏，导致在计算中，数值稳定性变得越来越差。

拉格朗日乘子$\lambda$与罚因子$\mu$取值无关，只要求$\mu$的取值保证乘子序列收敛即可，不然会有无数个拉格朗日乘子，这是不可能的。

改进：

解决了外部罚函数因罚因子增大，导致的数值计算不稳定的问题。

乘子法是针对外部罚函数法的改进，外部罚函数法随着罚因子的增大，增广目标函数的Hesse矩阵条件数变得越来越坏，导致在计算中，数值稳定性变得越来越差，难以精确求解。

乘子法是在约束问题的Lagrange函数中加入相应的惩罚项，使得在求解无约束问题的时候，罚因子不必趋于无穷大就能得到约束问题的最优解，保证数值计算的稳定性。

终止准则

如果无约束问题的最优解$x^$是原规划问题的容许点，那么也是原问题的*最优解。

等式约束

罚因子$\mu$的作用

a. 乘子序列${\lambda_k}$不收敛 ${\mu} <\mu^*$

b. 收敛的慢 ${\mu}\geq \mu^*$但不够大

c. $\frac{h(xk)}{h(x{k-1})} \geq 1$ 乘子序列${\lambda_k}$发散

d.$\frac{h(xk)}{h(x{k-1})}$介于$(0,1)$ 收敛，比值越小，收敛越快

终止准则：$h(x)=0$

不等式约束

$min\{s(x),\frac{v^k}{2u}\}=0 \\ h(x)=0$

一般形式算法中的终止条件：（平方和开根号）

$\varphi_k=[\sum{(min\{s(x_k),\frac{v^k}{2\mu}\})^2}+\sum{h^2_i(x_k)}]^{1/2}$

若$\varphi_k < \epsilon$：终止

若$\frac{\varphik}{\varphi{k-1}}\geq\theta$：放大罚因子 $\mu = c*\mu$，其中 $\theta \in (0,1)$，比值太大说明收敛效果不好，要放大罚因子。

只有等式约束时 $\frac{h(xk)}{h(x{k-1})}\geq\theta$放大罚因子