计算方法第7章 - 最优化方法简介

第七章 最优化方法简介

7.1 最优化问题—— Optimization

Minf(x)?Minf(x1,x2,?,xn)s.t.gi(x)?gi(x1,x2,?,xn)?0i?1,2,?,m

可行域： D?x?Rngi(x)?0可行点： ?x?D

问题的解：x??D——最优解； 线性规划——f(x),gi(x)?i?1,2,?,m

?i?1,2,?,m——均为线性函数，

其他一般称为：非线性规划；

其中，若f(x)为二次函数，gi(x)i?1,2,?,m为线性函数——二次规划， 其他如：几何规划、动态规划 etc.

7.2 一维优化方法

对象：Minf(x),x?[a,b]?R， 简化： f(x),x?[a,b] 为

单峰函数——

x??[a,b],f(x)?:?x?[a,x?),?f(x)?:?x?(x,b]

当f(x)在[a,b]上可导，则问题转化为求解方程f?(x)?0的问题，这是第5章所讨论的内容。

以下讨论其他方法。

7.2.1 四等分法

等分方法，或分段检验的目的主要是希望能确定解在哪部分内从而可以保留，或者说哪部分可以删去。据此，使保留部分越来越小，获得所需要的结果。

比较：二等分法，三等分法。

如图，显然，二等分法无法确定极小点的位置，因此不能用（这与求方程的解是不同的（比较求最优：Maxf(x)??，解方程?f(x)?0）。

00三等分法，考虑分点x10,x2，可以比较f(x10),f(x2)，从图可以看到，极小点

必在函数值较小的点左右的区间，因此只需保留该区间，而删去较大点外的部分。因此，新区间与原区间长度之比为23；然而下一次，在进行三等分时，（2个）

1

三等分点将全是新点，其函数值需要重新计算。因此，这种方法用计算2个函数值，取得区间的收缩比是23。

四等分法：见下图

(0)(0)(0)区间[a,b]?[a0,b0]，取四等分点：x1，比较其函数值，保留以最,x2,x3小值点为中心的左右两个小区间：

(0)(0)(0)(0)(0)记：x0),f(x2),f(x3)，则保留?a0,x4?b0，若f(xi(0))?Minf(x10)(0)11(0)(0)[xi(?1,xi?1]，并记[a,b]?[xi?1,xi?1]； 如此重复进行。由于在以后各步，区间的

??三个四等分点中的中间点的函数值已在前步计算，所以只需计算2个函数值，区间的收缩比例为1；

2

7.2.2

0.618法（

5?1?0.618033989） 2 前面的三等分法，优点是每次只需比较2个函数值，缺点是以前计算过的点

2

的函数值以后没有充分利用，而四等分法的优点就在于以前保留下来的点的函数值在下次比较中又被利用。现在考虑一种方法，区间内只考察2个点的函数值，而保留下来的点的函数值又能在下次数值比较中能被充分利用。如图：分点x1,x2，

目的：求点方便——对称取点

在候选区间中，对称点保持比例?；

x?ax1?a 2???

b?ax2?a注意到 x1?a?b?x2?b?a?x2?a?(b?a)?(x2?a) 所以

x2?ab?a1??1??， 或 ?1??

?b?ax2?a?1?55?1 ，取正，得 ???0.618. 22??2???1?0??? 收缩率：

5?1?0.618 27.2.3 插值法——近似函数法： 1、二次插值法

设：x1?x2?x3，且x??(x1,x3)

插值多项式p(x)??li(x)f(xi)，令 p?(x)??li?(x)f(xi)?0，

2222)f(x3)?(x2?x3)f(x1)?(x3?x12)f(x2)1(x12?x2解得：x?

2(x1?x2)f(x3)?(x2?x3)f(x1)?(x3?x1)f(x2)若：x2?x1?x3?x2?h 则 （x1?x?h,x3?x?h）

x?f(x1)?f(x3)1?h(2x?h)f(x3)?h(2x?h)f(x1)?2h2xf(x2)h?x2?

2?hf(x3)?hf(x1)?2hf(x2)2f(x3)?2f(x2)?f(x1) 3

若： f?(x)??，则 取 x??x 否则：当f?(x)?0 取 [x1,x]为新的搜索区间，

当f?(x)?0 取 [x,x3]为新的搜索区间；

x为中心的区间为新 若f?(x)不易求得，则取Min?f(x2),f(x)??f(~x)，取以~的搜索区间；

2、三次插值法：

，用f(a),f(b),f?(a),f?(b)构造三次f?(x) 若可以计算（f?(x)?0难解）

插值多项式，求此多项式的零点：

u?w?z??x?(b?a)?1??a ?u?v?2w??3(f(a)?f(b))?v?u,其中 u?f?(a),v?f?(b),z?b?aw?z2?uv

注：记f(x0)?y0,f(x1)?y1,f?(x0)?m0,f?(x1)?m1则

H(x)?l0(x)y0?l1(x)y1?p0(x)m0?p1(x)m1

使：li(xj)??ij,li?(xj)?0,pi(xj)?0,pi?(xj)??ij,有

l0(x)?(1?2

x?x0x?x12)()x0?x1x0?x1x?x12)x0?x1l1(x)?(1?2x?x1x?x02)()x1?x0x1?x0x?x02)x1?x0

