最优化方法最优化问题与凸分析基础.pptx

第一章 最优化问题与凸分析基础n n在日常生活中，无论做什么事情，总是有多种方案可供选择，并且可能出现多种不同的结果。我们在做这些事情的时候，总是自觉不自觉的选择一种最优方案，以期达到最优结果。这种追求最优方案以达到最优结果的学科就是最优化。寻求最优方案的方法就是最优化方法。这种方法的理论基础就是最优化理论，而凸分析又是最优化理论的基础之一。1.最优化问题n n最优化问题：求一个一元函数或多元函数的极值。在微积分中，我们曾经接触过一些比较简单的极值问题。下面通过具体例子来看看什么是最优化问题。1.1 最优化问题的例子例1 对边长为a的正方形铁板，在四个角处剪去相等的正方形以制成方形无盖水槽，问如何剪法使水槽的容积最大？解：设剪去的正方形边长为解：设剪去的正方形边长为x x，由题意易知，此问，由题意易知，此问题的数学模型为，题的数学模型为，例例2.（混合饲料配合）设每天需要混合饲料的批量为（混合饲料配合）设每天需要混合饲料的批量为100磅，这份饲料必须含：至少磅，这份饲料必须含：至少0.8%而不超过而不超过1.2%的钙的钙;至少至少22%的蛋白质的蛋白质;至多至多5%的粗纤维。的粗纤维。假定主要配料包括石灰石、谷物、大豆粉。这些配料假定主要配料包括石灰石、谷物、大豆粉。这些配料的主要营养成分如下表所示。试以最低成本确定满足的主要营养成分如下表所示。试以最低成本确定满足动物所需营养的最优混合饲料。动物所需营养的最优混合饲料。配料每磅配料中的营养含量钙蛋白质纤维每磅成本（元）石灰石谷物大豆粉0.380 0.00 0.000.001 0.09 0.020.002 0.50 0.08 0.0164 0.0463 0.1250解解:根据前面介绍的建模要素得出此问题的数学模型如下根据前面介绍的建模要素得出此问题的数学模型如下:设设 是生产是生产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梯度：多元函数梯度：多元函数 关于关于 的的一阶导数一阶导数2.3 Hesse矩阵nHesse 矩阵：多元函数矩阵：多元函数 关于关于 的二阶偏导的二阶偏导数矩阵数矩阵例：求目标函数的梯度和Hesse矩阵。解：因为 则 又因为：故Hesse阵为：下面几个公式是今后常用到的：（1），则 （2），则 (单位阵）（3），Q对称，则（4）若 ，其中f：则：3、多元函数的Taylor展开 多元函数Taylor展开式在最优化理论中十分重要。许多方法及其收敛性的证明都是从它出发的。定理：设定理：设 具有二阶连续偏导数。则：具有二阶连续偏导数。则：其中 而01 Taylor展开式还可写成如下形式：展开式还可写成如下形式：4、凸集、凸函数和凸规划凸集、凸函数和凸规划4.1 凸集定义：设集合定义：设集合 S Rn，若若 x(1),x(2)S,0,1，必有，必有 x(1)(1-)x(2)S，则，则称称 S 为凸集。为凸集。规定：单点集规定：单点集 x 为凸集，空集为凸集，空集为凸集。为凸集。注注:x(1)(1-)x(2)=x(2)(x(1)-x(2)是连接是连接 x(1)与与x(2)的线段的线段。凸集凸集非凸集非凸集非凸集非凸集例例:证明集合证明集合 是凸集。其中，是凸集。其中，A为为 m n矩阵，矩阵，b为为m维向量。维向量。证明：任取证明：任取 ，则，则所以，所以，例：给定线性规划 ，其中 ，若令 ，则 是凸集。定义：设定义：设 x(1),x(2),x(m)R Rn n,j j 0 j=1,那么称那么称 j x(j)为为x(1),x(2),x(m)的的凸组合。凸组合。性质：性质：1)1)凸集的交集是凸集；凸集的交集是凸集；（并集一般不是）（并集一般不是）（并集一般不是）（并集一般不是）2)2)凸集的内点集是凸集；凸集的内点集是凸集；3)3)凸集的闭包是凸集。凸集的闭包是凸集。4.2 凸函数定义定义定义定义:设集合设集合设集合设集合 S S R Rn n 为凸集，函数为凸集，函数为凸集，函数为凸集，函数 f f:S SR R，若若若若 x x(1)(1),x x(2)(2)S S,(0,1)(0,1)，均有，均有，均有，均有 f(f(x x(1)(1)(1-(1-)x x(2)(2)f(f(x x(1)(1)+(1-)+(1-)f(xf(x(2)(2)，则称则称则称则称 f(x)f(x)为凸集为凸集为凸集为凸集 S S 上的凸函数。上的凸函数。上的凸函数上的凸函数。若进一步有上面不等式以严格不等式成立，则称若进一步有上面不等式以严格不等式成立，则称若进一步有上面不等式以严格不等式成立，则称若进一步有上面不等式以严格不等式成立，则称 f(x)f(x)为凸集为凸集为凸集为凸集 S S 上的严格凸函数。上的严格凸函数。上的严格凸函数。上的严格凸函数。当当当当-f(x)f(x)为凸函数（严格凸函数）时，则称为凸函数（严格凸函数）时，则称为凸函数（严格凸函数）时，则称为凸函数（严格凸函数）时，则称 f(x)f(x)为为为为凹函数（严格凹函数）。凹函数（严格凹函数）。凹函数（严格凹函数）。凹函数（严格凹函数）。严格凸函数严格凸函数凸函数凸函数严格凹函数严格凹函数定理：定理：f(x)为凸集为凸集 S 上的凸函数上的凸函数 S 上任上任意有限点的凸组合的函数值不大于各点函数意有限点的凸组合的函数值不大于各点函数值的凸组合。值的凸组合。定理：可微函数定理：可微函数 f(x)为非空凸集为非空凸集 S 上的凸上的凸函函数数 对任意对任意 ，有，有定理：具有二阶连续偏导数的函数定理：具有二阶连续偏导数的函数 f(x)为非为非空凸集空凸集 S 上的凸函数上的凸函数 是半正定矩是半正定矩阵。阵。注：注：（1）当）当 是正定矩阵时，是正定矩阵时，f(x)是严是严格凸函数；格凸函数；（2）当）当 是半正定矩阵时，是半正定矩阵时，-f(x)是凹函数是凹函数例：判断下列函数的凹凸性。例：判断下列函数的凹凸性。（1 1）（2 2）解解：（：（1 1）为正定矩阵，为正定矩阵，为严格凸函为严格凸函数。数。（2 2）因为）因为 ，则易知，则易知所以所以 为凹函数。为凹函数。4.3 凸规划定义：对于规划定义：对于规划若若 与与 都是凸函数，则称其为凸规划。都是凸函数，则称其为凸规划。例：线性规划例：线性规划 是凸规划。是凸规划。例：数学规划 易知，与 都是凸函数，所以该规划是凸规划。对于一般的规划（P），其局部最优解不一定是全局最优解，其可行集也未必是凸集。但若（P）是凸规划，则有下面的结论。定理：设规划（P）是凸规划，则（1）（P）的可行集R为凸集；（2）（P）的最优解集合R*是凸集；（3）（P）的任何局部最优解都是全局最优解。练习：1、求 的梯度和Hesse矩阵。2、判断函数 的凹凸性。3、判断下述非线性规划是否为凸规划？