土地利用与交通需求 PPT课件版 L2 最优化方法

1最优化方法杨超土地利用与交通需求分析同济大学email:tongjiyc@2向量和矩阵符号向量是变量的列表（小写，粗体）向量举例：

x=矩阵是变量的表格（大写，粗体）

矩阵举例：A=下标约定：行在前，列在后3矩阵运算转置:行变成列，列变成行乘积:

y=Ax

是

可表示成下面的方程

y1=a11x1+a12x2 y2=a21x1+a22x2

注意矩阵的大小要一致4求逆方程的解是x=A-1y求逆:

A-1= 其中k=1/(a11a22-a12a21)

注意如果a11a22=a12a21

则没有逆矩阵，因为

，相应的方程无解5分块矩阵6向量和矩阵微分7约束条件许多最优化问题要求可行解集是凸的、有边界的和紧凑的凸意味着若x1和x2

是可行解，那么x＝x1λ+x2(1-λ)(1≥λ≥

0)也是可行的，同时，x称为x1和x2

的凸组合有边界意味着解的边界包括在可行解集中的紧凑意思是在可行区间内没有洞8凸集x1x2x1x2可行区域9凸函数10凸最优化：内部解x1x2优化f=5f=10f=15f=20解空间目标函数等高线-3维变2维11凸最优化：边界解x1x2f=5f=10f=15f=20优化12凸最优化：线性约束x1x2f=5f=10f=15f=2013线性规划标准形式

and

:subjectto

minimize

0x

b=

Axcx³目标函数约束条件其中：c为价值系数，a为技术系数，b为限额系数14线性规划x1x2解f=5f=15f=20f=1015线性规划所有的解都是极值点（边界处的极点）极值点：x不在凸集中任何线段的内部，x为凸集的极值点

多边形的顶点和圆周上任意点都是极值点因此，只有可行区域的顶点需要被检查（开发单纯形方法中使用的insight）可能存在多重极小16最小和极小17举例：IronWorks,Inc.

问题陈述：IronWorks,Inc.(IWI)制造两种钢制产品，刚刚收到这个月配额b磅的钢材。它用a1磅钢作了产品1的一个单位，用

a2磅钢作了产品2的一个单位

令x1

和x2

分别表示产品1和产品2这个月的生产水平。分别用p1

和p2

表示产品1和产品2的单位利润

制造商有一个每月至少生产m个单位的产品1的合同，公司的设备每个月最多能生产产品2的数量为u

个单位。

18举例：IronWorks,Inc.数学模型月总利润=

（产品1每个单位的利润） x（产品1的月产量） +（产品2每个单位的利润） x（产品2的月产量） =p1x1+p2x2

我们要使月总利润最大：

Maxp1x1+p2x219举例：IronWorks,Inc.数学模型（续）每月生产所用的钢材的总量等于：

（产品1每个单位所需要的钢）x（产品1的月产量）+（产品2每个单位所需要的钢）

x（产品2的月产量） =a1x1+a2x2

这个数量必须少于或等于b磅钢材的配额：

a1x1+a2x2

<

b20举例：IronWorks,Inc.数学模型（续）产品1的月产量必须大于或等于m:

x1

>

m产品2的月产量必须小于或等于u:

x2

<

u然而产品2的月产量不得为负:

x2

>021举例：IronWorks,Inc.数学模型小结 Maxp1x1+p2x2 s.t.a1x1+a2x2

<

b

x1

>

m

x2

<

u

x2

>0目标函数“Subjectto”约束条件22举例：IronWorks,Inc.问题：假设

b=2000,a1=2,a2=3,m=60,u=720,p1=100,p2=200.用这些具体的数字来代替不可控输入重写模型答案： Max100x1+200x2 s.t.2x1+3x2

<2000

x1

>60

x2

<720

x2

>023举例：IronWorks,Inc.问题：当前模型的最优化解为x1=60，

x2=6262/3.若产品为引擎，解释为什么这不是真实问题的真正的最优解。答案：因为不可能生产并卖出2/3个引擎。这样这个问题就进一步受到x1

和x2

必须是整数的约束。而如果假设不完整的部分能在下一个月完成，那么它们仍能保持为分数。24举例：IronWorks,Inc.不可控输入产品1每单位$100利润产品2每单位$200利润每单位产品1需要2lbs.钢材每单位产品2需要3lbs.钢材2000lbs.钢材配额最少生产60单位产品1最多生产720产品2最少生产0单位产品2

