数学建模（三）：非线性规划问题

&1.非线性规划
1.当一个规划问题的约束条件或者是目标函数中包含至少一个非线性函数，那么这种规划问题就是⎡非线性规划问题⎦。
举个例子说明：
设决策变量x_i的意义为对第i个项目投资与否，则x_i=1代表对这个项目投资，x_i=0代表对这个项目不投资；可以得到对于投资金额来说，由于至少要对一个项目投资，并且总投资金额不能超过总资金A

对于决策变量，它是一个只能二元取值的变量，所以有x_i(1-x_i)=0,i=1,2,…,n
我们这里对于投资收益最大化的理解是投资总收益与总投资的比值最大化，所以这个规划问题综上所述可以表示为

《数学建模算法与应用》中还给出了对于一个实际问题把它转化为非线性规划问题的注意要点，但过于泛泛而谈，以至于光看这些注意要点对于所有的规划问题都能成立。我认为非线性规划问题在建模时应当注意⎡是否有必要引入非线性的目标函数和约束条件⎦，一个线性规划问题总是比非线性规划问题容易求得最优解，因为线性规划问题的最优解总是会在问题的可行域的边界上，而非线性规划问题的最优解却可以存在于问题的可行域中的任意一点；
非线性规划是可以通过matlab的FMINCON函数求解的；

2.如何求解非线性规划问题？
一种方法是迭代法。在讲述迭代法之前，我们需要知道整体最优解、严格整体最优解、局部最优解和严格局部最优解的定义，这里假定你已经知道了这些概念代表的含义。使用迭代法的基本思想是：选定初始点x⁰∈Rⁿ，按照某种特定的迭代规则，可以由x⁰产生一系列的解，由它们组成点集{x^k}：
1）当{x^k}中元素个数是有限时，那该点集的最优一个点就是该非线性规划问题的最优解；
2）当{x^k}中元素个数是无限时，那么它有极限点，并且这个极限点就是非线性规划问题的最优解；
假设x^k∈Rⁿ是第k轮迭代点，那么在它不是NP问题（Non-linear Programming，非线性规划）最优解情况下，它必定有下一个迭代点x^k+1，它们之间的关系满足：

x^k+1=x^k+t_kp^k

式中的t_k是一个实数，p^k∈Rⁿ，||p^k||=1，并且p^k方向为从x^k向x^k+1的方向。这里的p^k我们称它为第k轮搜索方向，t_k我们称它为沿p^k方向的步长。
我们引入两个概念下降方向和可行方向：
1）下降方向：指当存在大于0的步长，使得目标函数在第k+1轮迭代中的结果小于第k轮迭代结果，此时的p^k方向称为目标函数在x^k点的下降方向；
2）可行方向：指当存在大于0的步长，使得第k+1轮的迭代结果在NP问题的可行域K中，此时的p^k方向称为x^k点关于可行域K的可行方向；
既是可行方向又是下降方向，我们称之为可行下降方向；接下来给出基本迭代格式求解NP问题的一般步骤：
0^。选取初始点x⁰，令k=0；
1^。构造搜索方向，按照迭代规则，得到可行下降方向p^k；
2^。寻找合适的步长t_k，求出x^k+1;若满足终止条件，则停止迭代；
3^。以x^k+1代替x^k，返回1^。步；

3.凸函数、凸规划
凸函数、严格凸函数的定义我们在此略去，考虑非线性规划
假定f(x)为凸函数，g_j(x)为凸函数，那么这样的规划称为凸规划。凸规划的可行域一定是凸集，它的局部最优解就是全剧最优解，它的最优解的集合可以形成一个凸集。当目标函数f(x)是严格凸函数时，假如凸规划问题有最优解，它的最优解是唯一的。

&2.无约束问题
1.一维搜索方法
沿某一已知方向求目标函数的极小值。常用的一维搜索方法：（1）试探发（Fibonacci法，黄金比例法）；（2）插值法（抛物线插值法，三次插值法）；（3）微积分中的求根法（切线法，二分法等）
在讲述详细的搜索方法之前，我们先考虑一维极小化问题，假设函数f(t)在a≤t≤b范围内有唯一的极值，那么我们通过不断缩短区间，来寻求近似最优解t^*；在[a,b]区间中任取两个关于(a+b)/2对称的点t₁,t₂，假定t₁<t₂，通过测定法f(t₁)和f(t₂)的值，我们可以得到：
1）若f(t₁)<f(t₂)，则必有t^*∈[a,t₂]；
2）若f(t₂)<f(t₁)，则必有t^*∈[t₁,b]；
3）若f(t₁)=f(t₂)，则必有t^*∈[t₁,t₂]；
(4.22 后续待更新)