非线性规划的一般形式

基本概念

1. 邻域：开球
   

2. 局部最优解：能找到一个邻域使得该点是邻域与可行域交集中的最优解，退化到一维模型就是极值点。
   

3. 全局最优解：整个可行域中的最优解，退化到一维模型就是最小值点。
   

4. 严格局部最优解和严格全局最优解：上述定义中的$\leq$≤换成$<$<。

5. 梯度（标量函数）：多元函数对每一个自变量分量求偏导，结果是列向量。
   

6. 梯度（向量函数）
   

7. 海塞矩阵
   

8. 求导法则：与一元函数基本一致
   （1）对向量函数的点积求偏导
   

   （2）对常数矩阵和向量函数的乘积求偏导
   
   （3）对二次函数求偏导
   

9. 泰勒展开
   （1）一元函数（假设存在连续的二阶导数）
   
   （2）多元函数 （沿着某个方向的泰勒展开，实际上就是一元函数）
   
   

凸函数和凹函数

1. 凸函数：凸组合的函数小于等于函数的凸组合。退化到一维模型中就是函数上任意两点的连线在函数曲线的上方。
   
2. 一元凸函数的判定。
   （1） 定义法。
   （2） 一阶导数：切线在连线下方
   $f'(x_1) \leq \frac{f(x_2)-f(x_1)}{x_2-x_1}$f′(x1​)≤x2​−x1​f(x2​)−f(x1​)​
   （3）二阶导数：一阶导数单调递增
   $f''(x) \geq 0$f′′(x)≥0
3. 多元凸（凹）函数的判定：
   （1）任意方向上的一元函数都是凸函数。方向和原点都是任意取的。
   
   （2）一阶导数
   
   （3）二阶导数
   

凸规化

1. 凸规化的定义：可行域是凸集，目标函数是连续凸函数。
   
2. 凸规划的性质：任意一个局部最优解就是全局最优解。
3. 可行下降方向：既可行又能下降的方向。
   
4. 求解非线性规划的基本途径是迭代。
   $X_{k+1} = X_{k} + \lambda_{k} D_{k}$Xk+1​=Xk​+λk​Dk​
   （1）确定初始可行解$X_{0}$X0​。
   （2）确定可行下降方向$D_{0}$D0​。
   （3）一维搜索求$\lambda_{0},X_{1}$λ0​,X1​。
   $X_{1} = X_{0}+\lambda_{0} D_{0}。$X1​=X0​+λ0​D0​。
   （4）将$X_{1}$X1​作为新的的可行解，重复步骤(2)~(3)，直到不存在可行下降方向。

一维搜索

1. 问题的提出：在求凸规划问题的过程中，假设我们已知了一个初始解$X_{0}$X0​和可行下降方向$D_{0}$D0​，那么如何在该方向上找到一个更优的点呢？（即目标函数值更小）
2. 一维精确搜索：寻找一元函数的最小值。
   
3. 一维非精确搜索：找一个比当前的结果好一点的点，并不要求是最优。
   
4. 一维精确搜索的性质：新找到的点和梯度与搜索方向正交。
   
5. 精确搜素的基本途径。
   （1）确定初始区间（单谷区间）。
   （2）压缩区间，直到区间长度小于给定阈值。
6. 区间压缩原理：比较区间内两点的函数值。
   
7. 0.618法：每次压缩区间变成原来的0.618倍。
   注意：
   （1）除了第一步，每次只需计算一个新增点和其函数值（第一步需要两次）。
   （2）迭代停止后最优解的选取：区间的中点。
8. Fibonacci法：设$F_{n}$Fn​是斐波那契数列的第n项，恰好是某个区间长度。则通过计算n点的函数值，能将该区间压缩到一个单位长度。
   
   
9. 利用导数的精确搜索：区间对分。
   我们求的最小值实际上就是该函数的极小值，即导数为0的点。确定了初始的单谷区间后，两个端点的导数一定是异号的，压缩比是0.5。
   
   
10. 利用二阶导数的精确搜索：牛顿法。
    

无约束优化：$\min_{x∈R^{n}}f(X)$minx∈Rn​f(X)

1. 基本假设：目标函数具有二阶导数
2. 无约束优化的局部最优性条件
   （1）必要条件（是极值点）：$\nabla f(X^{*})=0$∇f(X∗)=0
   （2）充分条件（是极小值点）：$\nabla f(X^{*})=0,\nabla^{2}f(X^{*})=0$∇f(X∗)=0,∇2f(X∗)=0
3. 基本方法：下降方向法
   （1）任取$X∈R^{n}$X∈Rn
   （2）如果在X处最优（即找不到下降方向），则停止。否则，确定下降方向$D∈R^{n}$D∈Rn
   （3）利用一维精确搜索的方法在方向D上寻找最小值，即求解下面的优化问题：
   $\min g(t) \\ g(t) = f(X+tD)$ming(t)g(t)=f(X+tD)
   （4）用$X+tD$X+tD替换X，返回（2）继续迭代。
   于是问题的关键在于如何寻找下降方向D？
4. 梯度下降法：$D=-\nabla f(X)$D=−∇f(X)
   （1）下降方向：该点的负梯度方向，在小邻域中的下降方向是最好的。
   （2）缺点：寻优速度太慢。
   （3）特点：相邻两点的寻优方向正交。
   
   （4）改进思路：改进寻优方向。