TABLE OF CONTENTS Due to its tremendous expressive abilities, SDP has an extremely wide spectrum of applications. We shall overview the most important of these applications. We start with brief presentation of what comes from inside mathematics and then continue with engineering applications. The most important mathematical applications of SDP deal with relaxations of combinatorial problems.
Combinatorial problems and their relaxations. Numerous problems of planning, scheduling, routing, etc., can be posed as combinatorial optimization problems, i.e., optimization programs with discrete design variables (integer or zero-one). There are several universal forms of combinatorial problems, among them LP with integer variables and LP with 0-1 variables. A problem given in one of these forms can always be converted to any other universal form, so that in principle it does not matter which form is used. Now, the majority of combinatorial problems are difficult-we do not know theoretically efficient (in a certain precise meaning of the notion) algorithms for solving these problems. What we do know is that nearly all these difficult problems are, in a sense, equivalent to each other and are NP-complete. The exact meaning of the latter notion will be explained in Lecture 5; for the time being it suffices to say that NP-completeness of a problem P means that the problem is as difficult as a combinatorial problem can be-if we knew an efficient algorithm for P, we would be able to convert it to an efficient algorithm for any other combinatorial problem.