p0(x)?(x?x0)(p1(x)?(x?x1)(7.3 无约束优化

7.3.1 基本问题 （可微情况）： 若f(x,y) 在 (x0,y0) 处可微， 极值必要条件：

?f(x0,y0)?f(x0,y0)??0 ?x?y充分条件：Jacobian:??2f(x0,y0)?2x?2f(x0,y0)?x?y?2f(x0,y0)?y?x?0 2?f(x0,y0)?2y?2f(x0,y0)2?x?f(x)?f(x)?f(x)T,,?,) 一般，N维，梯度：?f(x)?(?x1?x2?xn 极大 ??2f(x0,y0)?x2?0， 极小 ??0

?2f(x) 〈连续?Hf(x)对称〉

?xi?xj极值必要条件：?f(x?)?0

4

充分条件：Hf(x?) 正定→极小，Hf(x?) 负定→极大。 7.3.2 梯度法（gradient） 在 x的小邻域，设：p?Rn,p??1

2则 f(x?p)?f(x)?pT?f(x)?O(p)?下降方向p应满足：pT?f(x)?0，

f(x?p)?f(x)?pT?f(x)

——由向量乘积定义——p与?f(x)之夹角?(?2,?]

p???f(x) 绝对值最大，——最速下降方向。

方法：xi?1?xi?ti?f(xi)， ti由一维优化确定： f(xi?1)?minf(xi?t?f(xi))

t终止判断：?f(x)??

但：方向不最速，例 f(x,y)?ax2?by2

?f(x,y)?(2ax,2by)T与该点处切线垂直 [2ax?2byy??0?y???y?y0??kaxbyax022(x?x0)?byy0?by0??axx0?ax0by0?by?? 切向量：???ax???(x0,y0)点处切线

??22?axx0?byy0?ax0?by0?c]

修正：

1. 可接受算法——降低要求（简化，减少一维优化工作量）——步长ti的选取： f(xi?1)?f(xi?ti?f(xi))?f(xi)

2．平行切线法——由图得到启发

若xi,xi?1,xi?2已取得，令p?xi?2?xi, 作为下降方向作一维搜索。 例：f(x,y)?x2?2y2

?2x??2x??0??????解： ?f(x)??〈事实上，?f(x)??0?x??4y??4y??0?? 〉 ???????1??2??1?0????取x0??作为方向，取,??f(x)??p?0?1??4??2?? ????????1??1???(1?t)?222?????minf???t?minf?min(1?t)?2(1?2t)?min3?10t?9t??????1?2t?????1??2??

?1?5??4??8?2?9???9???f(x1)??9?~p???t??5?x1??1??1??9?1?2?5???1???4???9??9??9?????? 5

??4??2????min(4?2t)2?2(?1?t)2?min18?20t?6t2?minf??9??t?99819?1????1?????9????????

t?5?27??4?10??2??4?1?227???27???f(x)??27?~p???x??92?2????1?5??2??8???27??27??27??92??2??1????min(2?t)2?2(2?2t)2?min122?20t?9t2?minf??27??t?272727272???2???????27???2?102?4?8?2?3??????t???x3???f(x)?~p?3??????9*279*27??1?9*27??1???1???????注意：?f(x0)??f(x1),?f(x1)??f(x2),?f(x2)??f(x3),且p0?p2,p1?p3， 及 x0,x2,x??0 在同一直线上，x1,x3,x??0 在同一直线上；

又，若用平行切线法：p?x2?x0??225?1???， ??27?1??2?1?25?1??一维优化：minf(x?tp)?minf??1???t27??1????27??,

??????2?x2?t?p?0， 此即极小点； 易得： t??257.3.3、变尺度算法（Veriable-Metric Algorithm，Quasi-Newton） 一、Newton法

任何二次函数可记为：

1 f(x)?xTAx?bTx?c

2从而，?f(x)?Ax?b,Hf(x)?A；

12)?(?1x1??2x2)?c 中 例如，二元函数 f(x)?(?11x12?2?12x1x2??22x22??11?12???1????A??,b?,??????12?22???2?

??11x1??12x2??1???11?12?????f(x)???Ax?b,H(x)??Af??x??x??????2222??121?12?22?事实上，由Taylor展开式

f(x)?f(0?x)?f(0)?xT?f(0)?1TxHfx 2 6

此处，由于f(x)为二次函数，其二阶以上偏导数总为0，所以只有这前三项；记

f(0)?c,?f(0)??b,Hf?A，就得前述表示形式。

1当A正定时 f(x)?xTAx?bTx?c有极小，且极小点为?f(x)?Ax?b?0

2的解x??A?1b，若用梯度法（最速下降法），在最优点邻近逐次得到的点将发生振荡。因此考虑采用Newton法求解方程?f(x)?Ax?b?0寻求最优点：

任取初值x(0)，有x(1)?x(0)?[(?f(x(0)))?]?1?f(x(0))，由(?f(x))??Hf(x)?A得x(1)?x(0)?A?1(Ax(0)?b)?A?1b?x?；

结论：对二次函数，用Newton法求解方程?f(x)?0，迭代一步便得到f(x)的最优点。

另一方面，对一般的函数f(x)，它在xk处的Taylor展开式：

21f(x)?f(xk)?(x?xk)T?f(xk)?(x?xk)THf(xk)(x?xk)?o(x?xk)

2当 x?xk??1时，可将最后一项略去，从而

~1 f(x)?fk(x)?f(xk)?(x?xk)T?f(xk)?(x?xk)THf(xk)(x?xk)

2即，f(x)在xk的邻近近似于如此形式的二次函数。

根据前前面对于二次函数最优问题求解算法的描述与分析，可以考虑的迭代

~方法：在xk处求解“f(x)的局部二次化”得到的fk(x)的极小问题，通过解方程

~~?fk(x)?0，以寻求fk(x)的最优点x(k?1)，以此作为求f(x)最优点的新的近似，由此逐步迭代生成序列xk。

~由于 ?fk(x)??f(xk)?Hf(xk)(x?xk)

~因此，解?fk(x)?0，便得到迭代：

??x(k?1)?x(k)?Hf(x(k))?1?f(x(k))k?0,1,? （*）

此处p(k)??Hf(x(k))?1?f(x(k))称为Newton方向。

然而由于一般f(x)不是二次函数，可能出现以下情况：

1）Hf(xk)奇异（无法执行此算法），或?f(xk)THf(xk)?1?f(xk)?0，即梯度方向?f(xk)与Newton方向正交（此时Newton方向非下降方向），则取负梯度方向为下降的搜索方向：p(k)???f(x(k))，该步仍采用梯度法；

2）Hf(xk)非奇异，但不正定：?f(xk)THf(xk)?1?f(xk)?0 （此时x(k)与最优点x?较远，否则由Hf(x?)正定，在x?邻近应Hf(xk)正定），由此，根据下降方向应与梯度方向的内积非正，因此令p(k)?Hf(xk)?1?f(xk)；

3）Hf(xk)正定，但Hf(xk)?1?f(xk)??1，这样的x(k?1)可能远离x?，即

7

不能保证Newton迭代法得到的 f(x(k?1))?f(x(k))，因此采用“下降法”——取阻尼因子?：

x(k?1)?x(k)??kHf(x(k))?1?f(x(k))?k?(0,1)，

使 f(x(k?1))?f(x(k))；

二、变尺度算法

?2f(x)由于Hf(x)包含n个函数（，而且导数往往难以求得； i,j?1,2,?,n）

?xi?xj2另一方面在最优点邻近函数近似于二次，因此考虑采用方法使矩阵Ak逐渐逼近。 Hf(x?) （因为若是二次函数，有Hf(x?)则可用Newton法一步到达最优点）

仿Newton法，x(k?1)?x(k)?Hf(x(k))?1?f(x(k))，用预估的矩阵Ak替代

Hf(xk)作以下一维优化：

f(x(k)?tkAk?1?f(x(k)))?minfx(k)?tAk?1?f(x(k))

令

t???1 x(k?1)?x(k)?tkAk?f(x(k)) （#）

另一方面，对二次函数，有 ?f(xk?1)?Axk?1?b,?f(xk)?Axk?b

k?1kk?1?xk) （**） ??f(x)??f(x)?A(x及

?f(x?)??f(xk)???f(xk)?A(x??xk)

比较Newton方程（*）：

??f(xk)?Hf(xk)(xk?1?xk)

考虑从x0,A0,出发，按（#）逐次由一维优化求得新点，而一旦由xk获得xk?1，希望接着更新Ak取得Ak?1，以便下一步计算（#），而在逐次修改矩阵Ak（作为

Hf(xk)的近似）的目标应该是：在xk趋近于x?的过程中，使Ak逐步趋近于Hf(x?)?A；另一方面，xk与xk?1获得后，它们的梯度?f(xk),?f(xk?1)也同时获得，从而可以设法由xk与xk?1、?f(xk),?f(xk?1)这些信息确定Ak?1，即可以要求Ak?1满足方程（**）的要求，即满足所谓的“拟Newton方程”： ?f(xk?1)??f(xk)?Ak?1(xk?1?xk) （***） 若记

zk?xk?1?xk?1,yk??f(xk?1)??f(xk)

则对应的“拟Newton方程”可改写为：

8

yk?Ak?1zk.

注意到此处的yk,zk同是向量，而在一维优化的计算中总要求Ak的逆，因此通常

?1直接用Bk?Ak进行计算；即另一形式的“拟Newton方程”：

Bk?1yk?zk （***） 由 Ak?Ak?1 或 Bk?Bk?1 的改进应比较简单、方便， Ak?1?Ak??Ak 或 Bk?1?Bk??Bk 等等；一种简单的方法采用秩1修正（还有秩2修正），即

TT Ak?1?Ak?ukvk 或 Bk?1?Bk?wksk

其中u,v,w,s?Rn（若秩2修正则u,v,w,s?Rn?2）这是因为，由Sherman-Morrion引理，若Ak?1存在，??1?vTA?1u?0 则

1 (A?uvT)?1?A?1?(A?1uvTA?1).

?A0(B0)A1(B1)An(Bn)算法：x0??f(x0)????x1??f(x1)?????????xn??f(xn)?0

以 Bk?1?Bk??Bk 代入（***），可有 ?Bkyk?zk?Bkyk

TT取 ?Bk?zkqk ?BkykwkTT其中qk,wk 满足 zkqkyk?Bkykwkyk?zk?Bkyk；

因为极小问题的Hf(x?)一般对称正定，因此通常取初始的B0对称（例如，通常取B0?I，以后的修正?Bk也对称。一类方法取（?为参数）：

T1??ykBkykTT q?z??ykkBk,TzkykTkT1??zkykTT w?TykBk??zkykBkykTk其中取不同的参数?，便可得到不同的方法，如 1） ??0 ——DFP方法：

11TT Bk?1?Bk?Tzkzk?TBkykykBk

zkykykBkyk1 ——BFGS方法 TzkykT1ykBkykTTT Bk?1?Bk?T(?zkzk?Bkykzk?zykBk),??1?

zTykzkyk2）??算法：B0?0,x0 ，

下降方向：pk??Bk?f(xk)， 一维优化，xk?1?xk?tkpk，使

f(xk?1)?f(xk?tkpk)?minf(xk?tpk)

9

计算?f(xk?1),yk??f(xk?1)??f(xk),zk?xk?1?xk； 按某种方法修正Bk，生成Bk?1，至此便可进入下一次循环。

n维问题：二次函数——n步终止性——精确一维搜索 一般，n步重开始。

7.3.4 直接搜索法

1、模式搜索——取步长向量 δ?(?1,?2,?,?n)T

k I）试探移动： 记x0?xk，取：

?xik?1??iei? xik??xik?1??iei?xk?i?1ififf(xik?1??iei)?f(xik?1)f(xik?1??iei)?f(xik?1) otherwisekk 若 xn i) if ?i??0 缩小步长，（例如，步长减半，或按某系数缩小） ?x0 ii) if ?i??0, stop.

