最优化理论与方法概述.ppt

《最优化理论与方法概述.ppt》由会员分享，可在线阅读，更多相关《最优化理论与方法概述.ppt（45页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、最优化理论与方法概述现在学习的是第1页，共45页 1.最优化问题n最优化问题：求一个一元函数或多元函数的极值。在微积分中，我们曾经接触过一些比较简单的极值问题。下面通过具体例子来看看什么是最优化问题。现在学习的是第2页，共45页1.1 最优化问题的例子例1 对边长为a的正方形铁板，在四个角处剪去相等的正方形以制成方形无盖水槽，问如何剪法使水槽的容积最大？解：设剪去的正方形边长为x，由题意易知，此问题的数学模型为，现在学习的是第3页，共45页配料配料每磅配料中的营养含量每磅配料中的营养含量钙钙蛋白质蛋白质纤维纤维每磅成本（元）每磅成本（元）石灰石石灰石谷物谷物大豆粉大豆粉0.380 0.00 0

2、.000.380 0.00 0.000.001 0.09 0.020.001 0.09 0.020.002 0.50 0.080.002 0.50 0.08 0.01640.0164 0.0463 0.0463 0.1250 0.1250例例2.（混合饲料配合）设每天需要混合饲料的批量为（混合饲料配合）设每天需要混合饲料的批量为（混合饲料配合）设每天需要混合饲料的批量为（混合饲料配合）设每天需要混合饲料的批量为100磅，这份饲料必须含：至少磅，这份饲料必须含：至少磅，这份饲料必须含：至少磅，这份饲料必须含：至少0.8%而不超过而不超过而不超过而不超过1.2%的钙的钙的钙的钙;至至少少22%22

3、%的蛋白质的蛋白质;至多至多至多至多5%5%的粗纤维。假定主要配料包的粗纤维。假定主要配料包括石灰石、谷物、大豆粉。这些配料的主要营养成分括石灰石、谷物、大豆粉。这些配料的主要营养成分如下表所示。试以最低成本确定满足动物所需营养的如下表所示。试以最低成本确定满足动物所需营养的最优混合饲料。最优混合饲料。现在学习的是第4页，共45页解解解解:根据前面介绍的建模要素得出此问题的数学模型如下根据前面介绍的建模要素得出此问题的数学模型如下根据前面介绍的建模要素得出此问题的数学模型如下根据前面介绍的建模要素得出此问题的数学模型如下:设设设设 是生产是生产是生产是生产100100磅混合饲料所须的石灰石、谷

4、物、大豆磅混合饲料所须的石灰石、谷物、大豆磅混合饲料所须的石灰石、谷物、大豆磅混合饲料所须的石灰石、谷物、大豆粉的量（磅）。粉的量（磅）。粉的量（磅）。粉的量（磅）。现在学习的是第5页，共45页1.2最优化问题的数学模型n n一般形式一般形式n n向量形式向量形式其中其中现在学习的是第6页，共45页 目标函数目标函数目标函数目标函数不等式约束不等式约束不等式约束不等式约束等式约束等式约束等式约束等式约束 称满足所有约束条件的向量称满足所有约束条件的向量称满足所有约束条件的向量称满足所有约束条件的向量 为为为为可行解，或可行点可行解，或可行点可行解，或可行点可行解，或可行点，全体，全体，全体，全

5、体可行点的集合称为可行点的集合称为可行点的集合称为可行点的集合称为可行集，记为可行集，记为可行集，记为可行集，记为 。若若若若 是连续函数，则是连续函数，则是连续函数，则是连续函数，则 是闭集。是闭集。是闭集。是闭集。现在学习的是第7页，共45页 在可行集中找一点在可行集中找一点在可行集中找一点在可行集中找一点 ，使目标函数，使目标函数，使目标函数，使目标函数 在该点取最小值，即满足：在该点取最小值，即满足：在该点取最小值，即满足：在该点取最小值，即满足：的过程即为最优化的求解过程。的过程即为最优化的求解过程。的过程即为最优化的求解过程。的过程即为最优化的求解过程。称为问题的称为问题的称为问题

