Abstract

This paper presents a study on how to numerically solve the feasibil- ity test problem which is the core of the bisection algorithm for minimizing the error functions. We consider a strategy that minimizes the maximum infeasi- bility. The minimization can be performed using several numerical computation methods, among which the barrier method and the primal-dual method are exam- ined. In both of the methods, the inequalities are sequentially approximated by log-barrier functions. An initial feasible solution is found easily by the construc- tion of the feasibility problem, and Newton-style update computes the optimal solution iteratively. When we apply the methods to the problem of estimating the structure and motion, every Newton update requires solving a very large sys- tem of linear equations. We show that the sparse bundle-adjustment technique, previously developed for structure and motion estimation, can be utilized during the Newton update. In the primal-dual interior-point method, in contrast to the barrier method, the sparse structure is all destroyed due to an extra constraint in- troduced for finding an initial solution. However, we show that this problem can be overcome by utilizing the matrix inversion lemma which allows us to exploit the sparsity in the same manner as in the barrier method. We finally show that the sparsity appears in both of the formulations - linear programming and second-order cone programming.