《最优化方法》课程复习考试.doc.pdf
《《最优化方法》课程复习考试.doc.pdf》由会员分享,可在线阅读,更多相关《《最优化方法》课程复习考试.doc.pdf(54页珍藏版)》请在三一文库上搜索。
1、最优化方法复习提要 第一章最优化问题与数学预备知识 1.1模型 无约束最优化问题min /(x), x =(旺, 兀2,心)w R“? A 约束最优化问题疋简(兀)0,心1,2,?, 加也(兀) =0,丿=1,2,?,“ )min /(x); s.t. gQ)nO,i = l,2,,加, hj (x) = 0,j = ,2,?,l ? 其中.f(X)称为目标函数, 西, 兀2, ,暫称为 决策变量,S称为可行域, gQ) no(心1,2, ,加), 勺(兀) = 0。= 1,2,丿)称为约束条件. 1. 2多元函数的梯度、Hesse矩阵及Tayloi?公式 定义设f:R “TR,JR“?如果维
2、向量,VAre R n, 有 + Ax) -f(x) = p T x + 0(|Ax|)? 则称/(x)在点元处町微,并称df(x) = p Tx 为/(x)在点元处的微分 . 如果/(X)在点元处对丁 =(兀“2,?,)丁的各分量的偏导数 。/( 元) d x i 都存在,则称 / (兀)在点元处一阶可导,并称向量 为/ (兀)在点元处一阶导数或梯度. 定理1设f :R nR,xeRn?如果 / (兀)在点元处可微 , 则/ (兀)在点元处梯度 V/(x)存在,并且有#(x) = W) 7Ar . 定义 设f:R“TR,JR “?d是给定的n维非零向量,e = 2 ?如杲d min /( 兀
3、) ;即 v S.t. XG S. V/(x)=( df(x) T 。/(可。/(元) Um/a + 2e)-V(x) 久 TO 2 存在,则称此极限为/(x)在点元沿方向d的方向导数,记作冬学. da 定理2设f :R nR,xeRn. 如果/ (兀)在点元处可微 , 则/ (兀)在点元处沿任何 非零方向d的方向导数存在,且= VA元)。 , 其中丘 =厶? da a 定义 设/ (兀)是 /?“ 上的连续函数,xeR n. d是维非零向量 . 如果30, 使得V2w(O0),有/(x + 2J)()/(x).则称d为f(兀)在点元处的下降 (上 升) 方向. 定理3设f:R nR.xeRn
4、 ,且/(兀)在点元处可微 , 如果日非零向量de R n 9 使得Vf(x) T d() 0,则d是/ (兀)在点元处的下降(上升)方向. 定义 设f:R ”TR,HeR ”?如果/ (兀)在点元处对丁自变量x = (xpx2,-,x/J) 7的 各分量的二阶偏导数単匕丿?=1,2, , )都存在,则称函数 / (兀)在点元处二阶U Xj 可导,并称矩阵 为/(x)在点元处的二阶导数矩阵或Hesse矩阵. 定义 设h:R“记/1(兀)=(肉(兀) , 爲(兀) , ?, 饥(兀) 7, 如果 勺? (x) (i = 1,2, ,加)在点元处对于自变量x =(兀 , 吃, )丁的各分量的偏导
5、数 d 2x 扌/ (元) dxdx2 巧 ( 元) d 2f(x) 3 x2d ? d 2x 2 ? d xd x n L n ? ? d 2f(x) 97() ? ? d 2f(x) d x nd X d x nd x2 d 2f(x) V 2/(x) 丿 号(i = 1,2, ,加;J = 1,2,加dxf 都存在,则称向量函数加对在点元处是一阶可导的,并且称矩阵 为/?(%)在点x处的一阶导数矩阵或Jacobi矩阵, 例2 设aw R“,xw R“,bw R ,求f (x) = a Tx-h 在任意点兀处的梯度和Hesse 矩阵. 解 设 0 =(绚卫2,?, )/, 兀=(旺, 兀2
6、,?,),则/ (兀) =工绞母+b , k= 因。 =畋伙=1,2,? ,川),故得V/(x)二a? 无 乂因理半=0(门=1,2,加,则V 2/W = 0? d xfl x j 例3 设Qe R ,xt, 是对称矩阵,heRceR,称fM = x TQxhT x-c为二 次函数,求 / (劝在 任意点兀处的梯度和Hesse矩阵. 解 设Q = (qJwX =(呂,兀2, ,xjT,b = (b,b2, ,b$ ,贝lj 、J、J、 / (西, 尢 2,?,)二牙工工如巧+工仪母 +0, 匕 /=1 ;=1 *=1 再对¥(兀 )x +q (/= 1,2,?,?)求偏导得到?弓 X)=q(i
7、,j = ,2,加, 于 dxt肯dX/dXj d h (x) a h(元) 曲(元) dXdx2 dX n d人(x)独(元)沁(元) dx 乙 ? ? ? ? 巩(元) dhm(x) ? ? dh m(x) 9% dx2 dX n ) % 肿(元) = 简记为V/7(X). 从而V/*(x)= /(x) 工 qZj WjXj ;=1 =Qx + b ? 是 q 、 务 v7(x)= % 】 %2 Qin ? ? ? =Q 41 绻 2 Clnn ) 例4 设 (/ )= /(兀 + 力),其屮/:/? t/? 二阶可导,xwR“,dwR “,TwR, 试求0(/), (pt )? 解 由多
8、元复合函数微分法知(pt ) = V/(+d,(pt ) = d T2fx + td )d?定理4 设f:RJR, XG R n, 且/(x)在点x的某邻域内具有二阶连续偏导数,则/(%)在点元处冇 Taylor展式 fix + Ar) = /(%) + V/(x/Ar + - Ax TV2f (x + 如)心 ,(0 v s,t. h.(x) = 0, / = 1,2,,/ 解Lagrange 函数为L(x, v) = 4- x; - v(x lx2 - 8),则VLx, v) = 2x2 - vx, 一( 西兀2 一 ?丿 从而得厶 ( 兀,v)的| 人稳点(V8,A/8,2)7和(- 旋
9、2) ,对应有 x = (V8,V8) r,v = 2 和元=(-V8,-V8) r, v = 2 . 因此 M(X) = (Z1,Z2) / |(Z1,Z2)V/?(X) = 0 = (zI,z2)rz x2 + z2xl =0 = (z1,z2)r|z1=-z2. 并且fze M(元),zH0,有zrV(元,V)z = 2z; 4z】z? + 2z; = 8zj 0 . 利用定理2,所得的两个可行点X = (V8,A/8/和“(- 忌,- 旋r都是问题的严格局部极小点 . 2.3不等式约束最优化问题的最优性条件 定义SRxeclS,de RdQ,若曰力 0,使得,元 + S,X/Qw (0
10、,5), 则称为集合S在点元处的可行方向?这里c/5 = x|xe /?“,SnNd(QH0,/O? 令 “ |“0,财0,使 + 庇S,VAG(0,), 的严格局部极小点 . 例1试用最优性条件求解 min /(x)=彳 + 兀; s.t. /?(x) = x yx2 - 8 = 0. 由于V;X(x,v)= _ 一2 2 丿1-2 2 2 ,V/i(x) = (-1、ux 了 0、 11 了 0、 厂 0、 、。, 一 1 0, ie / (% ) ? 眾理3设元是问题(1)的可行点, / (劝和gQ)(iw/(元)在点元处可微, g心)(询 / (功在点元处连续,若元是问题(1)的局部极
11、小点,则存在不全为0 的非负数如 “?(沱/ (元),使 u(yf(x)- 为M/Vg,(元) =0 ?(元称为Fritz John 点) fe/ (T) 如果g/(Q(注/ (无)在点元处也可微,则存在不全为0的非负数如,岡,心,使 0. /A ( Q、(0、 解 因为W)= n ,Vg,(x)= ,v2(x)=, 且/(元)= 1,2, 、。丿 丿 (1) 成立,只有如=0才行. 取 uQ=O,ui=u 2=a 0 即可,因此无是 Fritz John 点. 定理4设元是问题(1)的可行点, / 和g,.(x)(ZG /(%)在点元处可微, g? )(注/(元)在点元处连续,并且Vgz.(
12、x) (zeZ(J)线性无关 . 若元是问题 (1) 的局部极小点,则存在WZ0(ZG/(X),使得 V/(x)-工乞Vg,( 元)=0 ? feZ(x) m Yf (元) -工均(元) = 0, /=! 色g(元) =,= 1,2,?,加. min /(x) = (x, 一I) 2 + x2; 例2 求最优化问题s.t. g1(x) = -xI-x2+20,的K?T点. g2(x) = x 20 2(x - in ( 解 因为V/(x)= 1 ,Vg(x)= , Vg9(x)= , 所以K?T条件为 I1丿1一1丿“U丿 2(X| -1) + W = 0, 1 + Wj _ “2 = 0,
13、v 比(X 兀? + 2) = 0, u2x2 = 0, u 0, u2 0. 则=-1 ,这与U 矛盾?故弘2 0,从而兀2 = ; 若-%, +2 = 0,贝ij 比=-2 ,这与Wj 0 矛盾 . ?故u = 0 ,从而w2 = 1, Xj = 1 ; 由于玛 no,血no,且元=(1,0)丁为问题的可行点 , 因此元是K?T点. 定理5设在问题(1)中,/(兀)和 -g,(兀)(心1,2,?, 加)是凸函数,元是可行点, 并且/和 0,ZG I(X), Wo = rf|V/?7(x) TJ = O,j = l,2,.,Z ? 定理2设元为问题(1)的可行点,/( 劝和g,.(%) (Z
14、GZ(X)在点无处可微, 包(兀)(./? = 1,2, 在点元处具有一阶连续偏导数,g?)(注/( 元) 在点元处连 续. 若元为问题(1)的局部极小点, 则存在不全为0的数如“ (沱/( 元) 和 vy(j = l,2,.,/),且Wo,W/O(ze/(x),使 w0V/(x) - 工色 ?( )- 工v7V/?.(x) = 0 ? /e/(T) ;=1 Vj (j = 1,2,?,/) ,?, 使 / “oVA 元)- X 坷Vgj (元)-X YjPhj ( 元)=0, /=1 j=l uigi(x) = 0,i = l,2, ,九 ( 元称为Fritz John点) 若gf(x) (
15、zV /(元) 在点x处也可微 , 则存在不全为0的数如必Q = 1,2, ,加) 和 ( 元称为Fritz John点) min f(x) = %,2 +x;; 例1 设M 51(%)= X,3 “ X2 “ 0, 试判断x = (l,O) r 是否为Fritz John . g2(x) = x2 0, h(x) = -(x, -1) 2 + x2 = 0. 取w0 =0,?2 =1, v = -l,即知元是Fritz John 点. 定理3设元为问题(1)的可行点, /( 劝和gz.(%) (ZGZ(X)在点无处可微,hj(Q (./ = 1,2,?,/) 在点x处具有一阶连续偏导数,g,
16、(x)( 氓/( 元) 在点% 处连续 , 且向量组Vgz(x) (/G Z(x), V/7.(x) (j = 1,2, ? ? ? ,/)线性无关 . 若元是问题(1)的局 部极小点,贝I存在数W/ 0(/?/(%) 和? (.) = 1,2, J),使 Y/(元) 一工ug( 元)一2 吓叫(x) = 0. ( 元称为K?T点) iel(x)y=l 如果g,( 兀)( 渥/( 元) 在点元处也可微,则存在数u. no(j = i,2, ,加) 和 vy. (; = 1,2,.,/),使 “ JI I V/X) - 工乞 ( 元)- 工v$hj (x) = 0, S /=! ;=1 乞 例2
17、 求解最优化问题0, /?(%) = 2x( 4- x2 - 3 0. 解 广义Lagrange函数为 r co L(x.u.v) = f(x)-ug(x) - vhx) = (x, -3)“ +(x2 -1) -u(-x +x2)-1(2 + x2 - 3). MyldL(x,u.v)_ dL(x,u,v)_ 内为 - =2(%| 3) + 2uX 2v , - = 2(X9 U V . 3x, dx2 所以K?T条件及约束条件为 2(兀 一3) + 2ux - 2v = 0, 2(兀2 1)比一u = 0, w(-% 2 + x 2) = 0, V + 卷0? 2壬 + 工2 - 3 二0
18、, w 0. 下而分两种情况讨论. (1)设弘=0,则有 2(壬3) 2v 0, 0,则有 2(兀一3) + 2ux - 2v = 0, 2( x2 1) 一况一u = 0, 一石+花=0, 2xj + 兀2 - 3 = 0? 由止匕可得一兀;一2兀+3 = 0 ,需军得兀 | = 1或兀| = 3。从血兀2=1或兀2=9?1? 是= 1 或u = -ll ( 这与” 0矛盾 ).v = -l或v = 27?由此可知元 = (1,1)丁是问题的K? T 点,但元 =(-3,9卩不是问题的K?T点. 易见,畑是F上的凸函数,g(兀) 是F上的凹函数,力 ( 兀) 是线性函数,因此由定理 4知,x
19、 = (l,l) r 是问题的全局最优解. 従理5设元为问题(1)的可行点,/G),gO)(iw/() 和勺(x)(J = l,2,?,/) 在 点元处具有 二阶连续偏导数,并且存在乘子向量历=(可, 历2, ,瓦y?0和 =(耳, ,,n 0使K?T 条件成立 , 即 fVxL(x,w,v) = 0, u Tg(x) = 0. 若对于任何满足 z T V gi.(x)0jG /(X)且瓦=0, 0, zW勺(元) = 0, ) = 1,2,?J 的向量ZH0,都有z TVl,L(x 9u,v)z09贝吹是问题 (1)的严格局部极小点 . ?c min/(x) =工丄; Z=1 xi 例3 求
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 最优化方法 优化 方法 课程 复习 考试 doc
链接地址:https://www.31doc.com/p-5622185.html