6、的称为问题的最优点或最优点或最优点或最优点或最优解最优解最优解最优解，称为称为称为称为最优值最优值最优值最优值。定义定义定义定义1 1：整体（全局）最优解：整体（全局）最优解：整体（全局）最优解：整体（全局）最优解：若若若若 ，对于一切，对于一切，对于一切，对于一切 ，恒有恒有恒有恒有 则称则称则称则称 是最优化问题的整体最优解。是最优化问题的整体最优解。是最优化问题的整体最优解。是最优化问题的整体最优解。定义定义定义定义2 2：局部最优解：局部最优解：局部最优解：局部最优解：若若若若 ，存在某邻域，存在某邻域，存在某邻域，存在某邻域 ，使得对于，使得对于，使得对于，使得对于一切一切一切一切

7、，恒有，恒有，恒有，恒有 则称则称则称则称 是最优化问题是最优化问题是最优化问题是最优化问题的局部最优解。其中的局部最优解。其中的局部最优解。其中的局部最优解。其中 严格最优解：严格最优解：严格最优解：严格最优解：当当当当 ，有，有，有，有 则称则称则称则称 为问题的为问题的为问题的为问题的严格最优解。严格最优解。严格最优解。严格最优解。现在学习的是第8页，共45页f(X)f(X)局部最优解局部最优解局部最优解局部最优解整体最优解整体最优解整体最优解整体最优解现在学习的是第9页，共45页1.3 最优化问题的分类n与时间的关系：静态问题，动态问题n是否有约束条件：有约束问题，无约束问题n函数类型

8、：线性规划，非线性规划现在学习的是第10页，共45页2、梯度与Hesse矩阵2.1 等值线二维问题的目标函数 表示三维空间中的曲面。在空间直角坐标系中，平面与曲面的交线在平面上的投影曲线为取不同的值得到不同的投影曲线。每一条投影曲线对应一个值，所以我们称此投影曲线为目标函数的等值线或等高线。现在学习的是第11页，共45页 当常数取不同的值时，重复上面的讨论，在平面上得到一族曲线等值线.等值线的形状完全由曲等值线的形状完全由曲面的形状所决定；反之，面的形状所决定；反之，由等高线的形状也可以推由等高线的形状也可以推测出曲面的形状测出曲面的形状现在学习的是第12页，共45页例例 在坐标平面在坐标平面

9、 上画出目标函数上画出目标函数的等值线的等值线 解解:因为当目标函数取常数时，曲线表示是以原点为圆心，半径为的圆因此等值线是一族以原点为圆心的同心圆（如图所示）现在学习的是第13页，共45页2.2 n元函数的可微性与梯度n n梯度：多元函数梯度：多元函数 关于关于 的的一阶导数一阶导数现在学习的是第14页，共45页n nHesse 矩阵：多元函数矩阵：多元函数 关于关于 的二阶偏导的二阶偏导数矩阵数矩阵现在学习的是第15页，共45页例：求目标函数例：求目标函数的梯度和的梯度和HesseHesse矩阵。矩阵。解：因为解：因为 则则 又因为：又因为：故故HesseHesse阵为：阵为：现在学习的是

