现代优化方法现代优化方法 (4).pdf

《现代优化方法现代优化方法 (4).pdf》由会员分享，可在线阅读，更多相关《现代优化方法现代优化方法 (4).pdf（13页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、9.6 Augmented Lagrangian Method forSVMQingna Li(BIT)9.6 Augmented Lagrangian Method for SVM1/13IntroductionAugmented Lagrangian Method for L1-loss SVCNumerical ResultsConclusionsQingna Li(BIT)9.6 Augmented Lagrangian Method for SVM2/13SVC and SVR(a)support vector classification(b)support vector regr

2、essionQingna Li(BIT)9.6 Augmented Lagrangian Method for SVM3/13L1-Loss SVCRecallminIRn,bIR122+Cli=1max(1 yi(Txi+b),0).By setting xTi xTi,1,T T,bThe L1-Loss SVC without bias term isminRn122+Cmi=1max(1 yi(Txi),0).(1.1)It can be written asminwRn12w2+Cmax(0,Bw+d)1(1.2)Qingna Li(BIT)9.6 Augmented Lagrang

3、ian Method for SVM4/13Augmented Lagrangian Method(ALM)By introducing s Rm,there isminwRn,sRm12w2+p(s)s.t.s=Bw+d,(1.3)where p(s)=Cmax(0,s)1.The augmented Lagrangian function isL(w,s;)=12w2+p(s),s Bw d+2s Bw d2,(1.4)Qingna Li(BIT)9.6 Augmented Lagrangian Method for SVM5/13Augmented Lagrangian Method(A

4、LM)Solve(wk+1,sk+1)=argminw,sLk(w,s;k).(1.5)k+1=k k(sk+1 Bwk+1 d),and k+1 k.Qingna Li(BIT)9.6 Augmented Lagrangian Method for SVM6/13Key Points:(Q1)How to solve the subproblem?(wk+1,sk+1)=argminw,sLk(w,s;k).(Q2)Global convergence and local convergence ratefor ALM?Qingna Li(BIT)9.6 Augmented Lagrangi

5、an Method for SVM7/13Moreau-Yosida RegularizationLet X be a real finite dimensional Euclidean space withan inner product,and its induced norm .Let q:X (,+)be a closed convex function.The Moreau-Yosida regularization of q at x X isdefined byq(x):=minyX12y x2+q(y).(1.6)The unique solution of(1.6),deno

6、ted as Proxq(x),iscalled the proximal point of x associated with q.Qingna Li(BIT)9.6 Augmented Lagrangian Method for SVM8/13PropositionLet q:X (,+)be a closed convex function,()be the Moreau-Yosida regularization of q and Proxq()be the associated proximal point mapping.Then q()iscontinuously differe

7、ntiable,and there isq(x)=x Proxq(x).Qingna Li(BIT)9.6 Augmented Lagrangian Method for SVM9/13The SubproblemRecall the subproblem(wk+1,sk+1)=argminw,sLk(w,s;k).Denote(w):=minsL(w,s;)=12w2122+mins12s z(w)2+1p(s)=12w2122+p(z(w),where z(w)=Bw+d+.By the property of Moreau decomposition,there is(w)=w+p(z(

8、w)=w+BT BT(s(w)Bw d).Qingna Li(BIT)9.6 Augmented Lagrangian Method for SVM10/13Therefore,we can get(w,s)byw=argminw(w),(1.7)s=s(w)=Prox1/p(z(w).(1.8)Solving(1.7)is equivalent to solve(w)=0.Qingna Li(BIT)9.6 Augmented Lagrangian Method for SVM11/13Q1:Semismooth Newtons Method forthe SubproblemSolving

9、(w)=w+p(z(w)=w+BT BT(s(w)Bw d)=0by semismooth Newtons method.Key Points:(Q1-1)Proximal Mapping Proxp()(Q1-2)Generalized Jacobian of(w)(Q1-3)How to reduce computational cost?Qingna Li(BIT)9.6 Augmented Lagrangian Method for SVM12/13SummaryAugmented Lagrangian Method for L1-Loss SVCMoreau-Yosida RegularizationQingna Li(BIT)9.6 Augmented Lagrangian Method for SVM13/13