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

Xuewen Mu | Zendy; SANYANG LID | Zendy; Yaling Zhang | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

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

Author(s) -

Xuewen Mu,

SANYANG LID,

Yaling Zhang

Publication year - 2005

Publication title -

bulletin of the korean mathematical society

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.295

H-Index - 27

eISSN - 2234-3016

pISSN - 1015-8634

DOI - 10.4134/bkms.2005.42.4.837

Subject(s) - quadratic programming , mathematics , binary number , semidefinite programming , quadratically constrained quadratic program , quadratic equation , relaxation (psychology) , convergence (economics) , sequential quadratic programming , algorithm , second order cone programming , mathematical optimization , convex optimization , psychology , social psychology , geometry , arithmetic , regular polygon , economics , economic growth

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

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research