深圳大学管理学院：《运筹学与最优化方法》课程教学资源（PPT课件讲稿）第2章 基本概念和基本理论

第二章 基本概念 基本理论

第 二 章 基本概念 和 基本理论

2.0、预备知识 1、向量和子空向投影定理 (1)n维欧氏空间:R 点(向量):xeB,x=(x,x2,…,x) 分量x;∈R(实数集) 方向(自由向量):d∈R,d≠0 d=(l1,d2,…,)表示从0指向d的方向 实用中,常用x+Md表示从x点出发沿d方向 动Ad长度得到的点 d x+(12d

2.0、预备知识 1、向量和子空间投影定理 (1) n维欧氏空间：R n 点（向量）：x  R n , x = (x1 ,x2 ,…,xn) T 分量 xi  R (实数集) 方向（自由向量）：d  R n , d  0 d =(d1 ,d2 ,…,dn) T 表示从0指向d 的方向 实用中，常用 x + d 表示从x 点出发沿d 方向移 动d 长度得到的点 d 0 x x+(1/2)d

20、预备知识(续) 1、向量和子空间投影定理 (2)向量运算:x,y∈R x,y的内积 1=2x出=x+x22+…+xny x,y的距离:xyl=(xy)(xy)2) x的长度 Lx=lxx (1/2) 三角不等式:x+y+yl 点列的收敛:设点列{x6)}cR,x∈R 点列{x6)}收敛到x,记 x=x台mx1=0=x

2.0、预备知识（续） 1、向量和子空间投影定理 (2) 向量运算：x , y  R n n x , y 的内积：x Ty =  xiyi = x1y1+ x2y2+ …+ xnyn i =1 x , y 的距离： ‖x-y ‖= [(x-y) T(x-y)](1/2) x 的长度： ‖x‖= [ x Tx ] (1/2) 三角不等式： ‖x + y ‖≤‖x‖＋‖y‖ 点列的收敛：设点列｛x (k)｝ R n , x R n 点列｛x (k)｝收敛到 x ，记 lim x (k) = x  lim‖x (k) - x‖ = 0  lim xi (k) = xi ,i k→ k→ k→ x+y y x

20、预备知识(续) 1、向量和子空间投影定理 (3)子空间:设d,d(),…,.d(m)∈,d()≠0 记(d(0,d),:1m)={x=2ad0|a∈R 为由向量d),d2),…,dm生成的子空间,简记为L。 ●正交子空间:设L为的子空间,其正交子空间为 L={x∈P|xy=0,抄yeL} 子空间投影定理:设L为R的子空间。那么 唯一x∈L,y∈L,使z=x+y,且x为问题 min z-ull t.ul∈L 的唯一解,最优值为y 特别,L=时,正交子空间L={0}(零空间)

2.0、预备知识（续） 1、向量和子空间投影定理 (3) 子空间：设 d (1) , d (2) , … , d (m)  R n , d (k)  0 m 记 L( d (1) , d (2) , … , d (m) )={ x =  j d (j) jR } j =1 为由向量d (1) , d (2) , … , d (m) 生成的子空间，简记为L。 ⚫ 正交子空间：设 L 为R n 的子空间，其正交子空间为 L ⊥ ＝{ x  R n x Ty=0 ,  y L } ⚫ 子空间投影定理：设 L 为R n 的子空间。那么 x R n ，  唯一 x L , y L ⊥ , 使 z=x+y , 且 x 为问题 min ‖z - u‖ s.t. u  L 的唯一解，最优值为‖y‖。 ⚫ 特别， L ＝R n 时，正交子空间 L ⊥ ＝{ 0 }（零空间）

20、预备知识(续) 规定:x,y∈R,xsy分x≤y,i类 似规定x≥y,x=y,xy 一个有用的定理 设x∈,c∈R,D为的线性子空间, (1)若xy≤a,Vy∈R且y≥0, 则x≤0,a≥0. (2)若xy≤a,vy∈LgR, 则x∈L,a≥0.(特别,L=时x=0) 定理的其他形式: “著若xy≤a,Vy∈m且y≤0,则x≥0,a≥0 “若xy≥a,Vy∈n且y≥0,则x≥0,a≤0” 若xy≥a,Vy∈R且y≤0,则x≤0,a≤0 若xy≥a,Vy∈Lgr2,则x∈l,a≤0

2.0、预备知识（续） ⚫ 规定：x , y  R n ，x ≤ y  xi ≤ yi ，i 类 似规定 x ≥ y，x = y，x y . ⚫ 一个有用的定理 设 xR n ，R，L为R n 的线性子空间， (1)若 x Ty ≤  ,  yR n 且 y ≥ 0， 则 x ≤ 0， ≥ 0 . (2)若 x Ty ≤  ,  y  L  R n ， 则 x  L ⊥ ， ≥ 0 .(特别, L＝R n 时,x =0) ⚫ 定理的其他形式： “若 x Ty ≤  ,  yR n 且 y ≤ 0，则 x ≥ 0， ≥ 0 .” “若 x Ty ≥  ,  yR n 且 y ≥ 0，则 x ≥ 0， ≤ 0 .” “若 x Ty ≥  ,  yR n 且 y ≤ 0，则 x ≤ 0， ≤ 0 .” “若 x Ty ≥  ,  y  L  R n ， 则 x  L ⊥ ，≤ 0

