Self-Regularity by Peng Jiming; Roos Cornelis; Terlaky Tamás

Author:Peng, Jiming; Roos, Cornelis; Terlaky, Tamás
Language: eng
Format: epub
Publisher: Princeton University Press
Published: 2009-03-14T16:00:00+00:00

5.1 INTRODUCTION TO SDO, DUALITY THEORY AND CENTRAL PATH

The first paper dealing with SDO problems dates back to the early 1960s [11]. For the next many years, the whole topic of SDO stayed silent except for a few isolated results scattered in the literature. The situation changed dramatically around the beginning of the 1990s when SDO started to emerge as one of the fastest developing areas of mathematical programming.

Several reasons can be given why SDO was out of interest for such a long time. One of the main reasons was the lack of robust and efficient algorithms for solving SDO before 1990s. The thrust of SDO research in the 1990s is rooted in two aspects. The first is the importance of the problem. The SDO paradigm not only contains many important class of problems in the field of mathematical programming including LO, QP, SOCO, LCPs, but is also widely used in other fields such as control theory, signal processing, statistics and combinatorial optimization. Interested readers are referred to [55,103,118, 120] for more concrete descriptions. Second, around the end of the 1980s, invigorated by the great achievements of IPMs in coping with problems such as LO, QP and LCPs, the investigation of efficient IPMs for solving SDO reached the top of the agenda of many experts in the field.

According to the records, Nesterov and Nemirovskii [83] were the first to extend IPMs from LO to SDO and build up the polynomial complexity of the algorithm, at least in a theoretical sense. Independently, Alizadeh [2] elegantly applied IPMs to solving SDO problems arising from combinatorics. Since then, a large number of results have been reported concerning two main aspects of SDO research: one is the theoretical analysis and efficient implementation of IPMs; the other is exploration of new applications. As the outcome of much effort in the first direction, the theory of IPMs for SDO has been developed into a mature discipline and quite a number of effective codes [3,26,104,112,116] have been designed in recent years with which most moderate-sized SDO problems can noe be solved successfully, although a general-purpose large-scale SDO solver remains an elusive goal. With regard to the second aspect, many exciting new results about the quality of relaxations of combinatorial and global optimization problems have been reported [30,82]. Even today, new algorithms and applications for SDO are still emerging. The book edited by Wolkowicz, Saigal and Vandenberghe [120] collects review papers on various topics associated with SDO and a large number of references. For more recent achievements, visit the online web site www.mcs.anl.gov/otc/InteriorPoint maintained by S. Wright, or the SDP Homepage http://www.zib.de/helmberg/semidef.html by Helmberg.

In this chapter we undertake the task of extending the algorithms posed in the previous chapter to the case of SDO. We consider the SDO problem in the following standard form:

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.