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

#由定义容易推出：强分离n严格分离n正常分离n分离。定理1.45设S,SuRn是非空凸集，若SCIS=0，则存在超平面分离S与S，即存在非零向121212量pGRn，使得pTX<pTX，VxGS，VxGS121122证明：设S=S-S=lx-xxGS,xGS证明：设12121122由S是凸集，及0电S（否则SJS2皿），再由前面推论，存在非零向量pGRn，使得:pTx<pT0=0，VxGSo注意到S-SuS，由此可得12pTx<pTx，VxGS，VxGSo121122定理］・46设S1和S2是闭凸集，且S1有界，若SfS2=0，则存在一个超平面强分离S1和S2,即存在非零向量p和8>0，使得inf8+inf8+sup证明：设S=S-S，可证S是闭的。事实上，设{x}uS，且xTx。由S的定义知:12kkx=y-z，(yGS，zGS)kkkk1k2由于S是紧的，故存在收敛子列{y}，使得yTyGS。1kkGKk1由于kgK时，yty，y-ztxkkk因而有zTy-x=zGSk2由yGS，zGS，进而得12x=y-zGS-S=S，12即xgS，故S为闭集。于是，存在非零向量p和实数8，使得:pTx>8，VxGS且pT0<8o由8>0，及S的定义，我们有：pTx>8+pTx，VxGS，VxGSo121122结果得证。§1.4.无约束问题的最优性条件一、极小点的概念1．局部极小点2．严格局部极小点3．全局(总体)极小点4．严格全局(总体)极小点。注：在非线性规划中，大多数算法都致力于求最优化问题的局部极小点，这是由于一般地求全局极小点极为困难，仅当问题为凸规划时，局部极小为全局极小。二、最优性条件定理1.47(—阶必要条件)若x*是局部极小点，则Yf(x*)二0。定理1.48(二阶必要条件)若x*是局部极小点，则Y(x*)二0，V2f(x*)>0。(半正定)定理1.49(二阶充分条件)x*是局部极小点的充分条件是：Vf(x*)二0，且V2f(x*)正定。注：使Vf(x)=0的点x称为函数的稳定点。稳定点可以是极大点，也可是极小点，也可两者均不是，此时称为鞍点。定理1.50若f(x):RnTR是连续可微的凸函数，则x*是总体极小点的充要条件是Vf(x*)二0。证明：必要性由定理1.47，充分性则由f(x)>f(x*)+Vf(x*)T(x—x*)直接可得。§1.5.最优化算法的结构一、算法结构最优化算法通常采用迭代形式，由算法产生一个有限或无限点列。一般地，需要证明迭代点列{x」的聚点(子序列的极限点)为一局部极小点。算法的基本迭代格式为：kx=x+adk+1kkk它包含两个要素：步长因子Q与搜索方向d。在最优化算法中，d通常是函数f在x处的下降方kkkk

向，即d满足：kdTVf(x)<0，或f(x+ad)<f(x)。kkkkkk基本结构给定初始点x；0确定搜索方向d；k确定步长因子a，使目标函数值有某种程度的下降；k令x二x+ad，若x满足某种终止条件，则迭代停止，得到近似最优解x；否则重复k+1kkkk+1k+1以上步骤。二、算法的收敛速度定义1.51假设算法产生的点列｛x｝收敛于最优解x*。若存在实数a>0及一个与迭代次数k无k关的常数q>0，使得limkfgalimkfga|x-x*则称算法产生的迭代点列｛xk｝具有a阶收敛速度。特别地,当a=1，q>0时，称为线性收敛；当1<aV2，q>0或a=1，q=0时，称超线性收敛；当a=2时，称二阶收敛。注：若一个算法应用于正定二次函数时，具有有限终止性质，则称该算法二次收敛。二次收敛与二阶收敛是完全不同的概念，不存在孰强孰弱的简单关系。但大量数值计算结果表明：具有二次收敛性质的算法，实际计算性能一般都较好，因而二次收敛也常作为一个好算法的标志。三、关于常用算法的终止条件定理1.52若序列｛x｝超线性收敛到x*，那么klim|x一x*证明：略此定理的意义在于：当算法具有超线性收敛性质时，可用卜-X||<e替代|lx-x^l<£作为k+1kk算法停止准则。事实