最优化理论与算法（数学专业研究生）第一章 引论§ 引言一、历史与现状最优化理论最早可追溯到古老的极值问题，但成为一门独立的学科则是在20世纪四十年代末至五十年代初。

其奠基性工作包括Fritz John 最优性条件（1948），Kuhn-Tucker 最优性条件（1951），和Karush 最优性条件(1939)。

近几十年来最优化理论与算法发展十分迅速，应用也越来越广泛。

现在已形成一个相当庞大的研究领域。

关于最优化理论与方法，狭义的主要指非线性规划的相关内容，而广义的则涵盖：线性规划、非线性规划、动态规划、整数规划、几何规划、多目标规划、随机规划甚至还包括变分、最优控制等动态优化内容。

本课程所涉及的内容属于前者。

二、最优化问题的一般形式 1、无约束最优化问题min ()nx Rf x ∈ （） 2、约束最优化问题min ()()0, ..()0, i i f x c x i E s t c x i I=∈⎧⎨≥∈⎩ （）这里E 和I 均为指标集。

§数学基础一、 范数 1. 向量范数max i x x ∞= （l ∞范数） （）11ni i x x ==∑ （1l 范数） （）12221()ni i x x ==∑ （2l 范数） （）11()np pi pi xx ==∑ （p l 范数） （）12()TAxx Ax = （A 正定） （椭球范数） （）事实上1－范数、2－范数与∞-范数分别是 p －范数当 p ＝1、2和p →∞时情形。

2．矩阵范数定义 方阵A 的范数是指与A 相关联并记做A 的一个非负数，它具有下列性质： ① 对于0A ≠都有0A >，而0A =时0A =； ② 对于任意k R ∈，都有kA k A =； ③ A B A B +≤+； ④ AB A B ≤； 若还进一步满足： ⑤ pp AxA x ≤则称之为与向量范数p g 相协调（相容）的方阵范数。

若令maxx AxA x≠= （这里x 是某一向量范数） （） 可证这样定义的范数是与向量范数g 相协调的，通常称之为由向量范数g 诱导的方阵范数。

特别地，对方阵()ij n n A a ⨯=，有：11max nij ji A a ==∑（列和的最大者） （）1max nij ij Aa ∞==∑（行和的最大者） （）122()T A A A λ=（T A A λ表示T A A 的特征值的最大者）称为谱范数（注：方阵A 的特征值的模的最大者称为A 的谱半径，记为()A ρ）。

对于由向量诱导的方阵范数，总有：101min x A Ax x-≠=，1I =（I 为单位阵）对于方阵范数，除了上述由向量范数诱导的范数之外，还有常用的Frobenius 范数，简称F-范数：1122211()[tr()]n nTij F i j A a A A ====∑∑及加权Frobenius 范数和加权2l 范数:,M F FA MAM=,22M A MAM =其中M 为对称正定矩阵。

3. 范数的等价性定义 设αg 与βg 是n R 上的两个范数，若存在12,0μμ>，使得12xxx αβαμμ≤≤， n x R ∀∈则称范数αg 与βg 是等价的。

容易证明：212x x ≤≤2xx ∞∞≤≤1x x n x ∞∞≤≤ 21xx x ∞≤≤22A x ≤≤其中1λ是A 的最大特征值，而n λ是A 的最小特征值。

由此可见，nR 中的常用向量范数均等价，事实上还可证明：nR 中所有向量范数均等价。

4. 关于范数的几个重要不等式。

① Cauchy-Schwarz 不等式T x y x y ≤（当且仅当x 和y 线性相关时，等式成立）② 设A 是正定矩阵，则T AA x Ay xy ≤（当且仅当x 与y 线性相关时，等式成立）由(,)Tx y x Ay =是一种内积，以及一般内积的Cauchy-Schwarz 不等式即得。

③ 设A 是n n ⨯正定矩阵，则1T AAx y xy-≤（仅当x 与1A y -线性相关时，等式成立）111T T AAA Ax y x AA y xA yxy---=≤=其中的不等号由②可得。

④ Young 不等式：假定p 与q 都是大于1的实数，且满足111p q+=，则,x y R +∀∈，有 p qx y xy p q≤+， 当且仅当pqx y = 时，等式成立。

其证明由算术－几何不等式直接给出，事实上11()()p qpqp qx y xy xy p q=+≤（算术－几何不等式） ⑤ H ölder 不等式1111()()pq nnpqTi i pq i i x y xy x y ==≤=∑∑其中p 与q 都是大于1的实数，且满足111p q+=，其证明利用Young 不等式可得。

⑥ Minkowski 不等式pp p x yx y +=≤+，（1p ≥） 后面将利用凸函数理论予以证明。

二、矩阵求逆与广义逆 1. Von-Neumann 引理定理 (Von-Neumann 引理) 设n nE R ⨯∈，n nI R⨯∈是单位阵，g 是满足1I =的相容矩阵范数。

如果1E <，则()I E -非奇异，且1()k K I E E ∞-=-=∑， 11()1I E E--≤-若A 非奇异，1()A A B --1<,则B 非奇异，且1110()k k B I A B A ∞---==-∑， 1111()A B A A B ---≤--.证明：因为1E <，故 2kk S I E E E =++++L 定义了一个Cauchy 序列，因而收敛。

