资源预览内容
第1页 / 共31页
第2页 / 共31页
第3页 / 共31页
第4页 / 共31页
第5页 / 共31页
第6页 / 共31页
第7页 / 共31页
第8页 / 共31页
第9页 / 共31页
第10页 / 共31页
亲,该文档总共31页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
第一章 最优化问题与凸分析基础,在日常生活中,无论做什么事情,总是有多种方案可供选择,并且可能出现多种不同的结果。我们在做这些事情的时候,总是自觉不自觉的选择一种最优方案,以期达到最优结果。这种追求最优方案以达到最优结果的学科就是最优化。寻求最优方案的方法就是最优化方法。这种方法的理论基础就是最优化理论,而凸分析又是最优化理论的基础之一。,1. 最优化问题,最优化问题:求一个一元函数或多元函数的极值。在微积分中,我们曾经接触过一些比较简单的极值问题。下面通过具体例子来看看什么是最优化问题。,1.1 最优化问题的例子,例1 对边长为a的正方形铁板,在四个角处剪去相等 的正方形以制成方形无盖水槽,问如何剪法使水槽 的容积最大? 解:设剪去的正方形边长为x,由题意易知,此问 题的数学模型为,,例2.(混合饲料配合)设每天需要混合饲料的批量为100磅,这份饲料必须含:至少0.8%而不超过1.2%的钙;至少22%的蛋白质;至多5%的粗纤维。假定主要配料包括石灰石、谷物、大豆粉。这些配料的主要营养成分如下表所示。试以最低成本确定满足动物所需营养的最优混合饲料。,配料,每磅配料中的营养含量,钙,蛋白质,纤维,每磅成本(元),石灰石 谷物 大豆粉,0.380 0.00 0.00 0.001 0.09 0.02 0.002 0.50 0.08,0.01640.04630.1250,解:根据前面介绍的建模要素得出此问题的数学模型如下: 设 是生产100磅混合饲料所须的石灰石、谷物、大豆粉的量(磅)。,1.2最优化问题的数学模型,一般形式向量形式其中,目标函数,不等式约束,等式约束,称满足所有约束条件的向量 为可行解,或可行点,全体可行点的集合称为可行集,记为 。,若 是连续函数,则 是闭集。,在可行集中找一点 ,使目标函数 在该点取最小值,即满足: 的过程即为最优化的求解过程。称为问题的最优点或最优解, 称为最优值。,定义1:整体(全局)最优解:若 ,对于一切 ,恒有 则称 是最优化问题的整体最优解。定义2:局部最优解:若 ,存在某邻域 ,使得对于一切 ,恒有 则称 是最优化问题的局部最优解。其中严格最优解:当 ,有 则称 为问题的严格最优解。,f(X),局部最优解,整体最优解,1.3 最优化问题的分类,与时间的关系:静态问题,动态问题是否有约束条件:有约束问题,无约束问题函数类型:线性规划,非线性规划,2、梯度与Hesse矩阵,2.1 等高线 二维问题的目标函数 表示三维空间中的 曲面。在空间直角坐标系中,平面与曲面的交线在 平面上的投影曲线为取不同的值得到不同的投影曲线。每一条投影曲线 对应一个值,所以我们称此投影曲线为目标函数的 等值线或等高线。,当常数取不同的值时,重复上面的讨论,在平面上得到一族曲线等高线.等高线的形状完全由曲面的形状所决定;反之,由等高线的形状也可以推测出曲面的形状,例 在坐标平面 上画出目标函数 的等高线解:因为当目标函数取常数时,曲线表示是以原点为圆心,半径为的圆因此等高线是一族以原点为圆心的同心圆(如图所示),2.2 梯度,梯度:多元函数 关于 的一阶导数,2.3 Hesse矩阵,Hesse 矩阵:多元函数 关于 的二阶偏导数矩阵,例:求目标函数 的梯度和Hesse矩阵。 解:因为 则又因为: 故Hesse阵为:,下面几个公式是今后常用到的: (1) ,则 (2) ,则 (单位阵) (3) ,Q对称, 则(4)若 ,其中f: 则:,3、 多元函数的Taylor展开,多元函数Taylor展开式在最优化理论中十分重要。 许多方法及其收敛性的证明都是从它出发的。定理:设 具有二阶连续偏导数。则:其中 而01Taylor展开式还可写成如下形式:,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为 mn矩阵,b为m维向量。 证明:任取 ,则所以,,例:给定线性规划 ,其中 , 若令 ,则 是凸集。,定义:设 x(1) , x(2) , , x(m) Rn, j 0 j =1,那么称 j x(j) 为x(1), x(2), , x(m) 的凸组合。性质: 凸集的交集是凸集;(并集一般不是) 凸集的内点集是凸集; 凸集的闭包是凸集。,4.2 凸函数,定义: 设集合 S Rn 为凸集,函数 f :SR,若 x(1), x(2) S, ( 0 , 1 ) ,均有 f( x(1)(1- ) x(2) ) f(x(1)+(1- )f(x(2) , 则称 f(x) 为凸集 S 上的凸函数。若进一步有上面不等式以严格不等式成立,则称f(x) 为凸集 S 上的严格凸函数。 当- f(x) 为凸函数(严格凸函数)时,则称 f(x) 为凹函数(严格凹函数)。,严格凸函数,凸函数,严格凹函数,定理: f(x) 为凸集 S 上的凸函数 S 上任 意有限点的凸组合的函数值不大于各点函数 值的凸组合。定理:可微函数 f(x) 为非空凸集 S 上的凸函 数 对任意 ,有,定理:具有二阶连续偏导数的函数 f(x) 为非 空凸集 S 上的凸函数 是半正定矩阵。 注: (1)当 是正定矩阵时,f(x) 是严格凸函数; (2)当 是半正定矩阵时,- f(x) 是凹函数,例:判断下列函数的凹凸性。 (1) (2) 解:(1)为正定矩阵, 为严格凸函数。 (2)因为 ,则易知所以 为凹函数。,4.3 凸规划,定义:对于规划若 与 都是凸函数,则称其为凸规划。例:线性规划 是凸规划。,例:数学规划 易知, 与 都是凸函数,所以该规划是凸规划。,对于一般的规划(P),其局部最优解不 一定是全局最优解,其可行集也未必是凸集。 但若(P)是凸规划,则有下面的结论。 定理:设规划(P)是凸规划,则 (1) (P)的可行集R为凸集; (2) (P)的最优解集合R*是凸集; (3) (P)的任何局部最优解都是全局最优解。,练习: 1、求 的梯度和Hesse矩阵。 2、判断函数 的凹凸性。 3、判断下述非线性规划是否为凸规划?,
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号