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

第一章 最优化问题与凸分析基础n n在日常生活中，无论做什么事情，总是有多种方案可供选择，并且可能出现多种不同的结果。我们在做这些事情的时候，总是自觉不自觉的选择一种最优方案，以期达到最优结果。这种追求最优方案以达到最优结果的学科就是最优化。寻求最优方案的方法就是最优化方法。这种方法的理论基础就是最优化理论，而凸分析又是最优化理论的基础之一。1.最优化问题n n最优化问题：求一个一元函数或多元函数的极值。在微积分中，我们曾经接触过一些比较简单的极值问题。下面通过具体例子来看看什么是最优化问题。1.1 最优化问题的例子例1 对边长为a的正方形铁板，在四个角处剪去相等的正方形以制成方形无盖水槽，问如何剪法使水槽的容积最大？解：设剪去的正方形边长为解：设剪去的正方形边长为x x，由题意易知，此问，由题意易知，此问题的数学模型为，题的数学模型为，配料每磅配料中的营养含量钙蛋白质纤维每磅成本（元）石灰石谷物大豆粉0.380 0.00 0.000.001 0.09 0.020.002 0.50 0.08 0.0164 0.0463 0.1250例例2.（混合饲料配合）设每天需要混合饲料的批量为（混合饲料配合）设每天需要混合饲料的批量为100磅，这份饲料必须含：至少磅，这份饲料必须含：至少0.8%而不超过而不超过1.2%的钙的钙;至少至少22%的蛋白质的蛋白质;至多至多5%的粗纤维。假定主的粗纤维。假定主要配料包括石灰石、谷物、大豆粉。这些配料的主要要配料包括石灰石、谷物、大豆粉。这些配料的主要营养成分如下表所示。试以最低成本确定满足动物所营养成分如下表所示。试以最低成本确定满足动物所需营养的最优混合饲料。需营养的最优混合饲料。解解:根据前面介绍的建模要素得出此问题的数学模型如下根据前面介绍的建模要素得出此问题的数学模型如下:设设 是生产是生产100磅混合饲料所须的石灰石、谷物、磅混合饲料所须的石灰石、谷物、大豆粉的量（磅）。大豆粉的量（磅）。1.2最优化问题的数学模型n n一般形式一般形式n n向量形式向量形式其中其中 目标函数目标函数不等式约束不等式约束等式约束等式约束 称满足所有约束条件的向量称满足所有约束条件的向量 为为可行解，或可行点可行解，或可行点，全体，全体可行点的集合称为可行点的集合称为可行集，记为可行集，记为 。若若 是连续函数，则是连续函数，则 是闭集。是闭集。在可行集中找一点在可行集中找一点 ，使目标函数，使目标函数 在该点取最小值，即在该点取最小值，即满足：满足：的过程即为的过程即为最优化的求解过程。最优化的求解过程。称为问题的称为问题的最优点或最优点或最优解最优解，称为称为最优值最优值。定义定义1：整体（全局）最优解：整体（全局）最优解：若若 ，对于一切，对于一切 ，恒有恒有 则称则称 是最优化问题的整体最优解。是最优化问题的整体最优解。定义定义2：局部最优解：局部最优解：若若 ，存在某邻域，存在某邻域 ，使得对于，使得对于一切一切 ，恒有，恒有 则称则称 是最优化问题是最优化问题的局部最优解。其中的局部最优解。其中 严格最优解：严格最优解：当当 ，有，有 则称则称 为问题的为问题的严格最优解。严格最优解。f(X)f(X)局部最优解局部最优解局部最优解局部最优解整体最优解整体最优解整体最优解整体最优解1.3 最优化问题的分类n n与时间的关系：静态问题，动态问题n n是否有约束条件：有约束问题，无约束问题n n函数类型：线性规划，非线性规划2、梯度与Hesse矩阵2.1 等值线二维问题的目标函数二维问题的目标函数 表示三维空间中表示三维空间中的的曲面。在空间直角坐标系中，平面与曲面的交线在曲面。在空间直角坐标系中，平面与曲面的交线在平面上的投影曲线为平面上的投影曲线为取不同的值得到不同的投影曲线。每一条投影曲线取不同的值得到不同的投影曲线。每一条投影曲线对应一个值，所以我们称此投影曲线为目标函数的对应一个值，所以我们称此投影曲线为目标函数的等值线等值线或或等高线等高线。当常数取不同的值当常数取不同的值时，重复上面的讨论，时，重复上面的讨论，在平面上得到一族曲线在平面上得到一族曲线等值线等值线.等值线的形状完全由等值线的形状完全由曲面的形状所决定；反曲面的形状所决定；反之，由等高线的形状也之，由等高线的形状也可以推测出曲面的形状可以推测出曲面的形状例例 在坐标平面在坐标平面 上画出目标函数上画出目标函数的等值线的等值线 解解:因为当目标函数取常数时，曲线表示是以原点为因为当目标函数取常数时，曲线表示是以原点为圆心，半径为的圆因此等值线是一族以原点为圆圆心，半径为的圆因此等值线是一族以原点为圆心的同心圆（如图所示）心的同心圆（如图所示）2.2 n元函数的可微性与梯度n梯度：多元函数梯度：多元函数 关于关于 的的一阶导数一阶导数nHesse 矩阵：多元函数矩阵：多元函数 关于关于 的二阶偏的二阶偏导数矩阵导数矩阵例：求目标函数的梯度和Hesse矩阵。解：因为 则 又因为：故Hesse阵为：下面几个公式是今后常用到的：（1），则 （2），则 (单位阵）（3），Q对称，则（4）若 ，其中f：则：3、多元函数的Taylor展开 多元函数Taylor展开式在最优化理论中十分重要。许多方法及其收敛性的证明都是从它出发的。定理：设定理：设 具有二阶连续偏导数。则：具有二阶连续偏导数。则：其中 而01多元函数Taylor展开其他形式：凸集和凸函数在非线性规划的理论中具有重要作用，下面凸集和凸函数在非线性规划的理论中具有重要作用，下面给出凸集和凸函数的一些基本知识。给出凸集和凸函数的一些基本知识。定义定义1 设设 ，若对，若对D中任意两点中任意两点 与与 ，连接，连接 与与 的线段仍属于的线段仍属于D；换言之，对；换言之，对 ，D，0,1恒有恒有 +(1-)D则称则称D为为凸集凸集。+(1-)称为称为 和和 的的凸组合凸组合。nRD )1(x)2(x)1(x)2(x)1(x)2(xa a)1(xa a)2(xa a)1(xa aa a)2(x)1(x)2(x5、凸集、凸函数和凸凸集、凸函数和凸规划划例例 规定：欧式空间规定：欧式空间 是凸集，空集是凸集，空集 是凸集，是凸集，单点集点集 x 为凸集凸集例例:证明集合明集合是凸集。其中，是凸集。其中，A为 m n矩矩阵，b为m维向量。向量。证明：任取明：任取 ，则所以，所以，例：给定线性规划 ，其中 ，若令 ，则 是凸集。凸集的性质凸集的性质有限个凸集的交集仍然是凸集。有限个凸集的交集仍然是凸集。设设 是凸集，则是凸集，则 是凸集。是凸集。设设 是凸集，则是凸集，则 是凸集。是凸集。凸集的和集仍然是凸集。凸集的和集仍然是凸集。设设 是凸集，则是凸集，则 是凸集。是凸集。推论：设推论：设 是凸集，是凸集，则，则 也是凸集，也是凸集，其中其中 。定定义3 极极点点（顶点点）：设设设设D D是是是是凸凸凸凸集集集集,若若若若D D中中中中的的的的点点点点x x 不不不不能能能能成成成成为为为为D D中中中中任任任任何线段上的内点，则称何线段上的内点，则称何线段上的内点，则称何线段上的内点，则称x x为凸集为凸集为凸集为凸集D D的极点。的极点。的极点。的极点。设D为凸集，凸集，X D,若若X不能用不能用X(1)D,X(2)D两点的两点的一个凸一个凸组合表示合表示为X=X(1)+(1-)X(2),其中其中01，则称称X为D的一个极点。的一个极点。定定义2.凸凸组合合：设X(1)，X(2)，X(k)是是n维欧欧式式空空间中中的的k个个点点，若存在若存在1,2,k满足足0i1,(i=1,2,k),使使X=1X(1)+2 X(2)+k X(k)，则称称X为X(1)，X(2)，X(k)的凸的凸组合。合。多边形的多边形的多边形的多边形的顶点顶点顶点顶点是是是是凸集的凸集的凸集的凸集的极点（顶点）极点（顶点）极点（顶点）极点（顶点）。圆周上的点都是圆周上的点都是圆周上的点都是圆周上的点都是凸集的凸集的凸集的凸集的极点（顶点）极点（顶点）极点（顶点）极点（顶点）。定义定义4 设设D为为R 中非空凸集，若对中非空凸集，若对 ，D ，(0,1)恒有恒有n)1(x)2(xa a f +(1-)+(1-)f (*)1(xa)2(xa)()1(xfaa)()2(x则称则称 为为D上的凸函数；进一步，若上的凸函数；进一步，若 时，时，(*)式式仅仅成立。成立。)(xf xf(x)证明：必要性证明：必要性即即由由Taylor公式公式令令 得得设设 则则充分性充分性令令即即所以所以同理同理定理定理3（二阶条件）：（二阶条件）：设设D是是R 中非空开凸集中非空开凸集,是定义在是定义在D上的二次可微上的二次可微函数函数,则则 是是凸函数凸函数的充要条件为对的充要条件为对 x D,0,即即Hesse矩阵矩阵 半正定半正定。n)(xf)(xf)(2xf)(2xf 若若 x D,0，即，即Hesse矩阵矩阵正定正定，则，则 为为严格严格凸函数凸函数。)(2xf)(xf证明：必要性证明：必要性所以所以由由Taylor公式公式令令 得得因为因为 为开集。为开集。由一阶条件由一阶条件所以所以由由p的任意性，的任意性，半正定。半正定。充分性充分性其中其中因为因为 半正定半正定故故 为凸函数。为凸函数。所以所以严格凸函数？严格凸函数？充分性充分性其中其中因为因为 正定，正定，故故 为严格凸函数。为严格凸函数。所以所以例：判断下列函数的凹凸性。例：判断下列函数的凹凸性。（1 1）（2 2）解解：若规划若规划 =ljhmigtsfji,2,1,0)(,2,1,0)(.)(minxxx中中,和和-为凸函数为凸函数,是线性函数是线性函数,则上述问题为则上述问题为凸规划。凸规划。)(xf)(xig)(xih定义定义6:凸规划凸规划 设设D 为凸集为凸集,是定义在是定义在D上的凸函数，则称规上的凸函数，则称规划问题划问题 为凸规划。为凸规划。例：线性规划例：线性规划 是凸规划。是凸规划。例：数学规划 易知，与 都是凸函数，所以该规划是凸规划。对于一般的规划（对于一般的规划（对于一般的规划（对于一般的规划（P P），其局部最优解不一定是全局最优），其局部最优解不一定是全局最优），其局部最优解不一定是全局最优），其局部最优解不一定是全局最优解，其可行集也未必是凸集。但若（解，其可行集也未必是凸集。但若（解，其可行集也未必是凸集。但若（解，其可行集也未必是凸集。但若（P P）是凸规划，则有下面）是凸规划，则有下面）是凸规划，则有下面）是凸规划，则有下面的结论。的结论。的结论。的结论。定理定理定理定理4 4：设规划（设规划（设规划（设规划（P P）是凸规划，则）是凸规划，则）是凸规划，则）是凸规划，则 （1 1）（P P）的可行集）的可行集）的可行集）的可行集R R为凸集；为凸集；为凸集；为凸集；（2 2）（P P）的最优解集合）的最优解集合）的最优解集合）的最优解集合R*R*是凸集；是凸集；是凸集；是凸集；（3 3）（P P）的任何局部最优解都是全局最优解）的任何局部最优解都是全局最优解）的任何局部最优解都是全局最优解）的任何局部最优解都是全局最优解。定理定理5：（1)凸规划的任意局部极小点就是整体极小点，凸规划的任意局部极小点就是整体极小点，且极小点集合是凸集。且极小点集合是凸集。(2)如果凸规划的目标函数是严格凸函数，又存在如果凸规划的目标函数是严格凸函数，又存在极小点，则它的极小点还是唯一的。极小点，则它的极小点还是唯一的。练习：1、求 的梯度和Hesse矩阵。2、判断函数 的凹凸性。3、判断下述非线性规划是否为凸规划？