最优化方法课件s

最优化方法

最优化篇

开篇有益

优化模型 实际问题中，人们经常遇到一类决策问题：在一系列客观或主观限制条件下，寻求使所关注的某个或多个指标达到最大（或最小）的决策。这种决策问题通常称为优化问题。解决这类问题的方法称为最优化方法，又称数学规划，它是运筹学里一个十分重要的分支。

最优化问题的数学模型的一般形式为：

opt z f x （1）

s.t. hi x 0,i 1, ,l gj x 0,j 1, ,m tk x 0,k 1, ,n x D Rs

（2）

opt（optimize）是最优化的意思，可以使求最小min（minimize）或求最大

max（maximize），s.t.（subject to）是“受约束于”。

模型包含三个要素：决策变量decision bariable，目标函数objective function，约束条件constraints。

（2）所确定的x的范围称为可行域feasible region，满足（2）的解x称为可行解feasible solution，同时满足（1）（2）的解x 称为最优解Optimal solution，整个可行域上的最优解称为全局最优解global optimal solution，可行域中某个领域上的最优解称为局部最优解local optimal solution。最优解所对应的目标函数值称为最优值optimum。

不同优化模型的求解方法以及求解难度有很大的不同，可按如下方法对模型进行分类：

（一）按有无约束条件（2）可分为：

1.无约束优化unconstrained optimization。 这类问题蕴含了重要的寻优计算方法。 2.约束优化constrained optimization。 大部分实际问题都是约束优化问题。 （二）按决策变量取值是否连续可分为：

1.数学规划mathematical programming或连续优化continuous optmization。 可继续划分为线性规划(LP)Linear programming和非线性规划(NLP) Nonlinear programming。在非线性规划中有一种规划叫做二次规划(QP)Quadratic programming，二次规划问题的目标为二次函数，约束为线性函数。

2.离散优化d-iscrete optimization或组合优化combinatorial optimization。 这类优化问题中包含一种常用的优化：整数规划(IP)Integer programming，整数规划中又包含很重要的一类规划：0-1（整数）规划Zero-one programming，这类规划问题的决策变量只取0或者1。

在求解组合优化问题中，出现了很多现代优化计算方法。

最优化方法

（三）按目标的多少可分为： 1.单目标规划。 2.多目标规划。

（四）按模型中参数和变量是否具有不确定性可分为： 1.确定性规划。 2.不确定性规划。

（五）按问题求解的特性可分为： 1.目标规划。 2.动态规划。 3.多层规划。 4.网络优化。 5.……等等。

求解软件

对优化问题的求解常用的是LINGO软件和MATLAB软件，本篇的程序编写基本都是用这两个软件完成的。

对于LINGO软件，线性优化求解程序通常使用单纯形法simplex method，单纯形法虽然在实际应用中是最好最有效的方法，但对某些问题具有指数阶的复杂性，为了能解大规模问题，也提供了内点算法interior point method备选（LINGO中一般称为障碍法，即barrier），非线性优化求解程序采用的是顺序线性规划法，也可用顺序二次规划法，广义既约梯度法，另外可以使用多初始点（LINGO中称multistart）找多个局部最优解增加找全局最优解的可能，还具有全局求解程序—分解原问题成一系列的凸规划。关于软件的使用方法可以参考ppt课件《LINGO软件武功秘籍》以及实验书籍《数学软件与数学实验》。

对于MATLAB软件，有MATLAB优化工具箱，线性规划大型问题使用内点算法（也是默认算法），单纯形法和积极集法根据实际情况来解中小型问题。对于非线性规划问题，基本函数用信赖域等方法的结合来求解不同规模的问题。

本篇导读

第一章 无约束优化

寻优经典计算算法,matlab实现 第二章 线性规划

完备的线性规划求解与应用 第三章 非线性规划

非线性模型的建立与求解 第四章 多目标规划

多目标决策的理论与方法 第五章 随机规划

随机规划的理论与方法 第六章 目标规划

目标规划的理论与方法 第七章 动态规划

动态规划的理论与方法

最优化方法

第八章 多层规划 ？？

第九章 网络优化

图论方法及其他网络方法 第十章 组合优化算法

禁忌搜索算法，模拟退火算法，遗传算法，蚁群优化算法，人工神经网络

最优化方法

第三章 非线性规划

理论印象

将非线性规划模型可以更具体的表示为如下形式：

minz f x

