《现代优化方法现代优化方法 (9).pdf》由会员分享，可在线阅读，更多相关《现代优化方法现代优化方法 (9).pdf（16页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、9.5 Quadratic Penalty Method forHypergraph Matching:IIQingna Li(BIT)9.5 Quadratic Penalty Method for Hypergraph Matching:II1/16Recall the hypergraph matching:minxRnf(x):=l,j,kAljkxlxjxk=16Ax3s.t.eT xi=1,i=1,.,n1,x 0,1,(1.1)where n=n1n2,A IRnnn.Qingna Li(BIT)9.5 Quadratic Penalty Method for Hypergrap
2、h Matching:II2/16Sparse FormulationOne equivalent reformulation isminxRnf(x)s.t.eT xi=1,i=1,.,n1,x 0,x0 n1.x0 the number of nonzero elements in xDeal with sparse constraint directly:hard-thresholding type based algorithms:Beck et al.2012,Pan et al 20170penalty based algorithms:Lu et al 2012lpregular
3、ization algorithms:Chen et al 2017,Jiang etal 2016Qingna Li(BIT)9.5 Quadratic Penalty Method for Hypergraph Matching:II3/16Relaxation ProblemsThe relaxation problem isminxRnf(x)eT xi=1,i=1,.,n1,x 0,(1.2)OrminxRnf(x)s.t.eT xi=1,i=1,.,n1,x 0,1.(1.3)Questions:the relation of the relaxation problem(1.2)
4、and theoriginal problem?Qingna Li(BIT)9.5 Quadratic Penalty Method for Hypergraph Matching:II4/16Main ResultTheorem 1.There exists a global minimizer xof the relaxationproblem(1.2)such that x0=n1.Furthermore,xis a globalminimizer of the original problem(1.1).Alg.1.Generating A Global Minimizer of(1.
5、1)S0.Given y=(yT1,.,yTn1)T Rn,a global minimizer of(1.2).Letx=0 Rn.S1.For i=1,.,n1,find pi=argmaxp(yi)p,and let(xi)pi=1.S2.Output x=(xT1,.,xTn1)T,a global minimizer of(1.1).An example:y1=1/31/25/6 x1=001,or x1=100.y2=010 x2=y2Qingna Li(BIT)9.5 Quadratic Penalty Method for Hypergraph Matching:II5/16Q
6、uadratic Penalty MethodMotivationIdentify the support set of a global minimizer for relaxationproblemQuadratic Penalty Method:minxRnf(x)+2n1i=1(eT xi 1)2s.t.x 0.However,it is not well-defined!minxRn(x):=f(x)+2n1i=1(eT xi 1)2s.t.0 x M,(1.4)where M 1.(1.4)is actually the quadratic penalty problem ofmi
7、nxRnf(x)s.t.eT xi=1,i=1,.,n1,0 x M,which is equivalent to(1.2).Qingna Li(BIT)9.5 Quadratic Penalty Method for Hypergraph Matching:II6/16Quadratic Penalty MethodAlg.2 Quadratic Penalty Method for(1.2)S0.Given an initial point x0 0,set the parameter0 0.Let k:=1.S1.Start from xk1and solve(Pk)to obtain
8、a globalminimizer xk.S2.If the termination rule is satisfied,project xkto itsnearest binary assignment matrix and stop.Otherwise,choose k+1 k,k=k+1,and go to S1.Qingna Li(BIT)9.5 Quadratic Penalty Method for Hypergraph Matching:II7/16Theorem 2.Let xk be generated by Algorithm 2,andlimkk=+.Then any a
9、ccumulation point of thegenerated sequence xk is a global minimizer of(1.2).Qingna Li(BIT)9.5 Quadratic Penalty Method for Hypergraph Matching:II8/16Convergence of Support SetAssumption 1.Let xk be generated by Al.2,andlimkk=+.Let K be a subset of 1,2,.Assume limk,kKxk=z,and z is a global minimizer
10、of(1.2).Case 1Theorem 3 Suppose Assumption 1 hold.If thereexists k0,such that xk0=n1for all k k0,k K.Then there exists k1 k0such that the support set ofz can be correctly identified,i.e.,k=(z),k k1,k K.Furthermore,z must be a global minimizer of(1.1).Here k=l:xkl 0,(z)=l:zl 0.Qingna Li(BIT)9.5 Quadr
11、atic Penalty Method for Hypergraph Matching:II9/16DefineJki=argmaxp(xki)p,pki=minp:p Jki,and Jk:=n1i=1pki+n2(i 1),andJi(z)=argmaxp(zi)p,pi(z)=minp:p Ji(z),J(z):=n1i=1pi(z)+n2(i1).Case 2.Theorem 4.Suppose Assumption 1 hold.(i)If z0=n1,then there exists k0 0,such that for all k k0,k K,there is(z)=Jk.(
12、ii)If z0 n1and|Ji(z)|=1 for all i=1,.,n1,then there exist a globalminimizer xof(1.1)and k0 0,such that for all k k0,k K,there is=Jk.(iii)If z0 n1and|Ji(z)|1 for one i 1,.,n1,then there exist a globalminimizer xof(1.1),a subsequence xkkKand k0 0,such that for allk k0,k K,there is=Jk.Qingna Li(BIT)9.5
13、 Quadratic Penalty Method for Hypergraph Matching:II10/16SubproblemRecall the subproblemminxRn(x):=f(x)+2n1i=1(eT xi 1)2s.t.0 x M,Active set based method:projected gradient method,modified fromBertsekas,D.P.:Projected newton methods foroptimization problems with simple constraints.SIAM J.Control Opt
14、im.20(2),221246(1982)Qingna Li(BIT)9.5 Quadratic Penalty Method for Hypergraph Matching:II11/16Numerical ResultsAlgorithms:QPPG:our quadratic penalty algorithm with projection gradient method assubsolverQPPG2:our method dealing with the case of n1=n2.TM:1RRWHM:2HGM:3BCAGM:4Measurement:Accuracy:denot
15、ing the ratio of successful matching,calculated bynumber of correct identified support indicesnumber of true support indices;Matching Score:calculated by16A(xkB)3,where xkBis the binary assignedmatrix of xkgenerated by Algorithm 1;Running Time:the total CPU time consumed in seconds.Qingna Li(BIT)9.5
16、 Quadratic Penalty Method for Hypergraph Matching:II12/16Test 1:support set k=j:xj 0n1=n2=30Figure:Entries in xkwith k=1,21,39 in QPPG.Qingna Li(BIT)9.5 Quadratic Penalty Method for Hypergraph Matching:II13/16Test 2:Small ProblemsFigure:CMU house matching of different v for n1=20 and n2=30.Figure:Re
17、sult of QPPG for matching two houses v1=0 and v2=60.Qingna Li(BIT)9.5 Quadratic Penalty Method for Hypergraph Matching:II14/16Test 3.Larger Problems:Fish DatasetFigure:Results for matching fish with different dimension n1.Figure:Example of matching fish data using QPPG.Qingna Li(BIT)9.5 Quadratic Pe
18、nalty Method for Hypergraph Matching:II15/16ConclusionsSummaryTightness of relaxation problemQuadratic penalty methodExact recovery in terms of support setCui,C.F.,Li,Q.N.,Qi,L.Q.and Yan,H.:A quadraticpenalty method for hypergraph matching.2018,70(1),237-259Qingna Li(BIT)9.5 Quadratic Penalty Method for Hypergraph Matching:II16/16