半正定値計画問題と内点法(<特集>最適化の数理)

概要

論文の詳細を見る
In recent years, the semidefinite program (abbreviated by SDP) has been studied intensively in the fields of combinatorial optimization, and systems and control theory. The SDP is a generalization of the linear program in the Euclidean space to the space of symmetric matrices. The extension of interior-point methods for linear programs to the SDP has largely contributed to the harmonious development in theory and practice in these fields. This article presents an introduction to the SDP, the SDP relaxation of the nonconvex quadratic program, and the primal-dual interior-point method for the SDP.
1996-12-16