《优化-第123章复习市公开课特等奖市赛课微课一等奖PPT课件》由会员分享，可在线阅读，更多相关《优化-第123章复习市公开课特等奖市赛课微课一等奖PPT课件（141页珍藏版）》请在金锄头文库上搜索。
1、要求：要求：要求：要求：空集和单元素集也是凸集。空集和单元素集也是凸集。三角形，矩形，圆，球，凸多边形，第一象限，第一卦限等都三角形，矩形，圆，球，凸多边形，第一象限，第一卦限等都是凸。是凸。等价定义（凸集）：等价定义（凸集）：等价定义（凸集）：等价定义（凸集）：设设凸集与性质凸集与性质凸集与性质凸集与性质 定义（凸集）：定义（凸集）：定义（凸集）：定义（凸集）：若集合若集合 中任意两点连线都属于中任意两点连线都属于 ，则称，则称 为凸集。为凸集。因为两点因为两点 连线上任一点能够表示为连线上任一点能够表示为 凸集几何特征凸集几何特征凸集代数特征凸集代数特征称集合称集合 为凸集为凸集。恒有恒有
2、凸集、凸函数与凸规划凸集、凸函数与凸规划凸集、凸函数与凸规划凸集、凸函数与凸规划 第1页 例例例例1:1:证实集合证实集合 S=x Ax=b 是凸集，其中是凸集，其中A为为 m n矩矩阵，阵，b为为m维向量。维向量。凸集与性质凸集与性质凸集与性质凸集与性质 证实证实证实证实:即即所以所以即即S是凸集。是凸集。例例例例2:2:集合集合是凸集是凸集,称为超平面，称为超平面，c为为n维向量。维向量。例例例例3 3：邻域邻域是凸集。是凸集。第2页定义：定义：定义：定义：设设 那么称那么称 是是 凸组合。凸组合。性质性质性质性质2 2：S 是凸集是凸集 S 中任意有限个点凸组合属于中任意有限个点凸组合属
3、于 S。凸集与性质凸集与性质凸集与性质凸集与性质 性质性质性质性质1 1：设设 是凸集，则是凸集，则 也是凸集。也是凸集。注：注：注：注：不一定是凸集。不一定是凸集。第3页定义（凸函数）定义（凸函数）定义（凸函数）定义（凸函数）:设集合设集合 D Rn 为凸集，函数为凸集，函数 f:DR,若若 x,y D,(0,1)，都有，都有 f(x+(1-)y)f(x)+(1-)f(y)，则称则称 f(x)为凸集为凸集 D 上凸函数。上凸函数。若深入有上面不等式以严格不等式成立，则称若深入有上面不等式以严格不等式成立，则称 f(x)为凸集为凸集 D 上上严格凸函数严格凸函数。当当-f(x)为凸函数为凸函数
4、(严格凸函数严格凸函数)时，则称时，则称 f(x)为为凹函数凹函数 (严格凹函数严格凹函数)。严格凸函数严格凸函数凸函数凸函数严格凹函数严格凹函数凸函数凸函数凸函数凸函数-推广到多元函数推广到多元函数推广到多元函数推广到多元函数第4页定理定理定理定理(一阶条件一阶条件一阶条件一阶条件):):设设D Rn 为非空凸集，函数为非空凸集，函数 f:DR 在在 D 上可微，则上可微，则 (1)f在在D上为凸函数上为凸函数 任意任意x，y D，恒有，恒有 f(y)f(x)+f T(x)(y-x)(1)(2)f在在D上为严格凸函数上为严格凸函数 任意任意xy D，恒有，恒有 f(y)f(x)+f T(x)
5、(y-x).(2)凸函数判定定理凸函数判定定理凸函数判定定理凸函数判定定理第5页定理（二阶条件）定理（二阶条件）定理（二阶条件）定理（二阶条件）:设设D Rn 为含有内点非空凸集，函为含有内点非空凸集，函数数 f:DR在在 D 上二次可微，则上二次可微，则 a)f在在D上为凸函数上为凸函数 x D，2f(x)半正定；半正定；b)若若 x D，2f(x)正定，则正定，则f在在D上为严格凸函数。上为严格凸函数。回想：回想：一个矩阵半正定充要条件是全部主子式非负；一个矩阵半正定充要条件是全部主子式非负；一个矩阵半正定充要条件是全部主子式非负；一个矩阵半正定充要条件是全部主子式非负；一个矩阵正定充要条
6、件是全部次序主子式非负。一个矩阵正定充要条件是全部次序主子式非负。一个矩阵正定充要条件是全部次序主子式非负。一个矩阵正定充要条件是全部次序主子式非负。凸函数判定定理凸函数判定定理凸函数判定定理凸函数判定定理第6页例：例：例：例：设二次函数设二次函数 (1)：若：若 为半定矩阵，为半定矩阵，在在 中为凸函数中为凸函数；(2)：若若 为正定矩阵，为正定矩阵，在在 中为严格凸函数。中为严格凸函数。例：例：例：例：判断判断f(x)=5x12-6x1x2+5x22在凸集在凸集D上是否是凸函数？上是否是凸函数？次序主子式都是正，所以正定，所以次序主子式都是正，所以正定，所以f(x)在凸集在凸集D上是严格凸
7、函数。上是严格凸函数。凸函数判定定理凸函数判定定理凸函数判定定理凸函数判定定理第7页定义（凸规划）定义（凸规划）定义（凸规划）定义（凸规划）:考虑以下非线性规划考虑以下非线性规划当当 都是凸函数时都是凸函数时,称规划称规划 为凸规为凸规划划凸规划凸规划凸规划凸规划第8页性质性质性质性质1:1:设设(1)为凸规划，则为凸规划，则 i)(1)可行集可行集R是凸集；是凸集；ii)(1)最优解集是凸集；最优解集是凸集；iii)(1)任何局部极小点都是全局极小点。任何局部极小点都是全局极小点。性质性质性质性质2:2:设设(1)为凸规划，若为凸规划，若f(x)在非空可行集在非空可行集R上是严格凸函上是严格
8、凸函 数，则数，则(1)全局极小点是唯一。全局极小点是唯一。证实：证实：证实：证实：见书中见书中(P24)定理定理 3.11.注注注注:非线性规划局部最优解不一定是非线性规划局部最优解不一定是 全局最优解全局最优解,其可行解和最优解集也其可行解和最优解集也 不一定是凸集不一定是凸集,甚至不是连通集甚至不是连通集.如如 果是凸规划果是凸规划,就有很多好性质。就有很多好性质。凸规划性质凸规划性质凸规划性质凸规划性质证实：证实：证实：证实：见书中见书中(P23)定理定理 3.9、3.10.第9页 普通情况下普通情况下 ,为正整数为正整数,分别表示约束条件个数分别表示约束条件个数和决议变量个数和决议变
9、量个数,为价值向量为价值向量,为决议向量为决议向量,通常通常 为已知常数。为已知常数。称称m为线性规划阶数为线性规划阶数,称称n为线性规划维数。为线性规划维数。线性规划标准形线性规划标准形线性规划标准形线性规划标准形第10页怎样化成标准形怎样化成标准形怎样化成标准形怎样化成标准形若要求目标函数是若要求目标函数是:max z=cTx,只需将目标函数最大值变换为求目标函数最小值只需将目标函数最大值变换为求目标函数最小值,即即 max z=min(-z)。令。令z=-z,于是得到：于是得到：min z=-cTx。目标函数转换目标函数转换第11页 若约束方程组为不等式若约束方程组为不等式 约束条件为约
10、束条件为“”形式不等式形式不等式,则在则在“”号左边加号左边加入非负松弛变量入非负松弛变量;把原把原“”形不等式变为等式形不等式变为等式;约束方程转换：由不等式转换为等式约束方程转换：由不等式转换为等式称为松弛变量称为松弛变量对应松弛变量在目标函数中价值系数取值为对应松弛变量在目标函数中价值系数取值为0。怎样化成标准形怎样化成标准形怎样化成标准形怎样化成标准形第12页 约束条件为约束条件为“”形式不等式形式不等式,则可在则可在“”号左号左端减去一个非负剩下变量。端减去一个非负剩下变量。约束方程转换：由不等式转换为等式约束方程转换：由不等式转换为等式称为剩下变量称为剩下变量对应剩下变量在目标函数
11、中价值系数取值为对应剩下变量在目标函数中价值系数取值为0 0。怎样化成标准形怎样化成标准形怎样化成标准形怎样化成标准形第13页 若存在取值无约束变量若存在取值无约束变量 ，可令，可令 其中：其中：变量转换变量转换若若 ，可令可令 ，显然，显然怎样化成标准形怎样化成标准形怎样化成标准形怎样化成标准形第14页例例例例1:1:试将以下线性规划问题化成标准形试将以下线性规划问题化成标准形任何形式线性规划问题都能够化成标准形。现举例以下：任何形式线性规划问题都能够化成标准形。现举例以下：怎样化成标准形怎样化成标准形怎样化成标准形怎样化成标准形第15页解：令解：令 x3=x4-x5,x4,x5 0,(1)
12、式左端加上非负松弛变式左端加上非负松弛变量量 x6,(2)式左端减去非负剩下变量式左端减去非负剩下变量 x7,则可将上述线则可将上述线性规划问题化成以下标准形性规划问题化成以下标准形:怎样化成标准形怎样化成标准形怎样化成标准形怎样化成标准形第16页1.1.可行解（或允许解）可行解（或允许解）可行解（或允许解）可行解（或允许解）:满足约束条件解满足约束条件解 x=(x1,x2,xn)T 称为线性规划问题可行解称为线性规划问题可行解;2.2.可行域：可行域：可行域：可行域：全部可行解集合称为可行解集或可行域。全部可行解集合称为可行解集或可行域。3.3.最优解最优解最优解最优解:使得目标函数取到最小
13、值可行解称为线性规划问题使得目标函数取到最小值可行解称为线性规划问题最优可行解，简称为最优解或者解。最优可行解，简称为最优解或者解。线性规划问题标准形为：线性规划问题标准形为：线性规划基本概念线性规划基本概念线性规划基本概念线性规划基本概念第17页4.4.基基基基:假设假设 A 是约束方程组系数矩阵是约束方程组系数矩阵,其秩数为其秩数为 m,B是是矩阵矩阵 A 中由中由 m 列组成非奇异子矩阵列组成非奇异子矩阵(B行列式值不为行列式值不为0），则称），则称 B 是是 线性规划问题一个基。线性规划问题一个基。5.矩阵矩阵 B 是由是由 m 个线性无关列向量组成个线性无关列向量组成,不失普通不失普
14、通性性,可假设可假设:称称 Pj(j=1,2,m)为基向量为基向量,与基向量与基向量 Pj 相对应变量相对应变量xj(j=1,2,m)为基变量为基变量,不然称为非基变量。不然称为非基变量。线性规划基本概念线性规划基本概念线性规划基本概念线性规划基本概念第18页5.5.基本解：基本解：基本解：基本解：若令若令(2.1)式中非基变量式中非基变量 xm+1=xn=0,求求出一个解出一个解 x=(x1,x2,xm,0,0)T,这个解非这个解非0分量数分量数目小于方程个数目小于方程个数 m,称称 x 为基本解。为基本解。线性规划基本概念线性规划基本概念线性规划基本概念线性规划基本概念当基本解中有一个或者
15、一个以上基变量是当基本解中有一个或者一个以上基变量是0时，称这个基本时，称这个基本解是解是退化基本解退化基本解退化基本解退化基本解。第19页6.6.基本可行解基本可行解基本可行解基本可行解:满足非负约束条件基本解称为基本可行解满足非负约束条件基本解称为基本可行解.7.基本可行解非基本可行解非0分量数目小于分量数目小于 m,都是非负。都是非负。7.7.可行基可行基可行基可行基:对应于基本可行解基称为可行基对应于基本可行解基称为可行基.约束方程组约束方程组Ax=b基本解数目至多是基本解数目至多是 Cnm 个个.普通地讲普通地讲,基本基本可行解数目要小于基本解数目可行解数目要小于基本解数目,至多相等
16、至多相等.以上提到几个解概念以上提到几个解概念,可用以下列图来表示可用以下列图来表示:基解可行解基本可行解线性规划基本概念线性规划基本概念线性规划基本概念线性规划基本概念第20页1947年年,美国学者美国学者George Dantzig(丹茨格丹茨格)提出了求解线提出了求解线性规划单纯形法性规划单纯形法,为线性规划推广奠定了基础。为线性规划推广奠定了基础。从可行域从可行域一个顶点一个顶点(基本可行解基本可行解)开始开始,转移到另一个顶点转移到另一个顶点(另一个基本可行解另一个基本可行解)迭代过程，迭代过程，转移条件转移条件是是使目标函数值使目标函数值得到改进得到改进(逐步变优逐步变优),当目标函数到达最优值时当目标函数到达最优值时,问题也问题也就得到了最优解。就得到了最优解。基本思想基本思想单纯形法单纯形法单纯形法单纯形法第21页重复以上过程，能够深入改进基本可行解，直到全部重复以上过程，能够深入改进基本可行解，直到全部 时为止。时为止。单纯形法基本原理单纯形法基本原理单纯形法基本原理单纯形法基本原理基变量基变量基变量基变量非基变量非基变量非基变量非基变量初始基本初始基本可行解可行解改
