A STRUCTURAL GEOMETRICAL ANALYSIS OF WEAKLY INFEASIBLE SDPS

• F. Lourenço Bruno

  Seikei University

• Muramatsu Masakazu

  The University of Electro-Communications

• Tsuchiya Takashi

  National Graduate Institute for Policy Studies

抄録

In this article, we develop a detailed analysis of semidefinite feasibility problems (SDFPs) to understand how weak infeasibility arises in semidefinite programming. This is done by decomposing a SDFP into smaller problems, in a way that preserves most feasibility properties of the original problem. The decomposition utilizes a set of vectors (computed in the primal space) which arises when we apply the facial reduction algorithm to the dual feasible region. In particular, we show that for a weakly infeasible problem over n× n matrices, at most n-1 directions are required to approach the positive semidefinite cone. We also present a discussion on feasibility certificates for SDFPs and related complexity results.

収録刊行物

• 日本オペレーションズ・リサーチ学会論文誌

  日本オペレーションズ・リサーチ学会論文誌 59 (3), 241-257, 2016

  公益社団法人 日本オペレーションズ・リサーチ学会

キーワード

• Optimization
• weak infeasibility
• semidefinite programming

詳細情報

• CRID: 1390282679085794176
• NII論文ID: 130005163067
• NII書誌ID: AA00703935
• DOI: 10.15807/jorsj.59.241
• ISSN: 21888299
• ISSN: 04534514
• NDL書誌ID: 027463114
• Web Site: https://ndlsearch.ndl.go.jp/books/R000000004-I027463114
• Web Site: https://www.jstage.jst.go.jp/article/jorsj/59/3/59_241/_pdf
• 本文言語コード: en
• データソース種別:
  • JaLC
  • NDL
  • Crossref
  • CiNii Articles
• 抄録ライセンスフラグ: 使用不可