【优化算法】02. 非线性规划_首页-傲世皇朝平台-注册登录中心

【优化算法】02. 非线性规划

日期：2024-08-12 02:37:51 / 人气：

若规划问题的目标函数或约束条件中包含非线性函数，则称为非线性规划。

非线性规划的最优解（若存在）可能在其可行域的任一点达到，目前非线性规划还没有适合各种问题的一般解法，各种方法都有其特定的适用范围。

Matlab中非线性规划的标准形式为

$\\min F(x)$

$s.t.~AX \\leq b$ （线性不等式约束）

$Aeq \\cdot X=beq$ （线性等式约束）

$C(X) \\leq 0$ （非线性不等式约束）

$Ceq(X)=0$ （非线性等式约束）

$VLB \\leq X \\leq VUB$ （有界约束）

调用格式：

[x, fval, exitflag, output, lambda, grad,
hessian]=fmincon(‘fun’, X0, A, b, Aeq, beq, VLB, VUB, ‘nonlcon’, options)

其中，大部分参数同线性规划；

‘fun’为用M-文件定义的目标函数F(x)；

‘nonlcon’为用M-文件定义的非线性向量函数[C(x),
Ceq(x)]

例1 求解下列非线性规划问题：

$\\min f(x)=x_1^2+x_2^2+8$

$s.t.~x_1^2-x_2 \\geq 0$

$x_1+x_2^2=2$ $x_1,\\,x_2 \\geq 0$

Matlab代码：

目标函数（M文件）：

function f=fun1(x)
f=x(1)^2+x(2)^2+8;

非线性约束（M文件）：

function [C,Ceq]=fun2(x)
C=-x(1)^2+x(2); % 非线性约束，若不止1个，则用C(1),C(2),...
Ceq= x(1)+x(2)^2-2; % 等式约束, 若没有等式约束，可令Ceq=[];

主程序：

x0 = rand(2,1);

VLB = zeros(2,1);

[x,fval,exitflag,output,lambda,grad,hessian] =  fmincon('fun1',x0,[],[],[],[],VLB,[],'fun2')

运行结果（部分）：

exitflag=1 优化成功

x=1.0000 最优解

1.0000

fval=10.0000
目标值

grad=2.0000

2.0000

hessian=1.4338 0.4960

0.4960
0.5902

Lingo代码：

model:

min=x1^2+x2^2+8;

x1^2-x2>0;

x1+x2^2=2;

end

运行结果：Global optimal solution found.

Objective value: 10.00000

Variable Value

X1 1.000000

X2 1.000000

Matlab中无约束非线性规划的标准形式为：

$\\min f(x), \\qquad s.t.~ x_1 \\leq x \\leq x_2$

Matlab提供了3个不同的函数分别适合不同情形：

1. fminbnd函数

用于求解定区间上单变量函数的最小值点，调用格式为：

[x,
fval, exitflag, output]=fminbnd(‘fun’, x1, x2, options)

其中，fun为用M-文件定义的目标函数。

2. fminunc函数

基于梯度的最优化算法，用于求解单变量及多变量函数的最小值，调用格式为：

[x,
fval, exitflag, output, lambda, grad, hessian]=fminunc(‘fun’, x0, options)

其中，x0为初始值；

options参数：

LargeScale，on或off设置大型中型优化算法；

HessUpdate，设置中型优化算法的搜索方向的算法，’bfgs’（默认）为拟牛顿法的BFGS公式；’dfp’为拟牛顿法的DFP公式；’steepdesc’为最速下降法；

LineSearchType，设置中型优化算法的步长一维搜索的两种算法，’quadcubic’（默认）为混合的二次和三次多项式插值；’cubicpoly’为三次多项式插值。

3. fminsearch函数

根据Nelder算法编写的，用于求解多变量函数的极小值，调用格式为：

[x,
fval, exitflag, output]=fminbnd(‘fun’, x0, options)

其中，options的选项有：

Display，’off’不显示输出；’iter’显示每次迭代信息；’final’只显示最终结果；

MaxFunEvals，允许进行函数评价的最大次数；

MaxIter，允许迭代的最大次数；

TolX，变量的容许误差限；

TolFun，函数值的容许误差限。

关于三个函数的说明：

（1）三个函数可能只输出局部最优解。

（2）三个函数均只对变量为实数的问题进行优化。

（3）fminunc函数要求目标函数必须连续。

例2 求解下列函数的极小值：

$\\min y=\\frac{1}{|x|}, \\qquad s.t.~-3 \\leq x \\leq 1$

Matlab代码：

目标函数（M文件）：

function f=fun3(x)
f=1/abs(x);

主程序：

x=linspace(-pi,pi);
y=abs(1./x);
plot(x,y,'r');
grid on
x0=1;
x1=-3; x2=1;
[x,fval,exitflag] = fminbnd('fun3',x1,x2)
[x,fval,exitflag] = fminunc('fun3',x0)
[x,fval,exitflag] = fminsearch('fun3',x0)

运行结果（部分）：

x=-2.9999

fval=0.3333

exitflag=1

fminbnd函数优化成功，是正确解。

x=889.4311

fval=0.0011

exitflag=1

