Optimization Online


An oracle-based projection and rescaling algorithm for linear semi-infinite feasibility problems and its application to SDP and SOCP

Masakazu Muramatsu(MasakazuMuramatsu***at***uec.ac.jp)
Tomonari Kitahara(tomonari.kitahara***at***econ.kyushu-u.ac.jp)
Bruno Lourenco(lourenco***at***mist.i.u-tokyo.ac.jp)
Takayuki Okuno(takayuki.okuno.ks***at***riken.jp)
Takashi Tsuchiya(tsuchiya***at***grips.ac.jp)

Abstract: We point out that Chubanovís oracle-based algorithm for linear programming [5] can be applied almost as it is to linear semi-infinite programming (LSIP). In this note, we describe the details and prove the polynomial complexity of the algorithm based on the real computation model proposed by Blum, Shub and Smale (the BSS model) which is more suitable for floating point computation in modern computers. The adoption of the BBS model makes our description and analysis much simpler than the original one by Chubanov [5]. Then we reformulate semidefinite programming (SDP) and second-order cone programming (SOCP) into LSIP, and apply our algorithm to obtain new complexity results for computing interior feasible solutions of homogeneous SDP and SOCP.

Keywords: Linear semi-infinite programming, Projection and rescaling algorithm, Oracle-based algo- rithm, Semidefinite programming.

Category 1: Linear, Cone and Semidefinite Programming

Category 2: Infinite Dimensional Optimization (Semi-infinite Programming )

Citation: Department of Computer and Network Engineering, The University of Electro-Communications.

Download: [PDF]

Entry Submitted: 09/26/2018
Entry Accepted: 09/27/2018
Entry Last Modified: 09/26/2018

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society