最优化理论与算法(第一章)

最优化理论与算法（数学专业研究生）第一章 引论1.1 引言一、历史与现状最优化理论最早可追溯到古老的极值问题，但成为一门独立的学科则是在20世纪四十年代末至五十年代初。其奠基性工作包括Fritz John最优性条件（1948），Kuhn-Tucker最优性条件（1951），和Karush最优性条件(1939)。近几十年来最优化理论与算法发展十分迅速，应用也越来越广泛。现在已形成一个相当庞大的研究领域。关于最优化理论与方法，狭义的主要指非线性规划的相关内容，而广义的则涵盖：线性规划、非线性规划、动态规划、整数规划、几何规划、多目标规划、随机规划甚至还包括变分、最优控制等动态优化内容。本课程所涉及的内容属于前者。二、最优化问题的一般形式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）可证这样定义的范数是与向量范数相协调的，通常称之为由向量范数诱导的方阵范数。特别地，对方阵，有：（列和的最大者） （1.9）（行和的最大者） （1.10）（表示的特征值的最大者） (1.11)称为谱范数（注：方阵的特征值的模的最大者称为的谱半径，记为）。对于由向量诱导的方阵范数，总有： ，（为单位阵）对于方阵范数，除了上述由向量范数诱导的范数之外，还有常用的Frobenius范数，简称F-范数： (1.12)及加权Frobenius范数和加权范数: (1.13) (1.14) 其中为对称正定矩阵。3. 范数的等价性定义1.2 设与是上的两个范数，若存在，使得， (1.15)则称范数与是等价的。容易证明： (1.16) (1.17) (1.18) (1.19) (1.20)其中是的最大特征值，而是的最小特征值。由此可见，中的常用向量范数均等价，事实上还可证明：中所有向量范数均等价。4. 关于范数的几个重要不等式。 Cauchy-Schwarz不等式（当且仅当和线性相关时，等式成立） (1.21) 设是正定矩阵，则（当且仅当与线性相关时，等式成立） (1.22)由是一种内积，以及一般内积的Cauchy-Schwarz不等式即得。 设是正定矩阵，则（仅当与线性相关时，等式成立） (1.23) (1.24)其中的不等号由可得。 Young不等式：假定与都是大于1的实数，且满足，则，有 ， (1.25)当且仅当 时，等式成立。其证明由算术几何不等式直接给出，事实上（算术几何不等式） Hlder不等式 (1.26)其中与都是大于1的实数，且满足，其证明利用Young不等式可得。 Minkowski不等式，（） (1.27)后面将利用凸函数理论予以证明。 二、矩阵求逆与广义逆1. Von-Neumann引理定理1.3 (Von-Neumann引理) 设，是单位阵，是满足的相容矩阵范数。如果，则非奇异，且， 若非奇异，,则非奇异，且， .证明：因为，故 定义了一个Cauchy序列，因而收敛。由 可得 故有 进一步有 。再令 ，知 由上面结论可得，所以有 进一步有 。注：这个定理表明，若充分接近一个可逆矩阵，则也可逆，且逆矩阵可由的逆矩阵来表示。上述定理还可以写成下面形式：定理1.4 设,，可逆，。若，且，则可逆，且。证明：只需注意到，再由上述Von-Neumann引理即得。2. 广义逆定义1.5 设，若满足： (1.28)则称是的广义逆。其中是的共轭转置。广义逆的求法 设，秩，若直交分解为，其中，分别为酉矩阵，其中是非奇异的上三角矩阵。则的广义逆为： 其中 (1.29) 若的奇异值分解为，其中，均为酉矩阵，而是的非零奇异值，则的广义逆为：，其中 (1.30) 若的最大秩分解为，则的广义逆为：. (1.31)三、 矩阵的Rayleigh商定义1.6 是 Hermite矩阵，则称 （） (1.32)为矩阵的Rayleigh商定理1.7 设是 Hermite矩阵，则Rayleigh商具有下列性质：1) 齐次性： （） 2) 极性： 这里，分别对应于矩阵的最大与最小特征值。这表明Rayleigh商具有有界性： 3）极小残量性质：对任意，。证明：1）由定义直接可得。2）由是Hermite矩阵，故存在酉矩阵，使又令 ，且，故则 当取时达到最大值，当取时，达到最小值。3）令，则，可直接验证，由于 注意到是与共线的，故与正交。即与是的正交分解。因而是在上的直交投影，因而具有极小残量性质。四、矩阵的秩一校正当矩阵变到时，即在上加了一个秩为1的矩阵，称为秩一校正。下面讨论如何求秩一校正的逆，行列式，特征值及矩阵分解。定理1.8 设是非奇异的，是任意向量。若，则的秩一校正非奇异，其逆矩阵可以表示为 (1.33)证明：可直接验证。上述定理的可进一步推广为：定理1.9 设是非奇异矩阵，是矩阵，若可逆，则可逆，且 (1.34)下面介绍关于秩一校正的行列式定理定理1.10 1）2）证明： 1）若，则结论显然成立；若，设是的特征向量。则易见要么与垂直，要么与平行。若与垂直，则特征值为1；若与平行，则对应特征值为。 进一步，平行于的特征向量只有一个（线性无关），而垂直于的线性无关的向量有个，它们均为属于特征值1的特征向量，即特征值1是重根， 而是单根。故有 。2） 对使用上面结果，故有： 。关于秩一校正矩阵的特征值定理。定理1.11设是对称矩阵，其特征值为，又设，其特征值为，那么1） 若，则2） 若，则五、函数与微分1.多元函数的梯度与Hessian矩阵梯度 (1.35)Hessian矩阵 (1.36)方向导数：（设为一方向向量，即长度为1的单位向量，显然与范数的取法有关） (1.37)注：对欧氏范数（2范数）而言，梯度方向是函数上升最快的方向，而负梯度方向则是函数下降最快的方向。正因为这个原因，使得梯度在最优化理论与算法中占有特殊重要的地位。若在开凸集上连续可微，则有 （1.38）其中。上式也可改写为： 或 若在上二阶连续可微，则对于任何，存在，使得2.向量函数的微分设是一个向量函数，若其每个分量都连续可微，则称连续可微。在处的导数记为： （1.39）称之为在处的Jacobi矩阵，而称为向量函数在处的梯度。若在开凸集上连续可微，则对任何，有：定义1.12 在处称为Lipschitz连续的，若，都有。若在中每一点均Lipschitz连续，则称在上Lipschitz连续，记为。其中，称为Lipschitz常数。定理1.13 （向量函数线性化近似的误差估计）设在开凸集上连续可微，在的邻域中Lipschitz连续，则对于任何，有.证明： 从而 注：在上述证明过程中的第一个不等式并不平凡，它实际上要求，对一般向量函数的积分，下述命题成立。 命题：对可积向量函数，有.证明：对于范数上述命题是成立的，这是因为：对于范数上述命题也成立。事实上，对于一般范数，需借助于Banach空间弱Riemann积分理论进行证明。定理1.13给出了线性近似的误差界，下面考虑二次近似的误差界。定理1.14 设在开凸集上二次连续可微，在的邻域上Lipschitz连续。则对于任何有：证明： 定理1.15 设在开凸集上连续可微，则对任何，有，若进一步在中Lipschitz连续，则有：.证明： （由此式即可得第一部分结论）.定理1.16设满足上面定理条件，假定矩阵存在（这蕴含着是方阵，即）。则存在，使得，当时，有： 证明： （令） 从而右边不等式得证。另一方面，注意到：）故有 因此，若取，且令，则得左边不等式结论。由，可得，从而有。六、差商（偏差商）设是一个向量函数，其Jacobi矩阵的第行列元素可用差商（偏差商） 近似。由偏差商构成的矩阵称为的差商矩阵。显然差商矩阵的第列为关于差商矩阵与Jacobi矩阵有如下误差估计式定理1.17 设在开凸集上连续可微，在中Lipschitz连续，则 若采用的范数是范数，则有：证明： 将定理1.13中的取为，则有两边同除，则有 .类似地，也可以用中心差分来近似梯度和Hessian矩阵，并有如下误差估计结果。定理1.18 设在开凸集上二次连续可微，在上Lipschitz连续，又设所采用的范数满足，定义在处的中心偏差商为：则 如采用范数，则 ，其中.证明：由定理1.14有： 令，则有再令，又有令上两式中左端绝对值内的部分分别为，则有 由此即得：由范数的定义，有 .定理1.19 设在开凸集上二次连续可微，在上Lipschitz连续，采用的范数满足，假定。定义：则有： 若采用矩阵范数是或F-范数，则 （这里是Hessian矩阵的离散形式）。证明：令 经简单计算有： 又由定理1.14有， 进而有 再由矩阵及F-范数的定义立即可得：1.3 凸集与凸函数一、凸集（Convex Set）1凸集的概念定义1.20 设，若，都有 则称是凸集。定理1.21 的子集为凸集的充分必要条件是有 其中且。凸集的例子：维球、半空间、超平面、等均为凸集。定理1.22 若是中的凸集，则 1） 是凸集；（事实上，任意多个凸集的交仍为凸集） 2） 也是凸集2凸包 集合的凸包的定义如下： 由定义知，集合的凸包由中元素所有可能的凸组合构成。还可证明：它是所有包含集合的凸集的交，即它是包含集合的最小凸集。3锥、凸锥定义1.23 设，若，有，则称为锥；若锥还是凸集，则称之为凸锥。容易证明：是凸锥的充要条件是，对正组合运算封闭。定理1.23 若是凸集，则的闭包也是凸集。证明：，则存在序列，使得，从而有 ，注意到 及的闭性，可知这就证明了是凸集。4极点与极方向定义1.24 设是非空凸集，若不在中任何线段的内部，则称是凸集的极点。显然，多边形顶点、圆周上的点均为极点。定义1.25 设是闭凸集，为非零向量，若对任意，当时，总有，则称为的方向；若中的某方向不能表示为该集合的两个不同方向的正的线性组合，则称为的极方向。极点与极方向是凸多面体中非常重要的概念，在线性规划中有重要应用，关于这些方面的详细讨论，可参阅有关线性规划教材。二、凸函数定义1.26 设是非空凸集，是定义在上的函数，若对任意的都有： 则称是上的凸函数。凸函数的另一等价定义是：其中，。若时，不等式严格成立，则称在上是严格凸的。若在上是凸（严格凸），则称在上是凹（严格凹）。定理1.27 设是定义在凸集上的凸函数，1） 若，则是上的凸函数；2） 若是上的凸函数，则也是凸函数。由此立即可得：若是上的凸函数，则也是上的凸函数。凸函数的一阶特征定理1.28 设是非空开凸集，是定义在上的可微函数，则为凸函数的充要条件是： 证明：必要性，设是凸函数，则对任意的，有 因此有 令得 即 必要性得证。充分性： 设，成立。任取及，令，于是有： 于是有 即 亦即是凸函数，充分性得证。 几何解释：凸函数图像位于割线之下，切线之上。凸函数的二阶特征定理1.29 设是非空开凸集，是定义在上的二次可微函数，则为凸函数的充要条件是上的每一点的Hessian矩阵半正定。证明：充分性， 设 在每一点均半正定。任取，由中值定理有： ，（其中在以为端点的线段上）所以，是凸函数。必要性，设是凸函数，则任取，对任意的，充分小时有 另一方面 故 两边除以并令，则有即 半正定。注：对严格凸函数有类似的一阶与二阶特征，但要注意一些细微的差别。定理1.30 设是非空开凸集，是定义在上的可微函数，则为严格凸的充要条件是 ， 证明：充分性证明与前述凸函数情形完全类似，故从略。必要性的证明如下：设在上严格凸，且，令，则显然。由于严格凸，故有 及 由上两式有 因此有 .定理1.31设是非空开凸集，是定义在上的二次可微函数，若正定，则为严格凸函数。注：严格凸不能推出正定，因此正定是严格凸的充分条件，但不是必要条件。如， 不正定，但它是严格凸的。定理1.32 设是非空开凸集，是定义在上的凸函数，是一个实数，则水平集是凸集。证明： 略进一步，若是连续凸函数，则是闭凸集。事实上，设，且那么 所以 ，故为闭集。定理1.33 设是上二次连续可微的凸函数，且存在常数，使得 ，则水平集是有界闭凸集。证明：由上面讨论可知，是闭凸集，因而仅需 证明是有界的。由于是凸的，因而 ，从而有 由Taylor展开式， 可知，有 再由 ，故有 即 由是中任一向量， 所以有界，因而是有界闭凸集。定理1.34 （Minkowski不等式） 对，有，即： .证明：当或为零向量时，结论显然成立。当时，也易证明。以下设，且。考虑函数 ， 由于 ，故严格凸。注意到 由函数的凸性，于是有，因此， 由此即得 ，即 .三、一致凸函数定义1.35 设是非空凸集上的函数，若存在一个常数，使得对任意的，及任意。均有 ，则称在凸集上一致凸。由定义立即可知：一致凸严格凸凸。一致凸函数的判别定理定理1.36 设是非空开凸集上连续可微函数，则在上一致凸的充要条件是存在常数，使得，证明：先证必要性。若一致凸，则 从而 因此 （）而 将上式代入（）即得：令，得。再证充分性。任取，令，。由是凸集，故，因而有：两式分别乘和再相加，则有将代入即得结论：. 定理1.37 设是开凸集上连续可微函数，则在上一致凸的充要条件是：存在常数，使得 ，证明：参见徐成贤等著近代优化方法P15。定理1.38 设在开凸集上二阶连续可微，则在上一致凸的充要条件是：存在常数，使得： ，.证明：充分性：，有其中，。由于是凸集，故。因此，。令，则 。必要性：设在上一致凸。任取，且，则有 .四、凸集的分离与支撑凸集的分离与支撑定理在研究约束最优化问题的最优性条件时具有基本的重要性，起着十分关键的作用。定理1.39 设是非空闭凸集，则存在唯一的点，它与的距离最短。进一步，与距离最短的充要条件是： ，证明：先证定理的第一部分存在性 任取一点，则集合为一非空有界闭集，而是的连续函数，故它必在的某一点上取得最小值，此即为所求。注意到，而，必有。唯一性 假定还有，满足 。由的凸性，则 考虑 由是中点到的最小距离，故上式必取等式。因而必有 再由 ，得。 若，则 ，得 与矛盾。因而只能是，即 ，或，唯一性得证。再证定理第二部分 若，都有，则 即与有极小距离。反之，若，都有由于对充分小的，有因此 另一方面， 所以 两边同除，并令，即得所要的结果。点与凸集的分离定理定理1.40 设是非空闭凸集，则存在向量和实数，使得，并且同时满足 即超平面严格分离点和闭凸集。证明：由于是闭凸集，。故定理1.39知，存在唯一的一点，使得 ，取 ，则 ，也即 。再取 ，则，有 。又 故有 定理证毕。定理1.41 （Farkas引理）设，则下面两个等式与不等式系统有且仅有一个有解。 证明：若有解，则存在，使。下证必无解。事实上，若满足。那么 ，（由，）故方程组无解。若无解，记 则是非空闭凸集，且，由上面凸集的分离定理，存在，和，使得 ，且，由于，故 ，又 ，由于可任意大,而为固定常数，故必有。可见向量满足 ，且因而是的解，定理证毕。凸集与凸集的分离定理定义1.42 设是非空集合，（的边界）。若 或 ，则称是在处的支撑超平面；若，则称为在处的正常支撑超平面。定理1.43 设是非空凸集，。那么，在存在一个支撑超平面。即存在非零向量，使得 ，这里表示的闭包。证明：由于（是的一个边界点），故存在序列，每个均不属于，且。由定理1.40可知，对每个，存在，且，使得 ，。由于有界，故存在收敛的子列，设其极限为（显然有，故为非零向量）。对此子序列，当时，有，。对每个固定，在上式中令得：，这便是所需结论。推论：设是非空凸集，若，则存在非零向量，使得：，。证明：若，由定理1.40，存在超平面分离和。 若，由上面定理1.43即得。 定义1.44 设是非空凸集，若有， 且 ，则称超平面分离和；若，则称正常分离与；若， 且 ，则称严格分离与；若， 且 ，（其中）则称强分离与。由定义容易推出：强分离严格分离正常分离分离。定理1.45 设是非空凸集，若，则存在超平面分离与，即存在非零向量，使得，证明：设 由是凸集，及（否则），再由前面推论，存在非零向量，使得： ，。注意到，由此可得，。定理1.46 设和是闭凸集，且有界，若，则存在一个超平面强分离和，即存在非零向量和，使得 证明：设，可证是闭的。事实上，设，且。由的定义知：，（，）由于是紧的，故存在收敛子列，使得。由于时， ，因而有 由，进而得，即，故为闭集。于是，存在非零向量和实数，使得： ， 且 。由，及的定义，我们有： ，。结果得证。 1.4. 无约束问题的最优性条件一、极小点的概念1局部极小点2严格局部极小点3全局（总体）极小点4严格全局（总体）极小点。注：在非线性规划中，大多数算法都致力于求最优化问题的局部极小点，这是由于一般地求全局极小点极为困难，仅当问题为凸规划时，局部极小为全局极小。二、最优性条件定理1.47 （一