kkkk II) 模式移动：令pk?xn?x0,y0?xn?pk kkk?1k If f(y0 )?f(xn) then x0?y0k?1k Otherwise x0 ?xn注意：方法失效情况！《参考书中图形》 2、单纯形法——直观启发 设 f0?f1?f2：

x1?x2令xc?，

21）反射?x3（图（a）） ① Iff1?f3?f2

尚可，以x1,x2,x3为新单纯形，重新开始； ② Iff1?f2?f3 佳，扩

张，x4?xc??(x3?xc) （1???2） （图（b）） Iff3?f4，以x1,x2,x4 为新单纯形，重新开始；

10

Iff4?f3，以x1,x2,x3为新单纯形，重新开始；

③ If i) ii)f3?f1?f2，即x3存疑：

f0?f3?f1，即x3可能比x0好，令 x4?xc??(xc?x0) f3?f0?f1，即x3比x0差，令 x4?xc??(xc?x0)

f4?min(f0,f3)，则以x1,x2,x4为新单纯形，重新开始；

判断：If 否则，向x2（最佳点）收缩，形成新单纯形，重新开始； ④ 终止：If??f(x)?f(x)?i0i?1n2?? （n维单纯形，共 n?1 个顶点，其函数

值的离差足够小）；取各顶点中函数值最小者为最优值点。

