Abstract
In this expository article, we study optimization problems specified via linear and relative entropy inequalities. Such relative entropy programs (REPs) are convex optimization problems as the relative entropy function is jointly convex with respect to both its arguments. Prominent families of convex programs such as geometric programs (GPs), second-order cone programs, and entropy maximization problems are special cases of REPs, although REPs are more general than these classes of problems. We provide solutions based on REPs to a range of problems such as permanent maximization, robust optimization formulations of GPs, and hitting-time estimation in dynamical systems. We survey previous approaches to some of these problems and the limitations of those methods, and we highlight the more powerful generalizations afforded by REPs. We conclude with a discussion of quantum analogs of the relative entropy function, including a review of the similarities and distinctions with respect to the classical case. We also describe a stylized application of quantum relative entropy optimization that exploits the joint convexity of the quantum relative entropy function.



Similar content being viewed by others
Notes
In full generality, density matrices are trace-one, positive semidefinite Hermitian matrices, and \(\mathbf {A}^{(j)} \in {\mathbb {C}}^{k \times n}\). As with SDPs, the Von-Neumann entropy optimization framework can handle linear matrix inequalities on Hermitian matrices, but we stick with the real case for simplicity.
References
Bapat, R.B., Beg, M.I.: Order statistics for nonidentically distributed variables and permanents. Sankhya Indian J. Stat. A 51, 79–93 (1989)
Barvinok, A.I.: Computing mixed discriminants, mixed volumes, and permanents. Discrete Comput. Geom. 18, 205–237 (1997)
Ben-Tal, A., El Ghaoui, L., Nemirovski, A.: Robust Optimization. Princeton University Press, Princeton (2009)
Ben-Tal, A., Nemirovski, A.: Optimal design of engineering structures. Optima. 47, 4–8 (1995)
Ben-Tal, A., Nemirovski, A.: Robust convex optimization. Math. Oper. Res. 23, 769–805 (1998)
Ben-Tal, A., Nemirovski, A.: On polyhedral approximations of the second-order cone. Math. Oper. Res. 26, 193–205 (2001)
Ben-Tal, A., Nemirovskii, A.: Lectures on Modern Convex Optimization. Society for Industrial and Applied Mathematics, Philadelphia (2001)
Betke, U.: Mixed volumes of polytopes. Arch. Math. 58, 388–391 (1992)
Blekherman, G., Parrilo, P., Thomas, R.: Semidefinite Optimization and Convex Algebraic Geometry. Society for Industrial and Applied Mathematics, Philadelphia (2013)
Boyd, S., Kim, S.J., Patil, D., Horowitz, M.: Digital circuit optimization via geometric programming. Oper. Res. 53, 899–932 (2005)
Boyd, S., Kim, S.J., Vandenberghe, L., Hassibi, A.: A tutorial on geometric programming. Optim. Eng. 8, 67–127 (2007)
Chandrasekaran, V., Shah, P.: Conic geometric programming. In: Proceedings of the Conference on Information Sciences and Systems (2014)
Chandrasekaran, V., Shah, P.: Relative entropy relaxations for signomial optimization. SIAM J. Optim. (2014)
Chiang, M.: Geometric programming for communication systems. Found. Trends Commun. Inf. Theory 2, 1–154 (2005)
Chiang, M., Boyd, S.: Geometric programming duals of channel capacity and rate distortion. IEEE Trans. Inf. Theory 50, 245–258 (2004)
Cover, T., Thomas, J.: Elements of Information Theory. Wiley, New York (2006)
Cox, D.R.: The regression analysis of binary sequences. J. R. Stat. Soc. 20, 215–242 (1958)
Dinkel, J.J., Kochenberger, G.A., Wong, S.N.: Entropy maximization and geometric programming. Environ. Plan. A 9, 419–427 (1977)
Drew, J.H., Johnson, C.R.: The maximum permanent of a 3-by-3 positive semidefinite matrix, given the eigenvalues. Linear Multilinear Algebra 25, 243–251 (1989)
Duffin, R.J., Peterson, E.L., Zener, C.M.: Geometric Programming: Theory and Application. Wiley, New York (1967)
Egorychev, G.P.: Proof of the Van der Waerden conjecture for permanents (english translation; original in russian). Sib. Math. J. 22, 854–859 (1981)
El Ghaoui, L., Lebret, H.: Robust solutions to least-squares problems with uncertain data. SIAM J. Matrix Anal. Appl. 18, 1035–1064 (1997)
Falikman, D.I.: Proof of the Van der Waerden conjecture regarding the permanent of a doubly stochastic matrix (english translation; original in russian). Math. Notes 29, 475–479 (1981)
Glineur, F.: An extended conic formulation for geometric optimization. Found. Comput. Decis. Sci. 25, 161–174 (2000)
Golden, S.: Lower bounds for the Helmholtz function. Phys. Rev. Ser. II 137, B1127–B1128 (1965)
Gonalves, D.S., Lavor, C., Gomes-Ruggiero, M.A., Cesrio, A.T., Vianna, R.O., Maciel, T.O.: Quantum state tomography with incomplete data: maximum entropy and variational quantum tomography. Phys. Rev. A 87 (2013)
Gouveia, J., Parrilo, P., Thomas, R.: Lifts of convex sets and cone factorizations. Math. Oper. Res. 38, 248–264 (2013)
Grone, R., Johnson, C.R., Eduardo, S.A., Wolkowicz, H.: A note on maximizing the permanent of a positive definite hermitian matrix, given the eigenvalues. Linear Multilinear Algebra 19, 389–393 (1986)
Gurvits, L.: Van der Waerden/Schrijver-Valiant like conjectures and stable (aka hyperbolic) homogeneous polynomials: one theorem for all. Electron. J. Comb. 15 (2008)
Gurvits, L., Samorodnitsky, A.: A deterministic algorithm for approximating the mixed discriminant and mixed volume, and a combinatorial corollary. Discrete Comput. Geom. 27, 531–550 (2002)
Han, S., Preciado, V.M., Nowzari, C., Pappas, G.J.: Data-Driven Network Resource Allocation for Controlling Spreading Processes. IEEE Trans. Netw. Sci. Eng. 2(4), 127–38 (2015)
Hastie, T., Tibshirani, R., Friedman, J.: The Elements of Statistical Learning. Springer, Berlin (2008)
Hellwig, K., Krauss, K.: Operations and measurements II. Commun. Math. Phys. 16, 142–147 (1970)
Helton, J.W., Nie, J.: Sufficient and necessary conditions for semidefinite representability of convex hulls and sets. SIAM J. Optim. 20, 759–791 (2009)
Holevo, A.S.: The capacity of the quantum channel with general signal states. IEEE Trans. Inf. Theory 44, 269–273 (1998)
Hsiung, K.L., Kim, S.J., Boyd, S.: Tractable approximate robust geometric programming. Optim. Eng. 9, 95–118 (2008)
Jaynes, E.T.: Information theory and statistical mechanics. Phys. Rev. Ser. II 106, 620–630 (1957)
Jerrum, M., Sinclair, A., Vigoda, E.: A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries. J. ACM 51, 671–697 (2004)
Kulis, B., Sustik, M., Dhillon, I.: Low-rank kernel learning with Bregman matrix divergences. J. Mach. Learn. Res. 10, 341–376 (2009)
Lieb, E.: Convex trace functions and the Wigner–Yanase–Dyson conjecture. Adv. Math. 11, 267–288 (1973)
Linial, N., Samorodnitsky, A., Wigderson, A.: A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents. Combinatorica 20, 545–568 (2000)
Lobo, M., Vandenberghe, L., Boyd, S., Lebret, H.: Applications of second-order cone programming. Linear Algebra Appl. 284, 193–228 (1998)
Minc, H.: Permanents. Cambridge University Press, Cambridge (1984)
Nesterov, Y., Nemirovski, A.: Interior-Point Polynomial Algorithms in Convex Programming. Society of Industrial and Applied Mathematics, Philadelphia (1994)
Nielsen, M., Chuang, I.: Quantum Computation and Quantum Information. Cambridge University Press, Cambridge (2011)
Potchinkov, A.W., Reemsten, R.M.: The design of FIR filters in the complex plane by convex optimization. Signal Process. 46, 127–146 (1995)
Prajna, S., Jadbabaie, A.: Safety Verification of Hybrid Systems Using Barrier Certificates. In: Hybrid Systems: Computation and Control, pp. 477–492. Springer (2004)
Rockafellar, R.T.: Convex Analysis. Princeton University Press, Princeton (1970)
Schumacher, B., Westmoreland, M.D.: Sending classical information via noisy quantum channels. Phys. Rev. A 56, 131–138 (1997)
Scott, C.H., Jefferson, T.R.: Trace optimization problems and generalized geometric programming. J. Math. Anal. Appl. 58, 373–377 (1977)
Shor, P.W.: Capacities of quantum channels and how to find them. Math. Program. B 97, 311–335 (2003)
Thompson, C.J.: Inequality with applications in statistical mechanics. J. Math. Phys. 6, 1812–1813 (1965)
Valiant, L.: The complexity of computing the permanent. Theor. Comput. Sci. 8, 189–201 (1979)
Vandenberghe, L., Boyd, S., Wu, S.: Determinant maximization with linear matrix inequality constraints. SIAM J. Matrix Anal. Appl. 19, 499–533 (1998)
Wall, T., Greening, D., Woolsey, R.: Solving complex chemical equilibria using a geometric programming based technique. Oper. Res. 34, 345–355 (1986)
Yazarel, H., Pappas, G.: Geometric programming relaxations for linear system reachability. In: Proceedings of the American Control Conference (2004)
Acknowledgments
The authors would like to thank Pablo Parrilo and Yong-Sheng Soh for helpful conversations, and Leonard Schulman for pointers to the literature on Von-Neumann entropy. Venkat Chandrasekaran was supported in part by National Science Foundation Career award CCF-1350590 and Air Force Office of Scientific Research grant FA9550-14-1-0098.
Author information
Authors and Affiliations
Corresponding author
Appendix
Appendix
The second-order cone \(L_2 \subset \mathbb {R}^3\) from (5) can be written as:
Combining this reformulation with the next result gives us the description (6).
Proposition 6
We have that \(\begin{pmatrix} a &{} c \\ c &{} b\end{pmatrix} \in \mathbb {S}^2_+\) if and only if there exists \(\nu \in \mathbb {R}_+\) such that:
Proof
We have that \(\begin{pmatrix} a &{} c \\ c &{} b\end{pmatrix} \in \mathbb {S}^2_+\) if and only if \(a \bar{\mathbf {z}}_1^2 + b \bar{\mathbf {z}}_2^2 + 2c \bar{\mathbf {z}}_1 \bar{\mathbf {z}}_2 \ge 0, ~ \forall \bar{\mathbf {z}} \in \mathbb {R}^2\). This latter condition can in turn be rewritten to obtain the following reformulation:
Each of these inequalities with universal quantifiers can be reformulated by appealing to GP duality. Specifically, based on the change of variables \(\mathbf {w}_i \leftarrow \log (\mathbf {z}_i), i=1,2\), which is commonly employed in the GP literature [11, 20], we have from (44) that \(\begin{pmatrix} a &{} c \\ c &{} b\end{pmatrix} \in \mathbb {S}^2_+\) if and only if:
As the optimization problem on the left-hand-side is a GP for \(a,b \in \mathbb {R}_+\), we can appeal to convex duality to conclude that
Combining this result with (45), we have that \(\begin{pmatrix} a &{} c \\ c &{} b\end{pmatrix} \in \mathbb {S}^2_+\) if and only if:
This concludes the proof. \(\square \)
Rights and permissions
About this article
Cite this article
Chandrasekaran, V., Shah, P. Relative entropy optimization and its applications. Math. Program. 161, 1–32 (2017). https://doi.org/10.1007/s10107-016-0998-2
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10107-016-0998-2
Keywords
- Matrix permanent
- Robust optimization
- Dynamical systems
- Quantum information
- Quantum channel capacity
- Shannon entropy
- Von-Neumann entropy
- Araki–Umegaki relative entropy
- Golden–Thompson inequality
- Optimization over non-commuting variables