最优化方法第二堂课

最优化方法主讲

王更生教授2.1回顾：一、最优控制问题50年代前：古典化——工程试探法解析法使系统误差平方和（ISE）最小提法A：

Min=

s.t

==c第二章线性规划提法B：Min=Mins.t

=c

频域基石：状态空间可控、可观（概念？）2.极小值原理动态规划特点：适用于多变量、非线形、时变系统初始条件可变可满足多个目标函数要求，并可有多余约束可计算求解（数值法）可控性举例：可控性举例：二、一维搜索（一）．搜索算法概述1．问题：一般要求=0，判定②③无法写出解析式因此，迭代算法——搜索算法①=0难求

难判别2．基本思想：通过逐次逼近，求最优解或近似最优解=+

步长

方向3．原则①下降性：f(x0)≥f(x1)≥┅f(xk)≥┅②收敛性：{xk}最终收敛到定义域内某极限点（最优解）（满足精度）4．步骤①选定初始点xk，令k=0②如果已得xk，且xk不是最优解，则选定搜索方向pk③从xk出发，沿pk求αk，以产生xk+1=xk+αkpk④新点是否极小？是，停止；否，令k=k+1，返回②。5．确定步长αk的方法①αk取常数（αk=1），简单，不保证f(xk)下降②可接受点算法：只要使f(xk)下降，取αk任意步长③一维搜索：沿搜索方向使目标函数值下降得最多，αk

：minf(xk+αkpk)即求一个以αk为变量的一元函数的极小值问题。6．一维搜索的判别准则：充分小的正数例：（1）|f()-f（）|（2）|f()-f（）|<

=[f()+f（）]满足（1）停；否，满足（2）停；否，返回，继续迭代。<7．原理设f（x）在[a，b]是下单峰函数，在[a，b]内任取两点、，且<若f()<f()，则[a，]，

若f()f()，则[，b]，

