∎

11institutetext: Lea Kapelevich, Corresponding author 22institutetext:
Operations Research Center, MIT
Cambridge, MA, USA
<EMAIL_ADDRESS>33institutetext: Erling D. Andersen 44institutetext: MOSEK ApS
Copenhagen, Denmark
<EMAIL_ADDRESS>55institutetext: Juan Pablo Vielma 66institutetext:
Google Research and MIT Sloan School of Management
Cambridge, MA, USA
<EMAIL_ADDRESS>
# Computing Conjugate Barrier Information for Nonsymmetric Cones

Lea Kapelevich  Erling D. Andersen  Juan Pablo Vielma

(Received: date / Accepted: date)

###### Abstract

The recent interior point algorithm by Dahl and Andersen dahl2021primal  for
nonsymmetric cones as well as earlier works nesterov2012towards ;
nesterov1999infeasible  require derivative information from the conjugate of
the barrier function of the cones in the problem. Besides a few special cases,
there is no indication of when this information is efficient to evaluate. We
show how to compute the gradient of the conjugate barrier function for seven
useful nonsymmetric cones. In some cases this is helpful for deriving closed-
form expressions for the inverse Hessian operator for the primal barrier.

###### Keywords:

conjugate barrier function nonsymmetric cones interior point

###### MSC:

90C25 90C51

This preprint has not undergone all peer review and post-submission
improvements or corrections. The Version of Record of this article is
published in the Journal of Optimization Theory and Applications, and is
available online at https://doi.org/10.1007/s10957-022-02076-1.

##  1 Introduction

Many convex optimization problems can be expressed as the minimization of a
linear function over an intersection of _symmetric_ cones. These include the
nonnegative, (rotated) second order, and positive semidefinite cones. Many
popular solvers for programming with symmetric cones implement primal-dual
interior point methods (PDIPMs) specialized for these cones only (e.g.
borchers1999csdp ; yamashita2003implementation ; vandenberghe2010cvxopt ).
These specialized PDIPMs enjoy properties such as efficiently computable
_symmetric_ search directions (that ensure the algorithm is invariant to
exchanging of roles of the primal and dual programs), which usually rely on
forming so-called _scaling matrices_ for symmetric cones, first suggested by
nesterov1997self . In addition, the symmetric cones are self-dual and admit
barrier functions with highly efficient oracles for PDIPMs. Unfortunately,
many properties of symmetric cones are not straightforward to generalize for
other conic sets. In spite of the fact that many useful sets can only be
modeled directly or can be modeled more efficiently with cones that are not
symmetric, there are significantly fewer implementations of algorithms for
_nonsymmetric_ cones.

Early algorithmic frameworks for nonsymmetric cones have been suggested by
nesterov1999infeasible  and nesterov2012towards , but have not been
implemented by any solver we are aware of. The high-level algorithms in both
papers require information relating to the conjugates of the barrier functions
of the cones in the problem, and it is not clear when this can be evaluated
efficiently. Specifically, the only nonsymmetric cones with known, efficient
procedures for evaluating the conjugate of the barrier function (or its
gradient) are the three-dimensional exponential cone serrano2015algorithms ,
the three-dimensional power cone nesterov2012towards , and the cone of sparse
positive semidefinite matrices with chordal sparsity andersen2013logarithmic .
Additionally, nesterov1999infeasible  requires solving a linear system in each
iteration that is twice the size of the linear systems that arise in symmetric
algorithms.

More recent nonsymmetric algorithms bypass some of the aforementioned issues.
These include the algorithm by Skajaa and Ye skajaa2015homogeneous , which has
been implemented in the solvers Alfonso papp2021alfonso  and Hypatia
coey2020solving . A key advantage of this algorithm is that it requires very
few oracles for each primal cone in the problem, and doesn’t require oracles
relating to the conjugate of the primal barrier.

In this paper we are primarily motivated by the alternative algorithm of Dahl
and Andersen dahl2021primal , which is implemented by the MOSEK solver
mosek2020modeling . The algorithm is based on a technique by
tunccel2001generalization ; myklebust2014interior  which generalizes the
concept of scaling matrices from symmetric cones. Like the algorithm of
skajaa2015homogeneous , the linear systems solved in each iteration are equal
in size to those arising in symmetric algorithms. Unlike the algorithm of
skajaa2015homogeneous , the gradient of the conjugate barrier is required to
compute search directions. However, the search directions satisfy a number of
desirable properties such as ensuring that the violations of residuals and
complementarity conditions decrease at the same rate. The authors also propose
a neighborhood that allows stepping further away from the central path
compared to skajaa2015homogeneous , although there is no proof of polynomial
time convergence. One might expect, owing to the use of conjugate barrier
information, that the search directions of dahl2021primal  would allow
convergence in fewer iterations than the search directions of
skajaa2015homogeneous .

The search directions in the algorithm by dahl2021primal  relate to those from
symmetric algorithms as follows. Given a primal-dual pair of points $(w,r)$
for a symmetric cone, there exists a unique scaling matrix $T$ satisfying the
secant equations $r=Tw$ and $g(w)=Tg^{\ast}(r)$, where $g$ and $g^{\ast}$
denote the gradients of the primal barrier and its conjugate nesterov1997self
; nesterov1998primal . A key idea of myklebust2014interior ; dahl2021primal
is to construct a general positive definite matrix for any cone, satisfying
the two secant equations. The authors choose a specific formula for this
scaling matrix that requires calculating the Hessian of a primal barrier
function, and adding BFGS updates to the Hessian. These low rank updates
include adding multiples of the conjugate gradient.

The conjugate gradient can always be evaluated via a numerical procedure (e.g.
applying Newton’s method to an optimization problem), but this generic
approach is computationally slow and can be numerically challenging. In
particular, it requires applying the inverse Hessian of the primal barrier in
each iteration (which can become a new bottleneck in a PDIPM). A large number
of damped Newton iterations may be necessary to get near the region of
quadratic convergence towards the end of the PDIPM, when the distance to the
cone boundary is small. Our aim is to show efficient methods of calculating
conjugate gradients for seven useful nonsymmetric cones, which an interior
point solver could support. Aside from their use in the algorithm by
dahl2021primal , procedures for evaluating conjugate gradients are useful due
to their applications in the frameworks by nesterov1999infeasible ;
nesterov2012towards . The cones for which we are able to demonstrate efficient
procedures for evaluating conjugate gradients are:

Logarithm cone,

the hypograph of the perspective of the sum of logarithms.

Log-determinant cone,

the hypograph of the perspective of the log-deter-minant function.

Hypograph power cone,

the hypograph of the power mean function.

Root-determinant cone,

the hypograph of the $d$th-root-determinant function.

Radial power cone,

the generalized power cone by (chares2009cones, , Section 3.1.2).

Infinity norm cone,

the epigraph of the $\ell_{\infty}$ norm function.

Spectral norm cone,

the epigraph of the spectral norm function.

In all cases, computing conjugate gradients can be reduced to simple numerical
procedures (e.g. univariate root-finding). For some special cases (e.g. where
the hypograph or radial power cones are parametrized by equal powers), the
conjugate gradients can be written as closed-form expressions.

Our conjugate gradient evaluations lead to a second result. By differentiating
the procedure to calculate the conjugate gradients we are able to derive
closed-form expressions for the inverse Hessian of the primal barrier. This is
useful for measuring central path proximity and some of the linear system
methods suggested by coey2021performance . The inverse Hessian is already
known for five of the cones above coey2021conic ; coey2022thesis , so we only
show it for the hypograph and radial power cones.

##  2 Preliminaries

###  2.1 Notation

We use $\mathbb{R}_{+}^{d}$, $\mathbb{R}_{++}^{d}$, $\mathbb{R}_{-}^{d}$, and
$\mathbb{R}_{--}^{d}$ to denote the $d$-dimensional vectors of nonnegative,
positive, nonpositive, and negative reals respectively. Likewise,
$\mathbb{S}_{+}^{d}$ and $\mathbb{S}_{++}^{d}$ are the positive semidefinite
and positive definite matrices respectively with side dimension $d$. For a
natural number $d$, we define the index set $\llbracket
d\rrbracket\coloneqq\\{1,2,\ldots,d\\}$. $1_{P}$ is the indicator function,
that is equal to one if statement $P$ is true and zero otherwise. For a set
$C$, $\operatorname{cl}(C)$ and $\operatorname{int}(C)$ denote the closure and
interior of $C$ respectively. We use round parentheses, e.g. $(a,b,c)$ for
Cartesian products of vectors or matrices, $\langle\cdot,\cdot\rangle$ for an
inner product between vectors or matrices, and $e$ to denote a vector of ones.
$V^{\top}$ is the transpose of $V$ with respect to
$\langle\cdot,\cdot\rangle$. Throughout this paper, division and
multiplication between vectors should be interpreted as componentwise. The
operator $\operatorname{Diag}$ maps a vector to a matrix with the vector on
the diagonal. We write $g(w)$ or $H(w)$ to denote gradients or Hessians
evaluated at $w$, and use subscripts to refer to partial derivatives.

###  2.2 Cones and Barrier Functions

A proper cone $\mathcal{K}$ is closed, convex, pointed, and full-dimensional.
The _dual cone_ of $\mathcal{K}$ is
$\mathcal{K}^{\ast}\coloneqq\\{r\in\mathbb{R}^{d}:\langle w,r\rangle\geq
0,\forall w\in\mathcal{K}\\}$. $\mathcal{K}^{\ast}$ is a proper cone if and
only if $\mathcal{K}$ is a proper cone.

Analysis of conic interior point methods relies on associating with each cone
a _logarithmically-homogeneous, self-concordant barrier_ (LHSCB). Following
(nesterov1994interior, , Sections 2.3.1 and 2.3.3),
$f:\operatorname{int}(\mathcal{K})\to\mathbb{R}$ is a $\nu$-LHSCB for
$\mathcal{K}$, where $\nu\geq 1$ is the _LHSCB parameter_ , if it satisfies
$f(w_{i})\to\infty$ along every sequence
$w_{i}\in\operatorname{int}(\mathcal{K})$ converging to the boundary of
$\mathcal{K}$, and:

$\displaystyle\big{\lvert}\nabla^{3}f(w)[r,r,r]\big{\rvert}$
$\displaystyle\leq 2\bigl{(}\nabla^{2}f(w)[r,r]\bigr{)}^{3/2}$
$\displaystyle\forall w\in\operatorname{int}(\mathcal{K}),r\in\mathbb{R}^{d},$
(1a) $\displaystyle f(\theta w)$ $\displaystyle=f(w)-\nu\log(\theta)$
$\displaystyle\forall
w\in\operatorname{int}(\mathcal{K}),\theta\in\mathbb{R}.$ (1b)

As a consequence of (1b), the gradient $g$ of $f$ satisfies (nesterov1997self,
, Equation (2.5)):

$\langle-g(w),w\rangle=\nu\quad\forall w\in\mathcal{K}.$ (2)

For the LHSCB $f$, we define the convex conjugate, $f^{\ast}$, as the
function:

$f^{\ast}(r)\coloneqq\textstyle\sup_{w\in\operatorname{int}(\mathcal{K})}\\{-\langle
r,w\rangle-f(w)\\}.$ (3)

In fact, $f^{\ast}$ is an LHSCB for $\mathcal{K}^{\ast}$ (nesterov1997self, ,
Equation (2.6)) and we refer to it as the _conjugate barrier_. The gradient
$g^{\ast}$ of $f^{\ast}$ may be defined from the unique solutions to the
optimization problem in 3:

$g^{\ast}(r)=-\operatorname{argsup}_{w\in\operatorname{int}(\mathcal{K})}\\{-\langle
r,w\rangle-f(w)\\}.$ (4)

From 3, 4 and 2:

$f^{\ast}(r)=-\langle
r,-g^{\ast}(r)\rangle-f(-g^{\ast}(r))=-\nu-f(-g^{\ast}(r)).$ (5)

We refer to $g^{\ast}$ as the _conjugate gradient_ (which has no relation to
the method of conjugate gradients). The negative gradients of LHSCBs $f$ and
$f^{\ast}$ are bijective linear maps between $\mathcal{K}$ and
$\mathcal{K}^{\ast}$. In particular (myklebust2014interior, , Theorem 2.5):

$-g^{\ast}(-g(w))=w\quad\forall
w\in\mathcal{K},\quad-g(-g^{\ast}(r))=r\quad\forall r\in\mathcal{K}^{\ast}.$
(6)