10、第16页，共45页下面几个公式是今后常用到的：下面几个公式是今后常用到的：（1 1），则，则 （2 2），则，则 (单位阵）单位阵）（3 3），Q Q对称，对称，则则（4 4）若）若 ，其中，其中f f：则：则：现在学习的是第17页，共45页3、多元函数的Taylor展开 多元函数多元函数TaylorTaylor展开式在最优化理论中十分重要。展开式在最优化理论中十分重要。许多方法及其收敛性的证明都是从它出发的。许多方法及其收敛性的证明都是从它出发的。定理：设定理：设定理：设定理：设 具有二阶连续偏导数。则：具有二阶连续偏导数。则：具有二阶连续偏导数。则：具有二阶连续偏导数。则：其中其中 而而0

11、 0 1 1现在学习的是第18页，共45页多元函数TaylorTaylor展开其他形式：现在学习的是第19页，共45页现在学习的是第20页，共45页现在学习的是第21页，共45页现在学习的是第22页，共45页现在学习的是第23页，共45页现在学习的是第24页，共45页 凸集和凸函数在非线性规划的理论中具有重要作用，下面给出凸集凸集和凸函数在非线性规划的理论中具有重要作用，下面给出凸集凸集和凸函数在非线性规划的理论中具有重要作用，下面给出凸集凸集和凸函数在非线性规划的理论中具有重要作用，下面给出凸集和凸函数的一些基本知识。和凸函数的一些基本知识。和凸函数的一些基本知识。和凸函数的一些基本知识。定

12、义定义定义定义1 1 设设设设 ，若对，若对，若对，若对DD中任意两点中任意两点中任意两点中任意两点 与与与与 ，连接，连接，连接，连接 与与与与 的线段仍属于的线段仍属于的线段仍属于的线段仍属于DD；换言之，对；换言之，对；换言之，对；换言之，对 ，DD，0,10,1恒有恒有恒有恒有 +(1-)+(1-)DD则称则称则称则称DD为为为为凸集凸集凸集凸集。+(1-)+(1-)称为称为称为称为 和和和和 的的的的凸组合凸组合凸组合凸组合。n nRD )1 1(x)2 2(x)1 1(x)2 2(x)1 1(x)2 2(xa a a a )1 1(xa a)2 2(xa a)1 1(xa aa a

13、)2 2(x)1 1(x)2 2(x5、凸集、凸函数和凸规划凸集、凸函数和凸规划现在学习的是第25页，共45页例例 规定：欧式空间规定：欧式空间规定：欧式空间规定：欧式空间 是凸集，空集是凸集，空集是凸集，空集是凸集，空集 是凸集，单点集是凸集，单点集是凸集，单点集是凸集，单点集 x x 为凸为凸为凸为凸集集集集现在学习的是第26页，共45页例例:证明集合证明集合是凸集。其中，是凸集。其中，A为为 m n矩阵，矩阵，b为为m维向量。维向量。证明：任取证明：任取 ，则，则所以，所以，现在学习的是第27页，共45页例：给定线性规划 ，其中 ，若令 ，则 是凸集。现在学习的是第28页，共45页凸集的

14、性质凸集的性质凸集的性质凸集的性质n有限个凸集的交集仍然是凸集。有限个凸集的交集仍然是凸集。设设 是凸集，则是凸集，则 是凸集。是凸集。n设设 是凸集，则是凸集，则 是凸集。是凸集。n凸集的和集仍然是凸集。凸集的和集仍然是凸集。设设 是凸集，则是凸集，则 是凸集。是凸集。推论：设推论：设 是凸集，是凸集，则，则 也是凸集，也是凸集，其中其中 。现在学习的是第29页，共45页定定定定义义义义3 3 极极极极点点点点（顶顶顶顶点点点点）：设设设设D D是是是是凸凸凸凸集集集集,若若若若D D中中中中的的的的点点点点x x 不不不不能能能能成成成成为为为为D D中中中中任任任任何何何何线线线线段上的

15、内点，则称段上的内点，则称段上的内点，则称段上的内点，则称x x为凸集为凸集为凸集为凸集D D的极点。的极点。的极点。的极点。设设设设D D为凸集，为凸集，为凸集，为凸集，X X D,D,若若若若X X不能用不能用不能用不能用X X(1)(1)D,XD,X(2)(2)D D两点的两点的两点的两点的一个凸组合表示为一个凸组合表示为一个凸组合表示为一个凸组合表示为X=XX=X(1)(1)+(1-)X+(1-)X(2)(2),其中其中其中其中01 01，则称则称则称则称X X为为为为D D的一个极点。的一个极点。的一个极点。的一个极点。定定定定义义义义2.2.凸凸凸凸组组组组合合合合：设设设设X X

16、(1)(1)，X X(2)(2)，X X(k)(k)是是是是n n维维维维欧欧欧欧式式式式空空空空间间间间中中中中的的的的k k个个个个点点点点，若存在若存在若存在若存在 1,1,2 2,k k满足满足满足满足00i i1,(1,(i=1,2,k),i=1,2,k),使使使使X=X=1 1X X(1)(1)+2 2 X X(2)(2)+k k X X(k)(k)，则称则称则称则称X X为为为为X X(1)(1)，X X(2)(2)，X X(k)(k)的凸组合。的凸组合。的凸组合。的凸组合。现在学习的是第30页，共45页 多边形的多边形的多边形的多边形的顶点顶点顶点顶点是是是是凸集的凸集的凸集的

17、凸集的极点（顶点）极点（顶点）极点（顶点）极点（顶点）。圆周上的点都是圆周上的点都是凸集的凸集的极点（顶点）极点（顶点）。现在学习的是第31页，共45页定义定义4 设设设设DD为为为为R R 中非空凸集，若对中非空凸集，若对中非空凸集，若对中非空凸集，若对 ，D D ，(0,1)(0,1)恒有恒有恒有恒有n n)1 1(x)2 2(xa a f +(1-)+(1-)f (*)1 1(xa)2 2(xa)()1 1(xfaa)()2 2(x x则称则称则称则称 为为为为DD上的凸函数；进一步，若上的凸函数；进一步，若上的凸函数；进一步，若上的凸函数；进一步，若 时，时，时，时，(*)(*)式式式

18、式仅仅仅仅 成立。成立。成立。成立。)(x xf f x xf(x)f(x)现在学习的是第36页，共45页证明：必要性证明：必要性证明：必要性证明：必要性即即即即由由由由TaylorTaylor公式公式公式公式令令令令 得得得得现在学习的是第37页，共45页设设设设 则则则则充分性充分性充分性充分性令令令令即即即即所以所以所以所以同理同理同理同理现在学习的是第38页，共45页定理定理定理定理3 3（二阶条件）：（二阶条件）：（二阶条件）：（二阶条件）：设设设设DD是是是是R R 中非空开凸集中非空开凸集中非空开凸集中非空开凸集,是定义在是定义在是定义在是定义在DD上的二次可微函数上的二次可微函

19、数上的二次可微函数上的二次可微函数,则则则则 是是是是凸函数凸函数凸函数凸函数的充要条件为对的充要条件为对的充要条件为对的充要条件为对 x x DD,0,0,即即即即HesseHesse矩阵矩阵矩阵矩阵 半正定半正定半正定半正定。n n)(x xf f)(x xf f)(2 2x xf f )(2 2x xf f 若若若若 x x DD,0,0，即，即，即，即HesseHesse矩阵矩阵矩阵矩阵正定正定正定正定，则，则，则，则 为为为为严格严格严格严格凸函数凸函数凸函数凸函数。)(2 2x xf f )(x xf f现在学习的是第39页，共45页证明：必要性证明：必要性证明：必要性证明：必要性

20、所以所以所以所以由由由由TaylorTaylor公式公式公式公式令令令令 得得得得因为因为因为因为 为开集。为开集。为开集。为开集。由一阶条件由一阶条件由一阶条件由一阶条件所以所以所以所以由由由由p p的任意性，的任意性，的任意性，的任意性，半正定。半正定。半正定。半正定。现在学习的是第40页，共45页充分性充分性充分性充分性其中其中其中其中因为因为因为因为 半正定半正定半正定半正定故故故故 为凸函数。为凸函数。为凸函数。为凸函数。所以所以所以所以严格凸函数？严格凸函数？现在学习的是第41页，共45页充分性充分性充分性充分性其中其中其中其中因为因为因为因为 正定，正定，正定，正定，故故故故 为

21、严格凸函数。为严格凸函数。为严格凸函数。为严格凸函数。所以所以所以所以现在学习的是第42页，共45页例：判断下列函数的凹凸性。例：判断下列函数的凹凸性。（1 1）（2）解：现在学习的是第43页，共45页若规划若规划若规划若规划 =l lj jh hmmi ig gt t s sf fj ji i,2 2,1 1,0 0)(,2 2,1 1,0 0)(.)(minminx xx xx x中中中中,和和和和-为凸函数为凸函数为凸函数为凸函数,是线性函数是线性函数是线性函数是线性函数,则上述问题为则上述问题为则上述问题为则上述问题为凸规划。凸规划。凸规划。凸规划。)(x xf f)(x xi ig g)(x xi ih h定义定义定义定义6:凸规划凸规划 设设设设D D 为凸集为凸集为凸集为凸集,是定义在是定义在是定义在是定义在DD上的凸函数，则称规划问题上的凸函数，则称规划问题上的凸函数，则称规划问题上的凸函数，则称规划问题 为凸规划。为凸规划。为凸规划。为凸规划。现在学习的是第44页，共45页例：线性规划 是凸规划。现在学习的是第45页，共45页