第1章 最优化基础

最优化原理与方法最优化是一门应用相当广泛的学科，它讨论如何在有限种或无限种可行方案（决策）中选择（或者）最佳的方案（决策），构造寻求最佳解的计算方法，研究这些计算方法的理论性质及实际计算表现。本课程旨在比较全面、系统地介绍最优化理论和方法，详细地论述无约束最优化、约束最优化和线性、非线性、光滑、非光滑最优化的最优性条件、求解方法以及各类求解方法的特点。第一章最优化理论的数学基础第1.1节最优化的数学模型第1.2节多元函数分析第1.3节凸集和凸函数第1.4节最优性条件第1.5节最优化方法概述第1.1节最优化的数学模型最优化（Optimization）问题的数学模型为：优化变量（Variable）：目标函数（ObjectFunction）：可行域（AdmitRegion）：若，则称x为可行点或可行解（AdmitSolution）。nTnRxxxx),,,(211:)(RRxfnnRDDx第1.1节最优化的数学模型最优化问题的分类：（1）按照是否有无约束条件：（1-1）无约束最优化问题：（Non-restrictOptimization）：无约束最优化问题的数学模型：无约束问题是在空间上寻求使得目标函数达到极小或最小的点。nRD)(minxf)(xf*xnR第1.1节最优化的数学模型按照是否有无约束条件：（1-2）约束最优化问题（RestrictOptimization）：约束最优化问题是在约束集合（RestrictCollection）上寻求使得目标函数达到极小或最小的点。IjxcEixctsxfii,0)(,,0)(..)(minniiRxIixcEixcxD,,0)(,,0)(|)(xf*x第1.1节最优化的数学模型（1-2）约束最优化问题（RestrictOptimization）：约束函数：（RestrictFunction）E和I分别称为等式约束的指标集和不等式约束的指标集。等式约束：不等式约束：统称为约束条件（RestrictCondition）。IixcEixctsxfii,0)(,,0)(..)(minIEiRRcni,:Eixci,0)(Iixci,0)(第1.1节最优化的数学模型（1-3）约束最优化问题的分类：按照约束条件的形式分为三类：（1）等式约束优化问题；（2）不等式约束优化问题；（3）混合优化问题；第1.1节最优化的数学模型最优化问题的分类：（2）按照目标函数和约束函数是否非线性分类：（1）线性规划（LinearProgramming）；（2）非线性规划（NonlinearProgramming）；（3）二次规划：目标函数为二次函数的线性规划问题。)(xf第1.1节最优化的数学模型几点说明：（1）极大化问题与极小化问题是可以相互转化的。（2）不等式约束条件也是可以相互转化的。第1.2节多元函数分析第1.2.1节多元函数及其微分第1.2.2节多元函数的泰勒展开式第1.2.3节向量值函数及其性质第1.2.1节多元函数及其微分、极值问题[定义1.1]如果多元连续函数在对于x的各个分量的偏导数都存在，则称函数在x处一阶可导，并称向量为函数在x处的一阶导数或梯度（Gradient）RRfn:nTnRxxxx),,,(21nixxfi,,2,1,)(Tnxxfxxfxxfxf)(,,)(,)()(21)(xf第1.2.1节多元函数及其微分[定义1.2]如果多元连续函数在对于x的各个分量的偏导数都存在且连续，则称函数在x处连续可微（ContinuouslyDerivable）。如果函数在开集中的每一点都连续可微，则称函数在D中连续可微，记作RRfn:nTnRxxxx),,,(21nixxfi,,2,1,)()(xf)(xfnRD)(xf)(1DCf第1.2.1节多元函数及其微分、极值问题一点说明：对于多元函数，即使偏导数在都存在，也不能保证函数在x处连续。[例1.3]二元函数在点处的偏导数都为0，但是这个函数在点处并不连续。)(xfnixxfi,,2,1,)(nTnRxxxx),,,(21)(xf000,),(2221222122212121xxxxxxxxxxfz0,00,0第1.2.1节多元函数及其微分、极值问题[定义1.4]如果多元连续函数在对于x的各个分量的二阶偏导数都存在，则称函数在x处二阶可导，并称矩阵为函数在x处的二阶导数矩阵或海森矩阵（HesseMatrix）。RRfn:nTnRxxxx),,,(21njnixxxfji,,2,1,,,2,1,)(2)(xfnn22221222222122122122122)(,,)(,)()(,,)(,)()(,,)(,)()(nnnnnxxfxxxfxxxfxxxfxxfxxxfxxxfxxxfxxfxf)(xf第1.2.1节多元函数及其微分、极值问题[定义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.2.1节多元函数及其微分、极值问题[例1.6]设是对称矩阵，向量，，求二次函数在任意点处的梯度和海森矩阵。[解]梯度为；海森矩阵为。nnRAnRb1RccxbAxxxfTT21)(bAxxf)(Axf)(2第1.2.2节多元函数的泰勒展开式根据多元复合函数的求导法则，导出一元函数的一阶、二阶导数。记则有：一阶导数为：1),()(RttdxfTnTnnuuutdxtdxtdxtdxu),,,(,,,212211dtdxfdufduufduufduufdtduuufdtduuufdtduuuftTTnnnn)()()()()()()()()(22112211第1.2.2节多元函数的泰勒展开式二阶导数为：dtdxfdddduufuuufuuufuuufuufuuufuuufuuufuufddddduufduuufduuufdduuufduufduuufdduuufduuufduuftTnnnnnnnnnnnnnnnn)()()()()()()()()()(,,,)()()()()()()()()()(221222212222221221221221221222221122222222112211222121212第1.2.2节多元函数的泰勒展开式[定理1.7]（1）设多元函数，若在点的某个邻域内一阶连续可微，则存在，使得，其中。（2）设多元函数，若在点的某个邻域内一阶连续可微，则1:RRfn1:RRfn)(xf*x)(*xU1,0)(),()()()(***xUxxxfxfxfT)(**xxx)(xf*x)(*xU)(),()()()()(*****xUxxxoxxxfxfxfT第1.2.2节多元函数的泰勒展开式[定理1.7]（3）设多元函数，若在点的某个邻域内二阶连续可微，则存在，使得，其中。（4）设多元函数，若在点的某个邻域内二阶连续可微，则1:RRfn1:RRfn)(xf*x)(*xU1,0)(**xxx)(xf*x)(*xU)(),)(()(21)()()()(**2****xUxxxfxxxxxfxfxfTT)(),())(()(21)()()()(*2**2****xUxxxoxxxfxxxxxfxfxfTT第1.2.2节多元函数的泰勒展开式多元函数在的近似：（1）线性近似：（2）二次近似：)(xf*x)()()()(***xxxfxfxfT))(()(21)()()()(*2****xxxfxxxxxfxfxfTT第1.2.2节多元函数的泰勒展开式[定理1.8若多元函数，在点的某个邻域内一阶连续可微，则[定理1.9]若多元函数在点的某个邻域内二阶连续可微，则有（1）积分形式的泰勒公式：（2）对任意的向量和任意实数t，有另一种积分形式的泰勒公式：1:RRfn*x)(*xU)(,)())(()()(*10****xUxdtxxxxtxfxfxfT1:RRfn*x)(*xU100***2****)))((()()()()()(dsdtxxxxtxfxxxxxfxfxfsTTnRdx,1022)()1()()()(dsdstdxfdstdxftxftdxfTT第1.2.3节向量值函数及其性质[定义1.10]如果向量函数的每一个分量在处连续可微，则称函数在x连续可微。F在x的导数称为向量函数在x处的Jacobi矩阵。它的转置称为在x处的梯度。mnTmRRxfxfxfxF:))(,),(),(()(21),,2,1(mifinRx)(xFnmnmmmnnRxxfxxfxxfxxfxxfxxfxxfxxfxxfxF)()()()()()()()()()(212221212111)(xF)(xF第1.2.3节向量值函数及其性质[例1.11]设，求其在点处的雅可比矩阵。[解]由定义可知，，代入，得到：322313121sin3)()()(2xxxxexxfxfxFxTx),0,1(32232213cossin233)(22xxxxxexexFxxTx),0,1(00313)(xF第1.2.3节向量值函数及其性质[定理1.12]（1）设向量函数在开凸集D上连续可微，则有：（1）对于，都有：（2）对于，都有：mnRRF:Dyx,))((sup)()(1,0xytxFxyxFyFtDzyx,,)())((sup))(()()(1,0xFzytzFzyzyxFzFyFt第1.3节凸集和凸函数第1.3.1节凸集第1.3.2节凸函数第1.3.3节凸函数的判别条件第1.3.4节水平集第1.3.5节凸集的分离和支撑第1.3.1节凸集[定义1.13]设集合，如果对任意的与任意的，有则称集合D是凸集（ConvexSet）。[定理1.14]是凸集当且仅当对于任意的都有其中，，并且。nRDDyx,1,0Dyx)1(nRDDxxxn,,,21Dxmiii1mii,,2,1,011mii第1.3.1节凸集凸集的例子：（1）超平面是凸集，其中是非零向量，称为超平面的法向量，为实数。（2）闭半空间和为凸集。开半空间和为凸集。（3）射线为凸集，其中d为给定的非零向量，是