Note that 6 characterizes the gradient and conjugate gradient maps as negative
inverses of each other.

Some of the LHSCBs we use are related to _unitarily invariant_ functions
lewis1995convex . Let $W=U_{W}\operatorname{Diag}(\sigma_{W})V_{W}^{\top}$ be
the singular value decomposition of $W\in\mathbb{R}^{d_{1}\times d_{2}}$, such
that $\sigma_{W}\in\mathbb{R}^{d_{1}}$. If $W$ is symmetric, then $\sigma_{W}$
are the eigenvalues of $W$ and $U_{W}=V_{W}$. Suppose
$F:\mathbb{R}^{d_{1}\times d_{2}}\to\mathbb{R}$ is a function given by
$F(W)=f(\sigma_{W})$, where $f\in\mathbb{R}^{d_{1}}\to\mathbb{R}$ is some
symmetric function (invariant to the order of its inputs). Then $F$ is
unitarily invariant. Let $G$ and $g$ denote the gradients of $F$ and $f$. In
Sections 3.1, 3.2 and 3.4, we use (lewis1995convex, , Theorem 3.1):

$G(W)=U_{W}\operatorname{Diag}(g(\sigma_{W}))V_{W}^{\top}.$ (7)

##  3 Conjugate Gradients

In Sections 3.1 to 3.4 we offer efficient procedures for evaluating conjugate
gradients. We defer some derivations to Section 5 to ease readability.

###  3.1 Logarithm Cone and Log-determinant Cone

Let $\varphi:\mathbb{R}^{d}_{++}\to\mathbb{R}$ be the function
$\varphi(w)\coloneqq\textstyle\sum_{i\in\llbracket d\rrbracket}\log w_{i}$.
Define the _logarithm_ cone:

$\mathcal{K}_{\log}\coloneqq\operatorname{cl}\bigl{\\{}(u,v,w)\in\mathbb{R}\times\mathbb{R}_{++}\times\mathbb{R}_{++}^{d}:u\leq
v\varphi\bigl{(}\tfrac{w}{v}\bigr{)}\bigr{\\}},$

which admits the $(2+d)$-LHSCB (coey2021conic, , Section 6):

$f(u,v,w)=-\log\bigl{(}v\varphi\bigl{(}\tfrac{w}{v}\bigr{)}-u\bigr{)}-\log(v)-\textstyle\sum_{i\in\llbracket
d\rrbracket}\log(w_{i}).$

The dual cone is given by (coey2020solving, , Section 5.5):

$\mathcal{K}_{\log}^{\ast}\coloneqq\operatorname{cl}\bigl{\\{}(p,q,r)\in\mathbb{R}_{--}\times\mathbb{R}\times\mathbb{R}^{d}_{++}:q\geq
p\textstyle\sum_{i\in\llbracket
d\rrbracket}\log\bigl{(}-\tfrac{r_{i}}{p}\bigr{)}+pd\bigr{\\}}.$

Let $\omega$ denote the Wright omega function corless2002wright , which can be
well approximated in $O(1)$ time and satisfies for all real $\beta$:

$\omega(\beta)+\log(\omega(\beta))=\beta.$ (8)

The Wright omega function is used in (serrano2015algorithms, , Chapter 8) for
deriving the conjugate barrier of a three-dimensional variant of
$\mathcal{K}_{\log}$ and in (nemirovski2005cone, , Section 7.1) for the
conjugate barrier of the epigraph of the univariate entropy function.

###### Proposition 1

The conjugate gradient at
$(p,q,r)\in\operatorname{int}(\mathcal{K}_{\log}^{\ast})$ has components:

$\displaystyle g^{\ast}_{p}$
$\displaystyle=\tfrac{-d-2+\nicefrac{{q}}{{p}}+2\bar{\omega}}{p(1-\bar{\omega})},$
(9a) $\displaystyle g^{\ast}_{q}$
$\displaystyle=-\tfrac{1}{p(1-\bar{\omega})},$ (9b) $\displaystyle
g^{\ast}_{r_{i}}$ $\displaystyle=\tfrac{\bar{\omega}}{r_{i}(1-\bar{\omega})}$
$\displaystyle\forall i\in\llbracket d\rrbracket,$ (9c)

where, $\bar{\omega}\coloneqq
d\cdot\omega\bigl{(}\nicefrac{{1}}{{d}}\bigl{(}1+d-\nicefrac{{q}}{{p}}+\textstyle\sum_{i\in\llbracket
d\rrbracket}\log(-\nicefrac{{r_{i}}}{{p}})\bigr{)}-\log(d)\bigr{)}$.

The proof is given in Section 5.1. By substituting 9 in 5, we obtain the
conjugate barrier:

$f^{\ast}(p,q,r)=-2-d-2\log(-p)-\log\Bigl{(}\tfrac{(\bar{\omega}-1)^{d+1}}{\bar{\omega}^{d}}\Bigr{)}-\textstyle\sum_{i\in\llbracket
d\rrbracket}\log(r_{i}).$

The conjugate gradient for $\mathcal{K}_{\log}$ can be easily modified to
obtain a conjugate gradient for the _log-determinant cone_ (coey2020solving, ,
Section 5.6):

$\mathcal{K}_{\operatorname{logdet}}\coloneqq\operatorname{cl}\bigl{\\{}(u,v,W)\in\mathbb{R}\times\mathbb{R}_{++}\times\mathbb{S}^{d}_{++}:u\leq
v\operatorname{logdet}(\nicefrac{{W}}{{v}})\bigr{\\}},$

which has the dual:

$\mathcal{K}_{\operatorname{logdet}}^{\ast}\coloneqq\operatorname{cl}\bigl{\\{}(p,q,R)\in\mathbb{R}_{--}\times\mathbb{R}\times\mathbb{S}^{d}_{++}:q\geq
p\operatorname{logdet}(-\nicefrac{{R}}{{p}})+pd\bigr{\\}}.$

Let $W=U_{W}\operatorname{Diag}(\lambda_{W})U_{W}^{\top}$ be the
eigendecomposition of $W$. $\mathcal{K}_{\operatorname{logdet}}$ admits the
$(2+d)$-LHSCB (coey2021conic, , Section 6):

$F(u,v,W)=-\log(v\varphi(\nicefrac{{\lambda_{W}}}{{v}})-u)-\log(v)-\textstyle\sum_{i\in\llbracket
d\rrbracket}\log(\lambda_{W,i})=f(u,v,\lambda_{W}).$

###### Proposition 2

Let
$(p,q,R)\in\operatorname{int}(\mathcal{K}_{\operatorname{logdet}}^{\ast})$,
let $R=U_{R}\operatorname{Diag}(\lambda_{R})U_{R}^{\top}$ be the
eigendecomposition of $R$, and let $\bar{\Omega}\coloneqq
d\cdot\omega\bigl{(}\nicefrac{{1}}{{d}}\bigl{(}1+d-\nicefrac{{q}}{{p}}+\textstyle\sum_{i\in\llbracket
d\rrbracket}\log(-\nicefrac{{\lambda_{R,i}}}{{p}})\bigr{)}-\log(d)\bigr{)}$.
The conjugate gradient $G^{\ast}$ has components:

$\displaystyle G^{\ast}_{p}$
$\displaystyle=g^{\ast}_{p}(p,q,\lambda_{R})=\tfrac{-d-2+\nicefrac{{q}}{{p}}+2\bar{\Omega}}{p(1-\bar{\Omega})},$
$\displaystyle G^{\ast}_{q}$
$\displaystyle=g^{\ast}_{q}(p,q,\lambda_{R})=-p^{-1}(1-\bar{\Omega})^{-1},$
$\displaystyle G^{\ast}_{R}$
$\displaystyle=U_{R}\operatorname{Diag}(g^{\ast}_{r}(p,q,\lambda_{R}))U_{R}^{\top}=\tfrac{\bar{\Omega}}{(1-\bar{\Omega})}R^{-1}.$

Proof For fixed $u$ and $v$, $F$ is a unitarily invariant function of $W$. Due
to 7, the gradient of $F$ is $G_{u}=g_{u}(u,v,\lambda_{W})$,
$G_{v}=g_{v}(u,v,\lambda_{W})$, and
$G_{W}=U_{W}\operatorname{Diag}(g_{w}(u,v,\lambda_{W}))U_{W}^{\top}$. The
result can be verified from this and 6. ∎

###  3.2 Hypograph Power Cone and Root-determinant Cone

Let $\varphi:\mathbb{R}^{d}\to\mathbb{R}$ be the function111We reuse symbols
with similar roles across subsections; their meaning should be taken from the
definition within each subsection.
$\varphi(w)\coloneqq\textstyle\prod_{i\in\llbracket
d\rrbracket}w_{i}^{\alpha_{i}}$, parametrized by
$\alpha=(\alpha_{1},\ldots,\alpha_{d})$ such that $\langle e,\alpha\rangle=1$
and $\alpha>0$. Define the _hypograph-power_ cone:

$\mathcal{K}_{\operatorname{hpower}}\coloneqq\bigl{\\{}(u,w)\in\mathbb{R}\times\mathbb{R}_{+}^{d}:u\leq\varphi(w)\bigr{\\}},$

which admits the $(1+d)$-LHSCB (nesterov2018lectures, , Section 5.4.7):

$f(u,w)=-\log(\varphi(w)-u)-\textstyle\sum_{i\in\llbracket
d\rrbracket}\log(w_{i}).$ (10)

The cone $\mathcal{K}_{\operatorname{hpower}}$ is the _power mean cone_ in
coey2021performance . In the special case where $\alpha=\nicefrac{{e}}{{d}}$,
we call $\mathcal{K}_{\operatorname{hpower}}$ the _hypograph geometric mean_
cone, $\mathcal{K}_{\operatorname{hgeom}}$. The dual cone is coey2021hypatia :

$\mathcal{K}_{\operatorname{hpower}}^{\ast}\coloneqq\bigl{\\{}(p,r)\in\mathbb{R}_{-}\times\mathbb{R}_{+}^{d}:-p\leq\varphi\bigl{(}\tfrac{r}{\alpha}\bigr{)}\bigr{\\}}.$

###### Lemma 1

Let $(p,r)\in\operatorname{int}(\mathcal{K}_{\operatorname{hpower}}^{\ast})$
parametrized by $\alpha$. The unique root of
$h(y)\coloneqq\textstyle\sum_{i\in\llbracket
d\rrbracket}\alpha_{i}\log(y-p\alpha_{i})-\log(\varphi(r))$ can be
approximated by a quadratically convergent Newton-Raphson method starting from
$0$.

The proof is given in Section 5.2.

###### Proposition 3

The conjugate gradient at
$(p,r)\in\operatorname{int}(\mathcal{K}_{\operatorname{hpower}}^{\ast})$ has
components:

$\displaystyle g^{\ast}_{p}$ $\displaystyle=-p^{-1}-{\hat{y}}^{-1},$ (11a)
$\displaystyle g^{\ast}_{r_{i}}$
$\displaystyle=\tfrac{p\alpha_{i}{\hat{y}}^{-1}-1}{r_{i}}$
$\displaystyle\forall i\in\llbracket d\rrbracket,$ (11b)

where $\hat{y}$ is the root of $h$ from Lemma 1. In the case where
$\alpha=\nicefrac{{e}}{{d}}$, the conjugate gradient at
$(p,r)\in\operatorname{int}(\mathcal{K}_{\operatorname{hgeom}}^{\ast})$ can be
written more simply:

$\displaystyle g^{\ast}_{p}$
$\displaystyle=-p^{-1}-(\varphi(r)+\nicefrac{{p}}{{d}})^{-1},$ (12a)
$\displaystyle g^{\ast}_{r_{i}}$
$\displaystyle=-\tfrac{\varphi(r)}{r_{i}(\varphi(r)+\nicefrac{{p}}{{d}})}$
$\displaystyle\forall i\in\llbracket d\rrbracket.$ (12b)

The proof is given in Section 5.2. Substituting 12 in 5, we obtain a simple
expression for the conjugate barrier of $\mathcal{K}_{\operatorname{hgeom}}$:

$f^{\ast}(p,r)=-1-d-d\log\big{(}\tfrac{d\varphi(r)+p}{d\varphi(r)}\big{)}-\log(-p)-\textstyle\sum_{i\in\llbracket
d\rrbracket}\log\big{(}r_{i}\big{)}.$

