Large-Scale Binary Quadratic Optimization Using Semidefinite Relaxation and Applications.

Area of Science:

• Computer Vision
• Optimization
• Mathematical Programming

Background:

• Many computer vision problems are formulated as binary quadratic programs (BQPs).
• BQPs are NP-hard, necessitating relaxation techniques for large-scale practical applications.
• Standard semidefinite programming (SDP) relaxation provides tight bounds but suffers from high computational complexity.

Purpose of the Study:

• To develop a more efficient and scalable SDP formulation for BQPs.
• To present a dual optimization approach that significantly improves computational efficiency.
• To introduce novel solvers for the simplified dual problem.

Main Methods:

• A novel semidefinite programming (SDP) formulation for binary quadratic programs (BQPs).
• Development of a more efficient and scalable dual optimization approach compared to conventional SDP.
• Implementation and evaluation of quasi-Newton and smoothing Newton solvers for the dual problem.

Main Results:

• The proposed SDP formulation yields bounds comparable to standard SDP.
• The dual optimization approach is considerably more efficient and scalable.
• Both quasi-Newton and smoothing Newton solvers outperform standard interior-point methods.
• Smoothing Newton is faster for dense/medium problems; quasi-Newton is better for large sparse/structured problems.

Conclusions:

• The novel SDP formulation offers an efficient and scalable method for solving BQPs in computer vision.
• The proposed solvers provide significant computational advantages over existing methods.
• The choice of solver depends on the specific problem characteristics (size, density, structure).