s.t. hi x 0,i 1, ,l

gj x 0,j 1, ,m x Rn

如果只有等约束hi，则可以用拉格朗日乘数法构造拉格朗日函数： ，然后求解非线性方程组 L x, f x ihi x （ i为参数）

i 1m

L

x 0 i

即可。

L 0 i

对上述模型，通过讨论x的可行方向与下降方向，可以得到如下的KKT条件（Karush-Kuhn-Tucker条件）（具体可微等条件略）：局部最优解x满足

ml

f x i hi x i gj x 0

， i, i 0。 i 1j 1

g x 0 jj

对等约束模型构造拉格朗日函数：

L x, , f x ihi x jgj x

i 1

j 1

ml

KKT条件中的公式刚好就是函数L对x的导数（梯度）等于0. , 通常称为拉格朗日乘子。

3.1 二次规划

理论印象

目标函数为二次函数，约束为线性函数的优化问题称为二次规划。 二次规划模型的一般形式：

1

minf x xTHx cTx

2

s.t. Ax b

H Rn n为对称矩阵。特别的，当H正定时，模型称为凸二次规划。凸二次

最优化方法

规划局部最优解（KKT点）就是全局最优解。

对等约束的凸二次规划，构造拉格朗日函数：

1

L x, xTHx cTx T Ax b

2

求导得如下方程组：

Hx c AT 0

Ax b 0

解方程组即得最优解。

有效集方法：对于存在不等式约束的二次规划，将等约束（对应有效集）与不等约束分开，将非有效约束去掉，通过解一系列等式约束的二次规划来实现不等式约束的优化。

例1

（1）如果在1955年你有一笔资金投资这三种股票，并期望年收益率至少达到15%，那么你应当如何投资？分析投资组合与回报率以及风险的关系。

最优化方法

（2）如果还可以投资国库券，年收益率为5%，如果投资呢？

（3）如果幂目前持有的股票比例为：A占50%，B占35%，C占15%，买卖股票按交易额的1%收取交易费，你会怎么办？

对问题1

问题分析1

投资股票的收益是不确定的，因而是一个随机变量，我们可以用期望值来表示。风险可以用方差来衡量，方差越大，风险越大。期望与协方差可由上表求得。

符号说明

R1,R2,R3：A,B,C三种股票的收益率,是随机变量。 x1,x2,x3：A,B,C三种股票的投资比例。 模型建立1

3

3

目标：minD x1R1 x2R2 x3R3 ，即min xixjcov Ri,Rj

j 1i 1约束：x1ER1 x2ER2 x3ER3 0.15

x1 x2 x3 1,x1,x2,x

3 0

这是一个二次规划问题。

LINGO程序编写

MODEL:

Title 投资组合模型; SETS:

YEAR/1..12/;

STOCKS/ A, B, C/: Mean,X; link(YEAR, STOCKS): R; STST(Stocks,stocks): COV; ENDSETS DATA:

TARGET = 1.15; ! R是原始数据; R =

1.300 1.225 1.149 1.103 1.290 1.260 1.216 1.216 1.419 0.954 0.728 0.922 0.929 1.144 1.169

最优化方法

1.056 1.107 0.965 1.038 1.321 1.133 1.089 1.305 1.732 1.090 1.195 1.021 1.083 1.390 1.131 1.035 0.928 1.006 1.176 1.715 1.908; ENDDATA

CALC: !计算均值向量Mean与协方差矩阵COV; @for(stocks(i): Mean(i) =

@sum(year(j): R(j,i)) / @size(year) ); @for(stst(i,j): COV(i,j) = @sum(year(k):

(R(k,i)-mean(i))*(R(k,j)-mean(j))) / (@size(year)-1) ); ENDCALC

[OBJ] MIN = @sum(STST(i,j): COV(i,j)*x(i)*x(j)); [ONE] @SUM(STOCKS: X) = 1;

[TWO] @SUM(stocks: mean*x) >= TARGET; END

计算结果：

A占53%，B占36%，C占11% ，风险（方差）为0.0224138。即标准差为0.1497123.

在数据段，修改赋值语句：TARGET =？;可以输入不同的回报率来观察投资组合以及相应的风险。略。

问题分析2

在实际股票市场上，由于股票种类庞大，对协方差的计算几乎是不可能进行的，因为有必要避开协方差的计算再来处理这个问题，我们可以利用股价指数。由于股票指数是整个市场的大势信息，对具体每只股票的涨跌有显著影响的，我们可简单假设影响是线性关系。从而可以通过线性回归的方法找这个线性关系。