The conjugate gradient for $\mathcal{K}_{\operatorname{hgeom}}$ can be easily
modified to obtain a conjugate gradient for the _root-determinant cone_
(coey2020solving, , Section 5.4):

$\mathcal{K}_{\operatorname{rtdet}}\coloneqq\bigl{\\{}(u,W)\in\mathbb{R}\times\mathbb{S}^{d}_{+}:u\leq\det(W)^{1/d}\bigr{\\}},$

which has the dual:

$\mathcal{K}_{\operatorname{rtdet}}^{\ast}\coloneqq\bigl{\\{}(p,R)\in\mathbb{R}_{-}\times\mathbb{S}^{d}_{+}:-p\leq
d\det(R)^{1/d}\bigr{\\}}.$

Let $W=U_{W}\operatorname{Diag}(\lambda_{W})U_{W}^{\top}$ be the
eigendecomposition of $W$. $\mathcal{K}_{\operatorname{rtdet}}$ admits the
$(1+d)$-LHSCB coey2021conic :

$F(u,W)=-\log(\varphi(\lambda_{W})-u)-\textstyle\sum_{i\in\llbracket
d\rrbracket}\log(\lambda_{W,i})=f(u,\lambda_{W}).$

###### Proposition 4

Let $(p,R)\in\operatorname{int}(\mathcal{K}_{\operatorname{rtdet}}^{\ast})$
and $R=U_{R}\operatorname{Diag}(\lambda_{R})U_{R}^{\top}$ be the
eigendecomposition of $R$. The conjugate gradient $G^{\ast}$ has components:

$\displaystyle G^{\ast}_{p}$
$\displaystyle=g_{p}^{\ast}(p,\lambda_{R})=-p^{-1}-(\det(R)^{1/d}+\nicefrac{{p}}{{d}})^{-1},$
$\displaystyle G^{\ast}_{R}$
$\displaystyle=U_{R}\operatorname{Diag}(g_{r}^{\ast}(p,\lambda_{R}))U_{R}^{\top}=-\tfrac{\det(R)^{1/d}}{\det(R)^{1/d}+\nicefrac{{p}}{{d}}}R^{-1}.$

Proof For fixed $u$, $F$ is a unitarily invariant function of $W$. Similar to
Proposition 2, the result can be verified from 7 and 6. ∎

###  3.3 Radial Power Cone

Let $\varphi:\mathbb{R}^{d}\to\mathbb{R}$ be the function
$\varphi(w)\coloneqq\textstyle\prod_{i\in\llbracket
d\rrbracket}w_{i}^{2\alpha_{i}}$, parametrized by
$\alpha=(\alpha_{1},\ldots,\alpha_{d})$ such that $\langle e,\alpha\rangle=1$
and $\alpha>0$. Define the _radial-power_ cone:

$\mathcal{K}_{\operatorname{rpower}}\coloneqq\bigl{\\{}(u,w)\in\mathbb{R}^{d_{1}}\times\mathbb{R}_{+}^{d_{2}}:\lVert
u\rVert\leq\textstyle\prod_{i\in\llbracket
d_{2}\rrbracket}w_{i}^{\alpha_{i}}=\sqrt{\varphi(w)}\bigr{\\}},$

which admits the $(1+d_{2})$-LHSCB (roy2021self, , Theorem 1):

$f(u,w)=-\log(\varphi(w)-\lVert u\rVert^{2})-\textstyle\sum_{i\in\llbracket
d_{2}\rrbracket}(1-\alpha_{i})\log(w_{i}).$

This is the _generalized power cone_ in coey2021performance ; chares2009cones
; roy2021self . Note that $f$ is not equivalent to the barrier from 10, even
when $d_{1}=1$. Hence the conjugate barrier and its derivatives take different
forms from our results in Section 3.2. In the special case where
$\alpha=\nicefrac{{e}}{{d_{2}}}$ and $d_{1}=1$, we call
$\mathcal{K}_{\operatorname{rpower}}$ the _radial geometric mean_ cone
$\mathcal{K}_{\operatorname{rgeom}}$. The dual cone is given by
(chares2009cones, , Theorem 4.3.1):

$\mathcal{K}_{\operatorname{rpower}}^{\ast}\coloneqq\bigl{\\{}(p,r)\in\mathbb{R}^{d_{1}}\times\mathbb{R}_{+}^{d_{2}}:\lVert
p\rVert\leq\textstyle\prod_{i\in\llbracket
d_{2}\rrbracket}\bigl{(}\tfrac{r_{i}}{\alpha_{i}}\bigr{)}^{\alpha_{i}}\bigr{\\}}.$

###### Lemma 2

Let $(p,r)\in\operatorname{int}(\mathcal{K}_{\operatorname{hpower}}^{\ast})$
parametrized by $\alpha$ and $p>0$. The unique positive root of
$h(y)\coloneqq\textstyle\sum_{i\in\llbracket
d_{2}\rrbracket}2\alpha_{i}\log(2\alpha_{i}y^{2}+\nicefrac{{2y(1+\alpha_{i})}}{{p}})-\log(\varphi(r))-\log(\nicefrac{{2y}}{{p}}+y^{2})-2\log(\nicefrac{{2y}}{{p}})$
can be approximated by a quadratically convergent Newton-Raphson method
starting from
$y_{-}\coloneqq-p^{-1}+d_{2}\tfrac{p+\sqrt{\varphi(r)(\nicefrac{{d_{2}^{2}}}{{p^{2}}}\varphi(r)+d_{2}^{2}-1)}}{\varphi(r)d_{2}^{2}-p^{2}}$.

The proof is given in Section 5.3.

###### Proposition 5

The conjugate gradient at
$(p,r)\in\operatorname{int}(\mathcal{K}_{\operatorname{rpower}}^{\ast})$ is
given by:

$\displaystyle g^{\ast}_{p_{i}}$ $\displaystyle=1_{p\neq
0}\cdot\hat{y}\tfrac{p_{i}}{\lVert p\rVert},$ $\displaystyle\forall
i\in\llbracket d_{1}\rrbracket,$ (13a) $\displaystyle g^{\ast}_{r_{i}}$
$\displaystyle=-\tfrac{\alpha_{i}(1+p\hat{y})+1}{r_{i}}$ $\displaystyle\forall
i\in\llbracket d_{2}\rrbracket,$ (13b)

where $\hat{y}$ is the positive root of $h$ from Lemma 2. In the case where
$d_{1}=1$ and $\alpha=\nicefrac{{e}}{{d_{2}}}$, the conjugate gradient at
$(p,r)\in\operatorname{int}(\mathcal{K}_{\operatorname{rgeom}}^{\ast})$ is:

$\displaystyle g^{\ast}_{p}$ $\displaystyle=y_{-},$ (14a) $\displaystyle
g^{\ast}_{r_{i}}$
$\displaystyle=-r_{i}^{-1}\Bigl{(}\tfrac{p^{2}+\sqrt{\varphi(r)(d_{2}^{2}\varphi(r)+d_{2}^{2}p^{2}-p^{2})}}{\varphi(r)d_{2}^{2}-p^{2}}+1\Bigr{)}$
$\displaystyle\forall i\in\llbracket d_{2}\rrbracket.$ (14b)

Note $y_{-}$ is from Lemma 2. The proof is given in Section 5.3.

###  3.4 Infinity Norm Cone and Spectral Norm Cone

Define the _infinity norm cone_ (coey2020solving, , Section 5.1):

$\mathcal{K}_{\ell_{\infty}}\coloneqq\bigl{\\{}(u,w)\in\mathbb{R}\times\mathbb{R}^{d}:u\geq\|w\|_{\infty}\bigr{\\}},$

which admits the $(1+d)$-LHSCB (guler1996barrier, , section 7.5):

$f(u,w)=-\textstyle\sum_{i\in\llbracket
d\rrbracket}\log(u^{2}-w_{i}^{2})+(d-1)\log(u).$

The dual cone is the epigraph of the $\ell_{1}$ norm function:

$\mathcal{K}_{\ell_{\infty}}^{\ast}\coloneqq\bigl{\\{}(p,r)\in\mathbb{R}\times\mathbb{R}^{d}:p\geq\|r\|_{1}\bigr{\\}}.$

###### Lemma 3

Let $(p,r)\in\operatorname{int}(\mathcal{K}_{\ell_{\infty}}^{\ast})$. The
unique negative root of $h(y)\coloneqq py+\textstyle\sum_{i\in\llbracket
d\rrbracket}\sqrt{1+r_{i}^{2}y^{2}}+1$ can be approximated by a quadratically
convergent Newton-Raphson method starting from $\max\\{-(p-\lVert
r\rVert_{1})^{-1},-\nicefrac{{(d+1)}}{{p}}\\}$.

The proof is given in Section 5.4.

###### Proposition 6

The conjugate gradient at
$(p,r)\in\operatorname{int}(\mathcal{K}_{\ell_{\infty}}^{\ast})$ is given by:

$\displaystyle g^{\ast}_{p}$ $\displaystyle=\hat{y},$ (15a) $\displaystyle
g^{\ast}_{r_{i}}$ $\displaystyle=1_{r_{i}\neq
0}\cdot\tfrac{\sqrt{1+{\hat{y}}^{2}r_{i}^{2}}-1}{r_{i}},$
$\displaystyle\forall i\in\llbracket d\rrbracket,$ (15b)

where $\hat{y}$ is the negative root of $h$ from Lemma 3.

The proof is given in Section 5.4. The conjugate gradient for
$\mathcal{K}_{\ell_{\infty}}$ can be easily modified to obtain a conjugate
gradient for the _spectral norm cone_ (coey2020solving, , Section 5.2):

$\mathcal{K}_{\ell_{\operatorname{spec}}}\coloneqq\\{(u,W)\in\mathbb{R}\times\mathbb{R}^{d_{1}\times
d_{2}}:u\geq\sigma_{\max}(W)\\},$

where $\sigma_{\max}$ is the maximum singular value function and $d_{1}\leq
d_{2}$. Let $R=U_{R}\operatorname{Diag}(\sigma_{R})V_{R}^{\top}$ be the
singular value decomposition of $R\in\mathbb{R}^{d_{1}\times d_{2}}$. The dual
cone is the epigraph of the nuclear norm:

$\mathcal{K}_{\ell_{\operatorname{spec}}}^{\ast}\coloneqq\\{(p,R)\in\mathbb{R}\times\mathbb{R}^{d_{1}\times
d_{2}}:p\geq\textstyle\sum_{i\in\llbracket d_{1}\rrbracket}\sigma_{R,i}\\}.$

Let $W=U_{W}\operatorname{Diag}(\sigma_{W})V_{W}^{\top}$ be the singular value
decomposition of $W$. $\mathcal{K}_{\ell_{\operatorname{spec}}}$ admits the
$(1+d_{1})$-LHSCB:

$F(u,W)=-\textstyle\sum_{i\in\llbracket
d_{1}\rrbracket}\log(u^{2}-\sigma_{W,i}^{2})+(d_{1}-1)\log(u)=f(u,\sigma_{W}).$

###### Proposition 7

The conjugate gradient $G^{\ast}$ at
$(p,R)\in\operatorname{int}(\mathcal{K}_{\ell_{\operatorname{spec}}}^{\ast})$
has components:

$\displaystyle G^{\ast}_{p}$ $\displaystyle=g^{\ast}_{p}(p,\sigma_{R}),$
$\displaystyle G^{\ast}_{R}$
$\displaystyle=U_{R}\operatorname{Diag}(g^{\ast}_{r}(p,\sigma_{R}))V_{R}^{\top}.$

Proof For fixed $u$, $F$ is a unitarily invariant function of $W$. Similar to
Proposition 2, the result can be verified using 7 and 6. ∎

##  4 Inverse Hessians

In coey2021conic  the authors derive efficient inverse Hessian operators for a
number of cones, including $\mathcal{K}_{\log}$,
$\mathcal{K}_{\operatorname{logdet}}$, $\mathcal{K}_{\operatorname{hgeom}}$,
and $\mathcal{K}_{\operatorname{rtdet}}$. Inverse Hessians for
$\mathcal{K}_{\ell_{\infty}}$ and $\mathcal{K}_{\ell_{\operatorname{spec}}}$
are described in coey2022thesis . The authors are motivated by the need to
apply inverse Hessians in several parts of the algorithm implemented by the
Hypatia solver coey2021performance . The inverse Hessian is used to measure
proximity to the central path as well as some of the linear system solving
methods described in (coey2021performance, , Appendix A). Our derivations of
the conjugate gradients offer an alternative method for deriving inverse
Hessian operators. Since these have not been previously written for
$\mathcal{K}_{\operatorname{hpower}}$ or
$\mathcal{K}_{\operatorname{rpower}}$, we derive those inverse Hessian
operators here.