再从中取一个点，又将新区间再缩短一次，反复直到最终区间长度缩短到满足预先给定的精确度在内在内二．Fibonacci法(书P14)[a，b]一定，计算n次，最多将多长（设)的原始区间缩短为1？设<，[a，]，-a[，b]，b-=b-a=(b-)+(-a)++若=+,n2==1则为最大原始区间长度设=，若[a，b]，最终区间长度（>0），可确定n，，…，，，可得：=a+（b-a）（-a）=a+（b-a）（-a）+=1=1--a=b-=（b-a）)、f()得新区间[a，b]计算比较f(设已迭代i-1次，第i次，有n-i+1个试点令： =a+（b-a）=a+i=h-1时，==1，与重合。)、f(③区间缩水率不固定（b-a）注意：①先计算n②第一次计算f(),其余每次只计一个f(x)例题见书《最优化方法》解可新编P172.2凸集、凸函数和凸规划一、凸集1、凸集的概念：定义1：设集合SRn，若x(1),x(2)S,[0,1]，必有

x(1)＋(1-)x(2)S，则称S为凸集。规定：单点集{x}为凸集，空集为凸集。注:x(1)＋(1-)x(2)=x(2)＋(x(1)-x(2))

是连接x(1)与x(2)的线段。凸集非凸集2.2凸集、凸函数和凸规划(续)一、凸集1、凸集的概念：例:证明集合S={x∣Ax=b}是凸集。其中，A为mn矩阵，b为m维向量。证明：任取x(1),x(2)S,(0,1)

记x

=x(1)＋(1-)x(2)

有Ax

=A(x(1)＋(1-)x(2))

=Ax(1)＋(1-)Ax(2)

=b＋(1-)b

=b

2.2凸集、凸函数和凸规划(续)定义2：凸组合：设

x(1),x(2),…,x(m)

Rn,j≥

0

mm

j=1,那么称

jx(j)为x(1),x(2),…,x(m)的

j=1j=1凸组合。

m比较:z=

jx(j)

j=1jR

—构成线性组合——线性子空间j≥0,

j>0—构成半正组合——凸锥j≥0,

j=0—构成凸组合——凸集2.2凸集、凸函数和凸规划(续)一、凸集1、凸集的概念：定理：S是凸集S中任意有限点的凸组合属于S多胞形

H(x(1),x(2),…,x(m))：由x(1),x(2),…,x(m)的所有凸组合构成。单纯形：若多胞形H(x(1),x(2),…,x(m))满足，

x(2)-x(1),x(3)-x(1),…,x(m)-

x(1)

线性无关。多胞形单纯形单纯形2.2凸集、凸函数和凸规划(续)一、凸集

2、凸集的性质：凸集的交集是凸集；（并？）凸集的内点集是凸集；（逆命题是否成立？）凸集的闭包是凸集。（逆命题是否成立？）分离：定义1：设集合S1，S2

Rn，非空，若p

Rn，p≠0,使满足

pT

x≥α，xS1

pT

x≤α，xS2则称超平面H={x∣pT

x=α}分离S1，S2

。H称为分离超平面2.2凸集、凸函数和凸规划(续)如果S1∪S2H，则称正常分离。如果等号去掉，则称严格正常分离。如果进一步ε>0,使满足

pT

x≥α+ε，xS1

pT

x≤α，xS2则称H强分离S1，S2

。强分离分离非正常分离2.2凸集、凸函数和凸规划(续)5）支撑：定义：设非空集合SRn，xS,p

Rn，p≠0,如果满足pT(x-x)≥0，xS，则称超平面H={x∣pT(x-x)=0}为S在x点的支撑超平面。又若SH，则称正常支撑。支撑2.2凸集、凸函数和凸规划(续)一、凸集3、凸锥：定义：C

Rn,若xC,>0

有xC,则称

C是以0为顶点的锥。如果C还是凸集，则称为凸锥。集合{0}、Rn

是凸锥。命题：C是凸锥C中任意有限点的半正组合属于S02.2凸集、凸函数和凸规划(续)二、凸函数

1、凸函数及水平集定义:设集合SRn

为凸集，函数f:SR

若

x(1),x(2)S,(0,1)，均有

f(x(1)＋(1-)x(2))≤f(x(1))+(1-)f(x(2))，则称f(x)为凸集S上的凸函数。若进一步有上面不等式以严格不等式成立，则称f(x)为凸集S上的严格凸函数。当-f(x)为凸函数（严格凸函数）时，则称f(x)为凹函数（严格凹函数）。严格凸函数凸函数严格凹函数2.2凸集、凸函数和凸规划(续)二、凸函数1、凸函数及水平集：定理：f(x)为凸集S上的凸函数S上任意有限点的凸组合的函数值不大于各点函数值的凸组合。思考：设f1,f2是凸函数，设1,2>0,1f1+2f2,1f1-2f2是否凸函数？f(x)=max{f1(x),f2(x)},g(x)=min{f1(x),f2(x)}是否凸函数？

2.2凸集、凸函数和凸规划(续)二、凸函数1、凸函数及水平集：定义：设集合

SRn

，函数f:SR，R

，称S={xS∣f(x)≤

}为f(x)在S上的水平集。定理：设集合SRn

是凸集，函数f:SR是凸函数，则对R

，S

是凸集。注：水平集的概念相当于在地形图中，海拔高度不高于某一数值的区域。上述定理的逆不真。考虑分段函数f(x)=1(x≥0)或0(x<0)，函数非凸，但任意水平集是凸集。2.2凸集、凸函数和凸规划(续)二、凸函数2、凸函数的性质：方向导数：设S

Rn

为非空凸集，函数f:SR，再设x*

S,d为方向，使当

>0

充分小时有x*+d

S,

如果

lim

[f(x*+d)-f(x*)]/

存在（包括）

则称f(x)为在点沿方向的方向导数存在，记

f`(x*;d)=lim

[f(x*+d)-f(x*)]/

若f(x)在x*可导，则f`(x*;d)=[f(x*)]Td.2.2凸集、凸函数和凸规划(续)二、凸函数2、凸函数的性质：以下设S

Rn

为非空凸集，函数f:SR2）若f凸，则f在S的内点集上连续；注：f在S上不一定连续。

例:f(x)＝2(当x=1)；f(x)＝x2(当x<1).3）设f凸，则对任意方向方向导数存在。4）设S是开集，f在S上可微，则

f凸x*S，有f(x)≥f(x*)+fT(x*)(x-x*),xS.5)设S是开集，f在S上二次可微，则

