add more primitive cone types with known barriers

[chriscoey]

• nonnegative (LP)
• dual (moment) sum of squares (interpolation-based SOS/WSOS)
• second-order
• exponential (3-D)
• rotated SOC
• PSD
• L_inf epigraph (useful for variable box bounds) and thus its dual cone the L_1 epigraph
• power (n-D) i.e. generalized geomean using AD
• epigraph of spectral norm (largest singular value) for real matrices and thus its dual cone the nuclear norm (sum of singular values) epigraph can improve barrier derivative evaluation using link
• hermitian PSD (see https://hal.inria.fr/hal-01497173/document)
• matrix pencil / LMI cone
• Siegel cone
• root-det (barrier?)
• homogenized log-det (barrier?)
• quantum (relative) entropy (see https://arxiv.org/pdf/1804.06925.pdf)
• `Fractional-quadratic' cone from S9.6.3 of https://www2.isye.gatech.edu/~nemirovs/Lect_IPM.pdf
• other standard operator norms (with L1 or Linf)?
• matrix functions of eigenvalues eg eigmin, sum of eigs
• nonnegative polynomials in other basis (monomial, chebyshev for univariate, etc)
• epigraph of perspective of sum of exponentials (n-dim exp cone, can be used for log-sum-exp modeling)
• p-norm
• finite autocorrelation sequences
• nonnegative trigonometric polynomials? etc
• hyperbolic polynomial cones (Guler)
• doubly nonnegative cone (primal barrier known but not dual barrier - mentioned in Skajaa & Ye)
• log-sum-exp cone? see Boyd and Vandenberghe example 3.25

Some of these are not defined in MOI but should be. I am willing to bet that performance will be much better with the n-D power cone than with n 3-D power cones, for example. Similarly for p-norm, log-sum-exp, entropy.

[chriscoey]

some references (a few a bit theoretical)

• https://link.springer.com/content/pdf/10.1007%2Fs002080010009.pdf
• https://arxiv.org/pdf/1411.2129.pdf
• https://arxiv.org/pdf/1705.06671.pdf
• https://uwspace.uwaterloo.ca/bitstream/handle/10012/12209/Karimi_Mehdi.pdf?sequence=3
• https://link.springer.com/content/pdf/10.1007%2Fs11590-017-1145-6.pdf
• https://arxiv.org/pdf/1411.2129.pdf
• https://link.springer.com/article/10.1007/s10208-018-9385-0
• https://epubs.siam.org/doi/pdf/10.1137/140998950
• https://pdfs.semanticscholar.org/7648/bd172d91ee1570bbada42d772961e0dc3e78.pdf
• s6.3.5 of http://yintat.com/pdf/thesis.pdf
• https://link.springer.com/content/pdf/10.1007/978-1-4757-3216-0_17.pdf
• http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.29.3082&rep=rep1&type=pdf
• https://thesis.library.caltech.edu/10048/1/Bruer-John-2017-thesis.pdf
• https://arxiv.org/pdf/1310.0899.pdf
• https://www.math.uwaterloo.ca/~ltuncel/publications/corr2007-03.pdf
• https://www2.isye.gatech.edu/~nemirovs/cone-free-mp.pdf
• https://perso.uclouvain.be/francois.glineur/files/theses/Chares-PhD-thesis-2007.pdf
• https://rucore.libraries.rutgers.edu/rutgers-lib/33968/PDF/1/play/
• https://perso.uclouvain.be/paul.vandooren/ThesisHachez.pdf
• http://www.seas.ucla.edu/~vandenbe/publications/alv01b.pdf
• https://pdfs.semanticscholar.org/9fd7/808743f5bb6dbbb64fda3a4a887acc64d69e.pdf
• https://www.microsoft.com/en-us/research/uploads/prod/2018/01/powercones-5a71024933c4b.pdf
• http://www.optimization-online.org/DB_FILE/2006/03/1355.pdf
• http://www2.ims.nus.edu.sg/Programs/012opti/files/talk_yosise1.pdf
• https://web.stanford.edu/group/SOL/dissertations/ThesisAkleAdobe-augmented.pdf
• http://www-ljk.imag.fr/membres/Roland.Hildebrand/vortrag260416.pdf
• http://www.optimization-online.org/DB_FILE/2012/05/3474.pdf
• https://arxiv.org/pdf/1507.02528.pdf
• https://link.springer.com/content/pdf/10.1007/s10107-008-0260-7.pdf
• https://hal.archives-ouvertes.fr/tel-01570016/file/HdR_Thesis.pdf
• https://drum.lib.umd.edu/bitstream/handle/1903/3977/umi-umd-3854.pdf?sequence=1

[chriscoey]

@blegat have you ever heard of a log-homogeneous self-concordant barrier for the log-det cone?

[blegat]

Log-det is the barrier for the PSD cone. If the log-det is in the objective function, we can leave it as is since it is self-concordant. For a constraint log-det Q <= t I don't know

[blegat]

I just asked François Glineur about the log-det barrier.

There is a paper of Lewis and Sendov which gives a construction for a barrier with parameter n^2 in the case t=1:
Self-concordant barriers for hyperbolic means
We could homogenize to get t different from one but barriers of homogenization is not well understood.

There is also a paper from Nesterov (apparently not published) which solves it in the case of X diagonal (i.e. the det is the product of positive variables) with a better parameter (n+1) :
Constructing self-concordant barriers for convex cones.
He thinks that it should be possible without too much trouble to generalize it to the matrix case (i.e. non-diagonal).

[chriscoey]

thanks Benoit, it is good to have a record of this here

[chriscoey]

@juan-pablo-vielma @blegat see the list I am maintaining above at #11 (comment)

the items with "(barrier?)" it may be worth discussing with Nesterov, Glineur etc in order to get the barriers if they are known. specifically, we just need the primal barrier gradient and inverse hessian product.

[chriscoey]

Some more cones to implement: https://github.com/hfawzi/cvxquad