《数值最优化方法》课程教学课件（讲稿，打印版）最优化理论基础

最优化方法及其Matlab程序设计 第一章最优化理论基础 Back Close

1/36 JJ II J I Back Close Å`zê{9Ÿ Matlab ßSO 1òŸ Å`znÿƒ:

§1.1最优化问题的数学模型 通俗地说，所谓最优化问题，就是求一个多元函数在某个给定集 合上的极值.几乎所有类型的最优化问题都可以用下面的数学模型来 描述： min f(x), (1.1) s.t.x∈K, 这里，K是某个给定的集合（称为可行集或可行域），(x)是定义在集 合K上的实值函数.此外，在模型(1.1)中，x通常称为决策变量，s.t. 是subject to(受限于)的缩写. 人们通常按照可行集的性质对最优化问题(1.1)进行一个大致的 分类： ·线性规划和非线性规划.一可行集是有限维空间中的一个子集： Back ·组合优化或网络规划.一可行集中的元素是有限的： Close

2/36 JJ II J I Back Close §1.1 Å`zØKÍÆ. œÇ/`ߧ¢Å`zØKß“¥¶òáıºÍ3,áâ½8 ‹˛4ä. A§ka.Å`zØK—å±^e°ÍÆ.5 £„: min f(x), s.t. x ∈ K, (1.1) ˘pßK ¥,áâ½8‹ (°èå18½å1ç)ßf(x) ¥½¬38 ‹ K ˛¢äºÍ. d ß3. (1.1) •ßx œ~°è˚¸C˛, s.t. ¥ subject to (.Åu) †. <Çœ~UÏå185üÈÅ`zØK (1.1) ?1òáåó ©a: • Ç55y⁄öÇ55y. — å18¥kÅëòm•òáf8; • |‹`z½‰5y. — å18•É¥kÅ;

