東華大學圖書館 |

Language: English

Help

回圖書館首頁

手機版館藏查詢

Back

Switch To: Labeled | MARC Mode | ISBD

First-order methods for semidefinite...

Wen, Zaiwen.

Linked to FindBook

Google Book

Amazon

博客來

First-order methods for semidefinite programming.

Record Type:	Language materials, printed : Monograph/item
Title/Author:	First-order methods for semidefinite programming./
Author:	Wen, Zaiwen.
Description:	91 p.
Notes:	Source: Dissertation Abstracts International, Volume: 71-02, Section: B, page: 1326.
Contained By:	Dissertation Abstracts International71-02B.
Subject:	Applied Mathematics. -
Online resource:	http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=3393547
ISBN:	9781109604931

First-order methods for semidefinite programming.
Wen, Zaiwen.

First-order methods for semidefinite programming. - 91 p.

Source: Dissertation Abstracts International, Volume: 71-02, Section: B, page: 1326.

Thesis (Ph.D.)--Columbia University, 2009.

Semidefinite programming (SDP) problems are concerned with minimizing a linear function of a symmetric positive definite matrix subject to linear equality constraints. These convex problems are solvable in polynomial time by interior point methods. However, if the number of constraints m in an SDP is of order O(n 2) when the unknown positive semidefinite matrix is n x n, interior point methods become impractical both in terms of the time (O(n6)) and the amount of memory (O(m2)) required at each iteration to form the m x m positive definite Schur complement matrix M and compute the search direction by finding the Cholesky factorization of M. This significantly limits the application of interior-point methods. In comparison, the computational cost of each iteration of first-order optimization approaches is much cheaper, particularly, if any sparsity in the SDP constraints or other special structure is exploited. This dissertation is devoted to the development, analysis and evaluation of two first-order approaches that are able to solve large SDP problems which have been challenging for interior point methods.

ISBN: 9781109604931Subjects--Topical Terms:

1669109
Applied Mathematics.

First-order methods for semidefinite programming.
LDR:03935nam 2200301 4500 001 1391016
005 20101222085248.5
008 130515s2009 ||||||||||||||||| ||eng d
020 $a 9781109604931
035 $a (UMI)AAI3393547
035 $a AAI3393547
040 $a UMI $c UMI
100 1 $a Wen, Zaiwen. $3 1669387
245 1 0 $a First-order methods for semidefinite programming.
300 $a 91 p.
500 $a Source: Dissertation Abstracts International, Volume: 71-02, Section: B, page: 1326.
500 $a Adviser: Donald Goldfarb.
502 $a Thesis (Ph.D.)--Columbia University, 2009.
520 $a Semidefinite programming (SDP) problems are concerned with minimizing a linear function of a symmetric positive definite matrix subject to linear equality constraints. These convex problems are solvable in polynomial time by interior point methods. However, if the number of constraints m in an SDP is of order O(n 2) when the unknown positive semidefinite matrix is n x n, interior point methods become impractical both in terms of the time (O(n6)) and the amount of memory (O(m2)) required at each iteration to form the m x m positive definite Schur complement matrix M and compute the search direction by finding the Cholesky factorization of M. This significantly limits the application of interior-point methods. In comparison, the computational cost of each iteration of first-order optimization approaches is much cheaper, particularly, if any sparsity in the SDP constraints or other special structure is exploited. This dissertation is devoted to the development, analysis and evaluation of two first-order approaches that are able to solve large SDP problems which have been challenging for interior point methods.
520 $a In chapter 2, we present a row-by-row (RBR) method based on solving a sequence of problems obtained by restricting the n-dimensional positive semidefinite constraint on the matrix X. By fixing any (n -- 1)-dimensional principal submatrix of X and using its (generalized) Schur complement, the positive semidefinite constraint is reduced to a simple second-order cone constraint. When the RBR method is applied to solve the maxcut SDP relaxation, the optimal solution of the RBR subproblem only involves a single matrix-vector product which leads to a simple and very efficient method. To handle linear constraints in generic SDP problems, we use an augmented Lagrangian approach. Specialized versions are presented for the maxcut SDP relaxation and the minimum nuclear norm matrix completion problem since closed-form solutions for the RBR subproblems are available. Numerical results on the maxcut SDP relaxation and matrix completion problems are presented to demonstrate the robustness and efficiency of our algorithm.
520 $a In chapter 3, we present an alternating direction method based on the augmented Lagrangian framework for solving SDP problems in standard form. At each iteration, the algorithm, also known as a two-splitting scheme, minimizes the dual augmented Lagrangian function sequentially with respect to the Lagrange multipliers corresponding to the linear constraints, then the dual slack variables and finally the primal variables, while in each minimization keeping the other variables fixed. Convergence is proved by using a fixed-point argument. A multiple-splitting algorithm is then proposed to handle SDPs with inequality constraints and positivity constraints directly without transforming them to the equality constraints in standard form. Numerical results on frequency assignment, maximum stable set and binary integer quadratic programming problems, show that our algorithm is very promising.
590 $a School code: 0054.
650 4 $a Applied Mathematics. $3 1669109
650 4 $a Operations Research. $3 626629
690 $a 0364
690 $a 0796
710 2 $a Columbia University. $3 571054
773 0 $t Dissertation Abstracts International $g 71-02B.
790 1 0 $a Goldfarb, Donald, $e advisor
790 $a 0054
791 $a Ph.D.
792 $a 2009
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=3393547