A general technique for obtaining an inverse Hessian operator using an oracle
for the conjugate gradient may be described as follows. For
$\mathcal{K},\mathcal{K}^{\ast}\subset\mathbb{R}^{1+d}$, where $\mathcal{K}$
is either $\mathcal{K}_{\operatorname{hpower}}$ or
$\mathcal{K}_{\operatorname{rpower}}$ parametrized by $\alpha$, let
$\tilde{u}=(u,w)\in\operatorname{int}(\mathcal{K})$, and
$\tilde{x}=(x,z)\in\mathbb{R}^{1+d}$ be an arbitrary direction. Due to
(nesterov1997self, , Equation (2.11)):

$H(\tilde{u})^{-1}\cdot\tilde{x}=H^{\ast}(-g(\tilde{u}))\cdot\tilde{x}.$ (16)

Therefore to derive the inverse Hessian operator
$H(\tilde{u})^{-1}\cdot\tilde{x}$, we may derive an expression for
$H^{\ast}(\tilde{p})\cdot\tilde{x}$, for arbitrary
$\tilde{p}=(p,r)\in\operatorname{int}(\mathcal{K}^{\ast})$, and substitute
$-g(\tilde{u})$ for $\tilde{p}$. In a practical implementation of a PDIPM,
$g(\tilde{u})$ is usually already available at the time when
$H(\tilde{u})^{-1}$ is needed. Note that:

$H^{\ast}(\tilde{p})\cdot\tilde{x}=\tfrac{\operatorname{d}}{\operatorname{d}t}g^{\ast}(\tilde{p}+t\tilde{x})\big{\rvert}_{t=0}.$

The right hand side can be deduced from our calculations for $g^{\ast}$.

###  4.1 Hypograph Power Cone

###### Proposition 8

The inverse Hessian operator at $\tilde{u}$ in the direction $\tilde{x}$ is:

$\displaystyle(H(\tilde{u})^{-1}\cdot\tilde{x})_{u}$
$\displaystyle=\bigl{(}(\varphi(w)-u)^{2}+\tfrac{k_{2}}{k_{3}}u^{2}\bigr{)}x-\tfrac{\varphi(w)}{k_{3}}\langle
z,\tfrac{\alpha w}{k_{1}}\rangle,$ (17a)
$\displaystyle(H(\tilde{u})^{-1}\cdot\tilde{x})_{w_{i}}$
$\displaystyle=\tfrac{w_{i}^{2}}{k_{1,i}}z_{i}+\tfrac{\alpha_{i}w_{i}}{k_{1,i}}\tfrac{\varphi(w)}{k_{3}}x+\tfrac{g_{u}\varphi(w)}{k_{3}}\langle
z,\tfrac{\alpha w}{k_{1}}\rangle\tfrac{\alpha_{i}w_{i}}{k_{1,i}}$
$\displaystyle\forall i\in\llbracket d\rrbracket,$ (17b)

where $\varphi$ is defined as in Section 3.2, and:

$k_{1,i}\coloneqq 1+\alpha_{i}\varphi(w)g_{u}\quad\forall i\in\llbracket
d\rrbracket,\quad k_{2}\coloneqq\textstyle\sum_{i\in\llbracket
d\rrbracket}\tfrac{\alpha_{i}^{2}}{k_{1,i}},\quad k_{3}\coloneqq
1-\varphi(w)g_{u}k_{2}.$

The proof is given in Section 6.1.

###  4.2 Radial Power Cone

###### Proposition 9

The inverse Hessian operator at $\tilde{u}$ in the direction $\tilde{x}$ is:

$\displaystyle(H(\tilde{u})^{-1}\cdot\tilde{x})_{u_{i}}$
$\displaystyle=\tfrac{\zeta x_{i}}{2}+\tfrac{u_{i}}{k_{3}}\big{(}\tfrac{\zeta
k_{3}-2k_{2}\varphi(w)}{k_{1}}\langle
x,u\rangle-\langle\nicefrac{{\alpha}}{{g_{w}}},z\rangle\big{)}$
$\displaystyle\forall i\in\llbracket d_{1}\rrbracket,$ (18a)
$\displaystyle(H(\tilde{u})^{-1}\cdot\tilde{x})_{w_{i}}$
$\displaystyle=-\tfrac{w_{i}z_{i}}{g_{w_{i}}}-\tfrac{\alpha_{i}}{k_{3}g_{w_{i}}}\big{(}\langle
x,u\rangle-\tfrac{2\lVert
u\rVert^{2}}{\zeta}\langle\nicefrac{{\alpha}}{{g_{w}}},z\rangle\big{)}$
$\displaystyle\forall i\in\llbracket d_{2}\rrbracket,$ (18b)

where $\varphi$ defined as in Section 3.3, $\zeta\coloneqq\varphi(w)-\lVert
u\rVert^{2}$, and:

$k_{1}\coloneqq\varphi(w)+\lVert u\rVert^{2},\quad
k_{2}\coloneqq\langle\nicefrac{{\alpha}}{{w}},\nicefrac{{\alpha}}{{g_{w}}}\rangle,\quad
k_{3}\coloneqq\tfrac{k_{1}}{2\varphi(w)}+2k_{2}\tfrac{\lVert
u\rVert^{2}}{\zeta}.$

The proof is given in Section 6.2.

##  5 Proofs of Conjugate Gradients

For convenience, we adapt (suli2003introduction, , Theorem 1.9) as a Lemma
below (without proof), which offers some conditions for quadratic convergence
of the Newton-Raphson method.

###### Lemma 4

Suppose that the continuous, real-valued function $h$ has a continuous second
derivative on the closed interval
$I_{\delta}\coloneqq[\hat{y}-\delta,\hat{y}+\delta]$, $\delta>0$, such that
$h(\hat{y})=0$ and $h^{\prime\prime}(\hat{y})\neq 0$. Suppose further that
$\lvert h^{\prime\prime}(x)\rvert/\lvert h^{\prime}(y)\rvert$ is bounded for
all $x,y\in I_{\delta}$. If there exists a real number $y_{+}>\hat{y}$ (or
$y_{-}<\hat{y}$), such that in the interval $J\coloneqq[\hat{y},y_{+}]$ (or
$J\coloneqq[y_{-},\hat{y}]$) both $h^{\prime}$ and $h^{\prime\prime}$ are
positive (or one is negative), then the Newton-Raphson method converges
quadratically to $\hat{y}$ from any starting value in $J$.

Lemma 4 is used in our proofs of Lemmas 1, 2 and 3.

###  5.1 Logarithm Cone

Proof of Proposition 1 For convenience, let $\zeta$ be the function
$\zeta(u,v,w)\coloneqq v\varphi(\nicefrac{{w}}{{v}})-u$, where $\varphi$ is
from Section 3.1. Let $(u,v,w)\in\operatorname{int}(\mathcal{K}_{\log})$. Then
the gradient of $f$ with respect to components, $u$, $v$, and $w$ is:

$\displaystyle g_{u}$ $\displaystyle=\zeta(u,v,w)^{-1},$ (19a) $\displaystyle
g_{v}$
$\displaystyle=-\zeta(u,v,w)^{-1}(\varphi\bigl{(}\tfrac{w}{v})-d\bigr{)}-\tfrac{1}{v},$
(19b) $\displaystyle g_{w_{i}}$
$\displaystyle=-\zeta(u,v,w)^{-1}\tfrac{v}{w_{i}}-\tfrac{1}{w_{i}}$
$\displaystyle\forall i\in\llbracket d\rrbracket.$ (19c)

Note that $\bar{\omega}>1$ since:

$\displaystyle(p,q,r)$
$\displaystyle\in\operatorname{int}(\mathcal{K}_{\log}^{\ast})$ (20a)
$\displaystyle\Rightarrow pd-q+p\textstyle\sum_{i\in\llbracket
d\rrbracket}\log\bigl{(}-\tfrac{r_{i}}{p}\bigr{)}$ $\displaystyle<0$ (20b)
$\displaystyle\Leftrightarrow\tfrac{1}{d}\bigl{(}1+d-\tfrac{q}{p}+\textstyle\sum_{i\in\llbracket
d\rrbracket}\log\bigl{(}-\tfrac{r_{i}}{p}\bigr{)}\bigr{)}-\log(d)$
$\displaystyle>\tfrac{1}{d}+\log\bigl{(}\tfrac{1}{d}\bigr{)}$ (20c)
$\displaystyle\Leftrightarrow\omega\bigl{(}\tfrac{1}{d}\bigl{(}1+d-\tfrac{q}{p}+\textstyle\sum_{i\in\llbracket
d\rrbracket}\log\bigl{(}-\tfrac{r_{i}}{p}\bigr{)}\bigr{)}-\log(d)\bigr{)}$
$\displaystyle>\tfrac{1}{d}$ (20d) $\displaystyle\Leftrightarrow\bar{\omega}$
$\displaystyle>1,$ (20e)

where 20d follows from 20c by applying $\omega$ to both sides, and noting that
$\omega$ is the inverse of $x\mapsto x+\log(x)$ on the reals (from the form of
8).

We would like to find
$g^{\ast}\coloneqq(g^{\ast}_{p},g^{\ast}_{q},g^{\ast}_{r})$ such that
$-g(-g^{\ast})=(p,q,r)$. Fix
$\zeta\coloneqq\zeta(-g^{\ast}_{p},-g^{\ast}_{q},-g^{\ast}_{r})$. Then, from
19a:

$p=-\zeta^{-1}.$ (21)

Combining 19c with 21, we need for all $i\in\llbracket d\rrbracket$:

$r_{i}=\tfrac{g^{\ast}_{q}}{\zeta
g^{\ast}_{r_{i}}}-\tfrac{1}{g^{\ast}_{r_{i}}}=-\tfrac{pg^{\ast}_{q}}{g^{\ast}_{r_{i}}}-\tfrac{1}{g^{\ast}_{r_{i}}}\Rightarrow
g^{\ast}_{r_{i}}=\tfrac{-pg^{\ast}_{q}-1}{r_{i}}.$ (22)

Combining 19b with 21 and 22, we need:

$q=\zeta^{-1}\bigl{(}\varphi\bigl{(}\tfrac{g^{\ast}_{r}}{g^{\ast}_{q}}\bigr{)}-d\bigr{)}-\tfrac{1}{g^{\ast}_{q}}=-p\big{(}\varphi\big{(}\tfrac{-pg^{\ast}_{q}-1}{rg^{\ast}_{q}}\big{)}-d\big{)}-\tfrac{1}{g^{\ast}_{q}}.$
(23)

Replacing the definition of $\varphi$ in 23 and rearranging:

$\displaystyle\tfrac{q}{p}-d-\textstyle\sum_{i\in\llbracket
d\rrbracket}\log(-\tfrac{r_{i}}{p})-1$
$\displaystyle=-\tfrac{1}{pg^{\ast}_{q}}-d\log(1+\tfrac{1}{pg^{\ast}_{q}})-1$
(24a) $\displaystyle\Rightarrow-\tfrac{q}{p}+d+\textstyle\sum_{i\in\llbracket
d\rrbracket}\log(-\tfrac{r_{i}}{p})+1$
$\displaystyle=1+\tfrac{1}{pg^{\ast}_{q}}+d\log(1+\tfrac{1}{pg^{\ast}_{q}}).$
(24b)

Note 24b has the form $\beta=a+d\log(a)$. Letting $a=db$:

$\beta=db+d\log(db)\Rightarrow\tfrac{\beta}{d}-\log(d)=b+\log(b).$

Therefore,

$\displaystyle\tfrac{1}{d}\bigl{(}1+d-\tfrac{q}{p}+\textstyle\sum_{i\in\llbracket
d\rrbracket}\log(-\tfrac{r_{i}}{p})\bigr{)}-\log(d)$
$\displaystyle=1+\tfrac{1}{pg^{\ast}_{q}}+\log\bigl{(}1+\tfrac{1}{pg^{\ast}_{q}}\bigr{)}$
(25a) $\displaystyle\Rightarrow\bar{\omega}$
$\displaystyle=1+\tfrac{1}{pg^{\ast}_{q}}$ (25b) $\displaystyle\Rightarrow
g^{\ast}_{q}$ $\displaystyle=-p^{-1}(1-\bar{\omega})^{-1}.$ (25c)