a)

f凸xS，2f(x)半正定；

b)若xS，2f(x)正定，则f严格凸。2.2凸集、凸函数和凸规划(续)三、凸规划：当（fS）中，S为凸集，f是S上的凸函数（求min），称（fS）为凸规划；对于（fgh）,f,gi为凸函数，hj为线性函数时，（fgh）为凸规划。定理：设集合S

Rn

为凸集，函数f:SRf(x)为凸集S上的凸函数。X*为问题（fs）的l.opt，则X*为g.opt；又如果f是严格凸函数，那么X*是（fs）的唯一g.opt。2.3多面体、极点、极方向1）多面体：有限个半闭空间的交例：S={xRnAx=b,x≥0}2)多面体的极点（顶点）：

xS，不存在S

中的另外两个点x(1)和x(2)，及λ(0,1)，使x=λx(1)+(1-λ)x(2).3)方向：xS,dRn,d

0及λ>0,总有x+λd

S.

d(1)=λd(2)(λ>0)时，称d(1)和d(2)同方向。4)极方向：方向d

不能表示为两个不同方向的组合(d=d(1)+d(2)).2.3多面体、极点、极方向多面体S={xRnAx=b,x≥0}的极点和极方向定理1（极点特征）设A

满秩，x

是S极点的充分必要条件是:

存在分解A=[B,N]，其中B为m阶非奇异矩阵，使xT=[xBT,xNT],

这里xB=B-1b≥0,xN=0.S中必存在有限多个极点。(≤Cnm)2.3多面体、极点、极方向多面体

S={xRnAx=b,x≥0}的极点和极方向定理2（极方向特征）设A=[p1,p2,…,pn]满秩，d

是S

极方向的充分必要条件是:存在分解A=[B,N]，其中B为m阶非奇异矩阵，对于N中的列向量pj

使B-1pj≤0,

dT=[dBT,dNT],这里j

dB=-B-1pj

,dN=(0,...,1,…,0)TS中必存在有限多个极方向。(≤(n-m)Cnm)考虑多面体

S={xRnAx=b,x≥0}，其中

3210065

A=21010b=400300175

即

3x1+2x2+x3=652x1+x2+x4=403x2+x5=75x1,x2,x3,x4,x5≥0

例题

32100A=[P1,P2,P3,P4,P5]=2101003001

A矩阵包含以下10个3×3的子矩阵：

B1=[p1，p2，p3]B2=[p1，p2，p4]

B3=[p1，p2，p5]B4=[p1，p3，p4]

B5=[p1，p3，p5]B6=[p1，p4，p5]

B7=[p2，p3，p4]B8=[p2，p3，p5]

B9=[p2，p4，p5]B10=[p3，p4，p5]

例题

其中B4=0，因而B4不能构成极点和极方向。其余均为非奇异方阵，因此该问题共有9个可构成极点、极方向的子矩阵，我们称之为基。对于基B3=[p1，p2，p5]，令x3

=0，x4=0，在等式约束中令x3=0，x4

=0，解线性方程组：

3x1

+2x2

+0x5

=652x1

+x2

+0x5

=400x1

+3x2

+x5

=75

得到x1

=15，x2

=10，x5=45，对应的极点：

x=(x1，x2，x3，x4，x5)T=(15，10，0，0，45)T例题

类似可得到极点

x(2)=(5,25,0,5,0)T

（对应B2）

x(7)=(20,0,5,0,75)T

（对应B5）

x(8)=(0,25,15,15,0)T

（对应B7）

x(9)=(0,0,65,40,75)T

（对应B10）而x(3)=(0,32.5,0,7.5,-22.5)T（对应B9）

x(4)=(65/3,0,0,-10/3,75)T

（对应B6）

x(5)=(7.5,25,-7.5,0,0)T

（对应B1）

x(6)=(0,40,-15,0,-45)T

（对应B8）

不是极点例题2.3多面体、极点、极方向多面体S={xRnAx=b,x≥0}的极点和极方向定理3（表示定理）考虑上述多面体S，

