《最优化理论与算法(第一章).doc》由会员分享，可在线阅读，更多相关《最优化理论与算法(第一章).doc（30页珍藏版）》请在金锄头文库上搜索。
1、最优化理论与算法（数学专业研究生）第一章 引论1.1 引言一、历史与现状最优化理论最早可追溯到古老的极值问题，但成为一门独立的学科则是在20世纪四十年代末至五十年代初。其奠基性工作包括Fritz John最优性条件（1948），Kuhn-Tucker最优性条件（1951），和Karush最优性条件(1939)。近几十年来最优化理论与算法发展十分迅速，应用也越来越广泛。现在已形成一个相当庞大的研究领域。关于最优化理论与方法，狭义的主要指非线性规划的相关内容，而广义的则涵盖：线性规划、非线性规划、动态规划、整数规划、几何规划、多目标规划、随机规划甚至还包括变分、最优控制等动态优化内容。本课程所涉及
2、的内容属于前者。二、最优化问题的一般形式1、无约束最优化问题 （1.1）2、约束最优化问题 （1.2）这里和均为指标集。1.2数学基础一、 范数1. 向量范数 （范数） （1.3） （范数） （1.4） （范数） （1.5） （范数） （1.6） （正定） （椭球范数） （1.7）事实上1范数、2范数与范数分别是 范数当 1、2和时情形。2矩阵范数定义1.1 方阵的范数是指与相关联并记做的一个非负数，它具有下列性质： 对于都有，而时； 对于任意，都有； ； ；若还进一步满足： 则称之为与向量范数相协调（相容）的方阵范数。若令 （这里是某一向量范数） （1.8）可证这样定义的范数是与向量范数相协
3、调的，通常称之为由向量范数诱导的方阵范数。特别地，对方阵，有：（列和的最大者） （1.9）（行和的最大者） （1.10）（表示的特征值的最大者） (1.11)称为谱范数（注：方阵的特征值的模的最大者称为的谱半径，记为）。对于由向量诱导的方阵范数，总有： ，（为单位阵）对于方阵范数，除了上述由向量范数诱导的范数之外，还有常用的Frobenius范数，简称F-范数： (1.12)及加权Frobenius范数和加权范数: (1.13) (1.14) 其中为对称正定矩阵。3. 范数的等价性定义1.2 设与是上的两个范数，若存在，使得， (1.15)则称范数与是等价的。容易证明： (1.16) (1.1
4、7) (1.18) (1.19) (1.20)其中是的最大特征值，而是的最小特征值。由此可见，中的常用向量范数均等价，事实上还可证明：中所有向量范数均等价。4. 关于范数的几个重要不等式。 Cauchy-Schwarz不等式（当且仅当和线性相关时，等式成立） (1.21) 设是正定矩阵，则（当且仅当与线性相关时，等式成立） (1.22)由是一种内积，以及一般内积的Cauchy-Schwarz不等式即得。 设是正定矩阵，则（仅当与线性相关时，等式成立） (1.23) (1.24)其中的不等号由可得。 Young不等式：假定与都是大于1的实数，且满足，则，有 ， (1.25)当且仅当 时，等式成立
5、。其证明由算术几何不等式直接给出，事实上（算术几何不等式） Hlder不等式 (1.26)其中与都是大于1的实数，且满足，其证明利用Young不等式可得。 Minkowski不等式，（） (1.27)后面将利用凸函数理论予以证明。 二、矩阵求逆与广义逆1. Von-Neumann引理定理1.3 (Von-Neumann引理) 设，是单位阵，是满足的相容矩阵范数。如果，则非奇异，且， 若非奇异，,则非奇异，且， .证明：因为，故 定义了一个Cauchy序列，因而收敛。由 可得 故有 进一步有 。再令 ，知 由上面结论可得，所以有 进一步有 。注：这个定理表明，若充分接近一个可逆矩阵，则也可逆，且
6、逆矩阵可由的逆矩阵来表示。上述定理还可以写成下面形式：定理1.4 设,，可逆，。若，且，则可逆，且。证明：只需注意到，再由上述Von-Neumann引理即得。2. 广义逆定义1.5 设，若满足： (1.28)则称是的广义逆。其中是的共轭转置。广义逆的求法 设，秩，若直交分解为，其中，分别为酉矩阵，其中是非奇异的上三角矩阵。则的广义逆为： 其中 (1.29) 若的奇异值分解为，其中，均为酉矩阵，而是的非零奇异值，则的广义逆为：，其中 (1.30) 若的最大秩分解为，则的广义逆为：. (1.31)三、 矩阵的Rayleigh商定义1.6 是 Hermite矩阵，则称 （） (1.32)为矩阵的Ra
7、yleigh商定理1.7 设是 Hermite矩阵，则Rayleigh商具有下列性质：1) 齐次性： （） 2) 极性： 这里，分别对应于矩阵的最大与最小特征值。这表明Rayleigh商具有有界性： 3）极小残量性质：对任意，。证明：1）由定义直接可得。2）由是Hermite矩阵，故存在酉矩阵，使又令 ，且，故则 当取时达到最大值，当取时，达到最小值。3）令，则，可直接验证，由于 注意到是与共线的，故与正交。即与是的正交分解。因而是在上的直交投影，因而具有极小残量性质。四、矩阵的秩一校正当矩阵变到时，即在上加了一个秩为1的矩阵，称为秩一校正。下面讨论如何求秩一校正的逆，行列式，特征值及矩阵分解
8、。定理1.8 设是非奇异的，是任意向量。若，则的秩一校正非奇异，其逆矩阵可以表示为 (1.33)证明：可直接验证。上述定理的可进一步推广为：定理1.9 设是非奇异矩阵，是矩阵，若可逆，则可逆，且 (1.34)下面介绍关于秩一校正的行列式定理定理1.10 1）2）证明： 1）若，则结论显然成立；若，设是的特征向量。则易见要么与垂直，要么与平行。若与垂直，则特征值为1；若与平行，则对应特征值为。 进一步，平行于的特征向量只有一个（线性无关），而垂直于的线性无关的向量有个，它们均为属于特征值1的特征向量，即特征值1是重根， 而是单根。故有 。2） 对使用上面结果，故有： 。关于秩一校正矩阵的特征值定
9、理。定理1.11设是对称矩阵，其特征值为，又设，其特征值为，那么1） 若，则2） 若，则五、函数与微分1.多元函数的梯度与Hessian矩阵梯度 (1.35)Hessian矩阵 (1.36)方向导数：（设为一方向向量，即长度为1的单位向量，显然与范数的取法有关） (1.37)注：对欧氏范数（2范数）而言，梯度方向是函数上升最快的方向，而负梯度方向则是函数下降最快的方向。正因为这个原因，使得梯度在最优化理论与算法中占有特殊重要的地位。若在开凸集上连续可微，则有 （1.38）其中。上式也可改写为： 或 若在上二阶连续可微，则对于任何，存在，使得2.向量函数的微分设是一个向量函数，若其每个分量都连续
10、可微，则称连续可微。在处的导数记为： （1.39）称之为在处的Jacobi矩阵，而称为向量函数在处的梯度。若在开凸集上连续可微，则对任何，有：定义1.12 在处称为Lipschitz连续的，若，都有。若在中每一点均Lipschitz连续，则称在上Lipschitz连续，记为。其中，称为Lipschitz常数。定理1.13 （向量函数线性化近似的误差估计）设在开凸集上连续可微，在的邻域中Lipschitz连续，则对于任何，有.证明： 从而 注：在上述证明过程中的第一个不等式并不平凡，它实际上要求，对一般向量函数的积分，下述命题成立。 命题：对可积向量函数，有.证明：对于范数上述命题是成立的，这是因为：对于范数上述命题也成立。事实上，对于一般范数，需借助于Banach空间弱Riemann积分理论进行证明。定理1.13给出了线性近似的误差界，下面考虑二次近似的误差界。定理1.14 设在开凸集上二次连续可微，在的邻域上Lipschitz连续。则对于任何有：证明： 定理1.15 设在开凸集上连续可微，则对任何，有，若进一步在中Lipschitz连续，则有：
