无约束非线性规划.ppt

非线性规划 南京航空航天大学经济与管理学院 党 耀 国 教授、博士生导师 管理科学与工程系主任 iamdangyg@163.com 该方法是1847年柯西提出的，它是求解无约束极值问题的解析法中最古老但又十分基本的一种方法，它的迭代过程简单，使用方便，对初始点的选取要求不严。 假设无约束极值问题中的目标函数f(x) 有一阶连续偏导数，且有极小点x*。我们取一初始近似点x(0)和一方向g(0)，作射线 x=x(0)+ ? 0 g(0) ? 0 0 这里的方向g(0)和步长? 0都是待定的。 此式表明，相邻的两个迭代点的梯度是彼此正交的。也即在梯度的迭代过程中，相邻的有哪些信誉好的足球投注网站方向相互垂直。梯度法向极小点的逼近路径是锯齿形路线，越接近极小点，锯齿越细，前进速度越慢。 这是因为，梯度是函数的局部性质，从局部上看，在该点附近函数的下降最快，但从总体上看则走了许多弯路，因此函数值的下降并不快。 2、迭代终止条件 采用梯度准则： || g(k) ||? ? 3、迭代步骤（1）任选初始迭代点x(0)，选收敛精度? 。（2）确定x(k)点的梯度（开始k=0)（3）判断是否满足终止条件|| g(k) ||? ?？若满足输出最优解，结束计算。否则转下步。（4）从x(k)点出发，沿-g(k)方向作一维有哪些信誉好的足球投注网站求最优步长?(k)。得下一迭代点 x(k+1)=x(k)-?(k)g(k) ，令k=k+1 返回步骤（2）。 4、梯度法流程图 5、例题试用最速下降法（梯度法）求 共轭梯度法是共轭方向法的一种，因为该方法中每一个共轭向量都是依赖于迭代点处的负梯度而构造出来的，所以称作共轭梯度法。 1、共轭方向 对于n维欧氏空间中的两个非零向量x和y， 如果 xTy=0 称x和y是正交的。 假设A是n阶对称正定矩阵，如果向量x和Ay正交，即 xTAy=0 称x和y是A共轭的。 若A为单位矩阵时， x和y是A共轭的和x和y是正交是相同的。即A共轭的概念是正交概念的推广。 不过， A共轭与正交之间并与任何联系。 共轭梯度法的特点 共轭梯度法属于解析法，其算法需求一阶导数，所用公式及算法简单，所需存储量少。该方法以正定二次函数的共轭方向理论为基础，对二次型函数可以经过有限步达到极小点，所以具有二次收敛性。但是对于非二次型函数，以及在实际计算中由于计算机舍入误差的影响，虽然经过n次迭代，仍不能达到极小点，则通常以重置负梯度方向开始，有哪些信誉好的足球投注网站直至达到预定精度，其收敛速度也是较快的。 前面介绍了用于正定二次函数的共轭梯度法，下面把这种方法推广到用于极小化任意n元函数。 一、共轭梯度法的有哪些信誉好的足球投注网站方向 设f(X)为某一凸函数，它具有二阶连续偏导数，其唯一极小点为X*。现取初始点X（0），计算? f(x(0))，选取p(0）= ? f(x(0))为初始有哪些信誉好的足球投注网站方向，作射线X(0) ＋ ?p(0)，并将f(X)= f(X(0)＋? p(0))于X(0)附近作泰勒展开式： f(X(0)＋? p(0))＝ f(X(0))＋?? f(x(0)) p(0)＋?2p(0)TH(x(0)) p(0）/2 上式的?为二次函数，因为p(0)TH(x(0)) p(0)0 故使该二次函数沿p(0)方向取极小值的?为 牛顿法 为了寻找收敛速度快的无约束最优化方法，我们考虑在每次迭代时，用适当的二次函数去近似目标函数f，并用迭代点指向近似二次函数极小点的方向来构造有哪些信誉好的足球投注网站方向，然后精确地求近似二次函数的极小点，以该极小点作为 f 的极小点的近似值。这就是牛顿法的基本思想。也是单变量牛顿法的推广。 牛顿法是求无约束最优解的一种古典解析算法。 牛顿法可以分为原始牛顿法和阻尼牛顿法两种。实际中应用较多的是阻尼牛顿法。 原始牛顿法 一、原始牛顿法的基本思想 在第k次迭代的迭代点xk邻域内，用一个二次函数去近似代替原目标函数f(x)，然后求出该二次函数的极小点作为对原目标函数求优的下一个迭代点，依次类推，通过多次重复迭代，是迭代点逐步逼