Substituting 25c in 22 gives 9c. Finally, due to 2:

$g^{\ast}_{p}=\tfrac{-d-2-qg^{\ast}_{q}-\langle
r,g^{\ast}_{r}\rangle}{p}=\tfrac{-d-2+\nicefrac{{q}}{{p}}+2\bar{\omega}}{p(1-\bar{\omega})}.$

∎

###  5.2 Hypograph Power Cone

Proof of Lemma 1 For $\varphi$ given in Section 3.2, let $\hat{y}$ denote the
root of $h$ from Lemma 1, which we show is unique. Note that $\hat{y}$ must
satisfy:

$\varphi(\hat{y}e-p\alpha_{i})=\varphi(r)\Rightarrow\varphi(\nicefrac{{\hat{y}}}{{\alpha}}-pe)=\varphi(\nicefrac{{r}}{{\alpha}}).$

Since
$(p,r)\in\operatorname{int}(\mathcal{K}_{\operatorname{hpower}}^{\ast})$, this
implies $\hat{y}>0$. The derivatives of $h$ are:

$\displaystyle h^{\prime}(y)$ $\displaystyle=\textstyle\sum_{i\in\llbracket
d\rrbracket}\tfrac{\alpha_{i}}{y-p\alpha_{i}},$ $\displaystyle
h^{\prime\prime}(y)$ $\displaystyle=\textstyle\sum_{i\in\llbracket
d\rrbracket}-\tfrac{\alpha_{i}}{(y-p\alpha_{i})^{2}}<0.$

Note that $p<0$ for
$(p,r)\in\operatorname{int}(\mathcal{K}_{\operatorname{hpower}}^{\ast})$ and
therefore $h^{\prime}(y)>0$ for all $y>\max_{i\in\llbracket
d\rrbracket}\\{p\alpha_{i}\\}$, i.e. the domain of $h$. So the root of $h$ is
unique. Since $h$ is concave and increasing, a root-finding Newton-Raphson
method will converge quadratically from any initial $y_{-}<\hat{y}$ (Lemma 4).
We may pick, for example, $y_{-}=0$, which ensures $y_{-}<\hat{y}$ and $y_{-}$
is in the domain of $h$. ∎

Proof of Proposition 3 For convenience, let $\zeta$ be the function
$\zeta(u,w)\coloneqq\varphi(w)-u$, where $\varphi$ is from Section 3.2. Let
$(u,w)\in\operatorname{int}(\mathcal{K}_{\operatorname{hpower}})$. Then the
gradient of $f$ with respect to components $u$ and $w$ is:

$\displaystyle g_{u}$ $\displaystyle=\zeta(u,w)^{-1},$ (26a) $\displaystyle
g_{w_{i}}$
$\displaystyle=-\zeta(u,w)^{-1}\tfrac{\varphi(w)\alpha_{i}}{w_{i}}-\tfrac{1}{w_{i}}$
$\displaystyle\forall i\in\llbracket d\rrbracket.$ (26b)

We would like to find $g^{\ast}\coloneqq g^{\ast}(p,r)$ such that
$-g(-g^{\ast})=(p,r)$. Using 26a, we need:

$p=-\zeta(-g^{\ast}_{p},-g^{\ast}_{r})^{-1}=-(\varphi(-g^{\ast}_{r})+g^{\ast}_{p})^{-1}.$
(27)

Using 26b and 27, we need for all $i\in\llbracket d\rrbracket$:

$r_{i}=-\zeta(-g^{\ast}_{p},-g^{\ast}_{r})^{-1}\tfrac{\varphi(-g^{\ast}_{r})\alpha_{i}}{g^{\ast}_{r_{i}}}-\tfrac{1}{g^{\ast}_{r_{i}}}=-\tfrac{1-p\alpha_{i}\varphi(-g^{\ast}_{r})}{g^{\ast}_{r_{i}}}.$
(28)

From 27 and 28:

$\displaystyle g^{\ast}_{p}$ $\displaystyle=-p^{-1}-\varphi(-g^{\ast}_{r}),$
(29a) $\displaystyle g^{\ast}_{r_{i}}$
$\displaystyle=\tfrac{p\alpha_{i}\varphi(-g^{\ast}_{r})-1}{r_{i}}$
$\displaystyle\forall i\in\llbracket d\rrbracket.$ (29b)

It remains to show how to evaluate $\varphi(-g^{\ast}_{r})$. Applying
$\varphi$ from Section 3.2 to both sides of 28, after collecting for each $i$:

$\displaystyle\varphi(r)$ $\displaystyle=\textstyle\prod_{i\in\llbracket
d\rrbracket}\bigl{(}-{g^{\ast}_{r_{i}}}^{-1}\bigl{(}-p\alpha_{i}\varphi(-g^{\ast}_{r})+1\bigr{)}\bigr{)}^{\alpha_{i}}$
(30a)
$\displaystyle=\varphi(-{g^{\ast}_{r}})^{-1}\textstyle\prod_{i\in\llbracket
d\rrbracket}\bigl{(}-p\alpha_{i}\varphi(-g^{\ast}_{r})+1\bigr{)}^{\alpha_{i}}$
(30b) $\displaystyle=\textstyle\prod_{i\in\llbracket
d\rrbracket}\varphi(-{g^{\ast}_{r}})^{-\alpha_{i}}\bigl{(}-p\alpha_{i}\varphi(-g^{\ast}_{r})+1\bigr{)}^{\alpha_{i}}$
(30c) $\displaystyle=\textstyle\prod_{i\in\llbracket
d\rrbracket}\big{(}-p\alpha_{i}+\varphi(-g^{\ast}_{r})^{-1}\big{)}^{\alpha_{i}}$
(30d) $\displaystyle\Rightarrow\log(\varphi(r))$
$\displaystyle=\textstyle\sum_{i\in\llbracket
d\rrbracket}\alpha_{i}\log\bigl{(}-p\alpha_{i}+\varphi(-g^{\ast}_{r})^{-1}\bigr{)}$
(30e) $\displaystyle\Rightarrow h(\varphi(-g^{\ast}_{r})^{-1})$
$\displaystyle=0.$ (30f)

From 30f, we can evaluate $\varphi(-g^{\ast}_{r})^{-1}$ easily due to Lemma 1.
Combining this with 29 justifies 11. In the special case where
$\alpha=\nicefrac{{e}}{{d}}$, we can solve $h(y)=0$ exactly, giving,
$\varphi(-g^{\ast}_{r})^{-1}=(\varphi(r)+\nicefrac{{p}}{{d}})^{-1}$.
Substituting this in 29 gives 12. ∎

###  5.3 Radial Power Cone

Proof of Lemma 2 Let $\hat{y}$ denote the positive root of $h$ from Lemma 2,
which we show is unique. In the special case where
$\alpha=\nicefrac{{e}}{{d_{2}}}$, we can solve $h(y)=0$ exactly. It can be
verified that $\hat{y}>0$ is given by:

$\hat{y}=-p^{-1}+d_{2}\tfrac{p+\sqrt{\varphi(r)(\nicefrac{{d_{2}^{2}}}{{p^{2}}}\varphi(r)+d_{2}^{2}-1)}}{\varphi(r)d_{2}^{2}-p^{2}},$
(31)

where $\varphi$ is given in Section 3.3. Note that the denominator is positive
since $(p,r)\in\operatorname{int}(\mathcal{K}_{\operatorname{rgeom}}^{\ast})$.
Let us turn to the case of non-uniform $\alpha$. The first two derivatives of
$h$ are:

$\displaystyle h^{\prime}(y)$ $\displaystyle=2\textstyle\sum_{i\in\llbracket
d_{2}\rrbracket}\tfrac{\alpha_{i}^{2}}{\alpha_{i}y+\nicefrac{{(1+\alpha_{i})}}{{p}}}-2\tfrac{y+\nicefrac{{1}}{{p}}}{y(y+\nicefrac{{2}}{{p}})},$
$\displaystyle h^{\prime\prime}(y)$
$\displaystyle=-2\textstyle\sum_{i\in\llbracket
d_{2}\rrbracket}\tfrac{\alpha_{i}^{3}}{(\alpha_{i}y+\nicefrac{{(1+\alpha_{i})}}{{p}})^{2}}+\tfrac{2(y^{2}+\nicefrac{{2}}{{p^{2}}})}{y^{2}(y+\nicefrac{{2}}{{p}})^{2}}.$

We have that $h$ is decreasing for $p,y>0$ (and cannot have more than one
root), since:

$h^{\prime}(y)<2\textstyle\sum_{i\in\llbracket
d_{2}\rrbracket}\tfrac{\alpha_{i}^{2}}{a_{i}y+\nicefrac{{(1+\alpha_{i})}}{{p}}}-2\tfrac{y}{y(y+\nicefrac{{2}}{{p}})}\leq
2\tfrac{1}{y+\nicefrac{{(1+1)}}{{p}}}-2\tfrac{1}{y+\nicefrac{{2}}{{p}}}=0.$
(32)

In the second inequality we use the fact that the preceding expression is
convex in $\alpha$, and therefore maximized at an extreme point of the simplex
that $\alpha$ belongs to. Similar reasoning shows that $h^{\prime\prime}(y)>0$
for $p,y>0$:

$h^{\prime\prime}(y)>-2\textstyle\sum_{i\in\llbracket
d_{2}\rrbracket}\tfrac{\alpha_{i}^{3}}{(\alpha_{i}y+\nicefrac{{(1+\alpha_{i})}}{{p}})^{2}}+\tfrac{2}{(y+\nicefrac{{2}}{{p}})^{2}}\geq-\tfrac{2}{(y+\nicefrac{{2}}{{p}})^{2}}+\tfrac{2}{(y+\nicefrac{{2}}{{p}})^{2}}=0.$
(33)

The second inequality follows from the fact that the preceding expression is
concave in $\alpha$.

Due to 32 and 33, a root-finding Newton-Raphson method converges quadratically
starting from some $y_{-}$ such that $y_{-}\leq\hat{y}$ (Lemma 4). We may use
the solution from the equal powers case, i.e. 31 for $y_{-}$. To see why, note
that the function $\bar{h}(\alpha,y)=\textstyle\sum_{i\in\llbracket
d_{2}\rrbracket}2\alpha_{i}\log(2\alpha_{i}y^{2}+(1+\alpha_{i})\nicefrac{{2y}}{{p}})-\log(\varphi(r))-\log(\nicefrac{{2y}}{{p}}+y^{2})-2\log(\nicefrac{{2y}}{{p}})$
is convex and symmetric in $\alpha$ (ignoring $y$, it can be checked that the
Hessian of $\bar{h}$ is diagonal with nonnegative entries). So for any fixed
$y$, $\bar{h}(\alpha,y)$ is minimized at $\alpha=\nicefrac{{e}}{{d_{2}}}$.
Since $h$ is decreasing, a solution to $\bar{h}(\nicefrac{{e}}{{d_{2}}},y)=0$
lower bounds $\hat{y}$. ∎

Proof of Proposition 5 For convenience, let $\zeta$ be the function
$\zeta(u,w)\coloneqq\varphi(w)-\lVert u\rVert^{2}$, where $\varphi$ is from
Section 3.3. Let
$(u,w)\in\operatorname{int}(\mathcal{K}_{\operatorname{rpower}})$. Then the
gradient of $f$ with respect to components $u$ and $w$ is:

$\displaystyle g_{u_{i}}$ $\displaystyle=\tfrac{2u_{i}}{\zeta(u,w)}$
$\displaystyle\forall i\in\llbracket d_{1}\rrbracket,$ (34a) $\displaystyle
g_{w_{i}}$
$\displaystyle=\tfrac{-2\alpha_{i}\varphi(w)}{w_{i}\zeta(u,w)}-\tfrac{1-\alpha_{i}}{w_{i}}$
$\displaystyle\forall i\in\llbracket d_{2}\rrbracket.$ (34b)

We would like to find $g^{\ast}\coloneqq g^{\ast}(p,r)$ such that
$-g(-g^{\ast})=(p,r)$. First, if $p=0$, it is easy to see from 34 that:

$\displaystyle g^{\ast}_{p_{i}}$ $\displaystyle=0$ $\displaystyle\forall
i\in\llbracket d_{1}\rrbracket,$ $\displaystyle g^{\ast}_{r_{i}}$
$\displaystyle=-\tfrac{1+\alpha_{i}}{r_{i}}$ $\displaystyle\forall
i\in\llbracket d_{2}\rrbracket.$

For the case $p\neq 0$, let us show that without loss of generality, we may
assume $p\in\mathbb{R}_{+}$ (and therefore $d_{1}=1$). Fix
$\zeta\coloneqq\zeta(-g^{\ast}_{p},-g^{\ast}_{r})$. Let
$Q\in\mathbb{R}^{d_{1}\times d_{1}}$ be a suitable Householder transformation
mapping $p\in\mathbb{R}^{d_{1}}$ to a vector of zeros except for one entry
that is equal to $\lVert p\rVert$. Since the function $\zeta$ is invariant to
orthonormal transformations on the first input, $f(u,w)=f(Qu,w)$. It is also
easy to see from the definition of the dual gradient in 4 that this implies:

$g^{\ast}_{p}=Q^{\top}g^{\ast}_{Qp}.$ (35)

From 34a:

$\displaystyle g^{\ast}_{p}=\tfrac{\zeta p}{2}.$ (36)

Let $g^{\ast}_{\lVert p\rVert}$ denote the $p$-component of the conjugate
gradient at $(\lVert
p\rVert,r)\in\operatorname{int}(\mathcal{K}_{\operatorname{rpower}}^{\ast})$
with $d_{1}=1$. Due to 35 and the invariance of $\zeta$ to transformation by
$Q^{\top}$:

$\zeta=\zeta(-g^{\ast}_{p},-g^{\ast}_{r})=\zeta(-Q^{\top}g^{\ast}_{Qp},-g^{\ast}_{r})=\zeta(-g^{\ast}_{\lVert
p\rVert},-g^{\ast}_{r})=\tfrac{2g^{\ast}_{\lVert p\rVert}}{\lVert p\rVert}.$

Substituting into 36:

$g^{\ast}_{p}=\tfrac{g^{\ast}_{\lVert p\rVert}\cdot p}{\lVert p\rVert},$

where $g^{\ast}_{\lVert p\rVert}\in\mathbb{R}_{+}$ can be computed as for the
$p\in\mathbb{R}_{+}$ case.

Suppose $p\in\mathbb{R}_{+}$ from hereon. Due to 34a, we need:

$\displaystyle\zeta$ $\displaystyle=\tfrac{2g^{\ast}_{p}}{p}.$ (37)

Since $\zeta>0$, we have $g^{\ast}_{p}>0$. From 34b:

$\displaystyle r_{i}$
$\displaystyle=\tfrac{2\alpha_{i}\varphi(-g^{\ast}_{r})}{-g^{\ast}_{r_{i}}\zeta}-\tfrac{1-\alpha_{i}}{g^{\ast}_{r_{i}}}$
$\displaystyle\forall i\in\llbracket d_{2}\rrbracket,$ (38a)
$\displaystyle\Rightarrow r_{i}(-g^{\ast}_{r_{i}})\zeta$
$\displaystyle=2\alpha_{i}\varphi(-g^{\ast}_{r})+(1-\alpha_{i})\zeta$
$\displaystyle\forall i\in\llbracket d_{2}\rrbracket.$ (38b)

Applying $\varphi$ to both sides, across all $i$:

$\varphi(r)\varphi(-g^{\ast}_{r})\zeta^{2}=\varphi(2\alpha_{i}\varphi(-g^{\ast}_{r})+(1-\alpha_{i})\zeta).$

Substituting for
$\varphi(-g^{\ast}_{r})=\zeta+{g^{\ast}_{p}}^{2}=\tfrac{2g^{\ast}_{p}}{p}+{g^{\ast}_{p}}^{2}$
and the expression for $\zeta$ from 37:

$\varphi(r)\bigl{(}\tfrac{2g^{\ast}_{p}}{p}+{g^{\ast}_{p}}^{2}\bigr{)}\bigl{(}\tfrac{2g^{\ast}_{p}}{p}\bigr{)}^{2}=\varphi\big{(}2\alpha_{i}(\tfrac{2g^{\ast}_{p}}{p}+{g^{\ast}_{p}}^{2})+(1-\alpha_{i})\tfrac{2g^{\ast}_{p}}{p}\big{)}.$
(39)

We treat this as a root-finding problem for $g^{\ast}_{p}$. Taking the
logarithm of both sides in 39 and rearranging, we would like to find a root
for $h(g^{\ast}_{p})=0$, where $p,g^{\ast}_{p}>0$. This can be solved easily
by Lemma 2. Due to 38b, the solution can be used to compute $g^{\ast}_{r}$
with:

$\displaystyle g^{\ast}_{r_{i}}$
$\displaystyle=-\tfrac{1}{r_{i}\zeta}(2\alpha_{i}\varphi(-g^{\ast}_{r})+(1-\alpha_{i})\zeta)=-\tfrac{\alpha_{i}(1+pg^{\ast}_{p})+1}{r_{i}}$
$\displaystyle\forall i\in\llbracket d_{2}\rrbracket,$ (40)

which shows 13. Combining 31 with 40 gives 14. ∎

###  5.4 Infinity Norm Cone

Proof of Lemma 3 Let $\hat{y}$ denote the negative root of $h$ from Lemma 3,
which we show is unique. Note that if $r=0$, then trivially
$\hat{y}=-\nicefrac{{(d+1)}}{{p}}$ ($p\neq 0$ on the
$\operatorname{int}(\mathcal{K}_{\ell_{\infty}}^{\ast})$). So assume that
$r\neq 0$. The derivatives of $h$ are:

$\displaystyle h^{\prime}(y)$ $\displaystyle=p+y\textstyle\sum_{i\in\llbracket
d\rrbracket}r_{i}^{2}(1+r_{i}^{2}y^{2})^{-1/2},$ $\displaystyle
h^{\prime\prime}(y)$ $\displaystyle=\textstyle\sum_{i\in\llbracket
d\rrbracket}r_{i}^{2}(1+r_{i}^{2}y^{2})^{-3/2}>0.$

Once again, $h$ can have at most one root $\hat{y}$ on the halfline $y\leq 0$
since:

$h^{\prime}(y)\geq p+y\textstyle\sum_{i\in\llbracket
d\rrbracket}\tfrac{r_{i}^{2}}{\sqrt{r_{i}^{2}y^{2}}}=p-\textstyle\sum_{i\in\llbracket
d\rrbracket}\lvert r_{i}\rvert>0.$

The last inequality follows from
$(p,r)\in\operatorname{int}(\mathcal{K}_{\ell_{\infty}}^{\ast})$. Since $h$ is
increasing and convex, a root-finding Newton-Raphson method will converge
quadratically from any $y_{+}\geq\hat{y}$ (Lemma 4). Consider the function:

$\bar{h}(y)\coloneqq y\bigl{(}p-\textstyle\sum_{i\in\llbracket
d\rrbracket}\lvert r_{i}\rvert\bigr{)}+1=py+\textstyle\sum_{i\in\llbracket
d\rrbracket}\lvert r_{i}\rvert\lvert y\rvert+1\leq h(y).$

The root of $\bar{h}$ is at $y=-(p-\textstyle\sum_{i\in\llbracket
d\rrbracket}\lvert r_{i}\rvert)^{-1}$. Since $h$ is increasing in $y$, we may
use this root for $y_{+}$. Alternatively, we could use $\bar{h}(y)\coloneqq
py+d+1\leq h(y)$, and its root gives $y_{+}=-\nicefrac{{(d+1)}}{{p}}$. ∎

Proof of Proposition 6 Let
$(u,w)\in\operatorname{int}(\mathcal{K}_{\ell_{\infty}})$ and define
$\zeta_{i}(u,w)\coloneqq u^{2}-w_{i}^{2}$ for all $i\in\llbracket
d\rrbracket$. Then the gradient of $f$ is:

$\displaystyle g_{u}$
$\displaystyle=\tfrac{d-1}{u}-\textstyle\sum_{i\in\llbracket
d\rrbracket}\tfrac{2u}{\zeta_{i}(u,w)},$ (41a) $\displaystyle g_{w_{i}}$
$\displaystyle=\tfrac{2w_{i}}{\zeta_{i}(u,w)}$ $\displaystyle\forall
i\in\llbracket d\rrbracket.$ (41b)

We would like to find $g^{\ast}\coloneqq g^{\ast}(p,r)$ such that
$-g(-g^{\ast}(p,r))=(p,r)$. Let us fix
$\zeta_{i}\coloneqq{g^{\ast}_{p}}^{2}-{g^{\ast}_{r_{i}}}^{2}$ for all
$i\in\llbracket d\rrbracket$. From 41b, for all $i\in\llbracket d\rrbracket$:

$r_{i}=\tfrac{2g^{\ast}_{r_{i}}}{\zeta_{i}}\Rightarrow\tfrac{1}{2}({g^{\ast}_{p}}^{2}-{g^{\ast}_{r_{i}}}^{2})r_{i}=g^{\ast}_{r_{i}}.$

This implies the signs of $r_{i}$ and $g^{\ast}_{r_{i}}$ equal for all
$i\in\llbracket d\rrbracket$, and:

$g^{\ast}_{r_{i}}=1_{r_{i}\neq
0}\cdot\tfrac{\sqrt{1+r_{i}^{2}{g^{\ast}_{p}}^{2}}-1}{r_{i}}.$ (42)

Substituting into the definition for $\zeta_{i}$, for all $i\in\llbracket
d\rrbracket$:

$\zeta_{i}=1_{r_{i}=0}\cdot{g^{\ast}_{p}}^{2}+1_{r_{i}\neq
0}\cdot\tfrac{-2+2\sqrt{1+r_{i}^{2}{g^{\ast}_{p}}^{2}}}{r_{i}^{2}}.$ (43)

From 41a and 43:

$\displaystyle d-1-\textstyle\sum_{i\in\llbracket
d\rrbracket}\tfrac{2{g^{\ast}_{p}}^{2}}{\zeta_{i}}$
$\displaystyle=pg^{\ast}_{p}$ (44a) $\displaystyle\Leftrightarrow
d-1-\textstyle\sum_{i\in\llbracket d\rrbracket:r_{i}\neq
0}\tfrac{2{g^{\ast}_{p}}^{2}r_{i}^{2}}{-2+2\sqrt{1+r_{i}^{2}{g^{\ast}_{p}}^{2}}}-\textstyle\sum_{i\in\llbracket
d\rrbracket:r_{i}=0}2$ $\displaystyle=pg^{\ast}_{p}$ (44b)
$\displaystyle\Leftrightarrow d-1-\textstyle\sum_{i\in\llbracket
d\rrbracket:r_{i}\neq
0}\tfrac{{g^{\ast}_{p}}^{2}r_{i}^{2}(-1-\sqrt{1+r_{i}^{2}{g^{\ast}_{p}}^{2}})}{1-(1+r_{i}^{2}{g^{\ast}_{p}}^{2})}-\textstyle\sum_{i\in\llbracket
d\rrbracket:r_{i}=0}2$ $\displaystyle=pg^{\ast}_{p}$ (44c)
$\displaystyle\Leftrightarrow d-1+\textstyle\sum_{i\in\llbracket
d\rrbracket}\tfrac{{g^{\ast}_{p}}^{2}r_{i}^{2}(-1-\sqrt{1+r_{i}^{2}{g^{\ast}_{p}}^{2}})}{r_{i}^{2}{g^{\ast}_{p}}^{2}}$
$\displaystyle=pg^{\ast}_{p}$ (44d) $\displaystyle\Leftrightarrow
pg^{\ast}_{p}+\textstyle\sum_{i\in\llbracket
d\rrbracket}\sqrt{1+r_{i}^{2}{g^{\ast}_{p}}^{2}}+1$ $\displaystyle=0.$ (44e)

We treat 44e as a root-finding problem in the variable $g^{\ast}_{p}<0$, which
can be easily solved due to Lemma 3. Expression 15b is obtained from 42. ∎

##  6 Proofs of Inverse Hessian Operators

We reuse the notation from Section 4. For convenience, we let
$\tilde{p}(t)=\tilde{p}+t\tilde{x}$ and we let $g^{\ast}(t)$ denote the
conjugate gradient at $\tilde{p}(t)$. We use ′ to denote derivatives with
respect to the linearization variable $t$, i.e.
$H^{\ast}(\tilde{p})\cdot\tilde{x}={g^{\ast}}^{\prime}(0)$.

