张强 - 优化中的分支定界方法及其在 计算机视觉中的应用

《张强 - 优化中的分支定界方法及其在 计算机视觉中的应用》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、优化中的分支定界方法及其在计算机视觉中的应用张强2009.10.20主要内容1.回顾——凸函数与非凸函数2.优化中的分支定界方法3.分支定界方法在计算机视觉的应用凸函数与非凸函数fn函数：RR→为凸函数(convexfunction)，如果其定义域为凸集，并且∀xy,d∈omf，01≤θ≤，有f((θxy+1)−≤+θθ)(fxf)(1)−θ(y)B.StephenandV.Lieven.ConvexOptimization.CambridgeUniversityPress,2004.凸函数与非凸函

2、数非凸函数：函数：fRRn→为拟凸函数(quasiconvex‐function)，如果其定义域及所有的子集Sx={∈≤dom

3、()ffxα,α∈R}α为凸。凸函数与非凸函数非凸函数：优化中的分支定界方法分支定界(branchandbound)方法是解决非凸优化全局极值的一种启发式方法。该方法利用目标函数的上界或者下界对可行集进行删减，并最终在一定精度上达到全局极小值。这种方法相当于在整个可行集上逐点进行枚举，但由于在搜索过程中不断更改可行集，所以其运算速度大大高于一般搜索方法。B.Kolmanan

4、dR.Beck.ElementaryLinearProgrammingwithApplications(internationaledition).AcademicPress,1980.F.Kahl,S.Agarwal,andetal.PracticalGlobalOptimizationforMultiviewGeometry.IJCV,79:271‐284,2008.优化中的分支定界方法例：一个3变量的0，1优化问题右图中根节点(rootnode)为整个可行集，而其他节点为根节点的子节点表示子可

5、行集，连接节点之的线称为分支(branch)，从节点1到节点k的一系列分支组成一条通路(path)，被未检查到的节点称为隐式枚举的(implicitlyenumerated)节点，反之称为显示枚举的(explicitlyenumerated)节点。隐式枚举节点的顶端节点称为终止节点(terminalnode)。优化中的分支定界方法一般的搜索方法在整个可行集中进行逐点枚举。相比之下，分支定界方法能够利用一些条件进行自顶向下的枚举，在这个过程中不符合条件的节点成为终止节点，从而使得隐式枚举节点不用显式的

6、被检查，大大加快了计算速度。优化中的分支定界方法例：一个连续函数优化问题的分支定界方法min()Φxst.l≤x≤u优化中的分支定界方法步骤1*给定初始最优估计值Φ()x，及终止条件。ε对Φ()x做凸松弛，计算出松弛函数在整个可行集Q上的最小值Φ()x′，如果Φ()xx′′−Φ()≤ε，则终止，lblb输出最佳值xx=′，否则继续迭代；opt优化中的分支定界方法步骤2将可行集分为k个子集，计算每个子集上松弛函Qi*数的最小值Φlb()xi′。定义xx1=Φargmin{}qk()i′，如ii=1*果

7、Φ()mxx11−Φin≤ik≤lb()i′≤ε，则停止迭代，输出结*果；x1优化中的分支定界方法步骤3*如果第个子集，jΦlb()()0xx′j−Φ>，则排除该子集，反之留下该子集。**如果存在Φ−()()0xx′jΦ<，则xx=′j。重复步骤2。优化中的分支定界方法分支定界方法的收敛条件：1.可行集为闭的紧集，以确保具有全局极值；2.当可行集的边界Qlu,，lu−趋近于0时，**Φ()xx−Φlb()亦趋近于0。分支定界方法在计算机视觉的应用问题描述重投影残差TT⎛⎞pXpX12ru=−⎜⎟,v

8、−TTpXpX⎝⎠33TT其中摄像机矩阵Pppp=[123,,]，图像坐标(uv,)，空间点齐次坐标。X分支定界方法在计算机视觉的应用对于计算重建问题，其目标函数可以表示为N2∑ri2i=1其形式为Nfx()imin∑subjecttoxD∈xgx()i=1i该优化不是一个凸优化问题。分支定界方法在计算机视觉的应用将上述进一步代换得到Ntimin∑xts,,si=1istfx.()≤tgx,()≥siiiixDtsQ∈∈,(,)0其可行集为凸集。为一个Q02p维空间[lu,][×LL×××lu,][

9、LU,][×LU,]11ppp11p。分支定界方法在计算机视觉的应用定界(Bounding)寻找合适的松弛方法对非凸函数进行松弛。生成的松弛函数应具有如下特点：1.便于计算；2.可以得到较紧的下界；3.易于最小化。分支定界方法在计算机视觉的应用分数函数tstlusLU/,[,],[,]∈∈的松弛函数为⎡⎤tconvenv=minr⎢⎥⎣⎦srrs,,′′strrs.,,′′∈R,2λl≤+′′rs,rs′′−2(1−λ)u≤−+−′′rrss,rrss−−+′′λλL