Page 158 - 数学建模算法与应用

Mathematical Modeling Algorithms and Applications
数学建模算法与应用

则称 f (x) 为定义在 R 上的严格凸函数。
考虑非线性规划

假定其中 f (x) 为凸函数，g j (x)( j =1，2，L，l) 为凸函数，这样的非线性规
划称为凸规划。
可以证明，凸规划实现的域是凸集，其局部最优解是全局最优解，最优解集

形成凸集。如果凸规划目标函数 f（x）是严格凸的，则其最优解必须是唯一的（假
设最优解存在）。可以看出，凸规划是一种相对简单且理论上重要的非线性规划。

第二节 无约束问题解决

一、一维搜索方法

迭代方法用于找到函数的最小点，这意味着在已知方向上找到目标函数的最
小值。一维搜索有很多方法，包括常用的方法：（1）试探法（斐波那契法，0.618

法等）；（2）插值法（三次插值法等）；（3）微积分中的求根法（二分法等）。
考虑一维极小化问题

（2）
若 f (t) 是[a，b] 区间上的下单峰函数，我们介绍通过不断地缩短[a，b] 的长度，
来搜索得（2）的近似最优解的两个方法。
为了缩短区间 [a，b] ，逐步搜索得（2）的最优解 t* 的近似值，我们可以采
用以下途径：在 [a，b] 中任取两个关于 [a，b] 是对称的点 t1 和 t2 （不妨设 t2 <

t1 ，并把它们叫做搜索点），计算 f (t1 )和 f (t2 ) 并比较它们的大小。对于单峰函数，
若 f (t2 ) < f (t1 ) ，则必有 t* ∈ [a，t1 ] ，因而 [a，t1 ] 是缩短了的单峰区间；若
f (t1 )<f (t2 ) ，则有 * t b t ∈ ，故 [t2 ，b] 是缩短了的单峰区间；若 f (t2 ) = f (t1 )，

则 [a，t1 ] 和 [t2 ，b] 都是缩短了的单峰。因此通过两个搜索点处目标函数值大
小的比较，总可以获得缩短了的单峰区间。对于新的单峰区间重复上述做法，显
然又可获得更短的单峰区间。如此进行，在单峰区间缩短到充分小时，我们可以

148