「最適モデリング」セミナー案内 (2/16)

「最適モデリング」セミナー案内 (2/16)

日時: 2017年2月16日(木) 14:00~15:00
場所: 東京大学工学部 14号館 5階 534号室
http://www.u-tokyo.ac.jp/campusmap/cam01_04_15_j.html

講演者: Kim Chuan TOH (National University of Singapore)
http://www.math.nus.edu.sg/~mattohkc/

講演題目: A two-phase augmented Lagrangian approach for
linear and convex quadratic semidefinite programming problems

講演概要:We consider the important class of high
dimensional linear and quadratic SDP problems with large
numbers of linear equality and/or inequality constraints. In
this talk, we first introduce a symmetric Gauss-Seidel (sGS)
decomposition theorem for solving an unconstrained convex
composite programming problem whose objective is the sum of
a multi-block quadratic function and a non-smooth function
involving only the first block. Then, based on the sGS
decomposition theorem, we design a two phase proximal
augmented Lagrangian method to efficiently solve the
targeted problem to high accuracy. Specifically, in Phase I,
we design an inexact sGS-based semi-proximal ADMM to
generate a reasonably good initial point to warm-start the
algorithm in Phase II, which is a semi-smooth Newton-CG
based proximal augmented Lagrangian method capable of
computing a high accuracy solution efficiently under certain
nondegeneracy conditions.
We have developed a solver called SDPNAL+ based on the
2-phase algorithm for solving large scale linear SDP problems.
Numerous problems arising from combinatorial optimization
and binary integer quadratic programming problems have been
tested to evaluate the performance of the solver. Extensive
numerical test results show that the proposed method is
quite efficient and robust.