7.4 约束最优化方法简介

7.4.1 Lagrange乘子法

对象：等式约束

?Minf(x)?f(x1,x2,?,xn)??s.tgi(x)?gi(x1,x2,?,xn)?0i?1,2,?,m(m?n)

Lagrange函数

L(x,λ)?f(x)???igi(x)

i?1m求L(x,λ)的（关于x,λ）无约束最优，则最优点(x?,λ?)应满足：

??L(x?,λ?)?f(x?)m??gi(x?)????i?0j?1,2,?,n??xj?xj?x?i?1j ?????L(x,λ)?g(x?)?0i?1,2,?,mi????i显然，关于x,λ的Lagrange函数无约束最优点(x?,λ?)的x?是：满足约束条件下，函数f(x)的最优点。

若非等式约束：gi(x)?0?gi(x)??i2?0 因此转化为：

L(x,λ,μ)?f(x)???i?gi(x)??i2?

i?1m无约束最优化：

11

??????????L(x?,λ?,μ?)?f(x?)m??gi(x?)????i?0j?1,2,?,n?xj?xj?xji?1?L(x?,λ?,μ?)?gi(x?)?(?i?)2?0i?1,2,?,m

??i??L(x,λ?,μ?)???2??i?1,2,?,mi?i?0??i???情况：i)?*, 此时关于约束 gi(x)?0 在可行域g(x)?0,?x?0,??0iii内（或：此约束非有效，non-active）；

