非线性规划
实例与定义
本来打算省出写博客的时间多看几页书……然而不写博客效率扑街，所以我又回来辽
非线性规划的定义在上一章中已经提到过，不重复了
与线性规划的区别
如果线性规划的优解存在，其优解只能在其可行域的边界上达到（特别是可行域的顶点上达到）；而非线性规划的优解（如果优解存在）则可能在其可行域的任意一点达到。
matlab解法
Matlab中非线性规划的数学模型写成以下形式
其中f(x)是标量函数，A,B，Aeq，Beq是相应维数的矩阵和向量，C(x) ，Ceq(x) 是非线性向量函数
求解非线性规划的基本迭代格式
对于线性函数来说，求出的最优解就是整个可行域上的全局最优解，但非线性规划则不然。
对于非线性函数，可以采用迭代法求其最优解。迭代法的基本思想是：从一个选定的初始点 $x^0\in R^n$ 出发，按照某一特定的迭代规律产生一个点列 $\{x^k\}$ ，使得当 $\{x^k\}$ 是有穷点时，其最后一个点是最优解；当 $\{x^k\}$ 是无穷点列时，它有极限点，并且其极限点是最优解。
设 $x^0\in R^n$ 是某迭代方法的第 k 轮迭代点， $x^{k+1}\in R^n$ 是第 k+1 轮迭代点，记
这里 $t_k\in R^1(步长),p^k\in R^n(第k轮搜索方向),||p^k||=1$ 式（1）就是求解非线性规划模型的基本迭代格式
求解的一般步骤如下：
- 选取初始点 x^0^ ，令 k = 0
- 构造搜索方向，按照一定规则，构造 $f$ 在点 $x^k$ 处关于 $K$ 的可行下降方向（简介略）作为搜索方向 $p^k$
- 寻求搜索步长。以 $x^k$ 为起点沿搜索方向 $p^k$ 寻求适当的步长 $t_k$ ，使目标函数值有某种意义的下降
- 求出下一个迭代点，若 $x^{k+1}$ 已满足某种终止条件，则停止迭代
- 以 $x^{k+1}$ 代替 $x^k$ ，回到第二步
好了，重新写了一遍终于把这个步骤看懂了
这里的步骤里提到了，在构造搜索方向和搜索步长时要按照一定规律，接下来就学习如何构造
无约束问题
一维搜索方法
即沿某一已知方向求目标函数的极小点。常用的有：
- 试探法（斐波那契法，0.618法）
- 插值法（抛物线插值法，三次插值法）
- 微积分中的求根法（切线法，二分法）
假设我们考虑一维极小化问题
若 $f(t)$ 是 $[a,b]$ 区间上的下单峰函数，我们可以通过不断地缩短 $[a,b]$ 的长度来搜索近似最优解 $t^*$
在 $[a,b]$ 中任取两个关于区间对称的点 $ t_1,t_2（t_2<t_1）$ 叫做搜索点，计算 $f(t_1)、f(t_2)$ 并比较其大小。
对于单峰函数：
若 $f(t_2)<f(t_1)$，则 $t^*\in [a,t_1]$ ，因而 $[a,t_1]$ 是缩短了的单峰区间
若 $f(t_2)>f(t_1)$，则 $t^*\in [t_2,b]$ ，因而 $[t_2,b]$ 是缩短了的单峰区间
若 $f(t_2)=f(t_1)$，则$[a,t_1]$ $[t_2,b]$ 都是缩短了的单峰区间
下面是一些个选取探索点的规则
Fibonacci法
使用对称搜索的方法，逐步缩短所考察的区间，能以尽量少的函数求值次数，达到预定的某一缩短率
步骤如下
选取初始数据，确定单峰区间 $[a_0,b_0]$ ，给出搜索精度 $ \delta>0 $ ，由公式
确定搜索次数 n
$k=1,a=a_0,b=b_0$ ，由公式
计算 $t_1和t_2$
当进行至 t_1=$k=n-1$ 时，$t_1=t_2=\frac{1}{2}(a+b)$ ，这就无法再进行比较了。因此，取
其中 $ \varepsilon $ 为任意小的数，在 $t_1 t_2$ 这两点中，以函数值较小者为近似极小点，相应的函数值为近似极小值，并得最终区间 $[a,t_1]$ 或 $[t_2,b]$ 。
0.618法
黄金分割数 $\omega$ 和 $Fibonacci$ 分数之间有着重要的关系
现用不变的区间缩短率 0.618，代替斐波那契法每次不同的缩短率，就得到了黄金分割法（0.618 法）。这个方法可以看成是斐波那契法的近似，实现起来比较容易，效果也相当好，因而易于为人们所接受
0.618 法是一种等速对称进行试探的方法，每次的探索点均取在区间长度的 0.618 倍和 0.382 倍处。
二次插值法
对极小化问题，当函数在这个区间上连续时，可以考虑用多项式插值来进行一维搜索。它的基本思想是：在搜索区间中，不断用低次（通常不超过三次）多项式来近似目标函数，并逐步用插值多项式的极小点来逼近最优解。
