文档介绍：第十一章 非线性规划 Nonlinear Programming
§11-1 非线性规划概述
§11-2 一维搜索
§11-3 无约束优化
§11-4 有约束优化
§11-5 投资组合决策分析
§11-6 非线性规划1-1 非线性规划概述——凸函数
*
Page * of 88
4. 凸函数的极值
一般而言，局部极小不等于全局极小；
对于凸函数而言，任一局部极小就等于全局极小。
5. 凸规划
对于一般的数学规划
若f(X)凸，gi(X)凹，则称之为凸规划。
可以证明，凸规划所对应的可行域为凸集，所以，对于凸规划求到一个局部极小，即为全局极小。
§11-1 非线性规划概述——凸函数
*
Page * of 88
四、无约束下降类算法步骤
采用逐步迭代算法：
步骤：
1）确定初始点X0 ；
2）确定搜索方向Pk
3）确定步长
4）终止准则
§11-1 非线性规划概述——算法步骤
*
Page * of 88
作业：教材
§11-1 非线性规划概述
*
Page * of 88
§11-2 一维搜索
一维搜索即求单变量函数的极值问题，其方法很多，可概括为二类
（1）试探法： 分数法；
（2）插值法： 切线法；抛物线法
*
Page * of 88
§11-2 一维搜索——分数法（Fibonacci方法）
原理：
思想：函数f(t)在[a , b ]区间内有极小点t* ，逐步缩小该区间直至[ar ,br ]，使其宽度满足精度要求为止。
取点：可以证明，按Fibonacci方法取点是最优的。
（见邓乃杨所著《运筹学》）
Fibonacci级数
一、分数法（Fibonacci方法）
*
Page * of 88
算法步骤：
根据精度要求确定取点数n：
精度要求有：绝对精度：
相对精度：
根据给定的精度ε和初始区间[a，b] ，确定取点数n：
根据Fn查Fibonacci级数表，确定取点数n 。
§11-2 一维搜索——分数法（Fibonacci方法）
*
Page * of 88
第一取点，取两点t1，t1’，按 Fn-1/Fn 的比例。
§11-2 一维搜索——分数法（Fibonacci方法）
*
Page * of 88
第二次取点，取一点t2(或t2’)，从t1和t1’中选择函数值较大者，作为新的边界点。如图：
§11-2 一维搜索——分数法（Fibonacci方法）
*
Page * of 88
第k次取点，取点tk （或tk’）如图 所示：
第n-1次取点：取点tn-1 (或t’n-1)，取点比例为
两者较小者即为所求
极小点。
§11-2 一维搜索——分数法（Fibonacci方法）
*
Page * of 88
例11-2：试用分数法求函数 在区间[-2,2]上近似的极小点和近似极小值，。
解：不难验证，函数 是区间[-2,2]上仅有唯一极小点的单峰函数。极小点为 ，极小值为 ，以供下面求解验证。
要求绝对误差
查Fibonacci级数表得 n=7，又知道区间端点为
§11-2 一维搜索——分数法（Fibonacci方法）
*
Page * of 88
§11-2 一维搜索——分数法（Fibonacci方法）
*
Page * of 88
§11-2 一维搜索——分数法（Fibonacci方法）
*
Page * of 88
并取x6=，近似极小值为f(x6)=
不难验证：
即为所求。
§11-2 一维搜索——分数法（Fibonacci方法）
*
Page * of 88
二、（黄金分割术）
在Fibonacci搜索法中，若用n个点来缩短区间长度时，其各次缩短率分别为：
这些值是在逐步变动的。这种取点方式虽然是最优的，但每次变动的区间缩短率却给计算带来一定的麻烦。如果每次缩短区间长度都按固定比值来进行，那计算起来就方便多了，。
§11-2 一维搜索——（黄金分割术）
*
Page * of 88
事实上，fibonacci搜索法的缩短率的极限为：