×

zbMATH — the first resource for mathematics

Long-step path-following algorithm for solving symmetric programming problems with nonlinear objective functions. (English) Zbl 1420.90044
Summary: We developed a long-step path-following algorithm for a class of symmetric programming problems with nonlinear convex objective functions. The theoretical framework is developed for functions compatible in the sense of Nesterov and Nemirovski with \(-\,\ln \det \) barrier function. Complexity estimates similar to the case of a linear-quadratic objective function are established, which gives an upper bound for the total number of Newton steps. The theoretical scheme is implemented for a class of spectral objective functions which includes the case of quantum (von Neumann) entropy objective function, important from the point of view of applications. We explicitly compare our numerical results with the only known competitor.

MSC:
90C25 Convex programming
90C51 Interior-point methods
Software:
CVX; Matlab; Mosek; SDPT3; YALMIP
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] ApS, MOSEK: The MOSEK optimization toolbox for MATLAB manual, version 8.0 (Revision 60). http://docs.mosek.com/8.0/toolbox/index.html (2017)
[2] Bhatia, R.: Matrix Analysis. Springer, New York (1997) · Zbl 0863.15001
[3] Chandrasecaran, V.; Shah, P., Relative entropy optimization and its applications, Math. Program. Ser. A, 161, 1-32, (2017) · Zbl 1357.81037
[4] den Hertog, D.: Interior Point Approach to Linear. Quadratic and Convex Programming. Springer, Dordrecht (1994) · Zbl 0808.90107
[5] Hertog, D.; Roos, C.; Terlaky, T., On the classical logarithmic barrier function method for a class of smooth convex programming problems, J. Optim. Theory Appl., 73, 1-25, (1992) · Zbl 0794.90044
[6] Faraut, J., Korányi, A.: Analysis on Symmetric Cones. Cambridge University Press, Cambridge (1994) · Zbl 0841.43002
[7] Fawzi, H., Saunderson, J., Parrilo, P.A.: Semidefinite approximations of the matrix logarithm. Comput. Math. Found. (2018). https://doi.org/10.1007/s10208-018-9385-0 · Zbl 1364.90245
[8] Faybusovich, L., Semidefinite programming: a path-following algorithm for a linear-quadratic functional, SIAM J. Optim., 6, 1007-1024, (1996) · Zbl 0868.90091
[9] Faybusovich, L., Several Jordan-algebraic aspects of optimization, Optimization, 57, 379-393, (2008) · Zbl 1191.90034
[10] Faybusovich, L., On Hazan’s algorithm for symmetric programming problems, J. Optim. Theory Appl., 164, 915-932, (2015) · Zbl 1327.90203
[11] Faybusovich, L., Primal-dual potential reduction algorithm for symmetric programming problems with nonlinear objective functions, Linear Algebra Appl., 536, 228-249, (2018) · Zbl 1419.90084
[12] Faybusovich, L.; Tsuchiya, T., Matrix monotonicity and self-concordance: How to handle quantum entropy in optimization problems, Optim. Lett., 11, 1513-1526, (2017) · Zbl 1394.90529
[13] Grant, M., Boyd, S.: CVX: Matlab software for disciplined convex programming, version 2.1. http://cvxr.com/cvx (2017)
[14] Korányi, A., Monotone functions on formally real Jordan algebras, Math. Ann., 269, 73-76, (1984) · Zbl 0552.17014
[15] Löfberg, J.: YALMIP: a toolbox for modeling and optimization in MATLAB, In: Proceedings of the CACSD Conference, Taipei, Taiwan (2004)
[16] MathWorks, Inc.: MATLAB R2016a. Natick, MA (2016)
[17] Nesterov, Y.: Introductory Lectures on Convex Optimization. Kluwer, Boston (2004) · Zbl 1086.90045
[18] Nesterov, Y., Nemirovskii, A.: Interior-Point Polynomial Algorithms in Convex Programming. SIAM, Philadelphia (1994) · Zbl 0824.90112
[19] Sutter, D.; Sutter, T.; Esfahani, PM; Renner, R., Efficient approximation of quantum channel capacities, IEEE Trans. Inf. Theory, 62, 578-598, (2016) · Zbl 1359.81074
[20] Toh, KC; Todd, MJ; Tütüncü, RH, SDPT3—a matlab software package for semidefinite programming, Optim. Methods Softw., 11, 545-581, (1999) · Zbl 0997.90060
[21] Zinchenko, Y.; Friedland, S.; Gour, G., Numerical estimation of the relative entropy of entanglement, Phys. Rev. A, 82, 052336, (2010)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.