预处理—线性回归

三支股票的收益Ri i 1,2,3 与股票指数M的线性关系为：

Ri ui biM ei

用最小二乘法求回归系数，LINGO程序如下：

MODEL:

Title 线性回归模型; SETS:

YEAR/1..12/:M,MM;

STOCKS/A, B, C/: u, b, s2, s; link(YEAR, STOCKS): R, RR, e;

最优化方法

ENDSETS DATA:

! RR和MM是原始数据; RR=

num=?; ENDDATA CALC:

@for(year:m=mm-1); @for(link:r=rr-1);

mean0=@sum(year: (M)/@size(year));!M的均值;

s20=@sum(year: (M-mean0)^2) / (@size(year)-1);!M的方差，标准差; s0=@sqrt(s20);!s0=(s20)^(1/2); ENDCALC

[OBJ] MIN = @sum(stocks(i)|i#eq#num: s2(i));

@for(link(k,i)|i#eq#num: [ERROR] e(k,i) = R(k,i)-u(i)-b(i)*M(k)); @for(stocks(i)|i#eq#num:

最优化方法

![VAR] s2(i)=(@sum(year(k): @sqr(e(k,i))) / (@size(year)-2)) ; [VAR] s2(i)=(@sum(year(k): (e(k,i))^2) / (@size(year)-2)) ; ![STD] s(i)=@sqrt(s2(i)) ); [STD] s(i)=s2(i)^(1/2) );

@for(stocks: @free(u);@free(b) ); @for(link: @free(e) ); END

运行结果：

指数M：均值m0 1.191458，方差s2，标准差s0 0.1695188。 0.028736610A:u1 =0.5639761， b1 =0.4407264， s12=0.005748320， s1=0.07581767 B:u2 = -0.2635059，b2 = 1.239802，s22= 0.01564263， s2= 0.1250705 C :u3 = -0.5809590， b3 = 1.523798， s32= 0.03025165， s3= 0.1739300

模型建立2

R xiRi xi ui biM ei

i 1

i 1

3

3

可计算期望得：ER xi ui bim0

i 1

2

方差：DR xibi s0 xi2si2

2

i 13

3

令y xibi，建立二次规划模型如下：

i 13

2min y2s0 xi2si2

i 1

3

s.t. y xibi

i 1

3

x u

ii 1

3

i

bim0 0.15

x1 x2 x3 1,x1,x2,x3 0

程序编写

MODEL:

Title 利用股票指数简化投资组合模型;

最优化方法

SETS:

STOCKS/A, B, C/: u, b, s2, x; ENDSETS DATA:

! mean0,s20,u,b,s2是线性回归的结果数据; mean0=1.191458; s20 = 0.02873661;

s2 = 0.005748320,0.01564263,0.03025165; u = 0.5639761, -0.2635059,-0.5809590; b = 0.4407264, 1.239802, 1.523798; ENDDATA

[OBJ] MIN = s20*y*y + @sum(stocks: s2*x*x);

![OBJ] MIN = s20*@sqr(y) + @sum(stocks: s2*@sqr(x)); @sum(stocks: b*x)=y; @sum(stocks: x)=1;

@sum(stocks: (u+b*mean0)*x)>1.15;

END

运行结果

Local optimal solution found.

Objective value: 0.2465621E-01 Extended solver steps: 5 Total solver iterations: 55

Model Title: 利用股票指数简化投资组合模型

Variable Value Reduced Cost ……

X( A) 0.5266052 0.000000 X( B) 0.3806461 0.000000 X( C) 0.9274874E-01 0.000000

对问题2，模型仿上建立，求解程序如下：

MODEL:

Title 含有国库券的投资组合模型; SETS:

STOCKS/ A, B, C, D/: Mean,X; STST(Stocks,stocks): COV; ENDSETS DATA:

TARGET = 1.1; ! 1.15; ! Mean是收益均值,COV是协方差矩阵;

mean=1.089083 1.213667 1.234583 1.05;

最优化方法

COV=0.01080754 0.01240721 0.01307513 0 0.01240721 0.05839170 0.05542639 0 0.01307513 0.05542639 0.09422681 0 0 0 0 0; ENDDATA