设A满秩，x(1),x(2),…,x(k)为所有极点，d(1),d(2),…,d(l)为所有极方向。那么，对于xS，λi≥0，且λ1+λ2+…+λk=1,j≥0,j=1,2,…,l,使

x=λ1x(1)+λ2x(2)+…+λkx(k)+1d(1)+2d(2)+…+ld(l).一线性规划模型

例1:某工厂拥有A、B、C三种类型的设备，生产甲、乙两种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示：

产品甲产品乙设备能力（h）设备A3265设备B2140设备C0375利润（元/件）15002500

问题：工厂应如何安排生产可获得最大的总利润？解：设变量xi为第i种（甲、乙）产品的生产件数（i＝1，2）。根据题意，我们知道两种产品的生产受到设备能力（机时数）的限制。对设备A，两种产品生产所占用的机时数不能超过65，于是我们可以得到不等式：3x1

+2x2

≤65；对设备B，两种产品生产所占用的机时数不能超过40，于是我们可以得到不等式：2x1

+x2

≤40；一线性规划模型

对设备C，两种产品生产所占用的机时数不能超过75，于是我们可以得到不等式：3x2

≤75；另外，产品数不可能为负，即x1,x2≥0。同时，我们有一个追求目标，即获取最大利润。于是可写出目标函数z为相应的生产计划可以获得的总利润：z=1500x1+2500x2

。综合上述讨论，在加工时间以及利润与产品产量成线性关系的假设下，把目标函数和约束条件放在一起，可以建立如下的线性规划模型：一线性规划模型目标函数

Maxz=1500x1+2500x2

约束条件

s.t.3x1+2x2≤652x1+x2≤403x2≤75

x1,x2≥0

一线性规划模型这是一个典型的利润最大化的生产计划问题。其中，“Max”是英文单词“Maximize”的缩写，含义为“最大化”；“s.t.”是“subjectto”的缩写，表示“满足于……”。因此，上述模型的含义是：在给定条件限制下，求使目标函数z达到最大的x1,x2

的取值。一线性规划模型[例2]求线性电阻电桥中消耗的总功率最小时的最优参数。设任意支路的电阻为Rk，其电流和电压分别为Ik、Vk，已知Vk=IkRk

，Ikmin≤Ik≤Ikmax，k=1，2，…，5，Vk

、

Ikmin

、

Ikmax为已知常数。Minf(x)=s.t

Ikmin≤Ik≤Ikmax=+=+,0，计算=求一般形式

目标函数：Max(Min)z=c1x1

+c2x2

+…+cnxn

约束条件：a11x1+a12x2+…+a1nxn≤(=,≥)b1a21x1+a22x2+…+a2nxn≤(=,≥)b2

...am1x1+am2x2

+…+amnxn≤(=,≥)bm

x1，x2，…，xn≥0一线性规划模型标准形式目标函数：Maxz=c1x1+c2x2+…+cnxn

约束条件：a11x1+a12x2+…+a1nxn

=

b1a21x1+a22x2+…+a2nxn

=b2

...am1x1+am2x2+…+amnxn

=bm

x1，x2，…，xn

≥0一线性规划模型可以看出，线性规划的标准形式有如下四个特点：目标最大化、约束为等式、决策变量均非负、右端项非负。对于各种非标准形式的线性规划问题，我们总可以通过以下变换，将其转化为标准形式:一线性规划模型

1.极小化目标函数的问题：设目标函数为

Minf=c1x1

+c2x2

+…+cnxn

则可以令z

＝-f

，该极小化问题与下面的极大化问题有相同的最优解，即

Maxz=-c1x1

-c2x2-…-cnxn

但必须注意，尽管以上两个问题的最优解相同，但他们最优解的目标函数值却相差一个符号，即

Minf

＝-Maxz一线性规划模型

2、约束条件不是等式的问题：设约束条件为

ai1x1+ai2x2+…+ain

xn

≤bi

可以引进一个新的变量s

，使它等于约束右边与左边之差

s=bi–(ai1x1

+ai2x2

+…+ain

xn

)

显然，s

也具有非负约束，即s≥0，这时新的约束条件成为

ai1x1+ai2x2+…+ain

xn+s=bi一线性规划模型当约束条件为

ai1x1+ai2x2+…+ain

xn

≥bi

时，类似地令

