본문 바로가기
KERD
논문KCI 등재

A successive quadratic programming algorithm for SDP relaxation of the binary quadratic programing

Yaling Zhang|Sanyang Liu|Xuewen Mu
대한수학회 (The Korean Mathematical Society)|2005.11|대한수학회보 (Bulletin of the KMS)|제42권 제4호|pp. 837-849

0

조회

0

다운로드

1

인용

0

참고문헌

주제분류수학

초록

Abstract

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

참고문헌 (12)

  1. "An application of combinatorial optimization to statiscal optimization and circuit layout design", 36(3), pp.493~513 (1998)
  2. "Eiffcient algorithms for layer assignment problems", (1), pp.67~78 (1987)
  3. "A graph theoretic via minimization algorithm for teo layer printed circuit boards", 30(5), pp.284~299 (1983)
  4. "Improved approximation algorithms for maximum cut and satisfiably problem using semidefinite programming", 42, pp.1115~1145 (1995)
  5. "Solving large scale sprase semidefinite programming for combinatorial optimization", 10(2), pp.443~461 (2000)
  6. "An interior point method for semidefinite programming", 10, pp.842~861 (1990)
  7. "A spectral bundle method for semidefinite programing", 10, pp.673~696 (2000)
  8. "Design and performance of parallel and distributed approximation algorithms for max-cut", 9, pp.141~160 (1998)
  9. "A projected gradient algorithm for solving the max-cut relaxation", 15, pp.175~200 (2001)
  10. "analysis and algorithms with application to optimization control", (nsmooth optimization) (1992)
  11. "Semidefinite programming for combinatorial optimization" (2000)
  12. "Courtant Institute of Mathematical Science" (1997)

관련 논문AI추천

On duality for nonconvex quadratic optimization problems김문희영남수학회 · East Asian Mathematical Journal2011 · 제27권 제5호An active set SQP-filter method for solving nonlinear programmingHui An, Ke Su, Yingna Yuan영남수학회 · East Asian Mathematical Journal2012 · 제28권 제3호ALGORITHMS FOR SYSTEMS OFNONLINEAR VARIATIONAL INEQUALITIESHo Jin Hwang, Nan-jing Huang, Ya-ping Fang, Yeol Je Cho대한수학회 · 대한수학회지2004 · 제41권 제3호Square quadratic proximal method for nonlinear complimentarity problemsAbdellah Bnouhachem, Ali Ou-yassine대한수학회 · 대한수학회논문집2019 · 제34권 제2호On Optimality Theorems for Semidefinite Linear Vector Optimization Problems김문희영남수학회 · East Asian Mathematical Journal2021 · 제37권 제5호A weighted-path following interior-point algorithm for Cartesian P*(k)-LCP over symmetric conesHossein Mansouri, Maryam Zangiabadi, Mohammad Pirhaji대한수학회 · 대한수학회논문집2017 · 제32권 제3호

이 간행물의 다른 논문 (19건)

Approximating common fixed points of asymptotically nonexpansive mappingsHaiyun Zhou, 조열제, 강정임pp. 661-670On derivations in noncommutative semiprime rings and Banach algebras박규홍pp. 671-678A one-sided version of Posner's second theorem on multilinear polynomialsVincenzo De Filippispp. 679-690Asymptotic equivalence between linear differential systems구남집, 최성규, 임동만pp. 691-701On $(\alpha, \beta)$-fuzzy subalgebras of $BCK/BCI$-algebras전영배pp. 703-711
원문 보기