[OBJ] MIN = @sum(STST(i,j): COV(i,j)*x(i)*x(j)); [ONE] @SUM(STOCKS: X) = 1;

[TWO] @SUM(stocks: mean*x) >= TARGET;

END

运行结果摘取一部分如下：

X( A) 0.4343274E-01 0.000000 X( B) 0.2142643 0.000000 X( C) 0.7169959E-01 0.000000 X( D) 0.6706034 0.000000

与前面结果比较发现，风险资产之间的比例不变，变化的只是投资于风险资产与无风险资产之间的比例，这正是经济学上的“分离定理”，1981年Tobin教授因发现这个定理获得诺贝尔奖。

对问题3，

设购买股票A,B,C的比例为y1,y2,y3。 卖出股票A,B,C的比例为z1,z2,z3。 可建立模型如下：

min xixjcov Ri,Rj

j 1i 1

33

s.t. x1ER1 x2ER2 x3ER3 0.15

x1 x2 x3 0.01 y1 y2 y3 z1 z2 z3 1, xi ci yi zi,i 1,2,3

x1,x2,x3,y1,y2,y3,z1,z2,z3 0程序编写

MODEL:

Title 考虑交易费的投资组合模型; SETS:

STOCKS/ A, B, C/: C,Mean,X,Y,Z; STST(Stocks,stocks): COV; ENDSETS DATA:

TARGET = 1.15; ! 股票的初始份额;

c=0.5 0.35 0.15;

最优化方法

! Mean是收益均值,COV是协方差矩阵;

mean=1.089083 1.213667 1.234583; COV=0.01080754 0.01240721 0.01307513 0.01240721 0.05839170 0.05542639 0.01307513 0.05542639 0.09422681; ENDDATA

[OBJ] MIN = @sum(STST(i,j): COV(i,j)*x(i)*x(j)); [ONE] @SUM(STOCKS: X+0.01*Y+0.01*Z) = 1; [TWO] @SUM(stocks: mean*x) >= TARGET; @FOR(stocks: [ADD] x = c - y + z);

END

运行结果（部分）

X( A) 0.5264748 0.000000 X( B) 0.3500000 0.000000 X( C) 0.1229903 0.000000

例2 钢管的订购和运输（2000年全国大学生数学建模竞赛B题）

要铺设一条A1 A2 A15的输送天然气的主管道, 如图一所示(见下页)。经筛选后可以生产这种主管道钢管的钢厂有S1,S2, S7。图中粗线表示铁路，单细线表示公路，双细线表示要铺设的管道(假设沿管道或者原来有公路，或者建有施工公路)，圆圈表示火车站，每段铁路、公路和管道旁的阿拉伯数字表示里程(单位km)。

为方便计，1km主管道钢管称为1单位钢管。

一个钢厂如果承担制造这种钢管，至少需要生产500个单位。钢厂Si在指定期限内能生产该钢管的最大数量为si个单位，钢管出厂销价1单位钢管为pi万元，如下表：

1单位钢管的铁路运价如下表：

最优化方法

1000km以上每增加1至100km运价增加5万元。

公路运输费用为1单位钢管每公里0.1万元（不足整公里部分按整公里计算）。

钢管可由铁路、公路运往铺设地点（不只是运到点A1,A2, ,A15，而是管道全线）。 （1）请制定一个主管道钢管的订购和运输计划，使总费用最小（给出总费用)。 （2）（3）问略

7 问题分析：从钢厂si向Aj运输钢管，应该走费用最短路相应的最小费用为，我们认为沿管cij，包括销售价和运费两部分，可由图论方法得到（此处省略）

道路线每铺设一公里要卸下一单位钢管，因而在某一点可向左铺（设为yj），也可向右铺（设为zj），相邻两点对铺应该是合拢的。可建立如下二次规划模型：

模型建立

0.115

1 yj yj 1 zj zj

minf cijxij 2j 1i 1j 1

715

最优化方法

s.t.

x

j 1

15

ij

si（产量限制）

（订货限制） 0或 xij 15，

j 115

x

j 1

15

ij

zj yj 1 aj，j 1 14（对铺合拢）

x

i 1

7

ij

yj zj，j 1 15（定铺相等）

y1 z15 0 xij 0,yj 0,zj 0 模型建立

MODEL:

TITLE 钢管购运计划;

SETS:

SUPPLY/S1..S7/:S,f; NEED/A1..A15/:a,y,z; LINK(Supply, need): C, X;