60单位产品1626.67单位产品2可控输入利润=$131,333.33使用钢材=2000输出数学模型Max100(60)+200(626.67)s.t.2(60)+3(626.67)<200060>60626.67<720626.67>025单纯形法基本概念:从一个基本的可行解（顶点）开始沿着一条使目标函数值连续减小（增加）的路径进行，直到达到最小（最大）值。系统地搜寻过程:(G.B.Dantzig,1948)(1)寻找任意一个可行解作为起点(2)检查最优性，如果是则停止，否则(3)定位一个更佳的基本可行解并转向这个解(4)重复(2)26图表举例单纯形法

从一个角点移到下一个，每一次减少目标函数的值x1=0x2x1x2=0x5=0x3=0x4=0举例：max4x1+x2最优解27小结(I)解则有一个最优基本可行若有一个最优可行解，则有一个基本可行解若有一个可行解，矩阵，那么的是一个秩其中线性规划用标准形式假设基本定理

(2)

(1)

mxn

mA

:

and

:subjectto

minimize

0x

b=

Axcx³28小结(II)29非线性规划在本课程中大多数网络交通流规划问题有非线性目标但是有线性约束它们可以作为一系列线性规划（LP）问题来求解单变量无约束多变量无约束单变量有约束多变量有约束30无约束最优化问题：单变量其中二阶泰勒展开问题：)(

),(

Minimize

xfxf¶二阶偏微分

)()(2020xxfxfxx¶¶=是一阶偏微分

)(00xxfx¶º)())(())(()()(200210xxExxxfxxxfxfxfxxx-+-+-+=000Exfxxxfxxxfxxxxx:()(),()=-+=-=-2326612632231无约束最优化问题：单变量最优条件一阶必要条件二阶必要条件二阶充分条件)(x*fx=0)(x*fx=0x*为驻点，可能是极小、极大或鞍点)(x*fx=0)(x*fx=032无约束最优化：多变量33严格凸函数34无约束最优化问题：多变量最优条件梯度＝0，Hessian正定35举例36一般的优化方法设xk为第k此迭代点，dk为第k次搜索方向，ak为第k次步长因子，则第k次迭代为不同的步长因子ak和不同的搜索方向dk构成了不同的方法此外，初始点和终止条件也很重要37梯度法（最速下降法）•最速下降：多变量函数最小化问题历史最悠久被最广泛认识的方法容易分析基本技术的许多修正能使得收敛性更好•方法：38下降方向最速下降方向？39梯度法（最速下降法）40二阶目标函数.41例142例243牛顿法44举例45有约束最优化问题（单变量）有可能有一个最小值，其一阶微分不消失，令x*为最小值当最小值在起作用约束的边缘发生时(情况b&c)

s.t.46一些观察：单变量如果起作用约束条件的形式是

，那么是上升的或者在是非下降的（情况b）如果起作用约束条件的形式是，那么是下降的或者在是非上升的（情况c）47一些观察：单变量（续）为了保证一阶条件，需要将规划问题用标准形式描述（约束条件描述如）：s.t.48一些观察：单变量（续）Case(b):Case(c):两种情况都有同样的符号。因此，可以记做：是起作用约束是一个非负标量（或乘子）其中49一阶条件：单变量对于每一个约束（包括起作用和不起作用）可以记做：

若(i.e.,约束是不起作用的)，令若，约束是不起作用的若约束是起作用的组合这些观察50一阶条件：单变量（续）

总的来说，

有约束的最小化问题的一阶条件是：多变量的情况被称作Kuhn-Tucker(KT)或Karoush-Kuhn-Tucker(KKT)条件51有约束最优化问题（多变量向量形式）52拉格朗日乘子（或双重变量）0}=h(x)yy)L(x)x,)L(x)x,0=h(x)=)x,0=h(x)x=)x,h(x)x=)x,0=h(x)xxMM2xMM2xxxxѺѺÑÑÑ+ÑÑ+:{=M

(

(

()((

)(

(

subjectto

)(

Minimize

其中正定二阶：同上一阶：局部最小的充分条件半正定二阶：一阶：局部最小的必要条件拉格朗日函数等式约束：lllllllllllflflf

:53图形示例54举例55不等式约束正定二阶：同上一阶：局部最小的充分条件空间上是半正定的处的活动约束的正切子在二阶：使得向量和向量那么是一个局部最小值，若条件一阶局部最小的必要条件拉格朗日函数

),(

),(

)(

:

)(

)(

,(

subjectto

)(

Minimize

)L(xx,x)L(xx,0=)g(x0,)h(x0=)g(x+)h(xx0x

:g(x)+h(x)x=)x,0g(x)

0,=h(x)x02x002x000x0x0x0ºÑºÑ=ÑÑ+ѳ$+£mlmlmmlmlmlmlllfflf

Tucker-Kuhn

:56举例57特殊数学规划非负约束规划Minz(X)st.X>=0一阶条件：58特殊数学规划线性等式约束规划Minz(X)st.一阶条件：59特殊数学规划非负线性等式约束规划Minz(X)st.一阶条件：60有约束最小化算法保持可行性:方向：搜索方向必须指向至少存在一些可行点的方向2.步长：给定这样一个搜索方向，步长将不会造成不可行(i.e.,移动的大小只受可行点的约束)61有约束最小化算法（续）若是当前解，那么其中是第n次迭代的绑定约束的指数集给定一个可行方向可能的最大步长是:最优的步长通过求解下面问题获得：s.t.62凸组合算法（也叫Frank-Wolfe算法）s.t.考虑令为第n次迭代的解s.t.搜索方向：步长：s.t.更新：63举例

s.t.64举例（续）65Frank-Wolfe(F-W)算法F-W算法重复一下两个步骤直至收敛：下降方向：通过基于可行下降方向求解一个线性规划问题来找到极值点线性搜索：沿着连接当前点到极值点的线进行搜索66下降方向x1x2最速下降方向x’xFW下降方向67线性搜索x1x2沿着x’到x”的直线达到最小x’x”68搜索方法lux1x2f(x)[l,u][x1,u][l,x2][x1,x2]69减小区间法1n1n+11n+2an+1bn+1Z(x)迭代n迭代n+1anbnxx70黄金分割法r=0.6180333n:=0xL:=[b-a][1-r]+axR:=[b–a]r+an:=n+1b:=xRa:=xLxR:=xLxL:=xRxR:=[b–a]r+axL:=[b–a][1–r]+astopYesYesYesNoNoNo输入Output只要评估函数71二分法n:=0n:=n+1stopYesYesNoNoInputOutput需要评估梯度72比较黄金分割和二分法73Frank-Wolfe算法几何N:=1and初始化x1重复直到收敛MinimizeLP(x)=xTf(xN)subjectto得到辅助x*Minimize得到

然后N:=N+174用F-W算法的问题起初的线性搜索是没有效率的（不应在错误的方向上搜索太长）接近解时的曲折75连续平均法(MSA)

x*N=(1/N)i=1..Nxi

可以递归计算如下: x*N=(1/N)xN+(1–1/N)x*N-1Var(x)N=(1/N)i=1..N(xi–x*N)2

也可递归计算如下: Var(x)N=(1/N)(xN–x*N)2+(1–1/N)Var(x)N-1这形成了连续平均法的基础76用MSA的问题在早期迭代中固定步长是有益的，但在后面阶段并不好用于很难计算目标函数的情况77对数线性模型考虑:Minimize subjecttoKKT条件:

由于x>0，意味着lnx=-ATu*

得到下面的对数线性模型:

x=exp(-Atu*)78迭代平衡iterativebalancing有时候解对偶问题比解原始问题简单对于对数线性模型，对偶问题可以通过迭代平衡找到假设有一个可行解，迭代平衡收敛收敛的最后阶段可能比较慢79迭代平衡：约束为大于等于

Minimize

subjectto令u

为0对每个约束j重复直至收敛x:=exp(-ATu)uj:=Min(0,uj–lnbj+lnajTx)80迭代平衡：约束为小于等于

Minimize

subjectto令u

为0对每个约束j重复直至收敛x:=exp(-ATu)uj:=Max(0,uj–lnbj+lnajTx)81迭代平衡：约束为等于

Minimize

subjectto令u

为0对每一个约束j重复直至收敛x:=exp(-ATu)uj:=uj–lnbj+lnajTx82重力模型举例考虑最优化问题：Minimize subjectto 在最优点 其中ui,uj和是双变