###  6.1 Hypograph Power Cone

Proof of Proposition 8 Let us differentiate 27 and 28 at $\tilde{p}(t)$ with
respect to $t$. Differentiating 27:

$\displaystyle p+tx$
$\displaystyle=-(\varphi(-g^{\ast}_{r}(t))+g^{\ast}_{p}(t))^{-1}$ (45a)
$\displaystyle\Rightarrow x$
$\displaystyle=(\varphi(-g^{\ast}_{r}(t))+g^{\ast}_{p}(t))^{-2}(\tfrac{\operatorname{d}}{\operatorname{d}t}\varphi(-g^{\ast}_{r}(t))+{g^{\ast}_{p}}^{\prime}(t)).$
(45b)

Differentiating 28, for all $i\in\llbracket d\rrbracket$:

$\displaystyle r_{i}+tz_{i}$
$\displaystyle=-\tfrac{1-p(t)\alpha_{i}\varphi(-g^{\ast}_{r}(t))}{g^{\ast}_{r_{i}}(t)}$
(46a) $\displaystyle\begin{split}\Rightarrow
z_{i}&=g^{\ast}_{r_{i}}(t)^{-2}{g^{\ast}_{r_{i}}}^{\prime}(t)(1-p(t)\alpha_{i}\varphi(-g^{\ast}_{r}(t)))+g^{\ast}_{r_{i}}(t)^{-1}\alpha_{i}(x\varphi(-g^{\ast}_{r}(t))+{}\\\
&\hphantom{{}={}}p(t)\tfrac{\operatorname{d}}{\operatorname{d}t}\varphi(-g^{\ast}_{r}(t))).\end{split}$
(46b)

Now 45b and 46b give a nonlinear system that we wish to solve for
${g^{\ast}}^{\prime}(t)$. From the chain rule:

$\tfrac{\operatorname{d}}{\operatorname{d}t}\varphi(-g^{\ast}_{r}(t))=\varphi(-g^{\ast}_{r}(t))\textstyle\sum_{i\in\llbracket
d\rrbracket}\alpha_{i}(g^{\ast}_{r_{i}}(t))^{-1}{g^{\ast}_{r_{i}}}^{\prime}(t).$

From hereon let us drop the variable $t$ from our notation for brevity.
Define:

$K\coloneqq\textstyle\sum_{i\in\llbracket
d\rrbracket}\alpha_{i}{g^{\ast}_{r_{i}}}^{-1}{g^{\ast}_{r_{i}}}^{\prime}.$

From 46b, for all $i\in\llbracket d\rrbracket$:

${g^{\ast}_{r_{i}}}^{\prime}={g^{\ast}_{r_{i}}}^{2}\cdot\tfrac{z_{i}+{g^{\ast}_{r_{i}}}^{-1}\alpha_{i}(-x\varphi(-g^{\ast}_{r})-p\varphi(-g^{\ast}_{r})K)}{1-p\alpha_{i}\varphi(-g^{\ast}_{r})}.$
(47)

Multiplying 47 by $\alpha_{i}{g^{\ast}_{r_{i}}}^{-1}$ and summing over all
$i\in\llbracket d\rrbracket$ gives:

$\displaystyle K$ $\displaystyle=\textstyle\sum_{i\in\llbracket
d\rrbracket}\tfrac{z_{i}\alpha_{i}g^{\ast}_{r_{i}}+\alpha_{i}^{2}\varphi(-g^{\ast}_{r})(-x-pK)}{-p\alpha_{i}\varphi(-g^{\ast}_{r})+1}$
$\displaystyle\Rightarrow K$
$\displaystyle=\big{(}1+\textstyle\sum_{j\in\llbracket
d\rrbracket}\tfrac{\alpha_{j}^{2}\varphi(-g^{\ast}_{r})p}{1-p\alpha_{j}\varphi(-g^{\ast}_{r})}\big{)}^{-1}\textstyle\sum_{i\in\llbracket
d\rrbracket}\tfrac{z_{i}\alpha_{i}g^{\ast}_{r_{i}}+\alpha_{i}^{2}\varphi(-g^{\ast}_{r})(-x)}{1-p\alpha_{i}\varphi(-g^{\ast}_{r})}.$

Let $k_{1,i}\coloneqq 1-\alpha_{i}\varphi(-g^{\ast}_{r})p$ for all
$i\in\llbracket d\rrbracket$, $k_{2}\coloneqq\textstyle\sum_{i\in\llbracket
d\rrbracket}\nicefrac{{\alpha_{i}^{2}}}{{k_{1,i}}}$, and $k_{3}\coloneqq
1+\varphi(-g^{\ast}_{r})pk_{2}$. Then from 45b and 47:

$\displaystyle{g^{\ast}_{p}}^{\prime}$
$\displaystyle=(\varphi(-g^{\ast}_{r})+g^{\ast}_{p})^{2}x-K\varphi(-g^{\ast}_{r})$
(48a)
$\displaystyle=\bigl{(}(\varphi(-g^{\ast}_{r})+g^{\ast}_{p})^{2}+\tfrac{k_{2}{g^{\ast}_{p}}^{2}}{k_{3}}\bigr{)}x-\tfrac{\varphi(-g^{\ast}_{r})}{k_{3}}\langle
z,\tfrac{\alpha g^{\ast}_{r}}{k_{1}}\rangle,$ (48b)
$\displaystyle{g^{\ast}_{r_{i}}}^{\prime}$
$\displaystyle={g^{\ast}_{r_{i}}}^{2}\cdot\tfrac{z_{i}+{g^{\ast}_{r_{i}}}^{-1}\alpha_{i}(-x\varphi(-g^{\ast}_{r})-p\varphi(-g^{\ast}_{r})K)}{k_{1,i}}$
(48c)
$\displaystyle=\tfrac{{g^{\ast}_{r_{i}}}^{2}}{k_{1,i}}z_{i}-\tfrac{\alpha_{i}g^{\ast}_{r_{i}}}{k_{1,i}}\tfrac{\varphi(-g^{\ast}_{r})}{k_{3}}x-\tfrac{p\varphi(-g^{\ast}_{r})}{k_{3}}\langle
z,\tfrac{\alpha
g^{\ast}_{r}}{k_{1}}\rangle\tfrac{\alpha_{i}g^{\ast}_{r_{i}}}{k_{1,i}}\quad
i\in\llbracket d\rrbracket.$ (48d)

Now the desired result 17 can be obtained by invoking 16. Recall that in 48,
${g^{\ast}}^{\prime}=H^{\ast}(\tilde{p})\cdot\tilde{x}$. So we simply
_replace_ instances of $\tilde{p}$ and $g^{\ast}$ in 48 by $-g(\tilde{u})$ and
$-\tilde{u}$ respectively to obtain 17. ∎

###  6.2 Radial Power Cone

Proof of Proposition 9 Let:

$K\coloneqq\textstyle\sum_{i\in\llbracket
d_{2}\rrbracket}\alpha_{i}(g^{\ast}_{r_{i}}(t))^{-1}{g^{\ast}_{r_{i}}}^{\prime}(t).$
(49)

For $\varphi$ defined in Section 3.3, we have that:

$\displaystyle\tfrac{\operatorname{d}}{\operatorname{d}t}\varphi(-g^{\ast}_{r}(t))$
$\displaystyle=\textstyle\sum_{i\in\llbracket
d_{2}\rrbracket}\varphi(-g^{\ast}_{r}(t))\cdot
2\alpha_{i}(-g^{\ast}_{r_{i}}(t))^{-1}(-{g^{\ast}_{r_{i}}}^{\prime}(t))$
$\displaystyle=2\varphi(-g^{\ast}_{r})K.$

We fix $\zeta\coloneqq\varphi(-g^{\ast}_{r}(t))-\lVert
g^{\ast}_{p}(t)\rVert^{2}$ for convenience. We start by rearranging and
differentiating 37 at $\tilde{p}(t)$ with respect to a linearization variable
$t$, which we omit for brevity:

$\displaystyle x_{i}$
$\displaystyle=\tfrac{\operatorname{d}}{\operatorname{d}t}\bigl{(}\tfrac{2g^{\ast}_{p_{i}}(t)}{\zeta(\tilde{p}(t))}\bigr{)}$
(50a)
$\displaystyle=2\big{(}\tfrac{{g^{\ast}_{p_{i}}}^{\prime}}{\zeta}-\tfrac{g^{\ast}_{p_{i}}}{\zeta^{2}}(2\varphi(-g^{\ast}_{r})K-2\langle
g^{\ast}_{p},{g^{\ast}_{p}}^{\prime}\rangle)\big{)}$ $\displaystyle\forall
i\in\llbracket d_{1}\rrbracket.$ (50b)

We use 50b to obtain a new expression for $\langle
g^{\ast}_{p},{g^{\ast}_{p}}^{\prime}\rangle$:

$\displaystyle\langle x,g^{\ast}_{p}\rangle$
$\displaystyle=2\Bigl{(}\tfrac{\langle{g^{\ast}_{p}}^{\prime},g^{\ast}_{p}\rangle}{\zeta}-\tfrac{\lVert
g^{\ast}_{p}\rVert^{2}}{\zeta^{2}}(2\varphi(-g^{\ast}_{r})K-2\langle
g^{\ast}_{p},{g^{\ast}_{p}}^{\prime}\rangle)\Bigr{)}$ (51a)
$\displaystyle\Rightarrow\langle g^{\ast}_{p},{g^{\ast}_{p}}^{\prime}\rangle$
$\displaystyle=\tfrac{\zeta^{2}}{2k_{1}}\bigl{(}\langle
x,g^{\ast}_{p}\rangle+\tfrac{4\lVert
g^{\ast}_{p}\rVert^{2}}{\zeta^{2}}\varphi(-g^{\ast}_{r})K\bigr{)},$ (51b)

where $k_{1}\coloneqq\varphi(-g^{\ast}_{r})+\lVert g^{\ast}_{p}\rVert^{2}$.
Next, we differentiate 38b, for all $i\in\llbracket d_{2}\rrbracket$:

$\begin{split}-z_{i}g^{\ast}_{r_{i}}\zeta-
r_{i}{g^{\ast}_{r_{i}}}^{\prime}\zeta-2r_{i}g^{\ast}_{r_{i}}(\varphi(-g^{\ast}_{r})K-\langle
g^{\ast}_{p},{g^{\ast}_{p}}^{\prime}\rangle)={}\\\ \quad
4\alpha_{i}\varphi(-g^{\ast}_{r})K+2(1-\alpha_{i})(\varphi(-g^{\ast}_{r})K-\langle
g^{\ast}_{p},{g^{\ast}_{p}}^{\prime}\rangle),\end{split}$

whence, for all $i\in\llbracket d_{2}\rrbracket$ (replacing $\langle
g^{\ast}_{p},{g^{\ast}_{p}}^{\prime}\rangle$ using 51b):

$\displaystyle-r_{i}{g^{\ast}_{r_{i}}}^{\prime}\zeta$
$\displaystyle=4\alpha_{i}\varphi(-g^{\ast}_{r})K+2(1-\alpha_{i}+r_{i}g^{\ast}_{r_{i}})(\varphi(-g^{\ast}_{r})K-\langle
g^{\ast}_{p},{g^{\ast}_{p}}^{\prime}\rangle)+z_{i}g^{\ast}_{r_{i}}\zeta$ (52a)
$\displaystyle=4\alpha_{i}\varphi(-g^{\ast}_{r})K-4\alpha_{i}\tfrac{\varphi(-g^{\ast}_{r})}{\zeta}(\varphi(-g^{\ast}_{r})K-\langle
g^{\ast}_{p},{g^{\ast}_{p}}^{\prime}\rangle)+z_{i}g^{\ast}_{r_{i}}\zeta$ (52b)
$\displaystyle=\tfrac{2\alpha_{i}\varphi(-g^{\ast}_{r})}{k_{1}}\big{(}2\lVert
g^{\ast}_{p}\rVert^{2}K+\zeta\langle
g^{\ast}_{p},x\rangle\big{)}+z_{i}g^{\ast}_{r_{i}}\zeta.$ (52c)

In the second equality we use the identity, for all $i\in\llbracket
d_{2}\rrbracket$:

$1-\alpha_{i}+r_{i}g^{\ast}_{r_{i}}=-2\alpha_{i}\tfrac{\varphi(-g^{\ast}_{r})}{\zeta},$

