{'fraction_non_alphanumeric': 0.05376972530683811, 'fraction_numerical': 0.01532567049808429, 'mean_word_length': 4.2631578947368425, 'pattern_counts': {'":': 0, '<': 4, '<?xml version=': 0, '>': 6, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Computing conjugate barrier information for nonsymmetric cones

The recent interior point algorithm by Dahl and Andersen [10] for nonsymmetric cones as well as earlier works [16,19] 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.


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 primaldual interior point methods (PDIPMs) specialized for these cones only (e.g. [2,29,28]). 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 [20]. 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 [19] and [16], 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 [24], the three-dimensional power cone [16], and the cone of sparse positive semidefinite matrices with chordal sparsity [1]. Additionally, [19] 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 [25], which has been implemented in the solvers Alfonso [22] and Hypatia [8]. 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 [10], which is implemented by the MOSEK solver [13]. The algorithm is based on a technique by [27,14] which generalizes the concept of scaling matrices from symmetric cones. Like the algorithm of [25], the linear systems solved in each iteration are equal in size to those arising in symmetric algorithms. Unlike the algorithm of [25], 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 [25], although there is no proof of polynomial time convergence. One might expect, owing to the use of conjugate barrier in-formation, that the search directions of [10] would allow convergence in fewer iterations than the search directions of [25].
The search directions in the algorithm by [10] 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 = T w and g(w) = T g * (r), where g and g * denote the gradients of the primal barrier and its conjugate [20,21]. A key idea of [14,10] 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 [10], procedures for evaluating conjugate gradients are useful due to their applications in the frameworks by [19,16]. 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-determinant function. Hypograph power cone, the hypograph of the power mean function. Root-determinant cone, the hypograph of the dth-root-determinant function. Radial power cone, the generalized power cone by [3, Section 3.1.2]. Infinity norm cone, the epigraph of the ℓ ∞ 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 [7]. The inverse Hessian is already known for five of the cones above [5,4], so we only show it for the hypograph and radial power cones.

Notation
We use R d + , R d ++ , R d − , and R d −− to denote the d-dimensional vectors of nonnegative, positive, nonpositive, and negative reals respectively. Likewise, S d + and 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 d := {1, 2, . . . , d}. 1 P is the indicator function, that is equal to one if statement P is true and zero otherwise. For a set C, cl(C) and 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, ·, · for an inner product between vectors or matrices, and e to denote a vector of ones. V ⊤ is the transpose of V with respect to ·, · . Throughout this paper, division and multiplication between vectors should be interpreted as componentwise. The operator 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.

Cones and Barrier Functions
A proper cone K is closed, convex, pointed, and full-dimensional. The dual Analysis of conic interior point methods relies on associating with each cone a logarithmically-homogeneous, self-concordant barrier (LHSCB). Follow- converging to the boundary of K, and: As a consequence of (1b), the gradient g of f satisfies [20, Equation (2.5)]: For the LHSCB f , we define the convex conjugate, f * , as the function: In fact, f * is an LHSCB for K * [20, Equation (2.6)] and we refer to it as the conjugate barrier. The gradient g * of f * may be defined from the unique solutions to the optimization problem in (3): From (3), (4) and (2): We refer to g * as the conjugate gradient (which has no relation to the method of conjugate gradients). The negative gradients of LHSCBs f and f * are bijective linear maps between K and K * . In particular [14, Theorem 2.5]: − g * (−g(w)) = w ∀w ∈ K, −g(−g * (r)) = r ∀r ∈ K * .
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 [12].
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.

Logarithm Cone and Log-determinant Cone
Let ϕ : R d ++ → R be the function ϕ(w) := i∈ d log w i . Define the logarithm cone: which admits the (2 + d)-LHSCB [5, Section 6]: The dual cone is given by [8, Section 5.5]: Let ω denote the Wright omega function [9], which can be well approximated in O(1) time and satisfies for all real β: The Wright omega function is used in [24,Chapter 8] for deriving the conjugate barrier of a three-dimensional variant of K log and in [15, Section 7.1] for the conjugate barrier of the epigraph of the univariate entropy function.
The conjugate gradient at (p, q, r) ∈ int(K * log ) has components: where,ω : The proof is given in Section 5.1. By substituting (9) in (5), we obtain the conjugate barrier: The conjugate gradient for K log can be easily modified to obtain a conjugate gradient for the log-determinant cone [8, Section 5.6]: which has the dual: R be the eigendecomposition of R, and letΩ := d·ω 1 /d 1+d− q /p+ i∈ d log(− λR,i /p) − log(d) . The conjugate gradient G * has components: Proof For fixed u and v, F is a unitarily invariant function of W . Due to (7), the gradient of F is The result can be verified from this and (6). ⊓ ⊔
The proof is given in Section 5.2.

Proposition 3.3
The conjugate gradient at (p, r) ∈ int(K * hpower ) has components: whereŷ is the root of h from Lemma 3.1. In the case where α = e /d, the conjugate gradient at (p, r) ∈ int(K * hgeom ) can be written more simply: The proof is given in Section 5.2. Substituting (12) in (5), we obtain a simple expression for the conjugate barrier of K hgeom : The conjugate gradient for K hgeom can be easily modified to obtain a conjugate gradient for the root-determinant cone [8, Section 5.4]: which has the dual: The conjugate gradient G * has components: Proof For fixed u, F is a unitarily invariant function of W . Similar to Proposition 3.2, the result can be verified from (6) and (7). ⊓ ⊔

Proposition 3.5
The conjugate gradient at (p, r) ∈ int(K * rpower ) is given by: whereŷ is the positive root of h from Lemma 3.2. In the case where d 1 = 1 and α = e /d2, the conjugate gradient at (p, r) ∈ int(K * rgeom ) is: Note y − is from Lemma 3.2. The proof is given in Section 5.3.

Infinity Norm Cone and Spectral Norm Cone
Define the infinity norm cone [8, Section 5.1]: which admits the (1 + d)-LHSCB [11, section 7.5]: The dual cone is the epigraph of the ℓ 1 norm function: The proof is given in Section 5.4.

Proposition 3.6
The conjugate gradient at (p, r) ∈ int(K * ℓ∞ ) is given by: whereŷ is the negative root of h from Lemma 3.3.
The proof is given in Section 5.4. The conjugate gradient for K ℓ∞ can be easily modified to obtain a conjugate gradient for the spectral norm cone [8, Section 5.2]: where σ max is the maximum singular value function and The dual cone is the epigraph of the nuclear norm: Let W = U W Diag(σ W )V ⊤ W be the singular value decomposition of W . K ℓspec admits the (1 + d 1 )-LHSCB: Proposition 3.7 The conjugate gradient G * at (p, R) ∈ int(K * ℓspec ) has components: Proof For fixed u, F is a unitarily invariant function of W . Similar to Proposition 3.2, the result can be verified using (6) and (7). ⊓ ⊔

Inverse Hessians
In [5] the authors derive efficient inverse Hessian operators for a number of cones, including K log , K logdet , K hgeom , and K rtdet . Inverse Hessians for K ℓ∞ and K ℓspec are described in [4]. The authors are motivated by the need to apply inverse Hessians in several parts of the algorithm implemented by the Hypatia solver [7]. The inverse Hessian is used to measure proximity to the central path as well as some of the linear system solving methods described in [7,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 K hpower or K 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 K, K * ⊂ R 1+d , where K is either K hpower or K rpower parametrized by α, letũ = (u, w) ∈ int(K), andx = (x, z) ∈ R 1+d be an arbitrary direction. Due to [20,Equation (2.11)]: Therefore to derive the inverse Hessian operator H(ũ) −1 ·x, we may derive an expression for H * (p) ·x, for arbitraryp = (p, r) ∈ int(K * ), and substitute −g(ũ) forp. In a practical implementation of a PDIPM, g(ũ) is usually already available at the time when H(ũ) −1 is needed. Note that: The right hand side can be deduced from our calculations for g * .

Hypograph Power Cone
Proposition 4.1 The inverse Hessian operator atũ in the directionx is: where ϕ is defined as in Section 3.2, and: The proof is given in Section 6.1.

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

Hypograph Power Cone
Proof of Lemma 3.1 For ϕ given in Section 3.2, letŷ denote the root of h from Lemma 3.1, which we show is unique. Note thatŷ must satisfy: Since (p, r) ∈ int(K * hpower ), this impliesŷ > 0. The derivatives of h are: Note that p < 0 for (p, r) ∈ int(K * hpower ) and therefore h ′ (y) > 0 for all y > max i∈ d {pα 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 − <ŷ (Lemma 5.1). We may pick, for example, y − = 0, which ensures y − <ŷ and y − is in the domain of h.
We have that h is decreasing for p, y > 0 (and cannot have more than one root), since: h ′ (y) < 2 i∈ d2 α 2 i aiy+ (1 + α i ) /p − 2 y y(y+ 2 /p) ≤ 2 1 y+ (1 + 1) /p − 2 1 y+ 2 /p = 0. (32) In the second inequality we use the fact that the preceding expression is convex in α, and therefore maximized at an extreme point of the simplex that α belongs to. Similar reasoning shows that h ′′ (y) > 0 for p, y > 0: The second inequality follows from the fact that the preceding expression is concave in α.