第五小组_非线性规划-无约束极值问题.pptVIP

非线性规划 无约束极值问题 何海燕 技术经济及管理 * 非线性规划：无约束极值问题 * 无约束极值问题可表述为： Min f ( X ), X ∈ En 解此类问题可以用迭代法，分为以下两类方法： 1、解析法（运用函数的一阶导数和二阶导数） 梯度法（最速下降法） 共轭梯度法 变尺度法 2、直接法：步长加速法（收敛速度较慢、迭代步骤简单） 梯度法 共轭梯度法 变尺度法 一、基本原理 1、假设目标函数f (X )有一阶连续偏导数，且具有极小点X＊ 2、推导 X = X (k)+λP (k) （λ≥0）X (k)为极小点的第k次近似值； f (x)= f (X (k)+λP (k) )= f X (k)+λ▽ f X (k)T P (k) +o(λ)（泰勒级数） 其中lim (o(λ)/λ）=0 当λ充分小时： ▽ f X (k)T P (k) 0 f (X (k)+λP (k) ) f X (k) 此时，取X (k+1) = X (k)+λP (k) ，则可以使目标函数得到改善 二、迭代法的基本步骤 给定初始点X(0) 确定有哪些信誉好的足球投注网站方向P(k) 从X(k)出发，沿方向P(k)求步长λk 得X(k+1)= X(k) +λkP(k) 检查X(k+1)是否为极小点或近似极小点 若是，则停止迭代， 否则，令k=k+1，继续迭代 注： X(0)：题目会给出 P(k) = -?f (X(k)) 梯度法 共轭梯度法 变尺度法 三、具体例子 1 Minf(X), X∈En f（x）=（x1-1）2+（x2-1）2，ε=0.1 2 选取初始点X(0)和精度ε0 取X(0)=(0,0)T 和 ε=0.1 3 计算?f(X(0)) ?f (x) = [2(x1-1),2(x2 -1)] ,?f (x ) = (-2,-2) T 4 判断| ?f(X(0))| 2 ≤ε？ 是，则X(0）为近似最小点，停止迭代 否，则继续迭代 ||?f (X(0）)||2 =( (-2)2 +(-2)2 )2 =8e 继续！ 梯度法 共轭梯度法 变尺度法 三、具体例子 5 计算P(0)，H(X)和l(0) 6 计算X1= X(0)-l0 ?f (X(0)) X1 =(1,1) T 7 判断| ?f(X(0))| 2 ≤ε？ 是，则X(0）为近似最小点，停止迭代 否，则继续迭代 ?f (x (1) ) = (0,0)T , || ?f (x (1) ) ||2= 0 e 故x(0)即为极小点 结束！ l(0) l(0) 梯度法 共轭梯度法 变尺度法 三、具体例子:λ0的两种计算方式 代入目标函数可得： 令： 得： λ0=1/2 梯度法 共轭梯度法 变尺度法 一、基本定义 设X和Y是n维欧氏空间En的两个向量，若有 就称X与Y正交 再设A为n*n对称正定阵，如果X与AY正交，即有 则称X与Y关于A共轭，或X和Y为A共轭。 设A为n*n对称正定阵，若非零向量组P（1） P（2）… P（n）∈ En 满足： 则称该向量组为A共轭；如果A=I（单位阵），则上述条件即为通常的正交条件 梯度法 共轭梯度法 变尺度法 二、基本定理 定理 8 设A为n*n对称正定阵， P（1）， P（2），… P（n）为Ａ共轭的非零向量，则这组向量线性独立。 证明：设向量P（1）， P（2），… P（n）之间存在如下线性关系： 对i=1,2,…,n，用(P(i)）A左乘上式得： 但P(i) ≠0 ,A为正定，即 故必有ai= 0,i =1,2,L从而P（1）， P（2），… P（n）线性独立 梯度法 共轭梯度法 变尺度法 二、基本定理 无约束极值的一个特殊情形是： 其中A为n×n对称正定阵；X，B∈ En ，c为常数。 正定二次函数极小问题 定理9：设向量P(i）,i=0,1,2，…，n-1为A共轭，则从任一点X（0） 出发，相继以P（0）， P（1），… P（n-1）为有哪些信誉好的足球投注网站方向的下述算法： 经n次一维有哪些信誉好的足球投注网站收敛于正定二次函数的极小点X* 梯度法 共轭梯度法 变尺度法 三、正定二次函数的共轭梯度法基本步骤 选取初始点X(0)和精度ε0 计算P(0) =-?f(X(0))和X(1)和lk 梯度法 共轭梯度法 变尺度法 四、具体例子 例：用共轭梯度法求下述二次函数的极小点： 解：将f(x)化成正定二次函数形式，可得： 现从 开始， 梯度法 共轭梯度法 变尺度法 Q ?f (X (2) ) = (0,0)T ,||?f (X (2) ) ||2= 0 ￡e