which can be derived as follows. From 38a, we have that for all
$i\in\llbracket d_{2}\rrbracket$:

$\displaystyle r_{i}g^{\ast}_{r_{i}}$
$\displaystyle=-\tfrac{2\alpha_{i}\varphi(-g^{\ast}_{r})}{\zeta}-(1-\alpha_{i})$
(53a) $\displaystyle\Rightarrow\textstyle\sum_{j\in\llbracket
d_{2}\rrbracket:j\neq i}-r_{j}g^{\ast}_{r_{j}}\alpha_{i}$
$\displaystyle=\textstyle\sum_{j\in\llbracket d_{2}\rrbracket:j\neq
i}\Bigl{(}\tfrac{2\alpha_{i}\alpha_{j}\varphi(-g^{\ast}_{r})}{\zeta}+\alpha_{i}(1-\alpha_{j})\Bigr{)}.$
(53b)

Multiplying 53a by $(1-\alpha_{i})$ and adding 53b, we get:

$\displaystyle(1-\alpha_{i})r_{i}g^{\ast}_{r_{i}}-\textstyle\sum_{j\in\llbracket
d_{2}\rrbracket:j\neq i}\alpha_{i}r_{j}g^{\ast}_{r_{j}}$
$\displaystyle=-1+d_{2}\alpha_{i}$ $\displaystyle\forall i\in\llbracket
d_{2}\rrbracket.$ (54)

Combining 54 with 2, for all $i\in\llbracket d_{2}\rrbracket$:

$\displaystyle
r_{i}g^{\ast}_{r_{i}}+\tfrac{-1+d_{2}\alpha_{i}-(1-\alpha_{i})r_{i}g^{\ast}_{r_{i}}}{-\alpha_{i}}+\langle
p,g^{\ast}_{p}\rangle$ $\displaystyle=-d_{2}-1$ (55a)
$\displaystyle\Rightarrow 1-\alpha_{i}+r_{i}g^{\ast}_{r_{i}}$
$\displaystyle=\alpha_{i}\bigl{(}\langle p,-g^{\ast}_{p}\rangle-2\bigr{)}.$
(55b)

Combining 55b with 37 gives the result:

$1-\alpha_{i}+r_{i}g^{\ast}_{r_{i}}=-2\alpha_{i}\Bigl{(}\tfrac{\lVert
g^{\ast}_{p}\rVert^{2}}{\zeta}+1\Bigr{)}=-2\alpha_{i}\tfrac{\varphi(-g^{\ast}_{r})}{\zeta}.$

Next, substituting into ${g^{\ast}_{r_{i}}}^{\prime}$ from 52c into 49:

$\displaystyle K$ $\displaystyle=-\textstyle\sum_{i\in\llbracket
d_{2}\rrbracket}\alpha_{i}(g^{\ast}_{r_{i}})^{-1}\tfrac{2\alpha_{i}\varphi(-g^{\ast}_{r})k_{1}^{-1}\big{(}2\lVert
g^{\ast}_{p}\rVert^{2}K+\zeta\langle
g^{\ast}_{p},x\rangle\big{)}-z_{i}(-g^{\ast}_{r_{i}})\zeta}{r_{i}\zeta}$
$\displaystyle=\tfrac{-2k_{2}k_{1}^{-1}\varphi(-g^{\ast}_{r})\langle
x,g^{\ast}_{p}\rangle-\langle\nicefrac{{\alpha}}{{r}},z\rangle}{1+4k_{2}k_{1}^{-1}\varphi(-g^{\ast}_{r})\lVert
g^{\ast}_{p}\rVert^{2}},$

where
$k_{2}\coloneqq\langle\nicefrac{{\alpha}}{{r}},\nicefrac{{\alpha}}{{g^{\ast}_{r}}}\rangle$.
To obtain ${g^{\ast}_{p}}^{\prime}$, we replace $\langle
g^{\ast}_{p},{g^{\ast}_{p}}^{\prime}\rangle$ in 50b using the expression in
51b, then substitute for $K$. Define for convenience
$k_{3}\coloneqq\nicefrac{{k_{1}}}{{2\varphi(-g^{\ast}_{r})}}+\nicefrac{{2k_{2}\lVert
g^{\ast}_{p}\rVert^{2}}}{{\zeta}}$. Then:

$\displaystyle{g^{\ast}_{p}}^{\prime}$
$\displaystyle=\zeta\big{(}\tfrac{x}{2}+\tfrac{g^{\ast}_{p}}{\zeta^{2}}(2\varphi(-g^{\ast}_{r})K-2\langle
g^{\ast}_{p},{g^{\ast}_{p}}^{\prime}\rangle)\big{)}$ (56a)
$\displaystyle=\tfrac{\zeta}{2}x-\tfrac{g^{\ast}_{p}}{k_{3}}\big{(}\tfrac{2k_{2}\varphi(-g^{\ast}_{r})+\zeta
k_{3}}{k_{1}}\langle
x,g^{\ast}_{p}\rangle+\langle\nicefrac{{\alpha}}{{r}},z\rangle\big{)}.$ (56b)

Finally, substituting for $K$ in 52c and rearranging, for all $i\in\llbracket
d_{2}\rrbracket$:

${g^{\ast}_{r_{i}}}^{\prime}=-\tfrac{g^{\ast}_{r_{i}}}{r_{i}}z_{i}+\tfrac{\alpha_{i}}{k_{3}r_{i}}\bigr{(}-\langle
x,g^{\ast}_{p}\rangle+\tfrac{2\lVert
g^{\ast}_{p}\rVert^{2}}{\zeta}\langle\nicefrac{{\alpha}}{{r}},z\rangle\bigr{)}.$
(57)

As in Section 4.1, applying 16 to 56 and 57 gives the result 18. ∎

###### Acknowledgements.

This work has been partially funded by the National Science Foundation under
grant OAC-1835443 and the Office of Naval Research under grant
N00014-18-1-2079. The authors thank the anonymous reviewers and editor for
their comments and suggestions.

## References

  * (1) Andersen, M.S., Dahl, J., Vandenberghe, L.: Logarithmic barriers for sparse matrix cones.  Optimization Methods and Software 28(3), 396–423 (2013).  DOI https://doi.org/10.1080/10556788.2012.684353
  * (2) Borchers, B.: CSDP, a C library for semidefinite programming.  Optimization Methods and Software 11(1-4), 613–623 (1999).  DOI https://doi.org/10.1080/10556789908805765
  * (3) Chares, R.: Cones and interior-point algorithms for structured convex optimization involving powers and exponentials.  Ph.D. thesis, Université Catholique de Louvain (2009)
  * (4) Coey, C.: Interior point and outer approximation methods for conic optimization.  Ph.D. thesis, Massachusetts Institute of Technology (2022)
  * (5) Coey, C., Kapelevich, L., Vielma, J.P.: Conic optimization with spectral functions on Euclidean Jordan algebras.  arXiv preprint arXiv:2103.04104 (2021).  DOI https://doi.org/10.48550/arXiv.2103.04104
  * (6) Coey, C., Kapelevich, L., Vielma, J.P.: Hypatia cones reference (2021).  URL https://github.com/chriscoey/Hypatia.jl/wiki/.  Accessed 26 June 2022
  * (7) Coey, C., Kapelevich, L., Vielma, J.P.: Performance enhancements for a generic conic interior point algorithm.  arXiv preprint arXiv:2107.04262 (2021).  DOI https://doi.org/10.48550/arXiv.2107.04262
  * (8) Coey, C., Kapelevich, L., Vielma, J.P.: Solving natural conic formulations with Hypatia.jl.  INFORMS Journal on Computing (2022).  DOI https://doi.org/10.1287/ijoc.2022.1202.  Published online
  * (9) Corless, R.M., Jeffrey, D.J.: The Wright $\omega$ function.  In: J. Calmet, B. Benhamou, O. Caprotti, L. Henocque, V. Sorge (eds.) Artificial Intelligence, Automated Reasoning, and Symbolic Computation, pp. 76–89. Springer (2002).  DOI https://doi.org/10.1007/3-540-45470-5˙10
  * (10) Dahl, J., Andersen, E.D.: A primal-dual interior-point algorithm for nonsymmetric exponential-cone optimization.  Mathematical Programming 194(1–2), 341–370 (2022).  DOI https://doi.org/10.1007/s10107-021-01631-4
  * (11) Güler, O.: Barrier functions in interior point methods.  Mathematics of Operations Research 21(4), 860–885 (1996)
  * (12) Lewis, A.S.: The convex analysis of unitarily invariant matrix functions.  Journal of Convex Analysis 2(1), 173–183 (1995)
  * (13) MOSEK ApS: Modeling Cookbook Release 3.2.3 (2022).  URL https://docs.mosek.com/modeling-cookbook/index.html.  Accessed 3 July 2022
  * (14) Myklebust, T., Tunçel, L.: Interior-point algorithms for convex optimization based on primal-dual metrics.  arXiv preprint arXiv:1411.2129 (2014).  DOI https://doi.org/10.48550/arXiv.1411.2129
  * (15) Nemirovski, A., Tunçel, L.: “Cone-free” primal-dual path-following and potential-reduction polynomial time interior-point methods.  Mathematical Programming 102(2), 261–294 (2005).  DOI https://doi.org/10.1007/s10107-004-0545-4
  * (16) Nesterov, Y.: Towards non-symmetric conic optimization.  Optimization Methods and Software 27(4-5), 893–917 (2012).  DOI https://doi.org/10.1080/10556788.2011.567270
  * (17) Nesterov, Y.: Lectures on Convex Optimization, _Springer Optimization and Its Applications_ , vol. 137.  Springer Cham (2018).  DOI https://doi.org/10.1007/978-3-319-91578-4
  * (18) Nesterov, Y., Nemirovskii, A.: Interior-Point Polynomial Algorithms in Convex Programming.  Studies in Applied Mathematics. SIAM (1994).  DOI https://doi.org/10.1137/1.9781611970791
  * (19) Nesterov, Y., Todd, M.J., Ye, Y.: Infeasible-start primal-dual methods and infeasibility detectors for nonlinear programming problems.  Mathematical Programming 84(2), 227–267 (1999).  DOI https://doi.org/10.1007/s10107980009a
  * (20) Nesterov, Y.E., Todd, M.J.: Self-scaled barriers and interior-point methods for convex programming.  Mathematics of Operations Research 22(1), 1–42 (1997).  DOI https://doi.org/10.1287/moor.22.1.1
  * (21) Nesterov, Y.E., Todd, M.J.: Primal-dual interior-point methods for self-scaled cones.  SIAM Journal on Optimization 8(2), 324–364 (1998).  DOI https://doi.org/10.1287/moor.22.1.1
  * (22) Papp, D., Yıldız, S.: alfonso: Matlab package for nonsymmetric conic optimization.  INFORMS Journal on Computing 34(1), 11–19 (2022).  DOI https://doi.org/10.1287/ijoc.2021.1058
  * (23) Roy, S., Xiao, L.: On self-concordant barriers for generalized power cones.  Optimization Letters 16(2), 681–694 (2022).  DOI https://doi.org/10.1007/s11590-021-01748-7
  * (24) Serrano, S.A.: Algorithms for unsymmetric cone optimization and an implementation for problems with the exponential cone.  Ph.D. thesis, Stanford University (2015)
  * (25) Skajaa, A., Ye, Y.: A homogeneous interior-point algorithm for nonsymmetric convex conic optimization.  Mathematical Programming 150(2), 391–422 (2015).  DOI https://doi.org/10.1007/s10107-014-0773-1
  * (26) Süli, E., Mayers, D.F.: An Introduction to Numerical Analysis.  Cambridge University Press (2003)
  * (27) Tunçel, L.: Generalization of primal—dual interior-point methods to convex optimization problems in conic form.  Foundations of Computational Mathematics 1(3), 229–254 (2001).  DOI https://doi.org/10.1007/s002080010009
  * (28) Vandenberghe, L.: The CVXOPT linear and quadratic cone program solvers (2010).  URL https://www.seas.ucla.edu/~vandenbe/publications/coneprog.pdf.  Accessed 28 May 2022
  * (29) Yamashita, M., Fujisawa, K., Kojima, M.: Implementation and evaluation of SDPA 6.0 (semidefinite programming algorithm 6.0).  Optimization Methods and Software 18(4), 491–505 (2003).  DOI https://doi.org/10.1080/1055678031000118482