ENDSETS DATA:

S=800 800 1000 2000 2000 2000 3000;

a=104, 301, 750, 606, 194, 205, 201, 680, 480, 300, 220, 210, 420, 500,; c=@text(finalcost.txt);

@TEXT(FinalResult.txt)=@writefor(supply(i):

@writefor(need(j):@format(x(i,j),'5.0f')), @newline(1) );

@TEXT(FinalResult.txt)=@writefor(need:@format(y,'5.0f') ); @TEXT(FinalResult.txt)=@write(@newline(1));

@TEXT(FinalResult.txt)=@writefor(need:@format(z,'5.0f') );

ENDDATA

[obj] MIN=@sum(link(i,j):c(i,j)*x(i,j))

+0.05*@sum(need(j):y(j)^2+y(j)+z(j)^2+z(j)); ! 约束;

@for(supply(i): [con1] @sum(need(j):x(i,j)) <= S(i)*f(i) ); @for(supply(i): [con2] @sum(need(j):x(i,j)) >= 500*f(i)); @for(need(j): [con3] @sum(supply(i):x(i,j)) = y(j)+z(j)); @for(need(j)|j#NE#15: [con4] z(j)+y(j+1)=a(j)); y(1)=0; z(15)=0; @for(supply: @bin(f)); @for(need: @gin(y)); END

最优化方法

二次规划的Matlab求解

假设二次规划模型的形式为：

1

minf x xTHx cTx

2

s.t. Ax b

xbeq Aeq

lb x ub

调用函数为quadprog（），调用形式如上，列举最简与最一般如下： X=quadprog(H,c,A,b);

[x,fval,exitflag,output,lambda]=quadprog(H,c,A,b,Aeq,beq,lb,ub,x0,options) 求解方法在中等规模模式下，是有效集法，在大规模模式下，是一种置信域方法。

例3 用matlab求解例1的问题一模型。

>> R=[1.300 1.225 1.149 1.103 1.290 1.260 1.216 1.216 1.419 0.954 0.728 0.922 0.929 1.144 1.169 1.056 1.107 0.965 1.038 1.321 1.133 1.089 1.305 1.732 1.090 1.195 1.021 1.083 1.390 1.131 1.035 0.928 1.006 1.176 1.715 1.908]; H=2*cov(R); A=mean(R); b=1.15; Aeq=[1 1 1]; beq=1;

x=quadprog(H,[0 0 0],-A,-b,Aeq,beq)

运行结果如下：

x = 0.5301 0.3564 0.1135

为了分析回报率与风险之间的关系，引入偏好系数 ，建立如下模型： 目标： min xixjcov Ri,Rj x1ER1 x2ER2 x3ER3

j 1i 13

3

最优化方法

约束：

x1 x2 x3 1,x1,x2,x3 0

可用下面程序画图观察分析回报率与风险的关系。需要调试

c=-A;

opt=optimset('large','off','Display','off'); for i=1:100,beta=0.01*i;H=beta*H;

x=quadprog(H,c,[],[],Aeq,beq,[0 0 0],[],[],opt); REV(i)=-c*x; STD(i)=sqrt(x'*H*x/2); end

plot(REV,STD) xlabel('预期收益率') ylabel('风险（均方差）')

3.2 一般非线性规划

理论印象

约束优化的算法基本上可以分为两大类，直接法，和间接法，其中间接法事将约束优化问题转化为无约束问题求解，而直接发则不需要转化。直接法包括可行方向法，坐标轮换法等。

序列二次规划法(SQP)

思想：用一序列二次规划的解，去逼近原问题的解。在某点将目标函数二阶泰勒展开，约束一阶泰勒展开，略去高阶项即得到在这个点处的二次规划，称为二次规划子问题，求解得到新的解，在新的解（点）处重复这个过程。

算法：step1.选取初始点x1，正定矩阵B1，令k 1； Step2.求解二次规划子问题：

1T

minQ d dTBkd f xk d

2s.t. hi xk d hi xk 0,i 1 m

T

gj xk d gj xk 0,j 1 l

T

求解得到dk及对应拉格朗日乘子 k 1；

Step3.从点xk，沿方向dk进行一维搜索，确定步长tk，令xk 1 xk tkdk； Step4.利用 k 1等信息，采用某种拟牛顿法对Bk进行修正得到Bk 1，k k 1转Step2。

罚函数法：