Dualnost u semidefinitnom programiranju

Semidefinite programming is class of optimization problems in which we optimize a linear function over the set of symmetric positive semidefinite matrices. Semidefinite programming can be considered as an extension of linear programming. Because of that in this paper we first took a short review of linear programming. We described one of the methods of solving linear programs, interior point method. This method can be successfully generalized to semidefinite programming. The central part of this paper is the duality theory in semidefinite programming and its main result - a strong duality theorem. It asserts that if the primal semidefinite program has a finite value and some positive solution, then the dual also has the same optimal value. The proof is done in the more general framework of cone programming. Cone programming and linear programming have very similar duality theory. The essential difference is that cone programs may exhibit limit feasibility, meaning that an infeasible program may become feasible under an arbitrarily small perturbation of the constraints. Similarly, a cone program has a limit value, which may differ from its value. We started with the separation theorem for closed convex cones, and by using it we proved Farkas lemma. With Farkas lemma we proved a regular duality for cone programs, then strong duality with some additional conditions. Since cone \(\Sym_n^+\)is a self-dual cone, the strong duality theorem for semidefinite programming followed easily.