Ekonomicka a financna matematika

Weighted central paths in semidefinite programming
Mária Trnovská
PhD thesis advisor: Margaréta Halická

Download
PhD thesis - Full text (PDF 748K)

Summary: Semidefinite programming (SDP) is a special class of convex mathematical programming, which has been recently intensively studied because of its applicability to various areas, such as combinatorial optimization, system and control theory or mechanical and electrical engineering. Moreover, semidefinite programming problems can be efficiently solved by interior point methods (IPM). The most important concept in the theory of IPM is the central path. It is an analytic curve in the interior of the feasible set which tends to an optimal point at the boundary. The properties of the central path are important for designing and analyzing interior point algorithms. In the thesis the existence and the limiting behavior of different types of the weighted central paths in SDP are studied.

The main results included in this thesis can be summarized as follows. We present a new and relatively simple proof of the existence of weighted paths associated with certain type of symmetrization map. This result can be considered as a generalization of the known proof of the existence of the weighted central path for linear complementarity problems associated with the so-called AHO symmetrization of Preiss, Stoer (2003) and is formulated in terms of semidefinite programming.

Also the asymptotic behavior of different types of weighted central paths was studied and these properties were useful for obtaining new results concerning the analyticity of the weighted paths at the boundary point. We focused on the paths associated with the so-called square-root symmetrization and Cholesky-type symmetrization and extended the known results of Lu, Monteiro (2004) and Chua (2007). We showed, that the both types of paths posses the same limiting behavior and that, under the strict complementarity assumption, these paths are analytic functions at the boundary point if and only if the weight matrix is block diagonal.

Related papers
[1] M. Trnovská, M. Halická, Limiting behavior and analyticity of weighted central pathsin semidefinite programming,
Optimization Methods and Software, 25(2) (2010), 247 - 262
Full text (PDF 309K)

[2] M. Trnovská, Existence of Weighted Interior Point Paths in Semidefinite Programming,
Proceedings of 15th International Scientific Conference of Mathematical Methods in Economics and Industry, 2007, Herlany, Slovakia
Full text (PDF 200K)

[3] M. Trnovská, Weighted Central Path in Semidefinite Programming Associated with Symmetrization Map (XS+SX)/2,
Journal of Electrical Engineering, Vol 57, No 12/s, 2006, 57--60
Full text (PS 288K)

[4] M. Trnovská, Strong Duality Conditions in Semidefinite Programming,
Journal of Electrical Engineering, Vol 56, No 12/s, 2005, 87--89
Full text (PDF 245K)