最优化第一部分课件

非线性优化与动态规划第一部分绪论最优化方法的定义、研究对象及研究方法2.最优化问题的基本概念3.梯度与Hesse矩阵4.凸函数与凸规划非线性优化与动态规划第一部分绪论内容简介：最优化方法

近几十年形成的.它主要运用数学方法研究各种系统的优化途径及方案，为决策者提供科学决策的依据。最优化方法的主要研究对象是各种有组织系统的管理问题及其生产经营活动。最优化方法的目的在于针对所研究的系统，求得一个合理运用人力、物力和财力的最佳方案，发挥和提高系统的效能及效益，最终达到系统的最优目标。实践表明，随着科学技术的日益进步和生产经营的日益发展，最优化方法已成为现代管理科学的重要理论基础和不可缺少的方法，被人们广泛地应用到公共管理、经济管理、国防等各个领域，发挥着越来越重要的作用。本门课程将介绍非线性最优化方法的研究对象、特点。主要是无约束优化计算、约束优化计算以及动态规划的模型、求解。非线性优化与动态规划第一部分绪论一、最优化方法的定义、研究对象及研究方法英国运筹学会给最优化方法下的定义是，最优化方法是一系列科学方法的应用。在工业、商业、政府及国防部门中，用这些方法处理大量的人员、机器、材料和资金等复杂问题。这种方法的特点是科学地建立系统模型，包括度量各种因素，例如分析机会和风险，以此预测和比较各种决策、策略或控制的结果，使管理机构科学地确定它的政策及行动。美国运筹学会下了一个比较简短的、与上述相类似的定义：最优化方法的研究内容是，在需要对有限的资源进行分配的情况下，作出人机系统最优设计的操作的科学决策。

非线性优化与动态规划第一部分绪论以上几种定义中虽然每个定义所强调的侧重点略有不同，但总的含义是一致的。一般说来，最优化方法的研究对象是各种有组织的系统（主要是经济组织系统）的经营管理问题，最优化方法所研究的系统是在一定时空条件下存在，为人所能控制和操纵，有两个以上行动方案可供选择而需要人们作决策的系统。最优化方法研究的问题是能用数量表示与系统各项活动有关而带有运用、策划、使用、安排、控制和规划等方面的问题。最优化方法的任务就是在现有条件下，根据问题的要求，对有关活动中的错综复杂的数量进行分析研究，并归纳为一定的模型，然后运用有关原理和方法求得解决问题的最优途径和方案，以求实现预期目标。非线性优化与动态规划第一部分绪论最优化问题的数学模型

数学模型是对实际问题的数学描述和概括,是进行最优化设计的基础.根据设计问题的具体要求和条件建立完备的数学模型是最优化设计成败的关键.这是因为最优化问题的计算求解完全是针对数学模型进行的.也就是说，最优化计算所得最优解实际上只是数学模型的解，至于是否是实际问题的解，则完全取决于数学模型与实际问题符合的程度.工程设计问题通常是相当复杂的，欲建立便于求解的数学模型，必须对实际问题加以适当的抽象和简化.不同的简化方法得到不同的数学模型和计算结果，而且一个完善的数学模型，往往需要在计算求解过程中进行反复地修改和补充才能最后得到.

非线性优化与动态规划第一部分绪论通过几个简单的最优化设计简例，说明数学模型的一般形式、结构及其有关的基本概念.

例1.用一块边长3m的正方形薄板，在四角各裁去一个大小相同的方块，做成一个无盖的箱子，试确定如何裁剪可以使做成的箱子具有最大的容积.

解:设裁去的4个小方块的边长为x，则做成的箱子的容积为:

于是，上述问题可描述为:求变量

x,使函数极大化.这样就把该设计问题转化成为一个求函数f(x)最大值的数学问题.其中,x是待定的求解参数,称为决策变量;函数f(x)代表设计目标,称为目标函数.由于目标函数是设计变量的三次函数,并且不存在任何限制条件,故称此类问题为非线性无约束最优化问题.非线性优化与动态规划第一部分绪论例2.某工厂生产甲、乙两种产品，生产每种产品所需的材料、工时、用电量和可以获得的利润，以及每天能够提供的材料、工时、用电量见表1—1，试确定该厂两种产品每天的生产计划，以使得每天获得的利润最大.表1-1生产条件基本数据产品材料/kg工时/h用电能量/kw—

