dual cones and conjugate functions

[chriscoey]

Hi, sorry for the noise but I'm interested in knowing: (1) the dual cones of your recognized cones, and (2) the conjugate functions of your recognized convex functions. I didn't see this in the reference in the readme, so I'm wondering if you can point to any sources that might help me with this.

FYI @lkapelevich and I work on a generic conic interior point solver https://github.com/chriscoey/Hypatia.jl and we want to support some of these cones (and cones constructed from your functions). We think we can construct SC barriers for some cones (eg a matrix entropy perspective cone), and for others we can construct non-SC but probably "good-enough" barriers (eg matrix relative entropy cone).

Thanks!

[rileyjmurray]

I'm not involved with this project, but I have some useful information for you anyway.

• quantum_entr(X) -- this has a known barrier; it's been mentioned in a couple papers, see https://arxiv.org/abs/1804.06925.
• quantum_rel_entr(X,Y) -- this does not have a known self-concordant barrier. If you look at https://arxiv.org/abs/1804.06925 you'll find this function is mentioned but no actual claim is made about an s.c. barrier. The implication from that paper is that one can try the naive matrix extension of the l.h.s.c. barrier for (scalar) relative entropy and hopefully get good results. The only paper that mentions efficient algorithms for quantum relative entropy is http://www.optimization-online.org/DB_HTML/2019/04/7165.html, which uses an alternating minimization scheme over the matrix variables. I think there is no known closed-form expression for the dual to the cone induced by this function.
• op_rel_entr_epi_cone. At present, there is no known closed-form for the dual to this cone. There is also no known l.h.s.c. barrier.

I have more thoughts on the above points (and how they might fit into Hypatia) if you'd like to discuss by email, @chriscoey and @lkapelevich.

Regarding the matrix geometric-means: those have explicit semidefinite formulations when the parameter t is rational, so nominally finding expressions for induced dual cones is doable.

[hfawzi]

Thanks Riley for your answer. To add to it: - the von Neumann entropy (quantum_entr) is a particular example of a spectral function, for which we know a lot. See e.g., https://people.orie.cornell.edu/aslewis/publications/96-convex.pdf for a simple expression of the conjugate. The book of Ben-Tal and Nemirovski (Lectures on Modern Convex Optimization) also has a section on such functions. - Having a way to natively handle the quantum relative entropy would be great for quantum applications, as the SDP approximation provided in cvxquad is quite large. The same is true for the functions (A,B) \mapsto tr(A^p B^{1-p}) where p \in [0,1] which are concave jointly in (A,B) [Lieb's theorem].

…

On Sun, Dec 20, 2020 at 4:28 PM rileyjmurray ***@***.***> wrote: I'm not involved with this project, but I have some useful information for you anyway. - quantum_entr(X) -- this has a known barrier; it's been mentioned in a couple papers, see https://arxiv.org/abs/1804.06925. - quantum_rel_entr(X,Y) -- this does not have a known self-concordant barrier. If you look at https://arxiv.org/abs/1804.06925 you'll find this function is mentioned but no actual claim is made about an s.c. barrier. The implication from that paper is that one can try the naive matrix extension of the l.h.s.c. barrier for (scalar) relative entropy and hopefully get good results. The only paper that mentions efficient algorithms for quantum relative entropy is http://www.optimization-online.org/DB_HTML/2019/04/7165.html, which uses an alternating minimization scheme over the matrix variables. I think there is no known closed-form expression for the dual to the cone induced by this function. - op_rel_entr_epi_cone. At present, there is no known closed-form for the dual to this cone. There is also no known l.h.s.c. barrier. I have more thoughts on the above points (and how they might fit into Hypatia) if you'd like to discuss by email, @chriscoey <https://github.com/chriscoey> and @lkapelevich <https://github.com/lkapelevich>. Regarding the matrix geometric-means: those have explicit semidefinite formulations when the parameter t is rational, so nominally finding expressions for induced dual cones is doable. — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <#4 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AD7SHIHIV45WKVPLEFPR2TDSVYQ2DANCNFSM4VDETX7A> .

[hfawzi]

FYI, we have just posted a new paper on the arxiv giving self-concordant barriers, with optimal barrier parameter, for various matrix relative entropy cones:
https://arxiv.org/abs/2205.04581 (joint with James Saunderson)

[ericphanson]

Congrats @hfawzi! That's awesome!

[chriscoey]

Very nice! We did some related (but simpler) cones in https://arxiv.org/abs/2103.04104

[hfawzi]

Thanks for the reference.
As we comment at the end of our paper, our results actually give s.c. barrier for perspectives of trace functions, ie., (x,y) -> y*tr f(X/y) whenever f is operator convex (without requiring f' is operator monotone). What would be interesting is to prove this just assuming that f is convex (and not necessarily op. convex).