SHERP

SDP의 개관 : 쌍대성, 계산복잡성 및 응용
A Survey : SDP, its Duality, Complexity and Applications

Cited 0 time in webofscience Cited 0 time in scopus
Authors
류춘호; 명영수; 홍성필
Issue Date
2001
Publisher
한국경영과학회 = The Korean Operations Research and Management Science Society
Citation
한국경영과학회지, 제26권, 제2호(2001). pp. 13-46
Keywords
SDP(Semidefinite Programming); combinatorial optimization; SDP duality; interior point method; survey
Abstract
SDP (Semidefinite Programming), as a sort of "cone-LP", optimizes a linear function over the intersectlon of an affine space and a cone that has the origin as its apex. SDP, however, has been developed in the process of searching for better solution methods for NP-hard combinatorial optimization problems. We surveyed the basic theories necessary to understand SDP researches. First, we examined SDP duality, comparing it to LP duality, which is essential for the interior point method. Second, we showed that SDP can be optimized from an interior solution in polynomial time with a desired error limit. Finally, we summarized several research papers that showed SDP can improve solution methods for some combinatorial optimization problems, and explained why SDP has become one of the most important research topics in optimization. We tried to integrate SDP theories, relatively diverse and complicated, to survey research papers with our own perspectives, and thus to help researchers to pursue their SDP researches in depth.
ISSN
1225-1119
Language
Korean
URI
http://uci.or.kr/G300-j12251119.v26n2p13
http://hdl.handle.net/10371/5342
Files in This Item:
Appears in Collections:
College of Engineering/Engineering Practice School (공과대학/대학원)Dept. of Industrial Engineering (산업공학과)Journal Papers (저널논문_산업공학과)
  • mendeley

Items in S-Space are protected by copyright, with all rights reserved, unless otherwise indicated.

Browse