《管理系统分析2008第七章系统优化理论1》由会员分享，可在线阅读，更多相关《管理系统分析2008第七章系统优化理论1（160页珍藏版）》请在金锄头文库上搜索。
1、管理系统分析,李旲 曹宏铎 中山大学管理学院,第九章、系统优化理论与方法,概述 非线性最优化搜索算法结构 无约束非线性优化典型算法 约束优化问题 动态优化与最优控制原理,9.1 概述,优化问题的一般形式及分类 优化问题的基本概念,9.1.1优化问题的一般形式及分类,其中： xi 为决策变量（可控制）j 为已知参数k 为随机因素f , gh 为（一般或广义）函数,优化问题的分类：目标性质：多目标、单目标；约束性质：有约束、无约束变量性质：连续、离散；确定性、不确定性变量间关系：线性、非线性；模型时间性质：动态、静态,优化模型的一般形式,数学规划模型的一般形式（续）,函数形式: f(x), gi(
2、x) , hj(x) : RnRmin f(x) (fgh) s.t. gi(x) 0 , i = 1,2,mhj(x) = 0 , j = 1,2,l 矩阵形式:min f(x) ，f(x) : RnR (fgh) s.t. g(x) 0 , g(x) : RnRmh(x) = 0 , h(x) : RnRl当 f(x), gi(x) , hj(x)均为线性函数时，称线性规划；若其中有非线性函数时，称非线性规划。,数学规划模型,9.1.2优化问题的基本概念,最优解 向量和子空间投影定理 多元函数及其导数 多元函数极值问题 凸集 凸函数 凸规划 多面体、极点、极方向 确定性优化模型解的核心问题
3、,S Rn，f :S R，xS称（f S )的可行解，S称为可行集。 最优点: x*S，满足f (x*) f (x), xS。则称x*为(f S)的全局最优点(最优点),记 g.opt.(global optimum),简记 opt. 最优值: x*为(f S)的最优点, 则称 f * = f (x*) 为(f S)的最优值(最优目标函数值) 最优解：（ x*，f * ）称为最优解，习惯上称x*为最优解。 局部最优解: x*S， x* 的邻域 N(x*) ，使满足 x S N(x*)， 有f (x*) f (x)。则称 x*为(f S)的局部最优解,记 l .opt.(local optimu
4、m) 在上述定义中，当x x* 时有严格不等式成立，则分别称 x* 为(f S)的严格全局最优解和严格局部最优解。,1、最优解,2、向量空间和子空间投影定理,(1) n维欧氏空间：Rn,实用中，常用 x + d 表示从x 点出发沿d 方向移动d长度得到的点,d,0,x,x+(1/2)d,(2) 向量运算：x , y Rn,x , y 的内积：,x , y 的距离：,x 的长度：,三角不等式：,规定：x , y Rn，x y xi yi ，i 类似规定 x y，x = y，x y .,子空间投影定理：设 L 为Rn的子空间。那么 z Rn， 唯一 x L , y L, 使 z=x+y , 且 x
5、 为问题min z - us.t. u L 的唯一解，最优值为y。 特别， L Rn 时，正交子空间 L 0 （零空间）,（3）子空间投影定理：,(1) n元函数：f (x): Rn R线性函数：f (x) = cTx + b = ci xi + b二次函数：f (x) = (1/2) xTQx + cTx + b = (1/2)i j aij xi xj + ci xi + b向量值线性函数：F(x) = Ax + d Rm 其中 A为 mn矩阵，d为m维向量F(x)=( f1(x), f2(x), , fm(x) )T 记 aiT为A的第i行向量，fi(x) = aiTx+di,3、多元函
6、数及其导数,(2) 梯度（一阶偏导数向量）：f (x)( f / x1 , f / x2 , , f / xn )TRn .线性函数：f (x) = cTx + b , f (x) = c 二次函数：f (x) = (1/2) xTQx + cTx + b f (x) = Qx + c向量值线性函数：F(x) = Ax + d Rm F / x = AT,(3) Hesse 阵（二阶偏导数矩阵）：,线性函数：f (x) = cTx + b , 2f (x) = 0 二次函数：f (x) = (1/2) xTQx + cTx + b, 2f (x)=Q,(4)n元函数的Taylor展开式及中值公
7、式：设 f (x): Rn R ，二阶可导。在x* 的邻域内 一阶Taylor展开式：f (x) = f (x*)+ f T(x*)(x-x*) + ox-x* 二阶Taylor展开式：f (x) = f (x*)+ f T(x)(x-x*) + (1/2)(x-x*)T 2f (x*)(x-x*) + ox-x*2 一阶中值公式：对x, , 使f (x) = f (x*)+ f (x*+(x-x*)T(x-x*) Lagrange余项：对x, , 记xx*+ (x-x*)f (x) = f (x*)+ f T(x)(x-x*) + (1/2)(x-x*)T 2f (x )(x-x*),（1）
8、二次型：,4、 多元函数极值问题,正定二次型：任x 0，有XTAX0 A:正定矩阵 半正定二次型：任x 0，有XTAX0 A:半正定矩阵 负定二次型：任x 0，有XTAX0负定二次型A各阶主子式负、正相间,(2)、极值条件,(2.1)、一元函数极值,(2.2)、二元函数极值,可写为H(x0 y0)正定,且,(2.3)、多元函数极值,例1、求f(x)=2x12 +5x22 +x32 +2x2x3 +2x3x1 -6x2 +3的极值点及极值,所以X=(1, 1, -2)极小点 f(x)=0,例2、 研究f(x1 x2)= x22-x12的驻点,5、 凸集,1、凸集的概念： 定义：设集合 S Rn，
9、若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)的线段 。,凸集,非凸集,非凸集,凸组合：设 x(1) , x(2) , , x(m) Rn, j 0 m m j =1, 那么称 j x(j) 为x(1), x(2), , x(m) 的j =1 j = 1 凸组合。m 比较: z = j x(j) j =1 jR 构成线性组合 线性子空间 j0 构成半正组合 凸锥 j0 , j =1 构成凸组合 凸集,6、凸
10、组合,定理：S是凸集S中任意有限点的凸组合属于S 多胞形 H(x(1) , x(2) , , x(m) )：由 x(1) , x(2) , , x(m) 的所有凸组合构成。 单纯形：若多胞形 H(x(1) , x(2) , , x(m) )满足，x(2)-x(1) , x(3) -x(1) , , x(m)- x(1) 线性无关。即N+1维多面体,多胞形,单纯形,单纯形,凸锥： 定义：C Rn, 若 x C, 0 有 x C, 则称 C 是（以 0 为顶点的）锥。如果 C 还是凸集，则称为凸锥。 集合 0 、Rn 是凸锥。命题：C是凸锥C中任意有限点的半正组合属于S,（1）凸函数 定义: 设集
11、合 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) 为凹函数（严格凹函数）。,严格凸函数,凸函数,严格凹函数,7、凸函数,定理： f(x) 为凸集 S 上的凸函数 S 上任意有限点的凸组合的函数值不大于各点函数值的凸组合。,x= x1+(1- )x2,（2）水平集 定义：设集合 S Rn ，函数
12、 f :SR， R ，称 S = x Sf(x) 为 f(x) 在 S 上的 水平集。 定理：设集合 S Rn 是凸集，函数 f :SR是凸函数，则对 R ，S 是凸集。 注： 水平集的概念相当于在地形图中，海拔高度不高于某一数值的区域。 上述定理的逆不真。考虑分段函数f(x)=1(x0)或0(x0)，函数非凸，但任意水平集是凸集。,证明： x1 , x2 S f(x1) f(x2 ) 0 0 充分小时有 x*+d S, 如果lim f(x*+ d )-f(x*) / 存在（包括 ） 则称 f(x) 为在点沿方向的方向导数存在，记f (x*;d) = lim f(x*+ d )-f(x*) /
13、 若 f(x) 在 x* 可导，则 f (x*;d) = f (x*) Td .,（4）凸函数的性质： 以下设 S Rn 为非空凸集，函数 f :SR 1）若f 凸，则 f 在 S 的内点集上连续；注： f 在 S 上不一定连续。例: f(x)2(当x=1)； f(x)x2 (当x1) . 2）设f 凸，则对任意方向方向导数存在。 3）（一阶判定条件）设 S 是开集，f 在 S 上可微，则f凸 x*S，有f (x) f (x*)+ f T(x*)(x-x*) , x S . 4)（二阶判定条件）设 S 是开集，f 在 S 上二次可微，则a) f 凸 xS，2f (x) 半正定；b) 若 xS，2f (x) 正定，则f严格凸。,几何意义：过f(x)任一点切线，必在f(x)曲线之下。,3）一阶判定条件 设 S 是开集，f 在 S 上可微，则f凸 x*S，有f (x) f (x*)+ f T(x*)(x-x*) , x S .,当（f S）中，S为凸集，f是S上的凸函数（求min），称（f S）为凸规划； 对于（fgh）, f, 为凸函数，gi为凹函数，hj为线性函数时，（fgh）为凸规划。定理：设集合 S Rn 为凸集，函数 f :SR f(x) 为凸集 S 上的凸函数。X*为问题（fs）的l.opt，则X*为g.opt；又如果f是严格凸函数，那么X*是（fs）的唯一g.opt。,