h利润/元甲乙供应量943603103004520060120解:这是一个简单的生产计划问题,可归结为在满足各项生产条件的基础上,合理安排两种产品每天的生产量,以使利润最大化的最优化设计问题.非线性优化与动态规划第一部分绪论设每天生产甲产品x1件,乙产品x2件,每天获得的利润用函数f(x1,x2)表示,即:每天实际消耗的材料、工时和电力分别用函数表示，即于是，该问题可归结为以下数学模型：求变量x1,x2,使函数极大化并满足条件:称此类问题为线性约束最优化问题.非线性优化与动态规划第一部分绪论二、最优化问题的基本概念

1.最优化问题的向量表示研究最优化问题，一般都采用向量表示，例如决策变量可以看作是n维向量空间Rn中的一个向量x的n个分量，即或例如，例1、例2中的目标函数都可以写成设x是n维向量变量，则如下函数称为向量值函数,如果它的定义域为D,则简记为MTAP-D-18-02390

非线性优化与动态规划第一部分绪论2.向量的范数约定：取向量为列向量，即n维Euclid空间Rn中的一个向量

x可表示为：或矩阵相等：设如果对一切都有则称向量x与y相等，记作类似可定义两向量小于等于或小于关系。非线性优化与动态规划第一部分绪论矩阵的正定性质及对称矩阵的判定：设A为n阶对称矩阵，x为任意非零n维向量(1)若xTAx>0,则称A为正定矩阵，记作A>0;(2)若xTAx0,则称A为半正定矩阵，记作A0;(3)若xTAx<0,则称A为负定矩阵，记作A<0;(4)若xTAx0,则称A为半负定矩阵，记作A0.除此之外，称A为不定矩阵.非线性优化与动态规划第一部分绪论判定方法：设A为

n阶对称矩阵A>0A的特征值都大于0A的各阶顺序主子式都大于0A0A的特征值都大于等于0A的各阶顺序主子式都大于等于0A<0A的特征值都小于0A的奇阶顺序主子式都小于0,A的偶阶顺序主子式都大于0A0A的特征值都小于等于0A的奇阶顺序主子式都小于等于0,A的偶阶顺序主子式都大于等于0A为不定矩阵A既有正的特征值,又有负的特征值非线性优化与动态规划第一部分绪论两向量内积：设称为向量x和y的内积.向量x的Euclid范数(向量x的长度)称为向量x的Euclid范数(向量x的长度).关于Euclid范数及内积的两个重要不等式(1)三角不等式(2)Cauchy不等式非线性优化与动态规划第一部分绪论3.最优化问题的一般形式非线性优化与动态规划第一部分绪论概括地说，后面大部分章节要讨论的问题是如下的最优化问题:其中是subjectto的缩写，表示“满足于”.其中f,si

,hj

都是x的实值连续函数，通常假定它们都具有二阶连续偏导数.上面的模型也可以用向量来表示.常用术语:

f(x)称为目标函数,或求它的极小,或求它的极大;被称为不等式约束，称为等式约束.称为集约束.在（1.1）中,集约束一般为（1.1）非线性优化与动态规划第一部分绪论不然的话,可以用不等式约束出来,因此，后面一般不考虑集约束.满足所有约束的向量x称为可行解或容许解,可行解的集合称为可行域（容许域）.全局极小点与局部极小点：若存在则称x*为f(x)在D上的全局极小点.这里的“”改为“”，则称x*为f(x)在D上的全局严格极小点.x*组成的集合称为最优解集.若存在并对有则称x*为问题（1.1）

