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

可知，，有再由，故有即由是中任一向量，所以有界，因而是有界闭凸集。定理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（一阶必要条件）若是局部极小点，则。定理1.48（二阶必要条件）若是局部极小点，则，。（半正定）定理1.49（二阶充分条件）是局部极小点的充分条件是：，且正定。注：使的点称为函数的稳定点。稳定点可以是极大点，也可是极小点，也可两者均不是，此时称为鞍点。定理1.50若是连续可微的凸函数，则是总体极小点的充要条件是。证明：必要性由定理1.47，充分性则由直接可得。§1.5.最优化算法的结构一、算法结构最优化算法通常采用迭代形式，由算法产生一个有限或无限点列。一般地，需要证明迭代点列的聚点（子序列的极限点）为一局部极小点。算法的基本迭代格式为：它包含两个要素：步长因子与搜索方向。在最优化算法中，通常是函数在处的下降方向，即满足：，或。基本结构给定初始点；(1)确定搜索方向；(2)确定步长因子，使目标函数值有某种程度的下降；(3)令，若满足某种终止条件，则迭代停止，得到近似最优解；否则重复以上步骤。二、算法的收敛速度定义1.51假设算法产生的点列收敛于最优解。若存在实数及一个与迭代次数无关的常数，使得则称算法产生的迭代点列具有阶收敛速度。特别地，(1)当，时，称为线性收敛；(2)当，或，时，称超线性收敛；(3)当时，称二阶收敛。注：若一个算法应用于正定二次函数时，具有有限终止性质，则称该算法二次收敛。二次收敛与二阶收敛是完全不同的概念，不存在孰强孰弱的简单关系。但大量数值计算结果表明：具有二次收敛性质的算法，实际计算性