第三章 非线性规划的几个基本概念 • 多元函数的Taylor展开• 无约束问题的最优性条件• 约束问题的最优性条件• 最优化的数值计算方法要点：方向导数、下降方向、无约束函数极值的必要条件、平稳点、 可行方向、几何最优性条件、起作用约束、K－T定理、K－T点、下降迭代算法、算法的收敛性§3.1 多元函数泰勒(Taylor)的展开公式 n元函数f(x1, x2, …,xn)在点x(0)=[ x1, x2, …,xn]T附近展开到二次项 的Taylor公式为余 项其中 x＝x－x(0) = [x1－x1(0),…, xn－xn(0)]T = [x1,…, xn]T (1) 梯度 是向 量f(x(0))梯度的重要性质：几个常用函数的梯度① f(x) = b1x1+…+bnxn = BTxf(x) = [b1, b2, …, bn]T =B② f(x) = x12+…+xn2 = xTxf(x) = [2x1, 2x2, …, 2xn]T =2x③ f(x) =xTAx (aij = aji)f(x) =2Ax④ f(x) = c+BTx+1/2xTAxf(x) =B+Axx(0)f(x(1))x(1)点x(0)处的梯度方向与过该点的等值面垂直 。
2) 二阶导数矩阵―Hesse矩阵 记为 H(x)n元函数f(x1, x2, …,xn)的Taylor展开公式的矩阵形式梯 度 H(x)§3.2 方向导数与最速下降方向 （一）方向导数定义：设p为从x(0)出发的某单位向量，称函数f(x)在点x(0)处沿方向p的变化率为f(x)在点x(0)处沿方向p的方向导数 f(x)x(0)θ Pf(x(0))（二）最速下降（上升）方向 称方向导数小于零的方向为下降方向, 方向导数大于零的方向为上升方向最速上升方向为梯度方向f(x(0))，最速下降方向为负梯度方 向 － f(x(0)) 由于上升方向下降方向变化率为0f(x(0))最速上升方向－ f(x(0)) 最速下降方向x(0)称 为点x(0)处的下降方向集合§3.3 局部最优与全局最优 （一）局部最优定义：设f(x)是定义在可行域S上的一个函数，若存在S中的点x*及其一个邻域N (x*)，使得对任意x N (x*)，都有f(x*) = f(x)－f(x*)0称x*为f(x)的局部最小点或极小点；称f* ＝f(x*)为局部最小值 （二）全局最优定义：若存在S中的点x**，使得对所有x S，都有f(x**) = f(x)－f(x**)0称x**为f(x)的全局部最小点或整体最小点；称f** ＝f(x**)为全局最小值 xf(x)x1 x2 x3 x4 x5 x6ab§3.4 无约束问题的最优性条件 研究最优性条件的目的：约定：实际问题目标函数可能不连续或导数不存在，甚至是离散函数，最优点可能在不连续点或导数不存在的点。
以下讨论时假定f(x)处处连续可导. （1）用以求最优点； （2）用以判定给定点是否为最优点； （3）优化方法的基础一）无约束函数极值的必要条件 若x*是f(x)的局部最小（大）点，则在x*处必有 以及Hesse矩阵 是半正定（半负定）的 此条件仅是必要的，即对导数存在的点，若不满足上述条件，肯定不是极值点但满足此条件，不一定是极值点.定义：对可微函数f(x), 使 的点为平稳点（或驻点 、定点） 对一元函数，两个条件变为 f ’(x)＝0及f ”(x)0 .极值点的候选点 平稳点导数不存在的点由必要条件可得“ 有资格”成为最优 的点, 如果有充分 条件该有多好!!!如 f(x)=x3 , 当 x = 0时，满足上述两个条件，但不是极值点 二）无约束函数极值的充分条件 若点x*满足 以及 是正定（负定）的，则 x* 是 f(x) 的一个严格的局部最小（大）点 例3.4.1 求f(x1,x2)=2x12－8x1+2x22－4x2+20的极值点及极值。
解： 先求平稳点平稳点为 x*＝[2, 1]T Hesse矩阵为x*＝[2, 1]T是f(x)的严格极小点，f(x*)=10 其前主子式4>0， =16>0 Hesse矩阵是正定的 ! ! 上述最优性条件都是对局部最优点而言的，工程问题都需要找全局最优点，这方面已进行大量研究，但仍没有一 个统一的判别方法如果在可行域中只有一个局部最优点，即为全局最优点，有多个局部最优点，则想法全找出来，再比较确定全局最优点§3.5 约束问题的最优性条件 min f(x) s.t.最优点同时与目标函数及约束函数的性质有关存在两种情况 ： (a) 无约束极值点x(0)Sx2x1x2x1SSx(0) =x*x(0)x*(b) 无约束极值点x(0)S ! 目标函数的梯度等于零并不是约束问题的最优性必要条件！带有不等式约束的优化问题的最优性条件通常是一组不等式与方程，比较复杂的，很难求解，所以在一般情况下，不是直接求解这些条件来获得极值点，而是使用各种迭代法求出近似的极值点但它在理论上很重要，是各种迭代方法的基础和依据 （一）可行方向与起作用约束 定义：设点xS，p是一个方向，如果存在实数a1>0, 使对所有a[0, a1]，有x+apS，则称p为点x 的一个可行方向,或容许方向、允许方向。
几何上，若从x处沿方 向p引一射线，若该射 线起始端有一段在可 行域内，则这个方向p 就叫可行方向 SxpSg1(x)=0g2(x)=0g3(x)=0! 是否为可行方向与起始点的位置有关！(1)若x是S的内点，则任何方向均为可行方向 g1(x) g2(x) g3(x)(2)若x是S的边界点，则有的方向不是可行方向 若x位于第i个约束上，即 ，若p为边界点x的可行方向， 则必有 几何最优性条件: 在判定边界点处的方向是否可行方向时，有必要对约束条件进行分类定义：对可行域S中某个点x, 称成立gi(x) = 0的那些不等式约束gi(x)0为点x处的起作用约束称集合 为在点x处起作用约束的下标集 最优点x*处一定不存在既可行又下降的方向（1.3.4）（1.3.5）（1.3.6）min f(x) s.t.（二）Kuhn-Tucker最优性必要条件 定理：设x*为非线性规划(1.3.4)-(1.3.6)的最优解，f, gi , hj为可微函数，其中=[1,2, …,l]T, =[1, 2, …,m]T 称为Lagrange乘子向量 以上三式称为K－T最优性条件，满足此条件的点称为K－T点。
如果在x*处各个起作用约束的梯度向量 线性无关， 则存在向量,使下述条件成立：! 在无约束情形下，上述条件等同于梯度等于0 ！ 互补松驰条件 : 在gi(x)不是起作用 约束时, i *=0K－T条件可写成 引入广义Lagrange函数 和向量函数 g(x) = [g1(x), g2(x), … , gl(x)]T，? 如何理解K-T定理? 它有什么几何意义?下面以最简单的两种情况加以说明：假定不存在等式约束(m=0)且n=2（二维），只有一个或两个起作用的不等式约束① 先考虑只有一个起作用不等式约束 g(x) ≤ 0 的情况 ：此时，K-T条件为（其中λ>0 ） g(x)=0x1x2 Sf(x)的等值 线x(1)x(2) = x*x(1)不是最优 点， K-T条 件不成立x(2)是最 优点， K -T条件成 立S g1(x)=0x1x2 g2(x)=0② 对有两个起作用不等式约束 g1(x) ≤ 0及 g2(x) ≤ 0的情况：此时，K-T条件为f(x)的等值线x(1)x(1)不是最 优点，K- T条件不 成立S g1(x)=0x1x2 g2(x)=0f(x)的等值线x*x*是最优 点，K-T条 件成立K-T条件为!!! 若最优点x*位于几个起作用不等式约束的交点上，则 位于这些起作用约束的梯度所构成的锥角内 Ø 关于K－T定理的几点说明 （1）定理中向量组 线性无关称为约束规范。
但要验证是否满足约束规范是很困难的，因为需要事先知道x* 对一些特定的非线性规划，约束规范总是成立的见p75)（2）约束规范不满足，定理不一定成立，最优点可以不是K－T点 例3.5.1 验证下面的非线性规划在最优点x*处不满足约束规范, 最优点不是K-T点： 显然最优点 x*=[x1*, x2*]T=[1, 0]T, f = f (x*) = 4. 下面验证在 x* =[1, 0]T处不满足约束规范 因为 g1(x*) = 0, g2(x*) 0，令迭代次数记数变量k=0 ；(2) 假定已得到第k次近似点x(k), (但它还不是极小点)，这时选择一个下降方向p(k) ，即 (3) 由x(k)出发，以p(k)为方向作射线 x(k)+λp(k) （λ>0），在此射线上选取步长因子λk ，使得到的第k+1次近似点 x(k+1)=x(k)+λkp(k) 满足 f(x(k+1))
(3) 算法的收敛性与收敛速度 Ø 收敛性：算法迭代得到的点序列{x(k)}，能够在有限步内达到问题 的最优解x*，或者序列{x(k)}有一个极限点x*，则算法是收敛的 ！收敛的算法不一定是好算法，还要看收敛速度 ！x(k)p(k)x(k+1)定义：对于收敛于最优解x*的序列{x(k)}，若存在与k无关的常数β ≥ 0和≥ 1，使得当k从某个k0 开始，即 k ≥ k0时，恒成立则称序列{x(k)}具有阶收敛速度，β为收敛系数或收敛比 越大，收敛速度越快 ＝1，0<β<1，线性收敛1< <2，或 ＝1，β=0 超线性收敛 ＝2，二阶收敛 Ø 二次收敛性：当一个算法用于具有对称正定矩阵的二次函 数时，可在有限步迭代内获得极小点 两者不是一回事[f(x) = c+BTx+1/2xTAx](4) 迭代终止准则由于不知道真正的极小点在哪里, 所以不可能计算迭代点接近极小点的精确程度只能根据计算过程中的一些信息判断是否终止计算常用的终止准则有三种： c. 对无约束问题可用a.b.其中ε1，ε2，ε3称为允许误差 3、算法的评价准则作业：P449 9；10P450 12；13(1) 通用性；(2) 达到一定精度所需计算函数值和导数的次数；(3) 终止时所用CPU时间；(4) 收敛性；(5) 上机准备工作的难易程度。