·动态规划.一可行集是一个依赖时间的决策序列： ·最优控制.一可行集是无穷维空间中的一个连续子集 本书主要考虑在工程设计中有着重要应用的非线性规划，其数 学模型为 min f(x), (1.2) s.t.h(c)=0,i=1,·,l, (1.3) g(x)≥0，i=1,·,m, (1.4) 其中，f(x),h(x(i=1,·,l)及g(x)(i=1,·,m)都是定义在R” 上连续可微的多元实值函数，且至少有一个是非线性的.记 E={i:h(x)=0},I={i:g(x)≥0}. (1.5) 若指标集EUI=0,称之为无约束优化问题，否则称为约束优化问 题.特别地，把E丰0且I=0的优化问题称为等式约束优化问题；而 Back Close

3/36 JJ II J I Back Close • ƒ5y. — å18¥òáù6ûm˚¸S; • Å`õõ. — å18¥Ã°ëòm•òáÎYf8. ÷Ãáƒ3ÛßO•kX­áA^öÇ55yßŸÍ Æ.è min f(x), (1.2) s.t. hi(x) = 0, i = 1, · · · , l, (1.3) gi(x) ≥ 0, i = 1, · · · , m, (1.4) Ÿ•ßf(x), hi(x) (i = 1, · · · , l) 9 gi(x) (i = 1, · · · , m) —¥½¬3 R n ˛ÎYåáı¢äºÍ, Öñkòá¥öÇ5. P E = {i : hi(x) = 0}, I = {i : gi(x) ≥ 0}. (1.5) eçI8 E ∪ I = ∅, °ÉèÃÂ`zØK߃K°èÂ`zØ K. AO/, r E 6= ∅ Ö I = ∅ `zØK°è™Â`zØK;

把I≠0且E=0的优化问题称为不等式约束优化问题.f(x)称为目 标函数，h(c),95(c)(i=1,·,l:j=1,.,m)称为约束函数.此外， 通常把目标函数为二次函数而约束函数都是线性函数的优化问题称 为二次规划；而目标函数和约束函数都是线性函数的优化问题称为 线性规划， 1.2向量和矩阵范数 在算法的收敛性分析中，需要用到向量和矩阵范数的概念及其 有关理论 设R”表示实n维向量空间，Rmxn表示实n阶矩阵全体所组成 的线性空间.在这两个空间中，我们分别定义向量和矩阵的范数， 向量x∈R”的范数‖x‖是一个非负数，它必须满足以下条件： (1)x‖≥0，xl=0→x=0 Back Close

4/36 JJ II J I Back Close r I 6= ∅ Ö E = ∅ `zØK°èÿ™Â`zØK. f(x) °è8 IºÍ, hi(x), gj(x) (i = 1, · · · , l; j = 1, · · · , m) °èºÍ. d ß œ~r8IºÍègºÍ º͗¥Ç5ºÍ`zØK° èg5y¶ 8IºÍ⁄º͗¥Ç5ºÍ`zØK°è Ç55y. 1.2 ï˛⁄› âÍ 3é{¬Ò5©¤•ßIá^ï˛⁄› âÍVg9Ÿ k'nÿ.  R n L´¢ n ëï˛òmßR n×n L´¢ n › N§|§ Ç5òm. 3˘¸áòm•ß·Ç©O½¬ï˛⁄› âÍ. ï˛ x ∈ R n âÍ kxk ¥òáöKÍßß7L˜v±e^áµ £1§kxk ≥ 0ßkxk = 0 ⇐⇒ x = 0;

(2)λx=A川x,入∈R; (3)x+yl≤lxl+ly: 向量x=(c1,.,xn)T的p范数定义为 zp=(∑cP. (1.6) 常用的向量范数有 1-范数：lx1=∑cl 2范数：l2=(P) 0o-范数：lxe=axlz 1<i< 矩阵A∈Rmxn的范数是一个非负实数，它除了满足跟向量范数 相似的三条性质之外，还必须具备乘法性质： (4)‖AB≤‖A‖B,A,B∈Rxm. Back Close

5/36 JJ II J I Back Close £2§kλxk = |λ|kxk, λ ∈ R; £3§kx + yk ≤ kxk + kyk. ï˛ x = (x1, · · · , xn) T  p-âͽ¬è kxkp = ￾X n i=1 |xi | p
1 p . (1.6) ~^ï˛âÍk 1-â͵kxk1 = P n i=1 |xi |; 2-â͵kxk2 = ￾ P n i=1 |xi | 2
1 2 ; ∞-â͵kxk∞ = max 1≤i≤n |xi |. › A ∈ R n×n âÍ¥òáöK¢Íßßÿ ˜vãï˛âÍ Éqn^5üÉ ßÑ7L‰¶{5üµ £4§kABk ≤ kAkkBk, A, B ∈ R n×n

如果一矩阵范数‖·‖相对于某向量范数‖·‖满足下面的不等式 (5)‖Axl‖≤LAll,x∈R”, 则称矩阵范数‖·‖和向量范数‖·‖是相容的.进一步，若存在x卡0 使成立 ‖Alμ=max ‖lAcl x max‖Axl,A∈Rmxn, (1.7） x≠0 x川=1 则称矩阵范数‖·‖4是由向量范数‖·‖诱导出来的算子范数，简称算 子范数，有时也称为从属于向量范数‖·‖的矩阵范数.此时向量范数 和算子范数通常采用相同的符号‖·‖ 不难验证，从属于向量范数x‖，‖x1,‖x2的矩阵范数分别 为 Ax=a∑ aijl, 1<<n 1=1 Back Close

6/36 JJ II J I Back Close XJò› âÍ k · kµ ÉÈu,ï˛âÍ k · k ˜ve°ÿ™ £5§kAxk ≤ kAkµkxk, x ∈ R n , K°› âÍ k · kµ ⁄ï˛âÍ k · k ¥ÉN. ?ò⁄ße3 x 6= 0 ¶§· kAkµ = max x6=0 kAxk kxk = max kxk=1 kAxk, A ∈ R n×n , (1.7) K°› âÍ k · kµ ¥dï˛âÍ k · k p—5éfâÍß{°é fâÍßkûè°èl·uï˛âÍ k · k › âÍ. dûï˛âÍ ⁄éfâÍœ~Ê^É”Œ“ k · k. ÿJyßl·uï˛âÍ kxk∞, kxk1, kxk2 › âÍ©O è kAk∞ = max 1≤i≤n X n j=1 |aij|

IlAll= 1≤j≤n i=1 lAl2=max{V入|入∈(ATA)} 它们分别称作行和范数、列和范数和谱范数. 本书在讨论各种迭代算法的收敛性时，通常采用谱范数和按下 述方式定义的F范数： Ar=(∑∑)'-VArA (1.8) 现在我们来讨论向量序列和矩阵序列的收敛性.我们知道，若 {x}21CR”,则 lim (=x←limx的=，i=l,.,n. Back Close

7/36 JJ II J I Back Close kAk1 = max 1≤j≤n X n i=1 |aij|, kAk2 = max{ √ λ | λ ∈ λ(A TA)}, ßÇ©O°ä1⁄âÍ!⁄âÍ⁄ÃâÍ. ÷3?ÿà´Sìé{¬Ò5ûßœ~Ê^ÃâÍ⁄Ue „꙽¬ F-âÍ: kAkF = X n i=1 X n j=1 a 2 ij1/2 = q tr(ATA) (1.8) y3·Ç5?ÿï˛S⁄› S¬Ò5. ·Çße {x (k)} ∞ k=1 ⊂ R n ßK lim k→∞ x (k) = x ⇐⇒ lim k→∞ x (k) i = xi , i = 1, · · · , n

类似地，若{A}e1CRx”,则 limA=A←1img=a,i,j=1,.,n. 为了利用范数来描述上述极限，必须建立向量范数的等价定理以及 矩阵范数的等价定理 定理1.1(1)设‖·‖和‖·'是定义在R”上的两个向量范数， 则存在两个正数C1,C2,对所有x∈Rn均成立 cillx≤lxl'≤c2. (2)设‖·‖和‖·'是定义在R”xm上的两个矩阵范数，则存在 两个正数m1,m2,对所有A∈Rmx均成立 mlA‖≤A'≤m2llAl. Back Close

8/36 JJ II J I Back Close aq/ße {A(k)} ∞ k=1 ⊂ Rn×n ßK lim k→∞ A (k) = A ⇐⇒ lim k→∞ a (k) ij = aij, i, j = 1, · · · , n. è |^âÍ5£„˛„4Åß7LÔ·ï˛âÍd½n±9 › âÍd½n. ½n 1.1 (1)  k · k ⁄ k · k0 ¥½¬3 Rn ˛¸áï˛âÍß K3¸áÍ c1, c2ßȧk x ∈ R n ˛§· c1kxk ≤ kxk 0 ≤ c2kxk. (2)  k · k ⁄ k · k0 ¥½¬3 R n×n ˛¸á› âÍßK3 ¸áÍ m1, m2ßȧk A ∈ R n× ˛§· m1kAk ≤ kAk 0 ≤ m2kAk

下面，我们利用范数的概念来等价地定义向量序列和矩阵序列 的收敛性， 定理1.2(1)设{x)}为n维向列序列，‖·‖为定义在R”上 的向量范数，则 limx肉=x←→lim ll()-x‖=0； k- (2)设{A}为n×n矩阵序列，‖·‖为定义在Rnxn上的向量 范数，则 limA=A←→1im‖A因-A‖=0. k00 1.3函数的可微性与展开 本节主要介绍后文经常需要用到元函数的一阶和二阶导数以 及泰勒展开式 Back Close

9/36 JJ II J I Back Close e°ß·Ç|^âÍVg5d/½¬ï˛S⁄› S ¬Ò5. ½n 1.2 (1)  {x (k)} è n ëïSßk · k 转3 R n ˛ ï˛âÍßK lim k→∞ x (k) = x ⇐⇒ lim k→∞ kx (k) − xk = 0; (2)  {A(k)} è n × n › Sßk · k 转3 R n×n ˛ï˛ âÍßK lim k→∞ A (k) = A ⇐⇒ lim k→∞ kA (k) − Ak = 0. 1.3 ºÍåá5Ü–m !Ãá0￾©²~Iá^ n ºÍò⁄ͱ 9V–m™.

定义1.1设有n元实函数f(c),其中自变量x=(ac1,.,xm)T∈ R”.称向量 Vf(x)= ∂f(x)∂f(x) ∂f( 0x1’∂x2 (1.9) 为f(x)在x处的一阶导数或梯度.称矩阵 82f(x) 82f(x) a2f(x) 0x3 0x1∂x2 0x1∂xn 82f(x) a2f(x) af(a) V2f(x)= 0x20x1 am喝 8x28Cn (1.10) ∂2f(c) 82f(x) 8f(x) 8xnOx1 0xn0x2 0r鼎 为f(x)在x处的二阶导数或Hesse矩阵.若梯度Vf(x)的每个分量 函数在x都连续，则称f在x一阶连续可微；若Hsse阵Vf(x)的 各个分量函数都连续，则称∫在x二阶连续可微 Back Close

10/36 JJ II J I Back Close ½¬ 1.1 k n ¢ºÍ f(x), Ÿ•gC˛ x = (x1, · · · , xn) T ∈ R n . °ï˛ ∇f(x) =  ∂f(x) ∂x1 , ∂f(x) ∂x2 , · · · , ∂f(x) ∂xn T (1.9) è f(x) 3 x ?òͽF›. °› ∇2 f(x) =   ∂ 2 f(x) ∂x2 1 ∂ 2 f(x) ∂x1∂x2 · · · ∂ 2 f(x) ∂x1∂xn ∂ 2 f(x) ∂x2∂x1 ∂ 2 f(x) ∂x2 2 · · · ∂ 2 f(x) ∂x2∂xn . . . . . . . . . ∂ 2 f(x) ∂xn∂x1 ∂ 2 f(x) ∂xn∂x2 · · · ∂ 2 f(x) ∂x2 n   (1.10) è f(x) 3 x ?ͽ Hesse › . eF› ∇f(x) zᩲ ºÍ3 x —ÎY, K° f 3 x òÎYåá¶e Hesse ∇2 f(x)  àᩲºÍ—ÎYßK° f 3 x ÎYåá.