由1()k k S I E I E +-=-可得 1lim ()lim()k k k k S I E I EI +→∞→∞-=-=故有10lim ()kk k k ES I E ∞-→∞===-∑进一步有 11()1kk I E E E∞-=-≤≤-∑。

再令 1E I A B -=-，知 11()1E I A B A A B --=-=-< 由上面结论可得，11110()()()k k I E A B I A B ∞----=-==-∑所以有 111()k k BI A B A ∞---==-∑进一步有 11111110()1()kkk k A BI A BA A AB A A A B -∞∞------==≤-=-≤--∑∑。

注：这个定理表明，若B 充分接近一个可逆矩阵A ，则B 也可逆，且逆矩阵可由A 的逆矩阵来表示。

上述定理还可以写成下面形式： 定理 设A ,n nB R⨯∈，A 可逆，1Aα-≤。

若A B β-≤，且1αβ<，则B 可逆，且11B ααβ-≤-。

证明：只需注意到11()1A B A A B A αβ---≤-≤<，再由上述Von-Neumann 引理即得。

2. 广义逆 定义 设m nA C⨯∈，若n mA C+⨯∈满足：**,(),(),AA A A A AA A AA AA A A A A ++++++++====则称A +是A 的广义逆。

其中*A 是A 的共轭转置。

广义逆的求法 ① 设m nA C⨯∈，秩()A r =，若A 直交分解为*A Q RP =，其中Q ，P 分别为,m m n n ⨯⨯酉矩阵，m n R C ⨯∈，11000R R ⎛⎫= ⎪⎝⎭，其中11R 是r r ⨯非奇异的上三角矩阵。

则A 的广义逆为：*A P R Q ++= 其中 111000R R -+⎛⎫= ⎪⎝⎭② 若A 的奇异值分解为*A UDV =，其中U ，V 均为酉矩阵，000m nD C ⨯∑⎛⎫=∈⎪⎝⎭，而1(,,),0r i diag σσσ=>∑L 是A 的非零奇异值，则A 的广义逆为：*A VD U ++=，其中1000D -+⎛⎫∑= ⎪⎝⎭③ 若A 的最大秩分解为A BC =，则A 的广义逆为：**1*1*()()A C CC B B B +--=.三、 矩阵的Rayleigh 商定义 A 是n n ⨯ Hermite 矩阵，nu C ∈，则称**()u AuR u u uλ= （0u ≠）为矩阵A 的Rayleigh 商定理 设A 是n n ⨯ Hermite 矩阵，则Rayleigh 商具有下列性质： 1) 齐次性： ()()R u R u λλα= （0α≠）2) 极性： 2**1*10max max u u u Auu Au u uλ=≠==2***10min min n u u u Auu Au u uλ=≠==这里1λ，n λ分别对应于矩阵A 的最大与最小特征值。

这表明Rayleigh 商具有有界性： 1()n R u λλλ≤≤ 3）极小残量性质：对任意nu C ∈，(())()A R u I u A I u λμ-≤-，R μ∀∈。

证明：1）由定义直接可得。

2）由A 是Hermite 矩阵，故存在酉矩阵T ，使1*n T AT λλ⎛⎫ ⎪=Λ=⎪ ⎪ ⎪⎝⎭O又令 u Ty =，且21u=，故21y =则 22****11n n u Au y T ATy y y y y λλ==Λ=++L当取(1,0,,0)y =L 时达到最大值1λ，当取(0,0,0,1)y =L 时，达到最小值n λ。

3）令()()s u Au R u u λ=-，(0)u ≠，则()()Au s u R u u λ=+，可直接验证(),()0s u R u u λ=，由于 **((),)((),)()0s u u Au R u u u u Au R u u u λλ=-=-=注意到()R u u λ是与u 共线的，故()s u 与()R u u λ正交。

即()R u u λ与()s u 是Au 的正交分解。

因而()R u u λ是Au 在{}L u =上的直交投影，因而具有极小残量性质。

四、矩阵的秩一校正当矩阵A 变到TA uv +时，即在A 上加了一个秩为1的矩阵，称为秩一校正。

下面讨论如何求秩一校正的逆，行列式，特征值及矩阵分解。

定理 设m nA R⨯∈是非奇异的，,n u v R ∈是任意向量。

若10T v Au +≠，则A 的秩一校正TA uv +非奇异，其逆矩阵可以表示为11111()1T T T A uv A A uv A v A u-----+=-+证明：可直接验证。

上述定理的可进一步推广为：定理 设A 是非奇异矩阵，,U V 是n m ⨯矩阵，若*1I V A U -+可逆，则*A UV +可逆，且*111*11*1()()A UV A A U I V A U V A ------+=-+下面介绍关于秩一校正的行列式定理 定理 1）det()1T TI uv v u +=+2）123412341423det()(1)(1)()()T T T T T TI u u u u u u u u u u u u ++=++-证明： 1）若0u =，则结论显然成立；若0u ≠，设w 是()TI uv +的特征向量。