③运筹学 第一章非线性规划 ★凸规划 在非线性规划模型(NP)中,若目标函数∫(X)是凸函 数,不等式约束函数g,(X),j=1,…为凹函数,等式约束 函数h(X),i=1…,m为仿射函数,则称(NP)是一个 凸规划。 性质:★约束集是凸集; ★最优解集是凸集; ★任何局部最优解也是全局最优解; ★若目标函数是严格凸函数,且最优解存在,则 其最优解是唯一的
http://www.tju.edu.cn 第一章 非线性规划 ★凸规划 性质：★约束集是凸集； ★最优解集是凸集； ★任何局部最优解也是全局最优解； ★若目标函数是严格凸函数，且最优解存在，则 其最优解是唯一的。 在非线性规划模型（NLP）中，若目标函数f（X）是凸函 数，不等式约束函数 为凹函数，等式约束 函数 为仿射函数，则称（NLP）是一个 凸规划。 ( ) , 1, , j gX j l = " ( ) , 1, , i hX i m =
③ 运筹学 operations resea 第一章非线性规划 例:判断下面的非线性规划是否为凸规划 min( f(X))=-x-x2 maxf(X)=x+x, 81(X)=1-x-x2≥0 2+2≤1 般化 s18(X=x1≥0 ≥0 83(X)=x2≥0 00 H_(x ≥0,H(X)= 00 计算 H.(X)=H2(X)= 0 说明-f(X是凸函数,g1(X)、g2(X)、g3(X)是凹函数 因此,本模型是凸规划
http://www.tju.edu.cn 第一章 非线性规划 例：判断下面的非线性规划是否为凸规划 1 2 2 2 1 2 1 2 max ( ) 1 . . , 0 f X x x x x st x x = + ⎧ + ≤ ⎨ ⎩ ≥ 1 2 2 2 1 12 2 1 3 2 min( ( )) ()1 0 .. ( ) 0 () 0 f X x x gX x x st g X x gX x − =− − ⎧ = −−≥ ⎪ ⎨ = ≥ ⎪ = ≥ ⎩ 一般化 1 2 3 ( ) 0 0 2 0 0, ( ) 0 0 0 0 2 0 0 () () 0 0 0 f g g g H X H X HXHX − − − − = ⎛⎞ ⎛⎞ ⎜⎟ ⎜⎟ ≥ => ⎝⎠ ⎝⎠ ⎛ ⎞ = =≥ ⎜ ⎟ ⎝ ⎠ 计算 123 说明 是凸函数， − f X( ) gX gX gX () () () 、 、 是凹函数 因此，本模型是凸规划
③运筹学 第一章非线性规划 1.2无约束极值问题 ★一般模型: min f(X X∈R ★求解:当可微,可应用极值条件求解,但往往得到 个非线性的方程组,求解十分困难。因此,一般采用迭 代的方法,称为下降类算法
http://www.tju.edu.cn 第一章 非线性规划 1.2 无约束极值问题 ★一般模型： min ( ) n X R f X ∈ ★求解： 当f(X)可微，可应用极值条件求解，但往往得到 一个非线性的方程组，求解十分困难。因此，一般采用迭 代的方法，称为下降类算法
③运筹学 第一章非线性规划 下降类算法的基本步骤与算法收敛性 1.基本思想 基本思想是使f(X逐步下降,逐 X P 渐趋近其最小值。迭代方式是从 个初始点X出发,选取某搜 索方向B,沿该方向搜索到下 个点X。若达到与最优解误差的 X 精度要求,则停止,否则再沿该 点的某方向搜索下一个点X2° 这一过程如图所示:
http://www.tju.edu.cn 第一章 非线性规划 一、下降类算法的基本步骤与算法收敛性 1.基本思想 0 0 1 1 2 f X( ) X P X P X 基本思想是使 逐步下降，逐 渐趋近其最小值。迭代方式是从 一个初始点 出发，选取某一搜 索方向 ，沿该方向搜索到下一 个点 。若达到与最优解误差的 精度要求，则停止，否则再沿该 点的某一方向 搜索下一个点 。 这一过程如图所示： P0 P1 P2 X0 X1 X3 X2
③运筹学 第一章非线性规划 2.基本步骤 (1)选取初始点X,令k=0,确定精度E>0 (2)对于点X,计算Vf(X若‖!f(X)kE则停止 得到近似最优解X’否则转(3) (3)从X出发,确定搜索方向P; (4)沿P方向搜索,即由x=X+AP确定搜索步长λ2 得到下一个点=X+P,令三k+1转(2 注:不同的搜索方向,就形成了不同的算法,不同的算 法所产生的点列收敛于最优解的速度也不一样
http://www.tju.edu.cn 第一章 非线性规划 2.基本步骤 0 (1) 选取初始点 ，令 确定精度 ； X k : 0, 0 = ε > ( ), ( ) , 3 k kk k X fX fX X 对于点 ，计算 若 ∇ ∇< & & ε 则停止, 得到近似最优解 ，否则转（）； (2) 从 出发，确定搜索方向 ； X P k k (3) 1 , , : 1, 2) k k k k k k kk P X X P X X P kk λ λ + λ + + =+ 沿 方向搜索，即由 ＝ 确定搜索步长 得到下一个点 ＝ 令 转( 。 (4) 注：不同的搜索方向，就形成了不同的算法，不同的算 法所产生的点列收敛于最优解的速度也不一样