运筹学-非线性规划-.pptx

非线性规划非线性规划约束问题：约束问题：D 称为可行域。称为可行域。无约束问题：无约束问题：运用最小二乘思想，可将其化为三维空间的无约束非运用最小二乘思想，可将其化为三维空间的无约束非线性规划问题，即线性规划问题，即例例.多参数曲线拟合问题多参数曲线拟合问题已知热电阻已知热电阻 R 与温度与温度 t 的函数关系为的函数关系为其中其中 x1,x2,x3 是待定参数。通过试验，得到是待定参数。通过试验，得到 R 和和 t 的的15 组数据组数据:i1 12 21515t i50505555120120Ri34780347802861028610330733071.基本概念基本概念迭代算法：迭代算法：i)i)给定初始点给定初始点 x0,设设 k=0;ii)按照某种规则确定搜索方向按照某种规则确定搜索方向 pk;iv)计算计算iii)按照某种规则确定搜索步长按照某种规则确定搜索步长 tk;v)判断判断 x k+1 是否满足终止准则：是，是否满足终止准则：是，x*=x k+1，终止，终止;否，否，k=k+1，转步骤，转步骤 ii）。）。xkpkxk+1tk可行下降方向可行下降方向迭代算法中如何确定迭代算法中如何确定搜索步长搜索步长 tk？(1)(1)定步长，即取定步长，即取 tk 等于某一常数。等于某一常数。(2)(2)可接受点法，即任意选取能使目标函数值下降的可接受点法，即任意选取能使目标函数值下降的 tk。(3)（精确）一维搜索，即求解一元函数极小化问题：（精确）一维搜索，即求解一元函数极小化问题：若若迭代点列迭代点列 xk 有子序列收敛于问题的解有子序列收敛于问题的解 x*，则称该迭代算法收敛。则称该迭代算法收敛。若对于任意初始点若对于任意初始点 x0，迭代算法收敛，则称为全迭代算法收敛，则称为全局收敛；局收敛；若仅当若仅当 x0 属于属于 x*的某个邻域时，的某个邻域时，迭代算法收敛，迭代算法收敛，则称为局部收敛。则称为局部收敛。若迭代算法产生的点列若迭代算法产生的点列 xk 满足满足称为下降算法。称为下降算法。终止准则：终止准则：xkxk+1x*xkxk+1x*算法分类算法分类需要利用函数的解析性质（导数和高阶导数）需要利用函数的解析性质（导数和高阶导数）的算法，如梯度法、牛顿法。的算法，如梯度法、牛顿法。解析法：解析法：对函数的解析性质没有要求，只需利用函数对函数的解析性质没有要求，只需利用函数值的算法，如值的算法，如 0.6180.618 法、单纯形替换法。法、单纯形替换法。直接法：直接法：凸规划凸规划二次规划二次规划极小点的判定条件极小点的判定条件函数在极小点附近的等值线为近似函数在极小点附近的等值线为近似的同心椭圆。的同心椭圆。正定二次函数正定二次函数有唯一有唯一极小点极小点两个结论：两个结论：2.一维搜索一维搜索在迭代法中确定在迭代法中确定搜索步长搜索步长 tk 需要一维搜索：需要一维搜索：考虑一元函数极小化问题：考虑一元函数极小化问题：方法方法:如何确定一个包含极小点的区间？如何确定一个包含极小点的区间？首先定出一个包含首先定出一个包含 f(t)的极小点的区间，然后的极小点的区间，然后不断缩小区间的长度，当区间充分小时，取其不断缩小区间的长度，当区间充分小时，取其中的一点作为近似极小点。中的一点作为近似极小点。进退法进退法:从一点出发，按一定的步长寻找函数值呈现从一点出发，按一定的步长寻找函数值呈现“高高-低低-高高”的三点，若一个方向不成功，的三点，若一个方向不成功，就退回来，然后沿相反方向寻找。就退回来，然后沿相反方向寻找。任取初始点任取初始点 t0,计算计算 f(t0),取步长取步长 h 0,计算计算 f(t0+h),若若 f(t0)f(t0+h),令令 t1=t0+h,h=2h,计算计算 f(t1+h),若若 f(t1)f(t1+h),令令 t2=t1+h,h=2h,计算计算 f(t2+h),如此继续下去如此继续下去,直到对某个直到对某个 k 得到得到 f(tk)f(tk+h),此时得到一个包含极小点的区间此时得到一个包含极小点的区间 tk 1,tk+h;若一开始若一开始 f(t0)f(t0+h),若若 f(t1-h)f(tk),此时得到一个包含极小点的区间此时得到一个包含极小点的区间 tk-h,tk 1。黄金分割法（黄金分割法（0.618 法）法）解一元函数极小化问题解一元函数极小化问题假设：假设：f(t)在在a,b 上是单谷函数，即上是单谷函数，即 f(t)在在 a,b 上上有唯一极小点（设为有唯一极小点（设为 t*）且）且.在在a,b 上任取两点上任取两点 t1 t2,计算计算 f(t1)、f(t2)，则，则.n 次函数值计算可使搜索区间缩短次函数值计算可使搜索区间缩短 n-1 次。次。下面推导黄金分割法如何选取计算点下面推导黄金分割法如何选取计算点 t1、t2。两个条件：两个条件：黄金分割法的计算步骤：黄金分割法的计算步骤：计算计算 f(t1)、f(t2)。黄金分割法的迭代效果：黄金分割法的迭代效果：其它试探点算法：其它试探点算法：Fibonacci 算法算法例例.用用 0.618 法计算法计算 f(t)=(t-1)2 在在 0,3 上的极小点。上的极小点。解解.3.最速下降法（梯度法）最速下降法（梯度法）注：在极小点附近，目标函数可用二次函数近似，因注：在极小点附近，目标函数可用二次函数近似，因此等值面近似为椭球面，上述性质说明最速下降法此等值面近似为椭球面，上述性质说明最速下降法的搜索路径呈直角锯齿状：的搜索路径呈直角锯齿状：最速下降方向只是目标函数的局部下降最快方向，最速最速下降方向只是目标函数的局部下降最快方向，最速下降算法收敛速度慢，但具有整体收敛性。下降算法收敛速度慢，但具有整体收敛性。近似最佳步长：近似最佳步长：右端为二次函数，右端为二次函数，时达到最小。时达到最小。4.共轭方向法共轭方向法注：共轭是正交的推广。注：共轭是正交的推广。性质：共轭向量组一定线性无关。性质：共轭向量组一定线性无关。正定二次函数的共轭方向法：正定二次函数的共轭方向法：其中其中 A 正定。正定。性质：性质：共轭方向法用于正定二次函数，则至多经过共轭方向法用于正定二次函数，则至多经过 n 次迭代即得极小点次迭代即得极小点。问题：如何选择一组问题：如何选择一组共轭方向？共轭方向？共轭梯度法：共轭梯度法：以已知迭代点处的梯度方向为基础产生共轭方向。以已知迭代点处的梯度方向为基础产生共轭方向。因此因此共轭梯度法的搜索方向：共轭梯度法的搜索方向：共轭梯度法用于正定二次函数时具有性质：共轭梯度法用于正定二次函数时具有性质：为了将共轭梯度法用于非二次函数，需消去公式中的为了将共轭梯度法用于非二次函数，需消去公式中的 A。5.牛顿法牛顿法在在 x k 附近，附近，f(x)有近似式：有近似式：牛顿法的迭代牛顿法的迭代公式公式牛顿方向牛顿方向(1)若若 f(x)为为正定二次函数，则牛顿法只需一步迭代即正定二次函数，则牛顿法只需一步迭代即得极小点，因为此时有得极小点，因为此时有 f(x)=g(x)，所以，所以(2)牛顿法具有二阶收敛速率，但要求初始点选在极小牛顿法具有二阶收敛速率，但要求初始点选在极小点附近。点附近。几点说明：几点说明：6.单纯形替换单纯形替换法法单纯形替换法是直接法，只需利用函数值。单纯形替换法是直接法，只需利用函数值。何谓单纯形何谓单纯形?一维一维单纯形：线段单纯形：线段二维二维单纯形：三角形单纯形：三角形三维三维单纯形：四面体单纯形：四面体如何构造单纯形如何构造单纯形?算法思想：算法思想：给定初始点给定初始点 x 0，并构造初始单纯形，并构造初始单纯形 S0，然后进行单，然后进行单纯形替换迭代，迭代包括反射步、延伸步、收缩步或纯形替换迭代，迭代包括反射步、延伸步、收缩步或棱长减半等类型。棱长减半等类型。x hx rx hx ex rx hx rx cx hx rx c单纯形替换法的计算步骤：单纯形替换法的计算步骤：