数学原理与模型分析-最优化基础.

1-多元函数及其微分[定义1.1]如果多元连续函数在对于x的各个分量的偏导数都存在，则称函数在x处一阶可导，并称向量为函数在x处的一阶导数或梯度（Gradient）RRfn:nTnRxxxx),,,(21nixxfi,,2,1,)(Tnxxfxxfxxfxf)(,,)(,)()(21)(xf1-多元函数及其微分[定义1.4]如果多元连续函数在对于x的各个分量的二阶偏导数都存在，则称函数在x处二阶可导，并称矩阵为函数在x处的二阶导数矩阵或海森矩阵（HesseMatrix）。RRfn:nTnRxxxx),,,(21njnixxxfji,,2,1,,,2,1,)(2)(xfnn22221222222122122122122)(,,)(,)()(,,)(,)()(,,)(,)()(nnnnnxxfxxxfxxxfxxxfxxfxxxfxxxfxxxfxxfxf)(xf1-多元函数及其微分[定义1.5]如果多元连续函数在对于x的各个分量的二阶偏导数都存在且连续，则称函数在x处二次连续可微。如果函数在开集中的每一点都二次连续可微，则称函数在D中二次连续可微，记作。显然，如果二次连续可微，则有从而是一个对称矩阵。RRfn:nTnRxxxx),,,(21njnixxxfji,,2,1,,,2,1,)(2)(xf)(xfnRD)(xf)(2DCf)(xfnjnixxxfxxxfijji,,2,1,,,2,1,)()(22)(2xf1-多元函数及其微分[例1]设是对称矩阵，向量，，求二次函数在任意点处的梯度和海森矩阵。[解]梯度为；海森矩阵为。nnRAnRb1RccxbAxxxfTT21)(bAxxf)(Axf)(2第3-3-2节共轭梯度法[例2]求解取初始点为1212221222123)(minxxxxxxf420x2-最优解的定义[定义1.36]设，（1）若对任意的，都有，则称为优化问题的全局最优解（极小点）。（2）若对任意的，，都有，则称为优化问题的严格全局（整体）最优解（极小点）。Dx)()(*xfxf*x*x)()(*xfxfDx*Dx*xx2-最优解的定义[定义1.37]设，若存在的一个邻域，使得：（1），则称为最优化问题的局部最优解（极小点）。（2），则称为最优化问题的严格局部最优解（极小点）。Dx**x)0(**|)(xxxxU)(),()(**xUDxxfxf*x***),(),()(xxxUDxxfxf*x2-最优解的定义几点说明：（1）显然，全局最优解也是局部最优解。反之不然。（2）本课讨论的求解最优解一般均指局部最优解。（a）人们在实际计算时往往关心的是全局最优解，但到目前为止，现有的在理论上成熟并且经过计算实践检验的算法，只能近似地求出局部最优解，而非全局最优解。（b）对于一般的寻求全局最优解的问题，通常采用的做法是先求出全部局部最优解，然后选择最优值最小的那个解作为全局最优解。（c）在很多实际应用中，求解局部最优解已经满足了问题的要求。（3）仅当研究的问题具有某种凸性时，局部最优解才是全局最优解。第1.4.2节无约束问题的最优性条件[定理1.41]（一阶必要条件）设f在开集D上连续可微，若是无约束最优化问题（*）的局部极小点，则。[定理1.42]（二阶必要性条件）设f在开集D上二阶连续可微，若是无约束最优化问题（*）的局部极小点，则，并且为半正定矩阵。[定理1.43]（二阶充分条件）设f在开集D上二阶连续可微，若，为正定矩阵，则是最优化问题的严格局部极小点。Dx*0)(*xfDx*0)(*xf)(2xf0)(*xf)(2xfDx*3-最优化方法概述最优化方法通常采用迭代方法求解其最优解，其基本思想是：给定一个初始点按照某个迭代规则产生一个迭代点列，使得：当是有穷点列时，它的最后一个点是最优化问题的最优解；当是无穷点列时，它具有极限点，并且极限点就是最优化问题的最优解。nRx0kxkxkx3-最优化方法概述最优化方法（信赖域方法除外）的基本迭代格式：（1）给定初始点，；（2）按照某个规则构造一个搜索方向；（3）确定搜索步长（有的算法采用固定步长）（4）取下一个迭代点；（5）判别是否满足某种终止准则。若满足，则停止迭代，取为所求优化问题的近似局部最优解；否则，令，返回第（2）步。nRx0k0kdkkkkkdxx11kx1kxkk14-无约束最优化方法策略表现形式方法线性近似梯度法二次近似Newton法用布鲁丹（Broyden）族或黄（Huang）族拟Newton法修正公式)(kkkxfHdIHk)(2kkxfH4-无约束最优化方法共轭梯度法的迭代公式为：kkkkkkkkdxfddxxxfd)()(111004-无约束优化方法FR，1964：PRP，1969：CW，1972：Dixon，1972：)()()()(11kTkkTkkxfxfxfxf)()()]()([)(11kTkkkTkkxfxfxfxfxf)]()([)]()([)(111kkTkkkTkkxfxfdxfxfxf)()()(11kTkkTkkxfdxfxf4-无约束优化方法信赖域方法的基本思想：首先选取一个信赖域半径，并由此定义的一个邻域使得n维二次模型是目标函数的一个合适的模拟。然后求解具有信赖域约束的子问题（*）khkknkhxxRx|sGssxfxfsqkTTkkk21)()()()(sxfkkkTTkkkhstssGssxfxfxq..21)()()(min4-无约束优化方法实际下降量：预测下降量：衡量二次模型近似目标函数的指标：)()(kkkksxfxffkkTkkTkkkkksGssxfsqxfq21)()()(kkkqfr5-约束优化问题约束最优化问题的数学模型为：IixgEjxhtsxfijRDxn,0)(,0)(..)(min5-约束优化问题若在约束优化问题（**）的局部最优解处，有某个指标，使得，那么在的某个邻域内将这个约束条件去掉，并且仍是问题的局部最优解。基于这个性质，我们称第个约束在是非有效的、不起作用的、非积极的。相反，若有，则该约束不能去掉，故称相应的约束是处的有效约束、积极约束、起作用约束。我们用表示在处有效约束的指标集，。*xIi000ig*x*x0i0i*xIixgi,0)(Iixgi,0)(*x*I*x0)(,|**xgIiiIi5-约束优化问题[定理1.49]（库恩-塔克一阶必要条件），设（1）是约束优化问题的一个局部最优解；（2）和在的某个邻域内一阶连续可微；（3），则必定存在向量，使得：（a）（b）（c）*x)(xf)(xci*x),(),(**DxLFDDxSFD**2*1*,,,m0)()(1***miiixcxfIii,0*Iixcii,0)(**5-约束优化问题最优性条件说明：（1）库恩-塔克定理中的条件（3）：称为约束规范条件。（2）结论（a）、（b）、（c）称为库恩-塔克条件（K-T条件），满足库恩-塔克条件的点称为库恩-塔克点（K-T点）。（3）条件（c）称为互补松弛条件。（4）与（a）相对应，我们定义元函数，称为约束优化问题的拉格朗日（Lagrange）函数，将称为Lagrange算子（向量）。),(),(**DxLFDDxSFDIixcii,0)(**nmIEiiixcxfxL)()(),(**5-约束优化问题[定理1.51]若在局部最优解处，下面两个条件之一成立：（1）都是线性函数；（2）线性无关。则。[定理1.52]设是约束优化问题的一个局部最优解，如果都是线性函数或者线性无关，则必有Lagrange乘子使得库恩-塔克条件（a），（b），（c）成立。*x))((*IEixci))((*IEixci),(),(**DxLFDDxSFD*x)()(*IEixci)()(*IEixci5-约束优化问题[例]求非线性规划的K-T点。01)(09)(..)(min21222211221xxxgxxxgtsxxxf5-约束优化问题惩罚函数法：根据约束的特点（等式或不等式）构造某种“惩罚”项，然后把它添加到目标函数中，使得约束问题的求解，转化为一系列无约束问题的求解。通过对无约束问题求解过程中违反约束的那些迭代点进行“惩罚”，迫使迭代点列或者不断地向可行域靠近，或者一直保持在可行域内活动，直到收敛到原约束问题的极小点。5-约束优化问题1、外点法：它对违反约束的点在目标函数中加入相应的“惩罚”，而对可行点不予惩罚。用此法得到的最优解往往是不满足约束条件的，一般在可行域外部。对于一般的约束优化问题：定义惩罚函数：其中是很大的正数，称为惩罚因子。ljjmiixhxgxfxF1212)]([)}](,0[max{)(),(5-约束优化问题[例]求解非线性规划1)(..)1()(min22221xxgtsxxxf5-约束优化问题2、内点法：它对企图从内部穿越可行域边界的点在目标函数中加入相应的“障碍”，距离边界越近，障碍越大，从而保障迭代一直在可行域内部移动。这种方法只适用于具有不等式约束的问题：mixgtsxfi,2,1,0)(..)(min5-约束优化问题定义障碍函数其中，r是很小的正数。)()(),(xrBxfrxGmiixgxB1)(1)(miixgxB1)(log)(5-约束优化问题[例]用内点法求解001..)1(121min21231xxtsxx