東華大學圖書館 |

Language: English

Help

回圖書館首頁

手機版館藏查詢

Back

Switch To: Labeled | MARC Mode | ISBD

Towards the optimum by semidefinite ...

Povh, Janez, (1973-)

Linked to FindBook

Google Book

Amazon

博客來

Towards the optimum by semidefinite and copositive programming : = new approach to approximate hard optimization problems /

Record Type:	Language materials, printed : Monograph/item
Title/Author:	Towards the optimum by semidefinite and copositive programming :/ Janez Povh.
Reminder of title:	new approach to approximate hard optimization problems /
remainder title:	Towards the optimum by conic programming
Author:	Povh, Janez,
Published:	Saarbrucken :VDM Verlag Dr. Muller, : c2009.,
Description:	124 p. ;23 cm.
Subject:	Combinatorial optimization. -
ISBN:	9783639166545 (pbk.) :

Towards the optimum by semidefinite and copositive programming : = new approach to approximate hard optimization problems /
Povh, Janez,1973-

Towards the optimum by semidefinite and copositive programming :new approach to approximate hard optimization problems /Towards the optimum by conic programmingJanez Povh. - Saarbrucken :VDM Verlag Dr. Muller,c2009. - 124 p. ;23 cm.

Includes bibliographical references (p. 115-122) and index.

In the first part of the book we present beside a survey of standard results from linear algebra and conic programming also a new method to solve semidefinite programs, based on the augmented Lagrangian method. This method which we named Boundary point method goes far beyond the reach of interior point methods when the linear constraints are nearly orthogonal. In the second part we demonstrate an application of semidefinite and copositive programming to the following NP-hard problems from combinatorial optimization: the bandwidth problem, the quadratic assignment problem, the min-cut problem and the general graph partitioning problem. We also give ideas how to extend our approach to some other 0-1 problems, like the stability number problem and the balanced vertex separator problem. We give a study of the approximation algorithm for the bandwidth problem from Blum et al., 2000, with a special focus on computational issues and suggest an effective strategy to solve this algorithm, which is based on the interior point methods. We rewrite the quadratic assignment problem, the min-cut problem and the graph partitioning problem as a copositive program in a lifted space. Using the increasing hierarchy of cones from De Klerk, Pasechnik, 2002 and Parrilo, 2000, which point-wise approximate the cone of copositive matrices, we get a hierarchy of semidefinite approximation models for these problems. We show that in all the cases already the simplest models from this hierarchy are at least as strong as the strongest semidefinite models from the literature.

ISBN: 9783639166545 (pbk.) :EUR59.00Subjects--Topical Terms:

544215
Combinatorial optimization.

LC Class. No.: T57.74

Towards the optimum by semidefinite and copositive programming : = new approach to approximate hard optimization problems /
LDR:02282nam 2200205 a 4500 001 878211
003 OCoLC
005 20100904110019.0
008 100906s2009 gw b 001 0 eng d
020 $a 9783639166545 (pbk.) : $c EUR59.00
020 $a 363916654X (pbk.)
035 $a (OCoLC)440806588
035 $a GO99T03007
040 $a SILIS $e ppiak $b slv $c SILIS $d NDHU
050 4 $a T57.74
100 1 $a Povh, Janez, $d 1973- $3 1047882
245 1 0 $a Towards the optimum by semidefinite and copositive programming : $b new approach to approximate hard optimization problems / $c Janez Povh.
246 1 8 $a Towards the optimum by conic programming
260 $a Saarbrucken : $c c2009. $b VDM Verlag Dr. Muller,
300 $a 124 p. ; $c 23 cm.
504 $a Includes bibliographical references (p. 115-122) and index.
520 $a In the first part of the book we present beside a survey of standard results from linear algebra and conic programming also a new method to solve semidefinite programs, based on the augmented Lagrangian method. This method which we named Boundary point method goes far beyond the reach of interior point methods when the linear constraints are nearly orthogonal. In the second part we demonstrate an application of semidefinite and copositive programming to the following NP-hard problems from combinatorial optimization: the bandwidth problem, the quadratic assignment problem, the min-cut problem and the general graph partitioning problem. We also give ideas how to extend our approach to some other 0-1 problems, like the stability number problem and the balanced vertex separator problem. We give a study of the approximation algorithm for the bandwidth problem from Blum et al., 2000, with a special focus on computational issues and suggest an effective strategy to solve this algorithm, which is based on the interior point methods. We rewrite the quadratic assignment problem, the min-cut problem and the graph partitioning problem as a copositive program in a lifted space. Using the increasing hierarchy of cones from De Klerk, Pasechnik, 2002 and Parrilo, 2000, which point-wise approximate the cone of copositive matrices, we get a hierarchy of semidefinite approximation models for these problems. We show that in all the cases already the simplest models from this hierarchy are at least as strong as the strongest semidefinite models from the literature.
650 0 $a Combinatorial optimization. $3 544215
650 0 $a Mathematical optimization. $3 517763
650 0 $a Semidefinite programming. $3 1047883