Bulletin of the Korean Mathematical Society

A SUCCESSIVE QUADRATIC PROGRAMMING ALGORITHM FOR SDP RELAXATION OF THE BINARY QUADRATIC PROGRAMMING

Xuewen Mu, SANYANG LID, Yaling Zhang

Published Nov 1, 2005• 0 citations

Abstract

In this paper, we obtain a successive quadratic programming algorithm for solving the semidefinite programming (SDP) relaxation of the binary quadratic programming. Combining with a randomized method of Goemans and Williamson, it provides an efficient approximation for the binary quadratic programming. Furthermore, its convergence result is given. At last, We report some numerical examples to compare our method with the interior-point method on Maxcut problem.

DOI: 10.4134/bkms.2005.42.4.837

Related papers

A Rank-Two Feasible Direction Algorithm for the Binary Quadratic Programming

Xuewen Mu, Yaling Zhang

Based on the semidefinite programming relaxation of the binary quadratic programming, a rank-two feasible direction algorithm is presented. The proposed algorithm restricts the rank of matrix variable to be two in the semidefinite programming relaxation and yields a quadratic objective function with simple quadratic constraints. A feasible direction algorithm is used to solve the nonlinear programming. The convergent analysis and time complexity of the method is given. Coupled with randomized algorithm, a suboptimal solution is obtained for the binary quadratic programming. At last, we report some numerical examples to compare our algorithm with randomized algorithm based on the interior point method and the feasible direction algorithm on max-cut problem. Simulation results have shown that our method is faster than the other two methods.

Journal of Applied MathematicsJan 1, 20131 citation

On Analyzing Semidefinite Programmng Relaxations of Complex Quadratic Optimization Problems

Teofilo F. Gonzalez

Following the seminal work of Goemans and Williamson [1], there has been an outgrowth in the use of semidefinite programming (SDP) for designing approximation algorithms. Recall that anα-approximation algorithm for a problem P is a polynomial-time algorithm such that for every instance I of P , it delivers a solution that is within a factor of α of the optimum value [2]. It is well known that SDPs can be solved in polynomial time (up to any prescribed accuracy) via interior-point algorithms (see, e.g., Refs. [3,4]), and they have been used very successfully in the design of approximation algorithms for a host of NP-hard problems, e.g., graph partitioning, graph coloring, and quadratic optimization [1-9], just to name a few.

Chapman & Hall/CRC eBooksMay 15, 20070 citations

Feasible direction algorithm for solving the SDP relaxations of quadratic {−1, 1} programming problems

Liu Hongwei*, Xinhui Wang, Liu Sanyang

In this article, we propose a feasible direction algorithm for solving the semidefinite programming (SDP) relaxations of quadratic {−1, 1} programming problems. This algorithm's distinguishing features are that it uses a low rank factorization and searches with a constant step-size. Its convergence is also proven. Finally, we report some numerical examples to compare our method with the low rank factorization method of Burer and Monteiro on the SDP relaxation of the max-cut problem. *E-mail: xdliuhongwei@hotmail.com

Optimization methods & softwareApr 1, 200413 citations

Large-Scale Binary Quadratic Optimization Using Semidefinite Relaxation and Applications

Peng Wang, Chunhua Shen, Anton van den Hengel +1 more

In computer vision, many problems can be formulated as binary quadratic programs (BQPs), which are in general NP hard. Finding a solution when the problem is of large size to be of practical interest typically requires relaxation. Semidefinite relaxation usually yields tight bounds, but its computational complexity is high. In this work, we present a semidefinite programming (SDP) formulation for BQPs, with two desirable properties. First, it produces similar bounds to the standard SDP formulation. Second, compared with the conventional SDP formulation, the proposed SDP formulation leads to a considerably more efficient and scalable dual optimization approach. We then propose two solvers, namely, quasi-Newton and smoothing Newton methods, for the simplified dual problem. Both of them are significantly more efficient than standard interior-point methods. Empirically the smoothing Newton solver is faster than the quasi-Newton solver for dense or medium-sized problems, while the quasi-Newton solver is preferable for large sparse/structured problems.

arXiv:1411.7564IEEE Transactions on Pattern Analysis and Machine IntelligenceMar 11, 201659 citations

A Direct SDP Approach for Constrained Quadratic Binary Optimization Problems

MilaNedic, Zvmcevap

This repository contains the source code, computational experiments, analysis, and benchmarks accompanying the paper A Direct SDP-Based Framework for Certified Bounds for Constrained Quadratic Binary Optimization Problems. The repository implements a direct semidefinite programming (SDP) approach for constrained quadratic binary optimization, designed to obtain strong bounds for exact optimization. The SDP relaxation is strengthened using quadratized linear constraints and triangle (hypermetric) inequalities. To address the numerical infeasibility of SDP solutions obtained from numerical solvers such as MOSEK, the framework includes a correction procedure that converts approximate SDP solutions into mathematically certified bounds suitable for use in Branch-and-Bound algorithms. The repository also implements an adaptation of the Goemans–Williamson randomized hyperplane rounding scheme to constrained binary optimization, together with problem-specific feasibility restoration. Computational experiments are provided for the Sparsest k-Subgraph and Maximum Independent Set problems. The work presented in this repository was funded and developed under the QBIQ project (project no. 644), funded by the Slovenian Research and Innovation Agency (ARIS) through the Applied Projects programme. The code and accompanying data are intended to facilitate reproducibility of the computational results and provide a foundation for further research on exact SDP-based methods for constrained quadratic binary optimization.

Aug 25, 20260 citations

A fast semidefinite approach to solving binary quadratic problems

Peng Wang, Chunhua Shen, Anton van den Hengel

Many computer vision problems can be formulated as binary quadratic programs (BQPs). Two classic relaxation methods are widely used for solving BQPs, namely, spec-tral methods and semidefinite programming (SDP), each with their own advantages and disadvantages. Spectral relaxation is simple and easy to implement, but its bound is loose. Semidefinite relaxation has a tighter bound, but its computational complexity is high for large scale prob-lems. We present a new SDP formulation for BQPs, with two desirable properties. First, it has a similar relaxation bound to conventional SDP formulations. Second, com-pared with conventional SDP methods, the new SDP for-mulation leads to a significantly more efficient and scalable dual optimization approach, which has the same degree of complexity as spectral methods. Extensive experiments on various applications including clustering, image segmen-tation, co-segmentation and registration demonstrate the usefulness of our SDP formulation for solving large-scale BQPs. 1.

Jan 1, 201326 citations