On the central paths and Cauchy trajectories in semidefinite programming

Julio López; Héctor Ramírez C.

Kybernetika (2010)

  • Volume: 46, Issue: 3, page 524-535
  • ISSN: 0023-5954

Abstract

top
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.

How to cite

top

López, Julio, and Ramírez C., Héctor. "On the central paths and Cauchy trajectories in semidefinite programming." Kybernetika 46.3 (2010): 524-535. <http://eudml.org/doc/196557>.

@article{López2010,
abstract = {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.},
author = {López, Julio, Ramírez C., Héctor},
journal = {Kybernetika},
keywords = {semidefinite programming; central paths; penalty/barrier functions; Riemannian geometry; Cauchy trajectories; semidefinite programming; central paths; penalty/barrier functions; Riemannian geometry; Cauchy trajectories},
language = {eng},
number = {3},
pages = {524-535},
publisher = {Institute of Information Theory and Automation AS CR},
title = {On the central paths and Cauchy trajectories in semidefinite programming},
url = {http://eudml.org/doc/196557},
volume = {46},
year = {2010},
}

TY - JOUR
AU - López, Julio
AU - Ramírez C., Héctor
TI - On the central paths and Cauchy trajectories in semidefinite programming
JO - Kybernetika
PY - 2010
PB - Institute of Information Theory and Automation AS CR
VL - 46
IS - 3
SP - 524
EP - 535
AB - 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.
LA - eng
KW - semidefinite programming; central paths; penalty/barrier functions; Riemannian geometry; Cauchy trajectories; semidefinite programming; central paths; penalty/barrier functions; Riemannian geometry; Cauchy trajectories
UR - http://eudml.org/doc/196557
ER -

References

top
  1. Alvarez, F., Bolte, J., Brahic, O., 10.1137/S0363012902419977, SIAM J. Control Optim. 43 (2004), 2, 477–501. MR2086170DOI10.1137/S0363012902419977
  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. 
  3. Auslender, A., C., H. Ramírez, Penalty and barrier methods for convex semidefinite programming, Math. Methods Oper. Res. 43 (2006), 2, 195–219. MR2264746
  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. Zbl0671.90045MR1005525
  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. 
  6. Goemans, M. X., 10.1007/BF02614315, Lectures on Mathematical Programming (ismp97). Math. Programming Ser. B 79 (1997), 1–3, 143–161. Zbl0887.90139MR1464765DOI10.1007/BF02614315
  7. Dieudonné, J. A., Foundations of Modern Analysis, Academic Press, New York 1969. Zbl0708.46002MR0349288
  8. Drummond, L. M. Graña, Peterzil, Y., 10.1080/02331930290019396, Optimization 51 (2002), 207–233. MR1928037DOI10.1080/02331930290019396
  9. Halická, E., Klerk, E. de, Roos, C., 10.1137/S1052623401390793, SIAM J. Optim. 12 (2002), 4, 1090–1099. MR1922510DOI10.1137/S1052623401390793
  10. Iusem, A. N., Svaiter, B. F., Neto, J. X. da Cruz, 10.1137/S0363012995290744, SIAM J. Control Optim. 37 (1999), 2, 566–588. MR1670649DOI10.1137/S0363012995290744
  11. Klerk, E. de, Aspects of Semidefinite Programming: Interior Point Algorithms and Selected Applications, (Applied Optimization 65.) Kluwer Academic Publishers, Dordrecht 2002. Zbl0991.90098MR2064921
  12. Kojima, M., Shindoh, S., Hara, S., 10.1137/S1052623494269035, SIAM J. Optim. 7 (1997), 86–125. MR1430559DOI10.1137/S1052623494269035
  13. Lewis, A. S., 10.1137/0806009, SIAM J. Optim., 6 (1996), 1, 164–177. Zbl0849.15013MR1377729DOI10.1137/0806009
  14. Lewis, A. S., Sendov, H. S., 10.1137/S089547980036838X, SIAM J. Matrix Anal. Appl. 23 (2001), 2, 368–386. Zbl1053.15004MR1871318DOI10.1137/S089547980036838X
  15. Lojasiewicz, S., Ensembles Semi-analitiques, Inst. Hautes Études Sci., Bures-sur-Yvette 1965. 
  16. Petersen, P., Riemannian Geometry, Springer-Verlag, New York 1998. MR1480173
  17. Seeger, A., 10.1137/S1052623495288866, SIAM J. Optim. 7 (1997), 679–696. Zbl0890.15018MR1462061DOI10.1137/S1052623495288866
  18. Shapiro, A., On Differentiability of Symmetric Matrix Valued Functions, Technical Report, School of Industrial and Systems Engineering, Georgia Institute of Technology, 2002. 
  19. Todd, M., 10.1017/S0962492901000071, Acta Numer. 10 (2001), 515–560. Zbl1105.65334MR2009698DOI10.1017/S0962492901000071
  20. Vandenberghe, L., Boyd, S., 10.1137/1038003, SIAM Rev. 38 (1996), 1, 49–95. Zbl1151.90512MR1379041DOI10.1137/1038003

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.