ii)?*?i??0, 此时gi(x?)?0,?x?在关于约束gi(x)?0的可行域边界i?0,上；

?*?，iii)?*i??i?0，问题的最优解x与无此约束gi(x)?0的解一致（??i?0）

且x?在关于约束gi(x)?0的可行域边界上（??i??0）；

7.4.2 梯度法

若xk在可行域内，按无约束梯度法，取 pk???f(xk)?f(x)k 一维优化（再比较约束）；

若xk在可行域边界，有效约束gi(xk)?0i?i1,i2,?,is，则 pk???f(xk)?f(x)k???g(xk)ii?gi(xk)

7.4.3 罚函数法——转化为无约束问题 ⑴ 外点罚函数法

F(x,?)?f(x)??m??(gi(x))

i?1?0ift?0??0 为逐次修正的参数——罚因子，?(t)??min?0,t??2??2

?tift?0???(gi(x))——罚项，

i?1m算法：给定??0，取0??0??1????k??k?1??，以x0为初值，求以后，再取x(?k)为初值，F(x,?0)?f(x)??0??(gi(x)) 之无约束极小：x(?0)；求F(x,?k?1)之无约束极小：x(?k?1)k?0,1,?；

i?1mIfx(?k) 满足：?k??(gi(x))??，则x(?k)可作为足够好的最优点（的近

i?1m似）x(?k)?x?。——对初值无要求，无论可行或不可行——允许在可行域外取

12

点，故称“外点罚函数法”。

⑵ 内点罚函数法

F(x,?)?f(x)???[gi(x)] 或 F(x,?)?f(x)???ln(gi(x))

?1i?1i?1mm讨论的点xk必须是可行点——可行域内的点，故称“内点罚函数法”。

算法：给定??0，及 ?k?0， ?0??1????k??k?1??，且 lim?k?0；从给定可行点x0出发，同外点罚函数法，以x(?k)为初值，求F(x,?k?1)的最优点

x(?k?1)，

Ifx(?k) 满足：?k?[(gi(x)]??，或 ?k?ln[gi(x)]??，则x(?k)可作

?1i?1mmi?1为足够好的最优点（的近似）x(?k)?x?。

⑶ 由于内点法?k?，而外点法?k?0，罚函数法易出现病态； 考虑将两者相结合；对点xk，凡可行的约束，取内点法，不可行的约束，或边界，取外点法：

F(x,?)?f(x)???ln(gi(x))?i?I1?(g(x)) ??ii?I21 I1??igi?01?i?m?,I2??igi?01?i?m?

13

本文来源：https://www.bwwdw.com/article/0kvp.html