第三章非线性规划 Maxz=cx 请回顾线性规划 AX≤b,其目标与约束函数 x≥0 均为线性的。线性规划具有相对完美的理论与方法,应用 也很广泛,但它终究不能穷尽各种优化问题,因为世界是 非线性的 非线性规划( Nonlinear Programming)研究具有非线 性构成函数的优化问题,是运筹学中相对活跃的重要研究 分支
第三章 非线性规划 请回顾线性规划: ,其目标与约束函数 均为线性的。线性规划具有相对完美的理论与方法，应用 也很广泛，但它终究不能穷尽各种优化问题，因为世界是 非线性的。 非线性规划（Nonlinear Programming）研究具有非线 性构成函数的优化问题，是运筹学中相对活跃的重要研究 分支。 = 0 . . X AX b st Maxz CX
第一节基本概念 非线性规划问题与模型 1.问题 1)生产计划问题 x:产量;P(x)价格;C(x)成本 max f(x)=xP(x)xC() s(8(20 h,(x)=0
第一节 基本概念 一、非线性规划问题与模型 1. 问题 ⑴生产计划问题 max ( ) ( ) ( ) ( ) 0 . . ( ) 0 i j f x xP x xC x g x s t h x = − = x:产量;P(x):价格;C(x)成本
(2投资决策问题 第i种股票的购买量;P:第i种股票的价格 B:总资金;H,:第种股票的每股平均收益 β:风险系数;σn:第i种与第j种股票收益的协方差 max(x)=∑x1-B∑∑x Px.≤B ≥0
⑵投资决策问题 1 1 1 1 : : : : : : max ( ) . . 0 j j j ij n n n j j i j j i j n j j j j x j P j B j i j f x x x x P x B s t x = = = = = − 第 种股票的购买量； 第 种股票的价格 总资金； 第 种股票的每股平均收益 风险系数； 第 种与第 种股票收益的协方差
2模型 min f(X) (NLP)St ∫h(X)=0,=1 g(X)≥0,j=1,…,l 其中X=[x1…,x 记D={X∈R|1(X)=0,9(X)≥0} 则(NP)也可以表示为minf(X) X∈D 其中D称为(NLP)的约束集或可行域 当D=R时,(NLP)称做无约束极值问题; 当D≠R咐时,(NLP)称做约束极值问题
2.模型 1 n n min ( ) ( ) 0, 1, , ( ) . . ( ) 0, 1, , [ , , ] { | ( ) 0, ( ) 0} min ( ) D NLP D R NLP D R NLP i j T n n i j X D f X h X i m NLP s t g X j l X x x D X R h X g X NLP f X = = = = = = 其中 记 则（ ）也可以表示为 其中 称为（ ）的约束集或可行域。 当 ＝ 时，（ ）称做无约束极值问题； 当 时，（ ）称做约束极值问题
模型的解及相关概 1.可行解与最优解 ★可行解:约束集D中的X ★最优解:如果有ⅹ∈D,对于任意的X∈D, 都有f(X)≤f(X),则称X为(NLP)的最优 解,也称为全局最小值点。 ★局部最优解:如果对于X"∈D,使得在X的邻 域B(X0,E)={X‖X-X‖<e}中的任意X∈D 都有(X)≤f(X),则称X0为(NLP)的局部最 优解,也称为局部最小值点
二 、模型的解及相关概念 1.可行解与最优解 ★可行解：约束集D中的X。 ★最优解：如果有 ，对于任意的 ， 都有 ，则称 为（NLP）的最优 解，也称为全局最小值点。 * X D X D * f X f X ( ) ( ) * X ★局部最优解：如果对于 ，使得在 的邻 域 中的任意 都有 ，则称 为（NLP）的局部最 优 解，也称为局部最小值点。 0 X D 0 X X D 0 f X f X ( ) ( ) 0 0 B X X X X ( , ) { | } = − 0 X
例1:考虑非线性问题 minf(X)=(x1-2)2+(x2-2) S:t.x1+x2=6 如果约束改为 x+x2≤6 呢 6
例 1：考虑非线性问题 2 2 1 2 1 2 min ( ) ( 2) ( 2) . . 6 f X x x s t x x = − + − + = 2 x 1 x 6 6 3 3 如果约束改为呢？ 1 2 x x + 6
2梯度、海塞阵与泰勒公式 ★梯度 若f(X)在X的邻域内有连续一阶偏导数,则称f(X)在X点对n 个变元的偏导数组成的向量为f(X)在的梯度,记为Vf(X0) 即Vf(x af (Xo af(x 几何意义: 梯度是过x点且与f(X)在x0的切平面垂直的向量 梯度向量的方向是函数值在该点增加最快的方向
2.梯度、海塞阵与泰勒公式 ★梯度 0 0 0 0 0 0 0 1 ( ) ( ) ( ) ( ) ( ) ( ) ( ) [ ]T n f X X f X X f X X f X f X f X f X x x 若 在 的邻域内有连续一阶偏导数，则称 在 点对n 个变元的偏导数组成的向量为 在 的梯度，记为 ， 即 ＝ ， ， 0 0 X f X X ( ) 几何意义： 梯度是过 点且与 在 的切平面垂直的向量， 梯度向量的方向是函数值在该点增加最快的方向
★海塞阵 若f(X)在X的邻域内有连续一阶偏导数,则称f(X)在X点对n 个变元两两组合的二阶偏导数组成的矩阵为(X)在X的海赛阵, 记为B(X),即H(x0代(mn Ox a af(Xo) f(X0) Ox a 6f(X0 02f(X) Ox ax
★海塞阵 0 0 0 0 0 0 0 0 1 1 0 0 1 2 2 2 2 2 2 2 ( ) ( ) ( ) ( ) ( ) ( ) [ ] ( ) ( ) ( ) ( ) i j n n n n n f X X f X X n f X X f X H X H X x x f X f X x x x f X f X x x x = 若 在 的邻域内有连续二阶偏导数，则称 在 点对 个变元两两组合的二阶偏导数组成的矩阵为 在 的海赛阵， 记为 ，即 =
★泰勒公式 若f(X)在X的邻域内有连续一阶偏导数,则可写出f(x)在X点 的(二阶)泰勒展开式: f(X=f(X0)+Vf(X0)(X-X)+(X-X0)H(X0(X-X0) +o(x-X6) 其中:oY-X0‖是当X→X时x-X0的高阶无穷小
★泰勒公式 0 0 0 0 0 0 0 0 2 0 2 2 0 0 0 ( ) ( ) ( ) ( ) ( ) 1 ( ) ( )( ) 2 ( ) ( ) T T f X X f X X f X f X f X X X X X H X X X o X X o X X X X X X + + − − + − → − 若 在 的邻域内有连续二阶偏导数，则可写出 在 点 的（二阶）泰勒展开式： ＝ （ － ） － 其中： 是当 时 的高阶无穷小
例2:写出f(X)=3x+Sinx2在X=[0.0点的二阶泰勒展开式 Hif: Vf(X)=[6x, cosx,, Vf(Xo=[0 1] 60 60 H(X)= H(X0) 0 -sin x 00 60 f(X)=0+[01 X|2) 如果忽略了o(X,则/(X)在X点的近似表达式为 f(X=3x1+x
例2：写出 在 点的二阶泰勒展开式 2 1 2 f X x ( ) 3 = + sin x 0 [0,0]T X = 1 2 0 0 2 ( ) [6 ( ) [0 1 cos ] , ] 6 0 6 0 ( ) , ( ) 0 sin 0 0 T T f X x f X x H X H X x = = = = − 解: 1 1 2 1 2 2 2 ( ) 0 [0 1 1 6 0 ] [ ] ( ) 2 0 0 x x f X x x o X x x = + + + 2 0 2 1 2 ( ) ( ) 3 ( ) f X f X x o X X = x 如果忽略了 在 ，则 点的近似表达式为 +