**@第三章 非线性规划

1 非线性规划

1.1 非线性规划的实例与定义

	 例1（投资决策问题）某企业有 n 个项目可供选择投资，并且至少要对其中一个

项目投资。已知该企业拥有总资金 A 元，投资于第i(i = 1,L,n) 个项目需花资金ai 元，并预计可收益bi 元。试选择最佳投资方案。
解 设投资决策变量为

最佳投资方案应是投资额最小而总收益最大的方案，所以这个最佳投资决策问题归结为总资金以及决策变量（取 0 或 1）的限制条件下，极大化总收益和总投资之比。因此，其数学模型为：

上面例题是在一组等式或不等式的约束下，求一个函数的最大值（或最小值）问题，其中至少有一个非线性函数，这类问题称之为非线性规划问题。可概括为一般形式

1.2 线性规划与非线性规划的区别

	如果线性规划的最优解存在，其最优解只能在其可行域的边界上达到（特别是可行

域的顶点上达到）；而非线性规划的最优解（如果最优解存在）则可能在其可行域的任意一点达到。

1.3 非线性规划的 Matlab 解法

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


解 （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* )f 是(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 ) 交 K，
则称 x 是（NP）的局部最优解， f(x ) 是(NP)的局部最优值。如果有
f (x ) <f (x), ∀ x∈ Nδ(x) 交 K
则称 x 是（NP）的严格局部最优解，f(x ) 是(NP)的严格局部最优值。
由于线性规划的目标函数为线性函数，可行域为凸集，因而求出的最优解就是整个可行域上的全局最优解。非线性规划却不然，有时求出的某个解虽是一部分可行域上的极值点，但却并不一定是整个可行域上的全局最优解。
对于非线性规划模型(NP)，可以采用迭代方法求它的最优解。迭代方法的基本思想是：从一个选定的初始点 x 0∈ R^n出发，按照某一特定的迭代规则产生一个点列{ x^k} ，使得当{x^k } 是有穷点列时，其最后一个点是(NP)的最优解；当{ x^k} 是无穷点列时，它有极限点，并且其极限点是(NP)的最优解。

1.5 凸函数、凸规划

没看

2 无约束问题

2.1 一维搜索方法

	当用迭代法求函数的极小点时，常常用到一维搜索，即沿某一已知方向求目标函数的极小点。一维搜索的方法很多，常用的有：（1）试探法（“成功—失败”，斐波那契法，0.618 法等）；（2）插值法（抛物线插值法，三次插值法等）；（3）微积分中的求根法（切线法，二分法等）。

2.4 Matlab 求无约束极值问题

