最优化第05章非线性优化概论.pptVIP

第五章 非线性规划的基本概念 非线性规划问题及其数学模型 非线性规划的图解法 梯度、Hesse矩阵、Jacobi阵 凸函数和凸规划 解非线性规划方法概述 在科学管理和其他领域中，大量应用问题可以归结为线性规划问题，但是，也有另外许多问题，其目标函数和（或）约束条件很难用线性函数表达。如果目标函数和（或）约束条件中包含有自变量的非线性函数，则这样的规划问题就属于非线性规划。 一般来说，求解非线性规划问题比线性规划问题困难得多。而且，也不象线性规划那样有单纯形法这一通用的方法，非线性规划目前还没有适合于各种问题的一般算法，这是需要深入研究的一个领域。以下我们只是对一些模型及应用作简单介绍。 1 非线性规划问题及其数学模型 2 非线性规划问题的图解法 2 非线性规划问题的图解法 3 梯度、Hesse矩阵、Jacobi阵 (1) 二次函数 几个常用的梯度公式： （3）Hesse矩阵 几个常用Hessian公式： （4）Jacobi矩阵 向量变量值函数： 5、非线性规划方法概述 * （1）数学规划模型的一般形式： 其中, x=(x1 ,x2,… xn)T，f(x), gi(x), hj(x)为x的实值函数, 简记为MP(Mathematical Programming) （2）简记形式： 引入向量函数符号： （3）数学规划问题的分类： ?若f(x),gi(x),hj(x)为线性函数，即为线性规划(LP)； ?若f(x),gi(x),hj(x)至少一个为非线性，即为非线性规划(NLP)； ?对于非线性规划，若没有gi(x),hj(x)即X=Rn,称为 无约束非线性规划或无约束最优化问题； 否则称为约束非线性规划或约束最优化问题。 （4）可行域和可行解： 称 为MP问题的约束集或可行域。 若x在X内，称x为MP的可行解或者可行点。 （5）最优解和极小点 对于非线性规划（MP），若 ，并且有 如果有 定义: 如果有 定义 则称 x* 是(MP)的局部最优解或局部极小解, 例1： 用图解法求解 min f(x)=(x1-2)2 +(x2-2)2 s.t. h(x)= x1 + x2 - 6 = 0 x1 x2 0 6 6 2 2 3 3 最优解 x* = ( 3，3 )T 可行解 x = ( 1.5，4.5 )T 最优解即为最小圆的半径： f(x)=(x1-2)2 +(x2-2)2 = 2 对二维最优化问题，总可以用图解法求解，而对三维或高维问题，已不便在平面上作图，此法失效。 x1 x2 0 6 6 2 2 D可行域 最优解 x* = ( 2，2 )T 例2： 用图解法求解 min f(x)=(x1 - 2)2 +(x2 - 2)2 s.t. h(x)= x1 + x2 - 6 ≤ 0 最优解即为最小圆的半径： f(x)=(x1 - 2)2 +(x2 - 2)2 = 0 解：①先画出等式约束曲线 的图形——抛物线， 例3：用图解法求解 ②再画出不等式约束区域， ③最后画出目标函数等值线， 所以 最优解x*=(4,1), 最优值min f(x)=4. 一般形式: 矩阵形式: 二次型: 矩阵A的正定性:正定、半正定、负定、不定。 其中A＝AT。 二次型的正定性:正定、半正定、负定、不定。 （2） 梯度 定义：f(x) 是定义在Rn上的可微函数。以f(x) 的n个偏导数为分量的向量称为f(x) 的梯度. 性质：设f(x) 在定义域内有连续偏导数，即有连续梯度，则梯度有以下两个重要性质： 性质一 函数在某点的梯度不为零，则梯度必与过该点的等值面垂直; 性质二 负梯度方向是函数值下降最快