f(x)的局部极小点（最优解）.非线性优化与动态规划第一部分绪论从以上定义可以看出，x*是局部极小点，是指在以x*为中心的一个小邻域中f(x)在点x*处取得极小值；而x*是全局极小点，是指在定义域中，f(x)在点x*处取得极小值.全局最小点必定是局部极小点.实际问题通常是求全局极小点，但直到目前为止，最优化中绝大多数方法都是求局部极小点的.解决这类问题的方法是，先求出所有的局部极小点，然后再求全局极小点.在模型(1.1)中,设向量均在D的内部，则称h为x的一个可行方向.结论:设在(1.1)中,对于x*的任意可行方向h,均有则x*为(1.1)的严格局部最优解.非线性优化与动态规划第一部分绪论4.最优化问题分类最优化问题可做如下分类：最优化问题静态问题动态问题无约束非线性规划问题约束问题一维问题n维问题线性规划非线性规划没有约束的问题：称为无约束问题.如决策变量只有一个，称为一维问题.求解一维问题的方法称为一维搜索或线性搜索，在最优化中起着十分重要的作用.非线性优化与动态规划第一部分绪论一维问题n维问题三、多元函数的梯度、Hesse矩阵及Taylor公式可微函数f(x)的梯度，记为▽f(x)，它是以f(x)对xi(i=1,2,…,n）的偏导数为元素的n维向量(本书规定为列向量)，即也可以把梯度称为函数关于向量x的一阶导数.函数在某一点x(1)的梯度可表示为：1.梯度非线性优化与动态规划第一部分绪论

定义1:

设f:Rn→R，xRn，如果存在n维向量p，对任意的非零向量Δx，使得则称f(x)在点x处可微分，记作定理1：设f:Rn→R，xRn，如果f(x)在x点可微，则f(x)在x点的梯度存在，且称为f(x)在x点的微分.非线性优化与动态规划第一部分绪论

定义2:设f:Rn→R，x

Rn，d是给定的n维非零向量，则称该极限为f(x)在点x处沿d的方向导数，记作定理２：设f:Rn→R，x∈Rn，如果f(x)在x点可微，则在x处沿任何非零向量d的方向导数存在，且如果下面的极限存在非线性优化与动态规划第一部分绪论

定义3

设f(x)是Rn上的连续函数，x0Rn，d是给定的n维非零向量，如果存在δ>0，使得则称d为f(x)在x0点的下降方向，若定理3设f:Rn→R，x

Rn，且f(x)在x点可微，如果存在非零向量d

Rn，使得f(x)Td<0，则d是下降方向，若f(x)Td>0，则d是上升方向。则称d为f(x)在x0点的上升方向。非线性优化与动态规划第一部分绪论此定理说明，与f在x0处的梯度方向交成锐角的任何方向都是f在x0处的上升方向；相反，与f在x0处的梯度梯度方向交成钝角的任何方向都是f在x0处的下降方向。可以证明：梯度方向是函数值上升最快的方向，梯度负方向是函数值下降最快的方向。因此我们把负梯度方向叫做最速下降方向.还可以证明：f(x)在x0处的梯度与f(x)过x0处等值面上任一曲线l在该点的切线垂直，即与过该点的切平面垂直。或者可以说f(x0)是曲面f(x)=f(x0)在点x0处的一个法线向量。注：过x0的等值面方程为：f(x)=f(x0)=c.非线性优化与动态规划第一部分绪论2.海赛（Hesse）矩阵假设函数f(x)二阶可微，则以其二阶偏导数为元素构成的下述n×n矩阵称为f(x)的海赛矩阵，记为即当f(x)在x处的所有二阶偏导数连续时，有这时的Hesse矩阵为对称矩阵.非线性优化与动态规划第一部分绪论向量函数的导数定义4设如果对于自变量的各分量的偏导数都存在，则称向量函数h在处是一阶可导的，并且称矩阵为h(x)在处的一阶导数或Jacobi矩阵，简记为非线性优化与动态规划第一部分绪论n元函数的梯度是向量函数由上面定义知，f(x)的一阶导数或Jacobi矩阵为：非线性优化与动态规划第一部分绪论即函数梯度的Jacobi矩阵即为该函数的Hesse矩阵.非线性优化与动态规划第一部分绪论

例1求函数在任意点的梯度和海赛矩阵。

解:先求f(x)的各阶偏导数，有非线性优化与动态规划第一部分绪论例2求二次齐次函数的Hesse矩阵解：非线性优化与动态规划第一部分绪论非线性优化与动态规划第一部分绪论3.Taylor展式设n元实函数f(x)在某点x(0)

的某一邻域内有连续二阶偏导数，则可写出它在x(0

)处的泰勒（Taylor）展开式如下：若在上式中略去高阶无穷小项，则有相应的近似关系式：非线性优化与动态规划第一部分绪论四、凸函数与凸规划

求解非线性规划问题的算法很多，但一般情况下求出的都是局部最优解。而我们的目的是求问题的全局最优解。为了达到这个目的，我们一般可以从两个方面着手考虑，一是寻求求全局极值的计算方法，二是从理论上说明在何种情况下，求出的局部极值一定是问题的全局极值。实际上，研究结果表明，对于凸规划来说，局部最优解一定是全局最优解（对极值问题而言）。本部分首先介绍凸函数的概念和性质，再介绍凸规划的概念与性质。非线性优化与动态规划第一部分绪论凸集的线段都全部包含在该集合内，就称该点集为凸集，否则为非凸集。一个点集（或区域），如果连接其中任意两点非线性优化与动态规划第一部分绪论1.凸函数及其性质定义5若对任意的及D中任意两点和有（1.2）

成立，则称f（X）为D上的凸函数，或称f（X）在D上是凸的.设f(X)为定义在非空凸集上的函数。（1.3）

成立,则称f(X)为D上的严格凸函数，或称f(X)在D上是严格凸的.若对任意的及任意两点有非线性优化与动态规划第一部分绪论注1：

若f是D上的（严格）凸函数，则称-f是D上的(严格)凹函数，或称-f在D上是（严格）凹的。实际上，我们也可以仿照定义2来定义凹函数，只要令式（1.2）和（1.3）不等号反向.当n=1时，如图1.1所示凸（凹）函数的函数曲线上任意两点间的连线总在函数曲线的上(下)图1.1（a）凸函数非线性优化与动态规划第一部分绪论图1.1（b）凹函数注2：由凸（凹）函数的定义，可知线性函数既是凸函数也是凹函数。非线性优化与动态规划第一部分绪论根据凸函数的定义，易证凸函数有如下的基本性质.性质1.1设f（X）是凸集D上的凸函数，为实数，则也是D上的凸函数。性质1.2设和均为凸集D上的凸函数，则也是D上的凸函数.性质1.3也是D上的凸函数.设均为凸集D上的凸函数，且则线性组合非线性优化与动态规划第一部分绪论性质1.4集合设f(X)是凸集D上的凸函数，对任一实数,也是凸集.证明：

任取则且任取因为D为凸集，所以又因为f（X）为D上的凸函数，所以由集合的定义知，证毕.根据凸集的定义知为凸集.我们称集合为f（X）在集合D上关于数的水平集.非线性优化与动态规划第一部分绪论2.凸函数的判定我们可以根据凸函数的定义来判定一个函数是否为凸函数,但如果该函数是可微函数，那么可按下述法则判别.定理4（函数凸性的一阶条件）设D是En的非空开凸集,函数具有一阶连续的偏导数，则函数f为凸函数的充要条件是,恒有（1.4）其中为函数f在处的梯度向量.非线性优化与动态规划第一部分绪论证明：必要性。因为D是的非空开凸集，所以因为函数f为凸函数，所以从而有由于上式不等式两边同除以得非线性优化与动态规划第一部分绪论由于f具有一阶连续的偏导数，故有所以于是得到非线性优化与动态规划第一部分绪论充分性。因为D是的非空开凸集，则由充分性条件式（1.4）得以和分别乘以上述两个不等式的两边，并相加整理得由定义知函数为凸函数.证毕.非线性优化与动态规划第一部分绪论定理5（函数凸性的二阶条件）设D是的非空开凸集，函数的偏导数，则函数f为凸函数的充要条件是函数f的Hesse矩阵H(X)在D上为半正定矩阵.函数f为严格凸函数的充要条件是函数f的Hesse矩矩阵H(X)在D上为正定矩阵.具有二阶连续证明：必要性。因为D是的非空开凸集，所以有f为严格凸函数，因为D是Rn的非空开凸集所以存在当时，由定理4得非线性优化与动态规划第一部分绪论因为函数f具有二阶连续的偏导数，由Taylor展式得所以由上两式得上式两边同除以注意到则有即Hesse矩阵H(X)在D上为半正定矩阵。充分性。由Taylor展式得，非线性优化与动态规划第一部分绪论其中因为D是凸集，所以由充分性的条件知Hesse矩阵H（X）在D上为半正定矩阵，从而为半正定矩阵，即有所以由定理4知函数为的凸函数.第二个结论的证明只要把上述的不等号换成严格的不等号即知成立.证毕.非线性优化与动态规划第一部分绪论例3判断是否为凸函数.解：用二阶条件.从而有因为顺序主子式所以H(X)正定，故f(X)为严格凸函数.非线性优化与动态规划第一部分绪论定理6若f(X)是凸集DRn上的凸函数,则它的任一局证明：设是任一局部极小点，为其充分小的邻域,则有充分小，则有所以部极小点就是它在D上的全局极小点，而且它的极小点全体形成一个凸集.因为f(X)是凸集DRn上的凸函数,所以将上两式相加并除以

,即得所以结论成立.证毕.非线性优化与动态规划第一部分绪论定理7设f（X）在凸集DRn

上可微且为凸函数，若存在点都有（1.5）则是f（X）在D上的全局极小点；若f（X）为可微的严格凸函数，则即是f（X）的唯一全局极小点.证明：由定理4知由条件知所以若f（X）为可微的严格凸函数，则(1.5)成立严格不等号,即是f（X）在D上的全局极小点.由X的任意性知由定理知结论成立.证毕.非线性优化与动态规划第一部分绪论定理7的含义可参考图1.2图1.2非线性优化与动态规划第一部分绪论3.凸规划及其性质考虑非线性规划问题