20、预备知识(续) 2、多元函数及其导数 (1)m元函数:∫(x):R→R 线性函数:f()=c1x+b=2+b 二次函数:f(x)=(1/2)xTQx+cx 12)212a1x1x+E 向量值线性函数:F(x)=Ax+d∈m 其中A为m矩阵,m雄维向量 F(x)=(f(x0,f2(x) x 记a为4的第行向量,fx)=a1x

2.0、预备知识（续） 2、多元函数及其导数 (1) n元函数：f (x): R n → R 线性函数：f (x) = cTx + b =  ci xi + b 二次函数：f (x) = (1/2) xTQx + cTx + b = (1/2)i j aij xi xj +  ci xi + b 向量值线性函数：F(x) = Ax + d  R m 其中 A为 mn矩阵，d为m维向量 F(x)=( f1 (x), f2 (x), … , fm(x) ) T 记 ai T为A的第i行向量，fi (x) = ai Tx

20、预备知识(续) 2、多元函数及其导数 (2)梯度(一阶偏导数向量) vfG=(af/axr, af/0x2, .,af/Bxn)ER 线性函数:f(x)=cx+b,Vf(x) 二次函数:∫(x)=(1/2)xTQx+cx+b Vf(=ox+c 向量值线性函数:Fx)=Ax+d∈m OF/Ox=AT

2.0、预备知识（续） 2、多元函数及其导数 (2) 梯度（一阶偏导数向量）： f (x)＝( f / x1 ,  f / x2 , … ,  f / xn ) T R n . 线性函数：f (x) = cTx + b , f (x) = c 二次函数：f (x) = (1/2) xTQx + cTx + b  f (x) = Qx + c 向量值线性函数：F(x) = Ax + d  R m  F /  x = AT

20、预备知识(续) 2、多元函数及其导数 (3) Hesse阵(二阶偏导数矩阵) of/,2 af/a f/anaI Vf(x)=of/a, d, f/a? o/an,a olf/aan of/a, ar 线性函数:f(x)=c"x+b,V/(x)=0 二次函数:f(x)=12)xx+cx+b,V(x)

2.0、预备知识（续） 2、多元函数及其导数 (3) Hesse 阵（二阶偏导数矩阵）：  2 f /x1 2  2 f /x2 x1 …  2 f /xn x1  2 f (x)=  2 f /x1 x2  2 f /x2 2 …  2 f /xn x2 … … … …  2 f /x1 xn  2 f /x2 xn …  2 f /xn 2 线性函数：f (x) = cTx + b ,  2 f (x) = 0 二次函数：f (x) = (1/2) xTQx + cTx + b,  2 f (x)=Q

20、预备知识(续) 2、多元函数及其导数 (4)m元函数的 Taylor展开式及中值公式 设∫(x):R→R,二阶可导。在x*的邻内 ●一阶 Taylor展开式 fe-f(x)+ vf(r(x-x)+olkx-x" 二阶 Taylor展开式: f()=f()+ vf(x(x-x)+(/2)(x-x) Vf(x(x-x 0L/2 一阶中值公式:对xλ∈(0,1),使 f(r)=f( +[ Vf(x*+l(x-x )I(x-x%) ● Lagrange 余项:对x,3H∈(O,1),记=x*(xx f()=f(x+V/(y(xx)+(12)(xy)v2r=xy

2.0、预备知识（续） 2、多元函数及其导数 (4)n元函数的Taylor展开式及中值公式： 设 f (x): R n → R ，二阶可导。在x* 的邻域内 ⚫ 一阶Taylor展开式： f (x) = f (x*)+ f T (x*)(x-x*) + o‖x-x*‖ ⚫ 二阶Taylor展开式： f (x) = f (x*)+ f T (x)(x-x*) + (1/2)(x-x*)T  2 f (x*)(x-x*) + o‖x-x*‖ 2 ⚫ 一阶中值公式：对x,   (), 使 f (x) = f (x*)+ ［f (x*+(x-x*))] T (x-x*) ⚫ Lagrange余项：对x,   (), 记x =x*+ (x-x*) f (x) = f (x*)+ f T (x)(x-x*) + (1/2)(x-x*)T  2 f (x )(x-x*)

2.1数学规划模型的一般形式 in f(a) 目标函数 (S) st.x∈S 约束集合,可行集 其中,SsR',f:s→R,x∈S称(∫S)的可行解 最优解:x*∈S,满足f(x)≤∫(x),Vx∈S则称 x为(S)的全局最优解(最优解), 记gop.( global optimum,简记opt ●最优值:x为(fS)的最优解,则称f*=f(x)为 S)的最优值(最优目标函数值)

2.1 数学规划模型的一般形式 min f(x) --------目标函数 s.t. xS --------约束集合，可行集 其中，S  R n ，f :S → R，xS称（f S )的可行解 ⚫ 最优解: x*S，满足f (x*)≤ f (x),  xS。则称 x*为(f S)的全局最优解(最优解), 记 g.opt.(global optimum),简记 opt. ⚫ 最优值: x*为(f S)的最优解, 则称 f * = f (x*) 为 (f S)的最优值(最优目标函数值) ( f S )