天津大学：《运筹学》精品课程教学资源（电子课件）第一章 非线性规划 Nonlinear Programming

Q买非点藏为同课程运笑 天津大学研究生精品课程运筹学 运筹学A、运筹学B、管理运筹学 运筹学A是针对管理专业本科没学过运筹学的 学生开设的学位课 运筹学B是针对管理专业本科已学过运筹学的 学生开设的学位课 管理运筹学是针对非管理专业的学生开设的 选修课 20016天津大学运筹学课程网站202.11.13.67/ou5/tg

2007-11-16 天津大学研究生精品课程运筹学—— 运筹学A、运筹学B、管理运筹学 -运筹学A是针对管理专业本科没学过运筹学的 学生开设的学位课 -运筹学B是针对管理专业本科已学过运筹学的 学生开设的学位课 -管理运筹学是针对非管理专业的学生开设的 选修课

③运筹学 第一章非线性规划 络意非线性划 Nonlinear programming 1.1基本概念 1.2无约束极值问题 1.3约束极值问题

http://www.tju.edu.cn 第一章 非线性规划 第一章 非线性规划 (Nonlinear Programming) 1.1 基本概念 1.2 无约束极值问题 1.3 约束极值问题

③运筹学 第一章非线性规划 Maxz= cx 请回顾线性规划 AX≤b,其目标与约束函数 st X>0 均为线性的。线性规划具有相对完美的理论与方法,应用 也很广泛,但它终究不能穷尽各种优化问题,因为世界是 非线性的。 非线性规划( Nonlinear programming)研究具有非线 性构成函数的优化问题,是运筹学中相对活跃的重要研究 分支

http://www.tju.edu.cn 第一章 非线性规划 请回顾线性规划: ,其目标与约束函数 均为线性的。线性规划具有相对完美的理论与方法，应用 也很广泛，但它终究不能穷尽各种优化问题，因为世界是 非线性的。 非线性规划（Nonlinear Programming）研究具有非线 性构成函数的优化问题，是运筹学中相对活跃的重要研究 分支。 ⎩⎨⎧ ≥≤ = 0 .. X bAX ts Maxz CX

③运筹学 第一章非线性规划 1.1基本概念 、非线性规划问题与模型 1.问题 (1)生产计划问题 x:产量;P(x):价格;C(x)成本 maxf(x)=xP(x)xC(x) 8(x)≥0 h,(x)=0

http://www.tju.edu.cn 第一章 非线性规划 1.1 基本概念 一、非线性规划问题与模型 1.问题 ⑴生产计划问题 max ( ) ( ) ( ) () 0 . . () 0 i j f x xP x xC x g x s t h x = − ⎧⎪ ≥ ⎨ ⎪ = ⎩ x:产量;P(x):价格;C(x):成本

③运筹学 第一章非线性规划 (2)投资决策问题 x:第i种股票的购买量;P:第j种股票的价格 B:总资金;μ:第种股票的每股平均收益 β:风险系数;σn:第与第种股票收益的协方差 maxf(x)=∑x,-B∑∑xx <B st x.≥0

http://www.tju.edu.cn 第一章 非线性规划 ⑵投资决策问题 1 1 1 1 : : : : : : max ( ) . . 0 j j j ij n n n j j ij i j j i j n j j j j x j P j B j i j f x x xx Px B s t x μ β σ μβ σ = = = = = − ⎧ ≤ ⎪⎨⎪ ≥ ⎩ ∑ ∑∑ ∑ 第 种股票的购买量； 第 种股票的价格 总资金； 第 种股票的每股平均收益 风险系数； 第 种与第 种股票收益的协方差

