SDPA PROJECT : SOLVING LARGE-SCALE SEMIDEFINITE PROGRAMS(<Special Issue>the 50th Anniversary of the Operations Research Society of Japan)

スポンサーリンク

概要

• 論文の詳細を見る

• The Semidefinite Program (SDP) has recently attracted much attention of researchers in various fields for the following reasons: (i) It has been intensively studied in both theoretical and numerical aspects. Especially the primal-dual interior-point method is known as a powerful tool for solving large-scale SDPs with accuracy. (ii) Many practical problems in various fields such as combinatorial optimization, control and systems theory, robust optimization and quantum chemistry can be modeled or approximated by using SDPs. (iii) Several software packages for solving SDPs and related problems (ex. the Second-Order Cone Program: SOCP) are available on the Internet. In 1995, we started the SDPA Project aimed for solving large-scale SDPs with numerical stability and accuracy. The SDPA (SemiDefinite Programming Algorithm) is a C++ implementation of a Mehrotra-type primal-dual predictor-corrector interior-point method for solving the standard form SDP and its dual. We have also developed some variants of the SDPA to handle SDPs with various features. The SDPARA is a parallel version of the SDPA on multiple processors and distributed memory, which replaces two major bottleneck components of the SDPA by their parallel implementation using MPI and ScaLAPACK. The SDPARA on parallel computer has attractive features; it can load a large-scale SDP into the distributed memory and solve it in a reasonable time. In this paper, we show through some numerical experiments that the SDPARA attains high performance. The SDPARA-C is an integration of two software SDPARA and SDPA-C which is a primal-dual interior-point method using the positive definite matrix completion technique. The SDPARA-C requires a small amount of memory when we solve sparse SDPs with a large-scale matrix variable and/or a large number of equality constraints. The paper also explains a grid portal system for solving SDPs, which we call the SDPA Online Solver. In this paper, we review the major achievements of the SDPA Project on solving large-scale SDPs. This paper provides an introductory and comprehensive materials for researchers who are interested in practical computational aspects of the SDPs.

著者

• Yamashita Makoto

  Kanagawa University

• Nakata Kazuhide

  Tokyo Institute Of Technology

• Fujisawa Katsuki

  Chuo University

• Fukuda Mituhiro

  Tokyo Institute of Technology

• Fujisawa Katsuki

  Chuo Univ. Tokyo Jpn

関連論文

• QUADRATIC AND CONVEX MINIMAX CLASSIFICATION PROBLEMS
• SOLVING LARGE SCALE OPTIMIZATION PROBLEMS VIA GRID AND CLUSTER COMPUTING(Network Design, Control and Optimization)
• SDPA PROJECT : SOLVING LARGE-SCALE SEMIDEFINITE PROGRAMS(the 50th Anniversary of the Operations Research Society of Japan)
• AN EXTENSION OF A MINIMAX APPROACH TO MULTIPLE CLASSIFICATION
• Computational Aspects of Bilinear Matrix Inequality Problems
• NETAL : HIGH-PERFORMANCE IMPLEMENTATION OF NETWORK ANALYSIS LIBRARY CONSIDERING COMPUTER MEMORY HIERARCHY(SCOPE (Seminar on Computation and OPtimization for new Extensions))

スポンサーリンク