Abstract
Symmetricity of an optimal solution of Semi-Definite Programming (SDP) is discussed based on the symmetry property of the central path that is traced by a primal-dual interior-point method. A symmetric SDP is defined by operators for rearranging elements of matrices and vectors, and the solution on the central path is proved to be symmetric. Therefore, it is theoretically guaranteed that a symmetric optimal solution is always obtained by using a primal-dual interior-point method even if there exist other asymmetric optimal solutions. The optimization problem of symmetric trusses under eigenvalue constraints is shown to be formulated as a symmetric SDP. Numerical experiments illustrate convergence to strictly symmetric optimal solutions.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Alizadeh, F. 1992: Optimization over the positive-semidefinite cone: Interior point methods and combinatorial applications. In: Pardalos, P. (ed.) Advances in optimization and parallel computing, pp. 1–25. Amsterdam: North-Holland
Alizadeh, F.; Haeberly, J.-P.A.; Overton, M.L. 1998: Primaldual interior-point methods for semidefinite programming: convergence rates, stability and numerical results. SIAM J. Optim. 8, 746–768
Arora, J.S.; Tseng, C.H. 1987: IDESIGN User’s Manual Ver. 3.5. Optimal Design Laboratory, The University of Iowa
Beling, A.; Verma, S. 1997: Combinatorial complexity of the central curve. In: Proc. Symposium on Theory of Computing
Ben-Tal, A.; Nemirovski, A. 1997: Robust truss topology optimization via semidefinite programming. SIAM J. Optim. 7, 991–1016
Fujisawa, K.; Kojima, M.; Nakata, K. 1999: SDPA (Semidefinite Programming Algorithm) -User’s Manual-. Tech. Report B-308, Department of Mathematical and Computing Sciences, Tokyo Institute of Technology, Japan
Goldfarb, D.; Scheinberg, K. 1998: Interior point trajectories in semidefinite programming. SIAM J. Optim. 8, 871–886
Halická, M. 1998: Two simple proofs of analyticity of the central path in linear programming. Mathematics Preprint, No. M198. Faculty of Mathematics and Physics, Comenius University, Bratislava, Slovakia
de Klerk, E.; Roos, C.; Terlaky, T. 1995: Semi-definite problems in truss topology optimization. Report 95-128. Faculty of Technical Mathematics and Computer Science. Delft University of Technology, Delft, Netherlands
Kojima, M.; Mizuno S.; Yoshise A. 1989: A primal-dual interior point algorithm for linear programming, In: Megiddo, N. (ed.) Progress in mathematical programming: interior-point algorithms and related methods, pp. 29–47. Berlin, Heidelberg, New York: Springer
Kojima, M.; Shindoh S.; Hara, S. 1997: Interior-point methods for the monotone semidefinite linear complementarity problems. SIAM J. Optim. 7, 86–125
Lewis, A.S.; Overton, M.L. 1996: Eigenvalue optimization. Acta Numerica 5, 149–190
Megiddo, N. 1989: Pathways to the optimal set in linear programming. In: Megiddo, N. (ed.) Progress in mathematical programming: interior-point algorithms and related methods, pp. 131–158. Berlin, Heidelberg, New York: Springer
Monteiro, R.D.C. 1997: Primal-dual path-following algorithms for semidefinite programming. SIAM J. Optimiz. 7, 663–678
Nesterov, Yu.E.; Nemirovskii, A.S. 1994: Interior Point Polynomial Methods in Convex Programming: Theory and Applications. Philadelphia, PA: SIAM
Ohsaki, M.; Fujisawa, K.; Katoh, N.; Kanno, Y. 1999: Semi-definite programming for topology optimization of trusses under multiple eigenvalue constraints. Comput. Meth. Appl. Mech. Engng. 180, 203–217
Vandenberghe, L.; Boyd, S. 1996: Semidefinite programming. SIAM Review 38, 49–95
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Kanno, Y., Ohsaki, M. & Katoh, N. Symmetricity of the solution of semidefinite programming. Struct Multidisc Optim 24, 225–232 (2002). https://doi.org/10.1007/s00158-002-0232-0
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/s00158-002-0232-0