非线性规划基础.pptx
一、非线性规划模型非线性规划的一般形式：称为决策变量称为不等式约束称为等式约束可行域称为目标函数第1页/共35页1、局部解 局部极大值 局部极小值2、全局解 全局最大值 全局最小值 局部最优解全局最优解 线性规划问题的最优解在角点取到，对非线性规划问题，最优解在何处取到呢？第2页/共35页二、非线性规划的几何求解例13.1 求解下列非线性规划的最优解。作图求解第3页/共35页例13.2 求解下列非线性规划的最优解。作图求解第4页/共35页例13.3 求解下列非线性规划的最优解。作图求解第5页/共35页线性规划与非线性规划有很大的区别：如果线性规划的最优解存在，其最优解只能在可行域的边界达到。而非线性规划的最优解（如果最优解存在）则可能在可行域的任何一点达到。第6页/共35页第二节 凸函数 一、凸函数的基本概念二、凸函数的判断三、凸规划第7页/共35页凸函数定义凹函数定义一、凸函数的基本概念凸函数凹函数非凸非凹函数第8页/共35页凸函数具有如下性质 第9页/共35页二、凸函数的判断 一元函数凸性的判断第10页/共35页多元函数凸性的判断 梯度：Hessian矩阵：第11页/共35页f(x)=x13+3x1x2+x22，则 f(x)的Hessian矩阵为：判定正定的方法：当一个nn矩阵A的任意k阶顺序主子式大于0时，则该矩阵为正定的。第12页/共35页D为凸集合，f(x)是定义在上的二次可微函数，则f(x)为凸函数的充要条件为f(x)在任意一点的Hessian矩阵为半正定。则f(x)为凸函数的充要条件为：第13页/共35页例13.4 判别下列函数的凸凹性 解：1 1）1）2）H(x1,x2)的两个顺序主子式分别H1(x1,x2)=4和H2(x1,x2)=8-4=4均大于0。所以 f(x)为凸函数。2 2）H(x1,x2)的两个顺序主子式分别H1(x1,x2)=20和H2(x1,x2)=-40。所以 f(x)不是凸函数。第14页/共35页三、凸规划当f(x),g(x)为凸函数，h(x)=(h1(x),hl(x)是线性函数时，上述规划问题称为凸规划问题。凸规划的求解可借助下节的KKT定理。h(x)=(h1(x),hl(x)=0第15页/共35页第三节 最优性条件一、无约束优化的最优性条件二、约束极值问题的最优性条件第16页/共35页引入两个概念 下降方向：可行方向：则称d为f(x)在点的下降方向。则称d为D在 点的可行方向。定理13.6 若f(x)在点 可微，如果存在方向d，使 ，则 使 有第17页/共35页一、无约束优化的最优性条件在无约束规划问题中，由于不涉及到可行域的问题，因此，只涉及下降方向。不涉及可行方向的问题。第18页/共35页定理13.713.7（一阶必要条件）若f(x)在点 可微，且为无约束优化问题（13.4）的局部最优解，则 。定理13.813.8（二阶必要条件）若f(x)在点 二阶连续可微，且点为无约束优化问题（13.4）的局部最优解。则 且 半正定。定理13.913.9（二阶充分条件）设 满足 且 正定，则 点为无约束优化问题（13.4）的局部最优解。定理13.1013.10 若目标函数f(x)是Rn上的连续可微凸函数，则 的充分必要条件 为无约束优化问题（13.4）的全局最优点和局部最优点。第19页/共35页例13.5 求函数f(x)的最优值点，即。正定解：所以 为局部最小值点。第20页/共35页二、约束极值问题的最优性条件 在x点取到局部最优值的条件为：无解约束规划问题不仅涉及到目标函数，还涉及到可行域。因此既要考虑下降方向，还要考虑可行方向第21页/共35页定理13.11（Gorden）：设 ，则Ax0有解的充分必要条件为：不存在非零向量 ，使得 。无解的充分必要条件为：存在不全为零的非负实数使 上述定理的几何意义为：dA1A2A3A3A1A2Ad0Ad0有解 Ad0无解无解 第22页/共35页定理（Fritz-John）：问题（13.5）在点取到局部极小值，则存在不全为零的非负实数使 例13.6：是下列优化问题的最优解，验证x满足Fritz-John定理。第23页/共35页紧指标集 I=1,2 如(w0,w1,w2)=(1,1,2)。因此，x满足Fritz-John定理。第24页/共35页例13.7 (0,2)T是下列优化问题的最优解，验证 x 满足Fritz-John定理(w0,w1,w2)=(0,k,2k)，w0=0 因此，x满足Fritz-John定理。第25页/共35页 约束规格：线性无关 定理（KKT）：设 是问题（13.5）局部最优解，在 处可微，在 处连续，且 线性无关，则存在不全为零的非负实数 使第26页/共35页例13.8 求下列问题的KKT点。KKT点：第27页/共35页定理13.14.在问题（13.5）中，f,gi(i=1,m)是凸函数，在 处可微，在 处连续，且在 处KKT条件成立，则 是问题（13.5）全局最优解。第28页/共35页 第四节 非线性规划问题的算法一、一维搜索法二、最速下降法第29页/共35页 min f(x)f:RnR 是一阶连续函数无约束优化问题的极值条件基本迭代格式寻找搜索方向是无约束优化的关键问题第30页/共35页一、一维搜索法一维搜索法是求解无约束优化的一种方法。它是沿射线 xk+1=xk+tdk，求 f(x)在该射线上的极小值，这一问题可转化为求一元函数的极小值，即因此，这一过程称为一维搜索法。第31页/共35页通常，无约束优化问题算法的一般形式为：初始步：给定初始点 ，令k=0。第1步：如果 ，停止计算；否则，进入下一步。第2步：计算下降方向dk，使 。第3步：计算步长tk，使得 ，令 ；k=k+1，转第1步。第32页/共35页一维搜索的方法很多，归纳起来，可分为试探法和函数逼近法。试探法中包括如黄金分割法、Fibonacci法等；函数逼近法中包括如牛顿法、割线法等。第33页/共35页牛顿算法计算步骤如下：初始步：给定初始点 ，令k=0=0。第1 1步：如果 ，则停止计算，得到点xk。否则，转第2 2步。第2 2步：计算点 xk+1：令k=k+1，转第1 1步。该算法特点是：收敛速度快，为二阶收敛。初始点要选在最优解附近。但有时初始点的选取困难，甚至无法实施。第34页/共35页感谢您的观看！第35页/共35页