fminunc函数优化成功，但解是错误的（fminunc的目标函数必须是连续函数，本例目标函数不连续）

x=6.3383e+28

fval=1.5777e-29

exitflag=0

fminsearch函数优化失败，因为该函数只能求解多变量目标函数。

Lingo代码：

model:
min=1/@abs(x);
@bnd(-3,x,1);
end

运行结果： Local optimal solution found.

Objective value: 0.3333333

Variable Value

X
-3.000000

4. 惩罚函数法

利用惩罚函数法，可将非线性规划问题的求解转化为一系列无约束非线性规划问题。

惩罚函数法求解非线性规划问题，是利用问题中的约束函数做出适当的惩罚函数，由此构造出带参数的增广目标函数，将问题转化为无约束非线性规划问题。下面介绍外惩罚函数法。

求解如下极小值问题：

$\\min f(x)$

$s.t.~g_i(x) \\leq 0, \\qquad i=1, \\, \\cdots, \\, r$

$h_i(x) \\geq 0, \\qquad i=1, \\, \\cdots, \\, s$ $k_i(x)=0, \\qquad i=1, \\, \\cdots, \\, t$

取一个充分大的数 $M > 0$ , 构造函数

$P(x,M)=f(x)+M \\sum_{i=1}^r \\max \\{ g_i(x), \\, 0 \\}- M \\sum_{i=1}^s \\min\\{h_i(x), \\, 0\\}+ M \\sum_{i=1}^t \\big| k_i(x) \\big|$

或者用向量表示：

$P(x,M)=f(x)+M \\cdot \\rm{sum}\\Big( \\max \\Big( G(x), \\, 0 \\Big)^T \\Big)- \\cdot \\rm{sum}\\Big( \\min \\Big( H(x), \\, 0 \\Big)^T \\Big) + M \\big\\| K(x) \\big\\|$

其中， $G(x)=\\big[ g_1(x), \\, \\cdots, \\, g_r(x) \\big]^T, \\, H(x)=\\big[ h_1(x), \\, \\cdots, \\, h_s(x) \\big]^T, \\, K(x)=\\big[ k_1(x), \\, \\cdots, \\, k_t(x) \\big]^T, \\,$

则以增广目标函数 $P(x,M)$ 为目标函数的无约束极值问题： $\\min P(x,M)$ 的最优解 $x$ 也是原问题的最优解。

例3 求解例1 的非线性规划问题：

Matlab代码：

增广目标函数（M文件）：

function g=fun4(x)

M=50000;

f=x(1)^2+x(2)^2+8;

g=f-M*min(x(1)^2-x(2),0)+M*abs(-x(1)-x(2)^2+2)-M*min(x(1),0) - M*min(x(2),0);

主程序：

[x,fval,exitflag]=fminunc('fun4',rand(2,1))

运行结果：

x=1.0467

0.9764

fval=10.0489

exitflag=5 说明重要方向导数小于规定的容许范围并且约束违背小于options
TolCom

注：最优解是(1,1), 上述结果也可以接受。另外，初始值的选取不同，会得到不同的局部最优解。

若非线性规划的目标函数为自变量 $x$ 的二次函数，约束条件又全是线性的，称为二次规划。

Matlab中的二次规划的标准形式为：

$\\min \\frac{1}{2}x^T H x +f^Tx$

$s.t.~Ax \\leq b$

$Aeq \\cdot x=beq$

其中， $H$ 为实对称矩阵；

$f, \\,b$ 为列向量；

$A$ 为相应维数的矩阵。

调用格式：

[x,
fval, exitflag, output]=quadprog(H,f,A,b,Aeq,beq,LB,UB,x0,options)

例4 求解下列二次规划问题：

$\\min f(x)=2 x_1^2 - 4x_1x_2+4x_2^2 - 6x_1 - 3x_2$

$s.t.~x_1+x_2 \\leq 3$

$4x_1 + x_2 \\leq 9$ $x_1, \\, x_2 \\geq 0$

Matlab代码：

H=[4,-4;-4,8];

f=[-6;-3];

A=[1,1;4,1];

b=[3;9];

[x,fval,exitflag]=quadprog(H,f,A,b,[],[],zeros(2,1))

运行结果：

x=1.9500

1.0500

fval=-11.0250

exitflag=1

Lingo代码：

model:

min=2*x1^2-4*x1*x2+4*x2^2-6*x1-3*x2;

x1+x2<3;

4*x1+x2<9;

end

运行结果：Local
optimal solution found.

Objective value: -11.02500

Variable Value

X1
1.950000

X2
1.050000

Matlab优化工具箱：非线性优化，MATLAB中文论坛
Matlab优化工具箱：无约束非线性优化，MATLAB中文论坛
卓金武等. Matlab在数学建模中的应用，北京：北京航空航天大学出版社，2011
谢金星，薛毅. 优化建模与LINDO/LINGO软件，北京：清华大学出版社，2006

上一篇 : 保利世贸博览馆在广州哪个区下一篇 : 世界248个国家和地区人口密度排名表格

奉行卓越设计
打造国际品质

傲世皇朝动态 NEWS真实、正向、传递价值

【优化算法】02. 非线性规划