| Title:
|
On the central paths and Cauchy trajectories in semidefinite programming (English) |
| Author:
|
López, Julio |
| Author:
|
Ramírez C., Héctor |
| Language:
|
English |
| Journal:
|
Kybernetika |
| ISSN:
|
0023-5954 |
| Volume:
|
46 |
| Issue:
|
3 |
| Year:
|
2010 |
| Pages:
|
524-535 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
In this work, we study the properties of central paths, defined with respect to a large class of penalty and barrier functions, for convex semidefinite programs. The type of programs studied here is characterized by the minimization of a smooth and convex objective function subject to a linear matrix inequality constraint. So, it is a particular case of convex programming with conic constraints. The studied class of functions consists of spectrally defined functions induced by penalty or barrier maps defined over the real nonnegative numbers. We prove the convergence of the (primal, dual and primal-dual) central path toward a (primal, dual, primal-dual, respectively) solution of our problem. Finally, we prove the global existence of Cauchy trajectories in our context and we recall its relation with primal central path when linear semidefinite programs are considered. Some illustrative examples are shown at the end of this paper. (English) |
| Keyword:
|
semidefinite programming |
| Keyword:
|
central paths |
| Keyword:
|
penalty/barrier functions |
| Keyword:
|
Riemannian geometry |
| Keyword:
|
Cauchy trajectories |
| MSC:
|
53C25 |
| MSC:
|
90C22 |
| MSC:
|
90C51 |
| idZBL:
|
Zbl 1225.90097 |
| idMR:
|
MR2676088 |
| . |
| Date available:
|
2010-09-13T17:02:50Z |
| Last updated:
|
2013-09-21 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/140766 |
| . |
| Reference:
|
[1] Alvarez, F., Bolte, J., Brahic, O.: Hessian Riemannian flows in convex programming.SIAM J. Control Optim. 43 (2004), 2, 477–501. MR 2086170, 10.1137/S0363012902419977 |
| Reference:
|
[2] Alvarez, F., López, J., C., H. Ramírez: Interior proximal algorithm with variable metric for second-order cone programming: applications to structural optimization and classification by hyperplanes.To appear in Optimization Methods and Software. |
| Reference:
|
[3] Auslender, A., C., H. Ramírez: Penalty and barrier methods for convex semidefinite programming.Math. Methods Oper. Res. 43 (2006), 2, 195–219. MR 2264746 |
| Reference:
|
[4] Bayer, D. A., Lagarias, J. C.: The nonlinear geometry of linear programming I.Affine and projective scaling trajectories. Trans. Amer. Math. Soc. 314 (1989), 499–526. Zbl 0671.90045, MR 1005525 |
| Reference:
|
[5] Neto, J. X. Cruz, Ferreira, O. P., Oliveira, P. R., Silva, R. C. M.: Central paths in semidefinite programming, generalized proximal point method and Cauchy trajectories in Riemannian manifolds.J. Optim. Theory Appl. 1 (2008), 1–16. |
| Reference:
|
[6] Goemans, M. X.: Semidefinite programming in combinatorial optimization.Lectures on Mathematical Programming (ismp97). Math. Programming Ser. B 79 (1997), 1–3, 143–161. Zbl 0887.90139, MR 1464765, 10.1007/BF02614315 |
| Reference:
|
[7] Dieudonné, J. A.: Foundations of Modern Analysis.Academic Press, New York 1969. Zbl 0708.46002, MR 0349288 |
| Reference:
|
[8] Drummond, L. M. Graña, Peterzil, Y.: The central path in smooth convex semidefinite programming.Optimization 51 (2002), 207–233. MR 1928037, 10.1080/02331930290019396 |
| Reference:
|
[9] Halická, E., Klerk, E. de, Roos, C.: On the convergence of the central path in semidefinite optimization.SIAM J. Optim. 12 (2002), 4, 1090–1099. MR 1922510, 10.1137/S1052623401390793 |
| Reference:
|
[10] Iusem, A. N., Svaiter, B. F., Neto, J. X. da Cruz: Central paths, generalized proximal point methods and Cauchy trajectories in Riemannian manifolds.SIAM J. Control Optim. 37 (1999), 2, 566–588. MR 1670649, 10.1137/S0363012995290744 |
| Reference:
|
[11] Klerk, E. de: Aspects of Semidefinite Programming: Interior Point Algorithms and Selected Applications.(Applied Optimization 65.) Kluwer Academic Publishers, Dordrecht 2002. Zbl 0991.90098, MR 2064921 |
| Reference:
|
[12] Kojima, M., Shindoh, S., Hara, S.: Interior-point methods for the monotone semidefinite linear complementary problem in symmetic matrices.SIAM J. Optim. 7 (1997), 86–125. MR 1430559, 10.1137/S1052623494269035 |
| Reference:
|
[13] Lewis, A. S.: Convex Analysis on the Hermitian Matrices.SIAM J. Optim., 6 (1996), 1, 164–177. Zbl 0849.15013, MR 1377729, 10.1137/0806009 |
| Reference:
|
[14] Lewis, A. S., Sendov, H. S.: Twice differentiable spectral functions.SIAM J. Matrix Anal. Appl. 23 (2001), 2, 368–386. Zbl 1053.15004, MR 1871318, 10.1137/S089547980036838X |
| Reference:
|
[15] Lojasiewicz, S.: Ensembles Semi-analitiques.Inst. Hautes Études Sci., Bures-sur-Yvette 1965. |
| Reference:
|
[16] Petersen, P.: Riemannian Geometry.Springer-Verlag, New York 1998. MR 1480173 |
| Reference:
|
[17] Seeger, A.: Convex analysis of spectrally defined matrix functions.SIAM J. Optim. 7 (1997), 679–696. Zbl 0890.15018, MR 1462061, 10.1137/S1052623495288866 |
| Reference:
|
[18] Shapiro, A.: On Differentiability of Symmetric Matrix Valued Functions.Technical Report, School of Industrial and Systems Engineering, Georgia Institute of Technology, 2002. |
| Reference:
|
[19] Todd, M.: Semidefinite optimization.Acta Numer. 10 (2001), 515–560. Zbl 1105.65334, MR 2009698, 10.1017/S0962492901000071 |
| Reference:
|
[20] Vandenberghe, L., Boyd, S.: Semidefinite programming.SIAM Rev. 38 (1996), 1, 49–95. Zbl 1151.90512, MR 1379041, 10.1137/1038003 |
| . |
