第三章非线性规划 §1非线性规划 1.1非线性规划的实例与定义 如果目标函数或约束条件中包含非线性函数，就称这种规划问题为非线性规划问 一般说来，解非线性规划要比解线性规划问题因难得多。而且，也不象线性规划 一通用方法，非线性规划日前还没有适于各种问题的一般算法，各个方法都 有目已 下面 概 的阴出非线性规划数学模型的一般形式，介绍有关非线性提划的基本 例1（投资决策问题）某企业有n个项日可供选择投资，并且至少要对其中一个 项目投资。己知该企业拥有总资金A元，投资于第i=,n)个项目需花资金a,元 并预计可收益b元。试选择最佳投资方案。 解设投资决策变量为 x=人决定投资第个项目 0.决定不投资第个项目1=L,n 则投资总额为∑，x,投资总收益为∑bX。因为该公司至少要对一个项目投资，并 且总的投资金额不能超过总资金A,故有限制条件 另外，由于x,(i=1,.,n)只取值0或1，所以还有 x1-x)=0i=1.,n. 最佳投资方案应是投资额最小而总收益最大的方案，所以这个最佳投资决策问题归 结为总资金以及决策变量（取0或1）的限制条件下，极大化总收益和总投资之比。因 此，其数学模型为： 2 02aA x,(1-x,)=0,i=1,.,n. 上面例题是在一组笔式或不等式的约束下，求一个函数的最大值（或最小值）问 题，其中至少有一个非线性函数，这类问题称之为非线性规划问题。可概括为一般形式 min f(x) st.h,(x)s0,j=1,.,q (NP) g,(x)=0i=1.,p -32
-32- 第三章 非线性规划 §1 非线性规划 1.1 非线性规划的实例与定义 如果目标函数或约束条件中包含非线性函数，就称这种规划问题为非线性规划问 题。一般说来，解非线性规划要比解线性规划问题困难得多。而且，也不象线性规划有 单纯形法这一通用方法，非线性规划目前还没有适于各种问题的一般算法，各个方法都 有自己特定的适用范围。 下面通过实例归纳出非线性规划数学模型的一般形式，介绍有关非线性规划的基本 概念。 例 1 （投资决策问题）某企业有 n 个项目可供选择投资，并且至少要对其中一个 项目投资。已知该企业拥有总资金 A 元，投资于第i(i = 1,L,n) 个项目需花资金ai 元， 并预计可收益bi 元。试选择最佳投资方案。 解 设投资决策变量为 ⎩ ⎨ ⎧ = ， 决定不投资第 个项目 决定投资第 个项目 i i xi 0 1, ，i = 1,L,n ， 则投资总额为 ∑= n i i i a x 1 ，投资总收益为 ∑= n i i i b x 1 。因为该公司至少要对一个项目投资，并 且总的投资金额不能超过总资金 A ，故有限制条件 ∑= < ≤ n i ai xi A 1 0 另外，由于 x (i 1, ,n) i = L 只取值 0 或 1，所以还有 x (1 x ) 0, i 1, ,n. i − i = = L 最佳投资方案应是投资额最小而总收益最大的方案，所以这个最佳投资决策问题归 结为总资金以及决策变量（取 0 或 1）的限制条件下，极大化总收益和总投资之比。因 此，其数学模型为： ∑ ∑ = = = n i i i n i i i a x b x Q 1 1 max s.t. ∑= < ≤ n i ai xi A 1 0 x (1 x ) 0, i 1, ,n. i − i = = L 上面例题是在一组等式或不等式的约束下，求一个函数的最大值（或最小值）问 题，其中至少有一个非线性函数，这类问题称之为非线性规划问题。可概括为一般形式 min f (x) s.t. hj(x) ≤ 0, j = 1,L, q (NP) gi(x) = 0, i = 1,L, p
其中x=[x1.x」称为模型(NP)的决策变量，∫称为目标函数，g,(i=L,.,p) 和h,(U=1,.,q)称为约束函数。另外，g,(x)=0(=1,.,p)称为等式约束 h,(x)≤0U=L,.,q)称为不等式的约束 对于 问题，在把它归结成非线性规划问题时 可 上 ,么是问题的 追求目 过 或极大化的目 运用各种科学 据实际 和可 数提要求授小化 （)给出价值标准 “坏”的价值标准，并用某种数量形式来描述它 (v)寻求限制条件：由于所追求的目标一般都要在一定的条件下取得极小化或 极大化效果，因此还需要寻找出问题的所有限制条件，这些条件通常用变量之间的一些 不等式或等式来表示。 1.2 线性规划与非线性规划的区别 点达 达到》而非线性规划的优解只能在可行城的边界上 minf(x) AxsB Aea.x=Bec C(x)≤0 Ceg(x)=0 其中fx)是标量函数，A,B,Aeq,Beg是相应维数的矩阵和向量，C(x),Ceg(x)是非 线性向量函数 Matlab中的命令是 A-FMIN N(FU 是用M文件定义的函数f(x):X0是x的初始值 A,B,Aeq,Beq定义了线性约束A*X≤B,Aeg*X=Beg,如果没有线性约束，则 A=门，B=门，Aeq=门，Beq=:LB和B是变量x的下界和上界，如果上界和下界没有约 束，则LB,B=门，如果x无下界，则LB的各分量都为-if,如果x无上界，则B 的各分量都为inf:NONLCON是用M文件定义的非线性向量函数C(x),Ceq(x):OPTIONS 定义了优化参数，可以使用Matlab缺省的参数设置。 例2求下列非线性规划 min f(x)=x2+x++8 stx2-x2+x3≥0 X++写≤20 -x22+2=0 -3
-33- 其中 T n x [x x ] = 1 L 称为模型（NP）的决策变量，f 称为目标函数，gi (i = 1,L, p) 和 h ( j 1, ,q) j = L 称为约束函数。另外， gi(x) = 0 (i = 1,L, p) 称为等式约束， hj(x) ≤ 0 ( j = 1,L,q) 称为不等式的约束。 对于一个实际问题，在把它归结成非线性规划问题时，一般要注意如下几点： （i）确定供选方案：首先要收集同问题有关的资料和数据，在全面熟悉问题的基 础上，确认什么是问题的可供选择的方案，并用一组变量来表示它们。 （ii）提出追求目标：经过资料分析，根据实际需要和可能，提出要追求极小化 或极大化的目标。并且，运用各种科学和技术原理，把它表示成数学关系式。 （iii）给出价值标准：在提出要追求的目标之后，要确立所考虑目标的“好”或 “坏”的价值标准，并用某种数量形式来描述它。 （iv）寻求限制条件：由于所追求的目标一般都要在一定的条件下取得极小化或 极大化效果，因此还需要寻找出问题的所有限制条件，这些条件通常用变量之间的一些 不等式或等式来表示。 1.2 线性规划与非线性规划的区别 如果线性规划的最优解存在，其最优解只能在其可行域的边界上达到（特别是可行 域的顶点上达到）；而非线性规划的最优解（如果最优解存在）则可能在其可行域的任 意一点达到。 1.3 非线性规划的 Matlab 解法 Matlab 中非线性规划的数学模型写成以下形式 min f (x) ⎪ ⎪ ⎩ ⎪ ⎪ ⎨ ⎧ = ≤ ⋅ = ≤ ( ) 0 ( ) 0 Ceq x C x Aeq x Beq Ax B , 其中 f (x)是标量函数， A, B, Aeq, Beq是相应维数的矩阵和向量，C(x),Ceq(x) 是非 线性向量函数。 Matlab 中的命令是 X=FMINCON(FUN,X0,A,B,Aeq,Beq,LB,UB,NONLCON,OPTIONS) 它的返回值是向量 x ，其中 FUN 是用 M 文件定义的函数 f (x)；X0 是 x 的初始值； A,B,Aeq,Beq 定义了线性约束 A* X ≤ B, Aeq * X = Beq ，如果没有线性约束，则 A=[],B=[],Aeq=[],Beq=[]；LB 和 UB 是变量 x 的下界和上界，如果上界和下界没有约 束，则 LB=[]，UB=[]，如果 x 无下界，则 LB 的各分量都为-inf，如果 x 无上界，则 UB 的各分量都为 inf；NONLCON 是用 M 文件定义的非线性向量函数C(x),Ceq(x) ；OPTIONS 定义了优化参数，可以使用 Matlab 缺省的参数设置。 例2 求下列非线性规划 min ( ) 8 2 3 2 2 2 f x = x1 + x + x + s.t. 0 2 2 3 2 x1 − x + x ≥ 20 3 3 2 x1 + x2 + x ≤ 2 0 2 − x1 − x2 + =
为2+2x=3 x1,x2,x3≥0 解(i)编写M文件funl.m定义目标函数 (i)编写M文件Eun2.m定义非线性约束条件 :不 x(2)+2*x(3)^2-3]；号非线性等式约束 (ii)编写主程序文件example2.m如下： opti fun2',options) 就可以求得当x-0.5522,x2=1.2033,x=0.9478时，最小值y=10.6511。 1.4求解非线性规划的基本迭代格式 记(NP)的可行域为K】 若xeK,并且 f(x')sf(x,x∈K 则称x是(NP)的整体最优解，f(x)是NP)的整体最优值。如果有 f(x)<f(x)xeK,x≠x 则称x是(NP)的严格整体最优解，f(x)是NP)的严格整体最优值。 若x'∈K,并且存在x'的邻域N,(x),使 f(x)sf(x).VxeN (x')nK. 则称x是(NP)的局部最优解，f(x')是NP)的局部最优值。如果有 f(x')<f(x).VxeN;(x')nK 则称x是(NP)的严格局部最优解，f(x)是(NP)的严格局部最优值 函数为 非线性 不 而求出的最优解就是整 可行域上 的极值点，但却并不 定是整个可行域上的全局最优解 对于非线性规划模型NP),可以采用迭代方法求它的最优解。迭代方法的基本思 想是：从一个选定的初始点x°∈R”出发，按照某一特定的迭代规则产生 个占 {x},使得当{x}是有穷点列时，其最后一个点是NP)的最优解：当{x}是无穷点 列时，它有极限点，并且其极限点是NP)的最优解。 设x∈R”是某迭代方法的第k轮迭代点，x+∈R”是第k+1轮迭代点，记 x= (1) 这里14∈R,p∈R",p=1,并且p*的方向是从点x向着点x+的方向。式(I) 就是求解非线性规划模型(NP)的基本迭代格式。 -34
-34- 2 3 2 x2 + x3 = x1, x2 , x3 ≥ 0 解 （i）编写 M 文件 fun1.m 定义目标函数 function f=fun1(x); f=sum(x.^2)+8; （ii）编写M文件fun2.m定义非线性约束条件 function [g,h]=fun2(x); g=[-x(1)^2+x(2)-x(3)^2 x(1)+x(2)^2+x(3)^3-20]; %非线性不等式约束 h=[-x(1)-x(2)^2+2 x(2)+2*x(3)^2-3]; %非线性等式约束 （iii）编写主程序文件 example2.m 如下： options=optimset('largescale','off'); [x,y]=fmincon('fun1',rand(3,1),[],[],[],[],zeros(3,1),[], . 'fun2', options) 就可以求得当 x1 = 0.5522, x2 =1.2033, x3 = 0.9478 时，最小值 y =10.6511。 1.4 求解非线性规划的基本迭代格式 记（NP）的可行域为 K 。 若 x ∈ K * ，并且 f (x ) ≤ f (x), ∀x ∈ K * 则称 * x 是（NP）的整体最优解， ( ) * f x 是(NP)的整体最优值。如果有 * * f (x ) < f (x), ∀x ∈ K, x ≠ x 则称 * x 是（NP）的严格整体最优解， ( ) * f x 是(NP)的严格整体最优值。 若 x ∈ K * ，并且存在 * x 的邻域 ( ) * N x δ ，使 f (x ) f (x), x N (x ) I K * * ≤ ∀ ∈ δ ， 则称 * x 是（NP）的局部最优解， ( ) * f x 是(NP)的局部最优值。如果有 f (x ) f (x), x N (x ) I K * * < ∀ ∈ δ 则称 * x 是（NP）的严格局部最优解， ( ) * f x 是(NP)的严格局部最优值。 由于线性规划的目标函数为线性函数，可行域为凸集，因而求出的最优解就是整 个可行域上的全局最优解。非线性规划却不然，有时求出的某个解虽是一部分可行域上 的极值点，但却并不一定是整个可行域上的全局最优解。 对于非线性规划模型(NP)，可以采用迭代方法求它的最优解。迭代方法的基本思 想是：从一个选定的初始点 n x ∈ R 0 出发，按照某一特定的迭代规则产生一个点列 { } k x ，使得当{ } k x 是有穷点列时，其最后一个点是(NP)的最优解；当{ } k x 是无穷点 列时，它有极限点，并且其极限点是(NP)的最优解。 设 k n x ∈ R 是某迭代方法的第k 轮迭代点， k n x ∈ R +1 是第k +1轮迭代点，记 k k k k x = x + t p +1 （1） 这里 , , 1 1 ∈ ∈ = k n k tk R p R p ，并且 k p 的方向是从点 k x 向着点 k +1 x 的方向。式（1） 就是求解非线性规划模型(NP)的基本迭代格式
通常，我们把基本逃代格式(1)中的p称为第k轮搜索方向，1为沿p方向的 长。使用选代方法求解9尚关健在于奥何造一轮的案方向和确适当的步 设x∈R”,p≠0，若存在6>0，使 f(+p)<f(),te(0,), 称向量P是∫在点下处的下降方向。 设x∈R",P≠0，若存在1>0，使 x+p∈K, 称向量P是点x处关于K的可行方向。 一个向量P,若既是函数∫在点天处的下降方向，又是该点关于区域K的可行方 向，称之为函数∫在点处关于K的可行下降方向 现在，我们给出用基本迭代格式(I)求解NP)的一般步骤如下： 0°选取初始点x°，令k=0。 1°构造搜索方向，依照一定规划，构造∫在点x处关于K的可行下降方向作为 搜索方向p。 2°寻求搜索步长。以x·为起点沿搜索方向p寻求适当的步长(，使日标函数值 个迭代点。按迭代格式(1)求出 xl=x+1p。 若x1已满足某种终止条件，停止迭代」 4以x代替x 15凸函数 设f(x)为定义在n维欧氏空间E中某个凸集R上的函数，若对任何实数 a(0<a<I)以及R中的任意两点x和x),恒有 f(aam+(1-a)x2)sa(x")+(1-a)fx2) 则称f(x)为定义在R上的凸函数。 若对每一个a(0<a<1)和x≠x2)∈R恒有 f(aa+(1-a)x2)<cgf(x)+(1-a)f（x2) 则称f(x)为定义在R上的严格凸函数。 考虑非线性规划 min f(x) R={xlg(x)≤0，j=1,2,.,1 假定其中f(x)为凸函数，8，(x=1,2,)为凸函数，这样的非线性规划称为 凸规 可以证明，凸规划的可行域为凸集，其局部最优解即为全局最优解，而且其最仍 解的集合形成一个凸集。当凸规划的目标函数(x)为严格凸函数时，其最优解必定唯 一（假定最优解存在）。由此可见，凸规划是一类比较简单而又其有重要理论意义的非 -35-
-35- 通常，我们把基本迭代格式（1）中的 k p 称为第k 轮搜索方向， kt 为沿 k p 方向的 步长，使用迭代方法求解(NP)的关键在于，如何构造每一轮的搜索方向和确定适当的步 长。 设 x ∈ R , p ≠ 0 n ，若存在δ > 0 ，使 f (x + tp) < f (x), ∀t ∈(0,δ )， 称向量 p 是 f 在点 x 处的下降方向。 设 x ∈ R , p ≠ 0 n ，若存在t > 0，使 x + tp ∈ K ， 称向量 p 是点 x 处关于 K 的可行方向。 一个向量 p ，若既是函数 f 在点 x 处的下降方向，又是该点关于区域 K 的可行方 向，称之为函数 f 在点 x 处关于 K 的可行下降方向。 现在，我们给出用基本迭代格式（1）求解(NP)的一般步骤如下： 0° 选取初始点 0 x ，令k := 0 。 1° 构造搜索方向，依照一定规划，构造 f 在点 k x 处关于 K 的可行下降方向作为 搜索方向 k p 。 2° 寻求搜索步长。以 k x 为起点沿搜索方向 k p 寻求适当的步长 kt ，使目标函数值 有某种意义的下降。 3° 求出下一个迭代点。按迭代格式（1）求出 k k k k x = x + t p +1 。 若 k +1 x 已满足某种终止条件，停止迭代。 4° 以 k +1 x 代替 k x ，回到 1°步。 1.5 凸函数、凸规划 设 f (x) 为定义在 n 维欧氏空间 (n) E 中某个凸集 R 上的函数，若对任何实数 α(0 <α <1) 以及 R 中的任意两点 (1) x 和 (2) x ，恒有 ( (1 ) ) ( ) (1 ) ( ) (1) (2) (1) (2) f αx + −α x ≤αf x + −α f x 则称 f (x)为定义在 R 上的凸函数。 若对每一个α(0 <α <1) 和 x ≠ x ∈R (1) (2) 恒有 ( (1 ) ) ( ) (1 ) ( ) (1) (2) (1) (2) f αx + −α x <αf x + −α f x 则称 f (x)为定义在 R 上的严格凸函数。 考虑非线性规划 ⎪⎩ ⎪ ⎨ ⎧ = ≤ = ∈ { | ( ) 0, 1,2, , } min ( ) R x g x j l f x j x R L 假定其中 f (x)为凸函数，g (x)( j 1,2, ,l) j = L 为凸函数，这样的非线性规划称为 凸规划。 可以证明，凸规划的可行域为凸集，其局部最优解即为全局最优解，而且其最优 解的集合形成一个凸集。当凸规划的目标函数 f (x)为严格凸函数时，其最优解必定唯 一（假定最优解存在）。由此可见，凸规划是一类比较简单而又具有重要理论意义的非
线性规划。 2无钓束方法 当用迭代法求函数的极小点时，常常用到一维搜索，即沿某一已知方向求目标函数 的扔小、占 一维搜索的方法很多，常用的有：(1)试探法(“成功一失败”，斐波那契法】 0.618法等)：(2)插值法（抛物线插值法，三次插值法等）：(3)微积分中的求根法（切 线法，二分法等)。 考虑一维极小化问题 min f(t) (2) 若f(t)是[a,b]区间上的下单峰函数，我们介绍通过不断地缩短[a,b]的长度，来 搜索得(2)的近似最优解的两个方法。 为了缩短区间[a,b],逐步搜索得(2)的最优解的近似值，我们可以采用以下 途径：在[a,b]中任取两个关于[a,b]是对称的点1和1，（不妨设12<1，并把它们叫 做搜索点)，计算f(L,)和f(1,)并比较它们的大小。对于单峰函数，若(1，)<「(1) 则必有t∈[a,4】,因而[a,4]是缩短了的单峰区间：若f化)<f),则有 t'∈[2，b,故[2，b是缩短了的单蜂区间：若f(2)=f(%,),则[a,4]和2，b都是 缩短了的单峰。因此通过两个搜索点处目标函数值大小的比较，总可以获得缩短了的单 峰区间。对于新的单峰区间重复上述做法 显然又可获得更短的单峰区间。如此进行 在单峰区间缩短到充分小时，我们可以取最后的搜索点作为(2)最优解的近似值。 应该按照怎样的规则来选取探索点，使给定的单峰区间的长度能尽快地缩短？ 2.L1 Fibonacci法 如用F表示计算个函数值能缩短为单位长区间的最大原区间长度，可推出F满 足关系 Fn=Fn-2+Fn-n=2,3. 数列{F}称为Fibonacci数列，Fn称为第n个Fibonacei数，相邻两个Fibonacci数之 比F二称为Fbac分数. 当用斐波邦契法以个探索点来缩短某一区间时，区间长度的第一次缩短率为 ，后各改分测为合会一青.自比，者私和L<)是单区同 F 中第1个和第2个探索点的话，那么应有比例关系 -a=a,-0=2 b-aF。 b-a F 从而 4=a+(b-a,5=a+2(b-a) (3) n 它们关于[a,)确是对称的点。 -36
-36- 线性规划。 §2 无约束问题 2.1 一维搜索方法 当用迭代法求函数的极小点时，常常用到一维搜索，即沿某一已知方向求目标函数 的极小点。一维搜索的方法很多，常用的有：（1）试探法（“成功—失败”，斐波那契法， 0.618 法等）；（2）插值法（抛物线插值法，三次插值法等）；（3）微积分中的求根法（切 线法，二分法等）。 考虑一维极小化问题 min f (t) a≤t≤b （2） 若 f (t) 是[a,b] 区间上的下单峰函数，我们介绍通过不断地缩短[a,b] 的长度，来 搜索得（2）的近似最优解的两个方法。 为了缩短区间[a,b] ，逐步搜索得（2）的最优解 * t 的近似值，我们可以采用以下 途径：在[a,b] 中任取两个关于[a,b] 是对称的点 1 t 和 2t （不妨设 2 1 t < t ，并把它们叫 做搜索点），计算 ( )1 f t 和 ( ) 2 f t 并比较它们的大小。对于单峰函数，若 ( ) ( ) 2 1 f t < f t ， 则必有 [ , ]1 * t ∈ a t ，因而 [ , ]1 a t 是缩短了的单峰区间；若 ( ) ( ) 1 2 f t < f t ，则有 [ , ] 2 * t ∈ t b ，故[ , ] 2t b 是缩短了的单峰区间；若 ( ) ( ) 2 1 f t = f t ，则[ , ]1 a t 和[ , ] 2t b 都是 缩短了的单峰。因此通过两个搜索点处目标函数值大小的比较，总可以获得缩短了的单 峰区间。对于新的单峰区间重复上述做法，显然又可获得更短的单峰区间。如此进行， 在单峰区间缩短到充分小时，我们可以取最后的搜索点作为（2）最优解的近似值。 应该按照怎样的规则来选取探索点，使给定的单峰区间的长度能尽快地缩短？ 2.1.1 Fibonacci 法 如用 Fn 表示计算n 个函数值能缩短为单位长区间的最大原区间长度，可推出 Fn 满 足关系 F0 = F1 = 1 , 2,3, , Fn = Fn−2 + Fn−1 n = L 数列{ } Fn 称为 Fibonacci 数列， Fn 称为第n 个 Fibonacci 数，相邻两个 Fibonacci 数之 比 n n F F −1 称为 Fibonacci 分数。 当用斐波那契法以 n 个探索点来缩短某一区间时，区间长度的第一次缩短率为 n n F F −1 ，其后各次分别为 2 1 2 3 1 2 , , , F F F F F F n n n n L − − − − 。由此，若 1 t 和 ( ) 2 2 1 t t < t 是单峰区间[a,b] 中第 1 个和第 2 个探索点的话，那么应有比例关系 n n F F b a t1 a −1 = − − ， n n F F b a t2 a −2 = − − 从而 ( ) 1 1 b a F F t a n n = + − − ， ( ) 2 2 b a F F t a n n = + − − （3） 它们关于[a,b] 确是对称的点