③运筹学 第一章非线性规划 2.模型 min f(X) h,(X)=0,i=1,…,m (NLP)St (x)≥0,j=1,…, 其中X=[x,…,xn 记D={X∈R"|1()=0,g(X)≥0)} 则(NP)也可以表示为minf(X) X∈D 其中D称为(NLP)的约束集或可行域。 当D=R时,(NP)称做无约束极值问题; 当D≠R时,(MP)称做约束极值问题

http://www.tju.edu.cn 第一章 非线性规划 2.模型 1 min ( ) ( ) 0, 1, , ( ) .. ( ) 0, 1, , [, , ] { | ( ) 0, ( ) 0} min ( ) i j T n n i j X D n n f X hX i m NLP s t gX j l Xx x D X R hX g X NLP f X D NLP D R NLP D R NLP ∈ ⎧⎪ = = ⎨⎪ ≥ = ⎩ = =∈ = ≥ ≠ " " 其中 " 记 则（ ）也可以表示为 其中 称为（ ）的约束集或可行域。 当 ＝ 时，（ ）称做无约束极值问题； 当 时，（ ）称做约束极值问题

③运筹学 第一章非线性规划 a二、模型的解及相关概念 1.可行解与最优解 ★可行解:约束集D中的X。 ★最优解:如果有X'∈D,对于任意的X∈D, 都有f(x)≤f(X),则称x为(NP)的最优 解,也称为全局最小值点。 ★局部最优解:如果对于X∈D,使得在X的邻 域B(X,E)={-X|k}中的任意X∈D 都有(X)≤f(X),则称X为(NP)的局部最 优解,也称为局部最小值点

http://www.tju.edu.cn 第一章 非线性规划 二 、模型的解及相关概念 1.可行解与最优解 ★可行解：约束集 D中的 X 。 ★最优解：如果有 ，对于任意的 ， 都有 ，则称 为（NLP）的最优 解，也称为全局最小值点。 * X ∈ D X ∈ D * f ( ) () X fX ≤ * X ★局部最优解：如果对于 ，使得在 的邻 域 中的任意 都有 ，则称 为（NLP）的局部最 优 解，也称为局部最小值点。 0 X ∈ D 0 X X ∈ D 0 f ( ) () X fX ≤ 0 0 BX X X X ( ,) ε ={ |& & − < ε} 0 X

③运筹学 第一章非线性规划 例:考虑非线性优化问题 minf(X)=(x-2)+(x2-2) S.t. x,+x2 如果约束改为 x +x<6 呢

http://www.tju.edu.cn 第一章 非线性规划 例：考虑非线性优化问题 2 2 1 2 1 2 min ( ) ( 2) ( 2) . . 6 fX x x st x x =−+− + = 2 x 1x 6 6 3 3 如果约束改为 呢？ 1 2 x x + ≤ 6

③运筹学 第一章非线性规划 2.梯度、海塞阵与泰勒公式 ★梯度 若f(X)在x的邻域内有连续阶偏导数,则称f(X)在x点对n 个变元的偏导数组成的向量为(X)在X的梯度,记为Vf(X df(X Of(X) 即Vf(x) 几何意义: 梯度是过X点且与(X)在X的切平面垂直的向量, 梯度向量的方向是函数值在该点增加最快的方向

http://www.tju.edu.cn 第一章 非线性规划 2.梯度、海塞阵与泰勒公式 ★梯度 0 0 0 0 0 0 0 1 ( ) ( ) ( ) ( ) () () ( )[ ] T n f X X f XX n fX X f X fX fX f X x x ∇ ∂ ∂ ∇ ∂ ∂ " 若 在 的邻域内有连续一阶偏导数，则称 在 点对 个变元的偏导数组成的向量为 在 的梯度，记为 ， 即 ＝ ，， 0 0 X fX X ( ) 几何意义： 梯度是过 点且与 在 的切平面垂直的向量， 梯度向量的方向是函数值在该点增加最快的方向

③运筹学 第一章非线性规划 ★海塞阵 若f()在X的邻域内有连续一阶偏导数,则称f(X)在X点对n 个变元两两组合的一阶偏导数组成的矩阵为(X)在x的海赛阵, 记为H(X),即H(X) af(Xo ax ax nXn 02f(X)8f(X) 2 0f(X0) f(X ax 2

http://www.tju.edu.cn 第一章 非线性规划 ★海塞阵 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 XX n fX X f X HX HX x x fX fX x xx fX fX xx x × ∂ ∂ ∂ ∂ ∂ ∂ ∂∂ ∂ ∂ ∂∂ ∂ ⎛ ⎞ ⎜ ⎟ … ⎜ ⎟ = ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎝ ⎠ #%# " 若 在 的邻域内有连续二阶偏导数，则称 在 点对 个变元两两组合的二阶偏导数组成的矩阵为 在 的海赛阵， 记为 ，即 =