Matlab 工具箱中，用于求解无约束极值问题的函数有 fminunc 和 fminsearch，用法介绍如下。
求函数的极小值
min f (x) ,
x
其中 x 可以为标量或向量。
Matlab 中 fminunc 的基本命令是
[X,FVAL]=FMINUNC(FUN,X0,OPTIONS,P1,P2, …)
其中的返回值 X 是所求得的极小点，FVAL 是函数的极小值，其它返回值的含义参见相关的帮助。FUN 是一个 M 文件，当 FUN 只有一个返回值时，它的返回值是函数 f (x)； 当 FUN 有两个返回值时，它的第二个返回值是 f (x)的梯度向量；当 FUN 有三个返回值时，它的第三个返回值是 f (x)的二阶导数阵（Hessian 阵）。X0 是向量 x 的初始值，OPTIONS 是优化参数，可以使用缺省参数。P1，P2 是可以传递给 FUN 的一些参数。
例 6 求函数 f (x) = 100(x2 − x1^2 ) ^2 + (1− x1 )^2 的最小值。
解：编写 M 文件 fun2.m 如下：
function [f,g]=fun2(x);
f=100*(x(2)-x(1)²⁾2+(1-x(1))^2;
g=[-400x(1)(x(2)-x(1)^{2)-2*(1-x(1));200*(x(2)-x(1)}2)];
编写主函数文件example6.m如下：
options = optimset(‘GradObj’,‘on’);
[x,y]=fminunc(‘fun2’,rand(1,2),options)
即可求得函数的极小值。
在求极值时，也可以利用二阶导数，编写 M 文件 fun3.m 如下：
function [f,df,d2f]=fun3(x);
f=100*(x(2)-x(1)²⁾2+(1-x(1))^2;
df=[-400x(1)(x(2)-x(1)^{2)-2*(1-x(1));200*(x(2)-x(1)}2)];
d2f=[-400x(2)+1200x(1)^2+2,-400x(1)
-400x(1),200];
编写主函数文件example62.m如下：
options = optimset(‘GradObj’,‘on’,‘Hessian’,‘on’);
[x,y]=fminunc(‘fun3’,rand(1,2),options)
即可求得函数的极小值。
解得：x =
1.0000 1.0000
y =
7.0417e-14

求多元函数的极值也可以使用 Matlab 的 fminsearch 命令，其使用格式为：
[X,FVAL,EXITFLAG,OUTPUT]＝FMINSEARCH(FUN,X0,OPTIONS,P1,P2,…)

例 7 求函数 f (x) = sin(x) + 3 取最小值时的 x 值。
解 编写 f (x) 的 M 文件 fun4.m 如下：
function f=fun4(x);
f=sin(x)+3;
编写主函数文件example7.m如下：
x0=2;
[x,y]=fminsearch(@fun4,x0)
即求得在初值 2 附近的极小点及极小值。
解得：x =
4.7124
y =
2.0000

3 约束极值问题

3.1二次规划

	定义：若某非线性规划的目标函数为自变量 x 的二次函数，约束条件又全是线性的，就称这种规划为二次规划。

解 编写如下程序：
h=[4,-4;-4,8];
f=[-6;-3];
a=[1,1;4,1];
b=[3;9];
[x,value]=quadprog(h,f,a,b,[],[],zeros(2,1))
求得
x= 1.9500
1.0500
Min f(x )= - 11.0250

3.2 罚函数法

	利用罚函数法，可将非线性规划问题的求解，转化为求解一系列无约束极值问题，因而也称这种方法为序列无约束最小化技术，简记为 SUMT (Sequential Unconstrained Minization Technique)。罚函数法求解非线性规划问题的思想是，利用问题中的约束函数作出适当的罚函数，由此构造出带参数的增广目标函数，把问题转化为无约束非线性规划问题。主要有两种形式，一种叫外罚函数法，另一种叫内罚函数法，下面介绍外罚函数法。

解 (i)编写 M 文件 test.m
function g=test(x);
M=50000;
f=x(1)^2+x(2)2+8;
g=f-Mmin(x(1),0)-Mmin(x(2),0)-Mmin(x(1)^{2-x(2),0)+M*abs(-x(1)-x(2)}2+2);
或者是利用Matlab的求矩阵的极小值和极大值函数编写test.m如下：
function g=test(x);
M=50000;
f=x(1)^2+x(2)2+8;
g=f-Msum(min([x’;zeros(1,2)]))-Mmin(x(1)^2-x(2),0)+ Mabs(-x(1)-x(2)^2+2);
我们也可以修改罚函数的定义，编写test.m如下：
function g=test(x);
M=50000;
f=x(1)^2+x(2)2+8;
g=f-Mmin(min(x),0)-Mmin(x(1)^{2-x(2),0)+M*(-x(1)-x(2)}2+2)^2;
(ii)在 Matlab 命令窗口输入
[x,y]=fminunc(‘test’,rand(2,1))
即可求得问题的解。
解得：x =
1.0000
0.9999
y =
10.0008
%解好像不唯一

3.3 Matlab 求约束极值问题

		Matlab 优化工具箱中，用于求解约束最优化问题的函数有：fminbnd、fmincon、quadprog、fseminf、fminimax，上面我们已经介绍了函数 fmincon 和 quadprog。

3.3.1 fminbnd 函数

求单变量非线性函数在区间上的极小值
min f( x) , x ∈[x1 , x2]
Matlab 的命令为
[X,FVAL] = FMINBND(FUN,x1,x2,OPTIONS)，
它的返回值是极小点 x 和函数的极小值。这里 fun 是用 M 文件定义的函数或 Matlab 中的单变量数学函数。
例 10 求函数 f( x) = ( x-3)^2 -1 x ∈[0 ,5] 的最小值。
解 编写 M 文件 fun5.m
function f=fun5(x);
f=(x-3)^2-1;
在 Matlab 的命令窗口输入
[x,y]=fminbnd(‘fun5’,0,5)
即可求得极小点和极小值。

3.3.2 fseminf 函数

上述问题的 Matlab 命令格式为
X=FSEMINF(FUN,X0,NTHETA,SEMINFCON,A,B,Aeq,Beq)
其中 FUN 用于定义目标函数 F(x) ；X0 为 x 的初始值；NTHETA 是半无穷约束PHI(x,w)的个数；函数 SEMINFCON 用于定义非线性不等式约束C(x) ，非线性等式约束Ceq(x) 和半无穷约束 PHI(x,w)的每一个分量函数，函数 SEMINFCON 有两个输入参量 X 和 S，S 是推荐的取样步长，也许不被使用。

解 （1）编写 M 文件 fun6.m 定义目标函数如下：
function f=fun6(x,s);
f=sum((x-0.5).^2);
（2）编写 M 文件 fun7.m 定义约束条件如下：
function [c,ceq,k1,k2,s]=fun7(x,s);
c=[];ceq=[];
if isnan(s(1,1))
s=[0.2,0;0.2 0];
end
%取样值
w1=1:s(1,1):100;
w2=1:s(2,1):100;
%半无穷约束
k1=sin(w1x(1)).cos(w1x(2))-1/1000(w1-50).^2-sin(w1x(3))-x(3)-1;
k2=sin(w2x(2)).cos(w2x(1))-1/1000*(w2-50).^2-sin(w2*x(3))-x(3)-1;
%画出半无穷约束的图形
plot(w1,k1,’-’,w2,k2,’+’);
（3）调用函数 fseminf
在 Matlab 的命令窗口输入
[x,y]=fseminf(@fun6,rand(3,1),2,@fun7)
即可。

3.3.3 fminimax 函数

上述问题的 Matlab 命令为
X=FMINIMAX(FUN,X0,A,B,Aeq,Beq,LB,UB,NONLCON)

解 （1）编写 M 文件 fun8.m 定义向量函数如下：
function f=fun8(x);
f=[2x(1)^2+x(2)2-48x(1)-40x(2)+304
-x(1)^2-3*x(2)2
x(1)+3x(2)-18
-x(1)-x(2)
x(1)+x(2)-8];
（2）调用函数 fminimax
[x,y]=fminimax(@fun8,rand(2,1))
解得：x =
4.0000
4.0000
y =
0.0000
-64.0000
-2.0000
-8.0000
-0.0000