s=(ai1x1+ai2x2+…+ain

xn)-bi

显然，s

也具有非负约束，即s≥0，这时新的约束条件成为

ai1x1+ai2x2+…+ain

xn-s=bi

一线性规划模型为了使约束由不等式成为等式而引进的变量s称为“松弛变量”。如果原问题中有若干个非等式约束，则将其转化为标准形式时，必须对各个约束引进不同的松弛变量。

一线性规划模型

例3：将以下线性规划问题转化为标准形式

Minf=3.6x1

-5.2x2+1.8x3s.t.2.3x1

+5.2x2-6.1x3

≤15.74.1x1

+3.3x3

≥8.9

x1

+x2+x3

=38

x1

,x2,x3≥0

一线性规划模型

解：首先,将目标函数转换成极大化：令z=-f=-3.6x1+5.2x2-1.8x3

其次考虑约束，有2个不等式约束，引进松弛变量x4，x5

≥0。于是，我们可以得到以下标准形式的线性规划问题：

Maxz=-3.6x1

+5.2x2-1.8x3s.t.2.3x1+5.2x2-6.1x3+x4=15.74.1x1+3.3x3-x5=8.9

x1+x2+x3=38

x1,x2,x3,x4,x5

≥0一线性规划模型

3.变量无符号限制的问题：在标准形式中，必须每一个变量均有非负约束。当某一个变量xj没有非负约束时，可以令

xj

=

xj’-

xj”其中

xj’≥0，xj”≥0即用两个非负变量之差来表示一个无符号限制的变量，当然xj的符号取决于xj’和xj”的大小。一线性规划模型

4.右端项有负值的问题：在标准形式中，要求右端项必须每一个分量非负。当某一个右端项系数为负时，如bi<0，则把该等式约束两端同时乘以-1，得到：-ai1x1-ai2x2-…-ain

xn

=-bi

。一线性规划模型例4：将以下线性规划问题转化为标准形式Minf=-3x1

+5x2+8x3

-7x4s.t.2x1

-3x2+5x3+6x4

≤284x1

+2x2+3x3-9x4

≥396x2+2x3+3x4≤-58

x1,x3,x4

≥0一线性规划模型解：首先，将目标函数转换成极大化：令z=-f=3x1–5x2–8x3+7x4

；

其次考虑约束，有3个不等式约束，引进松弛变量x5,x6,x7

≥0；由于x2无非负限制，可令x2=x2’-x2”,其中 x2’≥0，x2”≥0；

由于第3个约束右端项系数为-58，于是把该式两端乘以-1。于是，我们可以得到以下标准形式的线性规划问题：一线性规划模型Maxz=3x1–5x2’+5x2”–8x3+7x4s.t.2x1–3x2’+3x2”+5x3+6x4+x5=284x1+2x2’-2x2”+3x3-9x4-x6=39-6x2’+6x2”-2x3-3x4-x7

=58

x1,x2’,x2”,x3,x4,x5,x6,x7

≥0

一线性规划模型一线性规划模型矩阵形式：线性规划的标准形式：

MaxcTx(LP)s.t.Ax=b

x≥0其中,

c,x

Rn

b

Rm

Amn

矩阵一线性规划模型线性规划的规范形式：

MaxcTx(P)s.t.Ax≤b

x≥0其中,

c,x

Rn

b

Rm

Amn

矩阵二线性规划的单纯形法

线性规划的理论：考虑(LP)的最优性条件约束多面体S={xRnAx=b,x≥0}的极点和极方向定理1考虑(LP)及上述多面体S，设

A满秩，x(1),x(2),…,x(k)为所有极点，d(1),d(2),…,d(l)为所有极方向。那么，

1)(LP)存在有限最优解cTd(j)≤0,j.2)若(LP)存在有限最优解,则最优解可以在某个极点达到.二线性规划的单纯形法

线性规划的理论定理2考虑(LP),条件同上，设x*为极点,存在分解A=[B,N]，其中B为m阶非奇异矩阵，使x*T=[xB*T,xN*T],

这里xB*=B-1b≥0,xN*=0，相应cT=[cBT,cNT]。那么，

1）若

cNT-cBT

B-1N≤0,则

x*--opt.2）若

