最优化方法及其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