cj-cBT

B-1aj>0,且B-1aj≤0,则(LP)无有界解.线形规划的基本性质(一)．线形规划的可行域定理1：线形规划的可行域是凸集定理2：线形规划的可行域非空，若存在有限最优解，则目标函数的最优值可在某个极点上达到。(二)．最优基本可行解设矩阵A的秩为m，假设A=[B，N]，其中B为m维的可逆矩阵，相应有x=Ax=[B，N]=B+N=b=b-N

可任意,取=0=基本解：B基矩阵，若b0，xx=为约束条件Ax=b，x0的基本可行解，B为可行基矩阵b>0非退化的b0退化的x=0定理3：令k={x|Ax=b，x0}，A是mn矩阵，A的秩为m，则k0的基本可行解等价。的极点集与Ax=b，x三．存在的问题定理4：如果Ax=b，x>0有可行解，则一定存在基本可行解，其中A为m四．基本性质①可行解F={x|Ax=b，x②有可行解就一定有基本可行解③顶点与基本可行解一一对应，最优点一定可在基本可行解中找到④若有两个或两个以上的顶点是最优解，则凸组合均为最优解⑤基本可行解是有限的n矩阵，秩为m。0}为凸集1947年，丹茨格，研究出了单纯形法线形规划：目标函数，约束方程均为线形的①线形规划，合理的精度②高效的手段，方法③参数变化（灵敏度）易处理二线性规划的单纯形法表格单纯形法1、原理

Maxf(x)=cTx(LP)s.t.Ax=b

x≥0其中,

c,xRn

b

Rm

A

mn

矩阵，秩（A）=m记A=[,,…，]===[]=设x=由Ax=b=-代入目标函数可将A矩阵分解为[B，N]f=x=[]=+(-)+-(-)--若>0得到使目标函数减小的新基本可行解。===-=在n-m

个非基变量中，使其中n-m-1个非基变量仍为零，而令一个非基变量不为零。如果Xk增大，取正值；如果-选择，使=max假设-

>0，由零变为正数，得到Ax=b的解：=记=-

====-（3）越大，f减小的量越大；--=新的目标值为：f=-(-)

(4)如何确定①由（4）式，越大，f下降越多的取值受到可行解的限制-

>0，由零变为正数？②由（3）式，假设二线性规划的单纯形法2、算法过程

MaxcTx(LP)s.t.Ax=b

x≥0其中,

c,xRn

b

Rm

A

mn

矩阵，秩（A）=m二线性规划的单纯形法

单纯形法原理及算法过程算法过程(考虑一般步,k=0,1,2,…)设x(k)

为极点,对应分解A=[B,N]，使

xT=[xBT,xNT],这里xB=B-1b>0,xN=0，

相应cT=[cBT,cNT]。那么，

1）若

cNT-cBT

B-1N≤0,则x(k)–opt，停；

2）否则，存在

cj-cBT

B-1pj>0,a）若B-1pj≤0,则(LP)无有界解，停；

b）若存在

(B-1pj)i>0,

取α=min{(B-1b)i/(B-1pj)i

|(B-1pj)i

>0}=(B-1b)r/(B-1pj)r>0二线性规划的单纯形法

单纯形法原理及算法过程(续)

得到x(k+1)=x(k)+αd是极点其中,dT=[dBT,dNT

],这里j

dB=-B-1pj,dN=(0,...,1,…,0)T有,cTx(k+1)=cTx(k)+αcTd

=cTx(k)+α(cj

-cBTB-1pj)

>

cTx(k)

所以，x(k+1)

比

x(k)好重复这个过程，直到停机。二线性规划的单纯形法

表格单纯形法2、单纯形表：设x

为初始极点,相应分解A=[B,N]fxBTxNTRHS目标行1cBTcNT01行约束行0BNbM行1列m列n-m列1列作变换，使前m+1列对应的m+1阶矩阵变为单位矩阵。相当于该表左乘

1cBT-11-cBT

B-1

0B

0B-1

=二线性规划的单纯形法

表格单纯形法得到：检验数fxBTxNTRHS目标行10TcNT-cBT

B-1cBTB-1

b1行

xB0IB-1NB-1bM行1列m列n-