title: Interior-point methods for unconstrained geometric programming and scaling problems
authors: Peter Bürgisser Yinan Li Harold Nieuwboer Michael Walter
text: 
  
  
    We provide a condition-based analysis of two interior-point methods for unconstrained geometric programs, a class of convex programs that arise naturally in applications including matrix scaling, matrix balancing, and entropy maximization.
    Our condition numbers are natural geometric quantities associated with the Newton polytope of the geometric program, and lead to diameter bounds on approximate minimizers.
    We also provide effective bounds on the condition numbers both in general and under combinatorial assumptions on the Newton polytope.
    In this way, we generalize the iteration complexity of recent interior-point methods for matrix scaling and matrix balancing.
    Recently, there has been much work on algorithms for certain optimization problems on Lie groups, known as capacity and scaling problems.
    For commutative groups, these problems reduce to unconstrained geometric programs, which serves as a particular source of motivation for our work.
  
  Rogue waves on the double periodic background in Hirota equation
      N. Sinthuja 1, K. Manikandan 1 M. Senthilvelan 1, e-mail:velan@cnld.bdu.ac.in
      December 30, 2023
  =================================================================================
  
  
  
  
  
  
  § INTRODUCTION
  
  
  Geometric programming is an optimization paradigm that generalizes linear programming and has a wide range of applications <cit.>.
  In this paper, we are concerned with unconstrained geometric programs.
  These are optimization problems of the form
  
      minimize      f(z⃗) 
      subject to     z⃗∈^n,  z⃗ > 0⃗,
  
  where f(z⃗) is a posynomial in positive real variables z_1,…,z_n.
  That is,
  
      f(z⃗) = ∑_i=1^k q_i z⃗^ω_i = ∑_i=1^k q_i ∏_j=1^n z_j^ω_i,j,
  
  where the coefficients q_i are positive and the exponents ω_i,j are real numbers.
  In a general geometric program (GP), one adds posynomial inequality and monomial equality constraints.
  
  Although posynomials are non-convex in general, they are convex in x⃗ after the change of variables z⃗ = e^x⃗.
  As such, they are the simplest family of geodesically convex programming problems.
  
  It is well-known that standard convex programming techniques, like the ellipsoid method or interior-point methods, can solve GP in polynomial time, see for instance <cit.>.
  Furthermore, it has been observed that interior-point methods are also efficient and robust in practice (cf. <cit.>).
  However, explicit iteration complexity bounds are not readily available in the current literature.
  
  In this paper, we present a detailed analysis of two interior-point algorithms for unconstrained GP in terms of natural geometric condition numbers.
  Our first algorithm applies to instances that (roughly speaking) have a well-conditioned Newton polytope, while our second algorithm has no such assumption but instead relies on a novel condition number for the GP.
  We also provide effective bounds on these condition numbers both in general and under suitable combinatorial assumptions.
  The latter assumptions apply in particular to matrix scaling and balancing and, as a consequence, we match the iteration complexity of the recent work <cit.>.
  In fact, the recent interest in generalized scaling problems is a particular source of motivation for this paper, and we expand on this connection in <ref>.
  
  
  
  
   §.§ Computational problems
  
  
  Let us discuss the computational problems associated with (<ref>) in more detail.
  We first introduce some terminology and notation.
  We write q⃗=(q_1,…,q_k)∈^k_++ for the vector of coefficients and Ω={ω_1,…,ω_k}⊆^n for the set of exponents of the posynomial (<ref>).
  By the logarithmic change of variables e^x_j = z_j, j ∈ [n], and e^F = f, we can write (<ref>) as
  [Throughout this paper log is the natural logarithm (so with respect to base e).]
  
      F^* = inf_x⃗∈^n F(x),    F(x) = log∑_i=1^k q_ie^ω_ix⃗,
  
  where ·· denotes the standard inner product in ^n.
  The objective F(x) is a convex function.
  It will in general not attain its infimum F^*, as the domain is unbounded.
  The problem of unconstrained geometric programming is to approximate the infimum to arbitrary precision:
  
  [Unconstrained GP]
  Given as input the exponents ω_1,…,ω_k∈^n, coefficients q⃗∈^k_++, and a precision δ∈(0,1), find x⃗_δ∈^n such that F(x⃗_δ)≤F^* + δ.
  
  
  Clearly, any solution to this problem provides a (1+2δ)-multiplicative and a (2 q_1 δ)-additive approximation to the value of the original geometric program (<ref>).
  
  <Ref> depends crucially on the Newton polytope of f, which is defined as the convex hull of the exponents Ω={ω_1,…,ω_k} (recall that all coefficients q_j are assumed nonzero).
  Two well-known important properties are:
  
  
    * the infimum exists (i.e., F^* > -∞) if and only if 0⃗∈Ω, and
  
    * the infimum is attained (i.e., F^*=F(x) for some x∈^n, so in particular F^* is finite) if and only if 0⃗∈Ω.
  
  Property (a) characterizes when <ref> has a solution.
  It follows from the observation that F is unbounded from below if and only if there exists some x∈^n such that ω_ix<0 for all i∈[k], which in turn is equivalent to 0∉Ω by Farkas' lemma.
  Thus, deciding whether F^* is finite or not can be done by testing membership in the Newton polytope (a linear programming problem).
  
  Property (b) may be interpreted as characterizing when the instance is well-conditioned.
  To get some intuition, one can verify that the gradient F(x) is a convex combination of the exponents ω_i, with positive coefficients.
  Thus if F has a minimum then 0 is in relative interior of the Newton polytope.
  We give a quantitative version of the reverse implication in <ref>.
  
  By convexity, <ref> is directly related to the problem of minimizing the gradient F(x).
  We refer to this as the associated scaling problem, as it captures the well-known polynomial scaling and matrix scaling problems as important special cases (see <ref> for details).
  
  [Scaling problem]
  Given as input the exponents ω_1,…,ω_k∈^n, coefficients q⃗∈_++^k, and a precision ϵ > 0, find x⃗_ϵ∈^n such that F(x⃗_ϵ)_2≤ϵ.
  
  
  The scaling problem is feasible for all ϵ>0 precisely when F is bounded from below, that is, when the Newton polytope contains the origin.
  
  In many applications, which we will elaborate on in <ref>, one is naturally interested in varying a given geometric program by translating all exponents by some fixed vector θ∈^n.
  
  For this, let
  
      F^*_θ=inf_x⃗∈^nF_θ(x⃗),   
        F_θ(x⃗) = log∑_i=1^k q_ie^ω_i - θx⃗
        = F(x) - θ x.
  
  
  
  
  When we refer to the Newton polytope of such a shifted problem, we always mean the convex hull of the original exponents Ω={ω_1,…,ω_k}.
  
  In the remainder of this paper we will focus on solving the following computational problems, which generalize <ref>:
  
  [Unconstrained GP with shift]
  Given as input a shift θ∈^n, exponents ω_1,…,ω_k∈^n, q ∈^k_++, and a precision δ∈(0,1), find x_δ∈^n such that F_θ(x_δ) ≤ F_θ^* + δ.
  
  
  [Scaling problem with shift]
  Given as input a shift θ∈^n, exponents ω_1,…,ω_k∈^n, q ∈_++^k, and a precision ϵ > 0, find x_ϵ∈^n such that F_θ(x_ϵ)_2= F(x⃗_ϵ) - θ_2≤ϵ.
  
  
  Throughout we will always assume that the shift is contained in the Newton polytope (i.e., θ∈Ω).
  This assumption is natural, since otherwise the two problems have no solution (the latter for small ϵ), as follows from properties (a) and (b).
  
  
  
  
  
  
   §.§ Motivations and prior work
  
  
  Before discussing our results we discuss three important motivations from machine learning and optimization, which reduce to unconstrained GPs and have been subject of intense recent research.
  This will also shed more light on the connection between <ref>.
  
  
  
  
    §.§.§ Entropy maximization
  
  The Lagrange dual of the convex optimization problem (<ref>) is given by an entropy maximization problem.
  More precisely,
  
      F^*_θ = inf_x∈^n F_θ(x) = sup{ -D_(p⃗q⃗)  : ∑_i=1^k p_iω_i=θ, ∑_i=1^k p_i=1, p⃗≥ 0 },
  
  where D_(p⃗‖q⃗) =∑_i=1^k p_ilogp_i/q_i denotes the Kullback–Leibler (KL) divergence between a probability distribution p⃗ and the distribution q⃗ (which need not be normalized).
  Thus, the dual program (<ref>) is feasible when θ is in the Newton polytope, and the optimal solution is a probability distribution on Ω≅ [k] with mean θ that minimizes the KL divergence to the initial distribution q⃗.
  When q⃗=(1,…,1) is the all-ones vector, -D_(p⃗q⃗) = ∑_i=1^k p_i log1/p_i is the Shannon entropy of p.
  In this case, <ref> amounts to the discrete entropy maximization problem which naturally arises in machine learning and statistics, motivated by the maximum entropy principle <cit.>.
  
  To solve the entropy maximization problem, <cit.> proposed ellipsoid methods for the equivalent geometric program (<ref>) that are tractable even when k is large.
  
  They focused on the case that Ω consists of integer vectors (which is already of substantial interest) and gave a priori diameter bounds as required for the ellipsoid method.
  In <cit.>, it was shown that
  if θ is at a distance η>0 from the boundary of the Newton polytope then there is a minimizer x⃗^* of norm x⃗^*_2≤log k/η.
  In <cit.>, a diameter bound was obtained in terms of the unary facet complexity of the Newton polytope:
  if Ω can be described by linear inequalities with integer coefficients in {-M,…,M}, then for any θ∈Ω there is a δ-approximate minimizer x⃗_δ to the problem (<ref>) with x⃗_δ_2≤ R where R = (n,M,log1/δ).
  This bound is particularly useful if θ is very close to (or on) the boundary of the Newton polytope.
  Below we show how to generalize these diameter bounds to the case that the Newton polytope is not integral.
  
  More recently, <cit.> discusses a second-order box-constrained Newton method for entropy maximization, based on results from <cit.>.
  The number of required iterations for approximately minimizing the objective is polynomial in R, log1/δ and a parameter known as the robustness parameter of the objective.
  Robustness of the objective gives local quadratic approximations, and the robustness parameter controls the diameter of the region in which these approximations hold.
  A more general version of this second-order method is presented in <cit.>.
  
  
  
    §.§.§ Matrix scaling
  
  Let M ∈^n × n be a matrix with non-negative entries, and suppose we are given non-negative vectors r⃗, c⃗∈^n with r⃗_1 = c⃗_1 = 1.
  Let r(M) denote the vector of row sums of M, and let c(M) denote the vector of column sums.
  Then the (r,c)-matrix scaling problem asks us to rescale the rows and columns of M so that its row and column sums are given by r⃗ and c⃗, respectively.
  That is, we wish to find positive diagonal matrices L, R ∈^n such that r(LMR) = r and c(LMR) = c.
  This problem is very well-studied and has a wide range of applications (see, e.g., <cit.> and references therein).
  A strongly polynomial algorithm based on the Sinkhorn-Knopp algorithm is presented in <cit.>, and recent works provide very fast algorithms <cit.>.
  
  
  The connection to unconstrained GP is as follows.
  Consider the objective
  
      f(x_1, …, x_n, y_1, …, y_n) = ∑_i,j=1^n M_ij e^x_i + y_j
  
  in 2n variables and let θ=(r,c).
  Then,
  
      ∇ F_θ(x,y) = ∑_i,j N_ij (e_i,e_j)/∑_i,j N_ij - θ = (r(N),c(N))/ N_1 - (r,c),
  
  where N = LMR is the matrix rescaled by L = (e^x_i) and R = (e^y_j).
  This shows that finding an approximate (r,c)-matrix scaling is precisely equivalent to <ref> and can be achieved by solving a geometric program, as in <ref>.
  Indeed, state-of-the-art algorithms for matrix scaling (as well as the very similar matrix balancing problem) are based on minimizing F_θ or closely related functions, and our results can be understood as a generalization of the interior point method of <cit.> to arbitrary unconstrained GPs.
  
  
  
    §.§.§ Optimization over linear group actions
  
  Let G be a continuous group acting linearly on a complex vector space V=^k by a representation π G→(V), with (V) the group of invertible linear operators.
  The action partitions the vector space into orbits 𝒪_v⃗ = {π(g)v⃗ : g ∈ G} for v⃗∈ V.
  
  A basic algorithmic problem is then to compute the smallest norm of any vector in an orbit, known as the capacity (v⃗)=inf{w⃗_2: w⃗∈𝒪_v⃗} of v⃗.
  
  The capacity problem for suitable groups and actions captures natural important problems in computational complexity, algebra, analysis, quantum information, and statistics: see the recent developments <cit.>. 
  In the special case when G is commutative, estimating the capacity of a vector can be recast as an unconstrained GP <cit.>.
  We briefly recall the connection.
  Let G=(n) be the group of invertible diagonal complex n× n matrices.
  
  Under very mild assumptions, π has the following simple form: there exists an orthonormal basis e⃗_1,…,e⃗_k of V and integer vectors ω_1,…,ω_k∈^n such that π(g) e_i = ∏_j=1^n g_j^ω_i,j e_i for any i∈[k] and g=(g_1,…,g_n)∈(n).
  Accordingly, given an arbitrary vector v=∑_i=1^k v_i e_i we have
  
      π(g) v_2^2
      
      = ∑_i=1^k v_i^2 ∏_j=1^n g_j^2ω_i,j,
  
  By replacing q_i = v_i^2 and e^x_j=g_j^2, we see that computing log(v⃗) reduces to solving an unconstrained GP of the form (<ref>).
  
  To make this connection concrete, we briefly sketch how the matrix scaling problem discussed earlier arises as a special case.
  Consider the group G=(n) ×(n) ≅(2n) and the vector space V=^n× n of complex n× n-matrices, endowed with the Frobenius norm.
  The action is given by π(g,h)A = g A h.
  
  Then,
  
      π(g,h) A_F^2
      = ∑_i,jg_i A_ij h_j^2.
  
  Therefore, substituting g_i^2 = e^x_i, h_j^2 = e^y_j, and M_ij = A_ij^2 returns us precisely to the situation of <ref>.
  
  Interestingly, most of the concepts used in the above discussions are not restricted to the case where G is commutative.
  We briefly recall some of the concepts and refer the readers to <cit.> for more details.
  Consider a `nice' noncommutative group such as G=(n) acting on V by π G→(V).
  The function F(g) = logπ(g)v⃗_2 is not convex but geodesically convex.
  Geodesic convexity can be thought of as a generalization of convexity in Euclidean spaces to arbitrary Riemannian manifolds.
  Here this means that the function F(exp(tH) g) is convex in t∈ for any Hermitian n× n matrix H and g∈(n), where exp(·) denotes the matrix exponential map.
  We can minimize geodesically convex functions on Riemannian manifolds just as in the Euclidean case by minimizing the gradient ∇ F(g), which in the present context is the Hermitian n× n matrix defined by the property:
  (∇ F(g) H)=∂_t=0logπ(exp(tH) gv⃗_2.
  A surprising result is that the closure of the set {(∇ F(g)) : g ∈ G }, where (·) denotes the vector of eigenvalues of a Hermitian matrix in non-increasing order, is always a convex polytope, known as a moment polytope <cit.>!
  Note that when restricted back to the commutative group setting, all the aforementioned concepts coincide with the ordinary ones (geodesically convex → convex, Riemannian gradient → gradient, moment polytope → Newton polytope).
  Thus, efficient algorithms for solving unconstrained GP and the corresponding scaling problem are an important step towards a deeper understanding of the capacity problem of general (noncommutative) group actions.
  This serves as an important motivation for our work.
  In this spirit, we note that the box-constrained Newton methods of <cit.> have recently been generalized to general noncommutative capacity and scaling problems <cit.>.
  
  
  
  
  
  
   §.§ Our results
  
  
  We provide two interior-point algorithms for unconstrained geometric programming and the corresponding scaling problem (<ref>).
  The two algorithms differ in that the first algorithm assumes well-conditioned instances, where the shift θ is contained in the relative interior of the Newton polytope, while the second algorithm applies to any point in the Newton polytope.
  For each algorithm, we give natural condition numbers associated with the input that allow us to tightly bound the number of iterations required to find an approximate solution.
  For rational inputs, we accompany these results with a priori bounds for these condition numbers that are exponential in the encoding length of the input (resulting in polynomial-time algorithms), and we explain how to obtain polynomial bounds in special situations.
  Our results improve over the optimization algorithms of <cit.>, which apply to general capacity and scaling problems, and our iteration complexities generalize recent results for matrix scaling and balancing <cit.>.
  
  
  
    §.§.§ Well-conditioned instances
  
  We first discuss our results in the well-conditioned situation.
  Here we use the following natural condition measures:
  
  
  
  For an instance of the unconstrained GP or scaling problem with Ω = {ω_1, …, ω_k}⊆^n and shift θ∈Ω, define
  the distance from θ to the (relative) boundary of the Newton polytope as
  
      r_θ   = max{ r ≥ 0 : B(θ, r) ∩Ω⊆Ω} = d(θ, ∂Ω)
      where B(θ,r) denotes the closed ball centered at θ with radius r, and
      
      Ω denotes the affine hull. 
      Equivalently, r_θ is the radius of the largest ball about θ contained in the polytope.
      Similarly, define the radius of the smallest enclosing ball about θ as
        R_θ   = min{ R ≥ 0 : Ω⊆ B(θ, R) }
      = max_i∈[k]ω_i - θ_2.
  
  
  We say that the instance is well-conditioned if r_θ > 0, otherwise it is called ill-conditioned.
  Thus, the instance is well-conditioned when θ is in the relative interior of the Newton polytope, and ill-conditioned if it is on the boundary.
  
  
  We remark that the ratio R_θ/r_θ can be understood as a natural scale-invariant condition number of the instance.
  See <ref> for an illustration.
  
  
  
  The geometric condition measure r_θ is closely related to a condition measure due to Goffin <cit.>, which is widely used in the context of testing polyhedral cone feasibility (e.g., see <cit.>).
  Let A∈^n× k be a matrix with nonzero columns a⃗_1,…, a⃗_k, and let â_i = a_i / a_i_2.
  The Goffin measure ρ(A) of A is defined as
  
      ρ(A)=max_x⃗∈im(A)∖{0⃗}min_j∈[n]â⃗̂_jx⃗/x⃗_2.
  
  Its inverse has been called the GCC condition number <cit.>.
  To see the connection, note that the distance to the boundary can be reformulated as
  
      r_θ = min_x⃗∈ W ∖{0}max_i ∈ [k] ω_i - θx⃗/x_2,
  
  where W is the linear span of the ω_i - θ in ^n (see <ref>).
  Therefore, if every ω_i - θ is a unit vector, then r_θ/R_θ = r_θ = - ρ(A),
  where A is the matrix with columns a_i = ω_i - θ. 
  As such, r_θ can in general be viewed as an unnormalized Goffin measure.
  Indeed, while normalizing the vectors a⃗_i does not affect the solvability of the corresponding conic feasibility problem, the relative sizes of the vectors ω_i - θ directly influence the value of the corresponding geometric program, and so it is natural not to normalize in our setting.
  
  Besides the geometric condition measures, we will also need the following quantity which captures the condition of the distribution q∈_++^k:
  
  
      β = q⃗_1/min_i∈ [k] q_i,
  
  where q⃗_1=∑_i=1^k q_i denotes the ℓ_1-norm.
  
  
  In general, k ≤β≤max_i∈[k] q_i/min_i∈[k] q_i k < ∞.
  We note that since θ∈Ω,
  
  it holds that
  
      F_θ^* ≥logmin_i∈[k] q_i,
  
  hence F_θ(0) - F_θ^* ≤log(β).
  
  Our first result is a bound on the number of iteration steps of a natural interior-point method (IPM) which solves unconstrained GP for well-conditioned instances.
  
  
  
  
  We emphasize that it is not necessary to provide a lower bound on r_θ as input.
  The algorithm follows the interior-point method framework of <cit.>, which consists of a preliminary stage and a main stage.
  The preliminary stage uses a starting point that is easily computed in terms of the input data, and outputs a starting point for the main stage within O( √(k)log( k  R_θ/r_θlog(kβ) ) ) Newton iterations.
  The main stage then produces a sequence of points x_0, x_1, … such that F_θ(x_j) - F_θ^* ≤ C log(kβ) e^-j c/√(k) for some constants c,C > 0, implying the claimed iteration bound.
  
  
  
  The same algorithm along with a known result relating the precision for geometric programming to the precision required to solve the scaling problem gives the following result (see <ref>).
  
  
    There exists an algorithm that, given as input a well-conditioned instance of the scaling problem with shift (<ref>), returns x⃗_ϵ∈^n such that
    
      F_θ(x⃗_ϵ)_2 =  F(x⃗_ϵ) - θ_2 ≤ϵ
  
    within
    
      O(√(k)log( k R_θ/r_θR_θ/ϵlog(kβ) ) )
  
    iterations.
  
  
  
  
    §.§.§ General instances
  
  We now discuss our results for general instances (well-conditioned or not).
  Here we provide an interior-point algorithm that approximates the unconstrained GP to arbitrary precision with an iteration complexity bound that is independent of θ.
  For this, we prove a θ-independent diameter bound for approximate minimizers.
  The quantity that controls our bound is the following.
  
  
    Let Ω⊆^n be a finite set.
    The facet gap φ > 0 of Ω is the smallest distance from any ω∈Ω to the affine span of any facet of Ω not containing ω.
    That is, it is the largest φ > 0 such that
    
      d(ω,  F) ≥φ
  
     for any facet F ⊆Ω and ω∈Ω∖ F.
  
  
  
  
  
  See <ref> for an illustration.
  The facet gap does not just depend on Ω, i.e., it is not a quantity that is purely controlled by the geometry of the Newton polytope.
  We provide an example that shows that this is necessary for any diameter bound in the ill-conditioned setting (<ref>).
  
  Our diameter bound in terms of the facet gap (<ref>) generalizes a θ-independent diameter bound obtained in <cit.> for integral Ω⊆^n to arbitrary Ω⊆^n, with only small modifications to the proof.
  The quantity that controls their diameter bound is called the unary facet complexity of the Newton polytope, denoted by .
  We recover their diameter bound by showing that, in the integral case, the facet gap and the unary facet complexity are related by φ^-1≤√(n)·.
  See <ref> for details.
  Finally, we denote the diameter of the Newton polytope by
  
      N = max_i≠ jω_i - ω_j_2.
  
  Our algorithmic result is then the following.
  
  
  
  
  <Ref> applies to arbitrary points θ in the Newton polytope and achieves an iteration complexity that is fully independent of θ.
  In contrast, <ref> applies only to well-conditioned instances and its complexity is sensitive to the distance of θ to the boundary of the Newton polytope.
  However, the former algorithm relies crucially on an a priori lower bound on the facet gap of Ω, while the latter has no such requirement.
  As such, our two algorithmic results are incomparable.
  
  As in the well-conditioned case, our algorithm also allows one to solve the scaling problem with a similar iteration complexity bound.
  
  
    There exists an algorithm that, given as input an instance of the scaling problem (<ref>) with shift θ∈Ω as well as a lower bound 0 < φ_0 ≤φ on the facet gap, returns x⃗_ϵ∈^n such that
    
      F_θ(x⃗_ϵ)_2 =  F(x⃗_ϵ) - θ_2 ≤ϵ
  
    within
    
      O( √(k)log( k n N/φ_0R_θ/ϵlog( kβ R_θ/ϵ) ) )
  
    iterations.
  
  
  The algorithm in <ref> can also solve the weak membership problem for the Newton polytope or any other convex polytope given in V-representation <cit.>.
  Suppose one is given Ω⊆^n, θ∈^n, and ϵ > 0, without assuming that θ∈Ω.
  The weak membership problem asks to assert either that d(θ, Ω) ≤ϵ or that the ball B(θ, ϵ) is not contained in Ω (these conditions are not mutually exclusive).
  One can run the algorithm from <ref> with q = (1, …, 1) ∈^k, precision ϵ, and the lower bound on the facet gap given below in (<ref>).
  If the algorithm does not terminate within the stated (polynomial) number of iterations, or if the returned point x_ϵ∈^n does not satisfy F(x_ϵ) - θ_2 ≤ϵ, one may conclude that θ∉Ω, hence B(θ, ϵ) is not contained in Ω either.
  Otherwise, we obtain a point x_ϵ∈^n such that F(x_ϵ) - θ_2 ≤ϵ; since F(x_ϵ) ∈Ω, one can therefore safely assert that d(θ, Ω) ≤ϵ.
  
  
  
  
    §.§.§ Bounds on condition measures
  
  Up to now, instances of the GP and scaling problems were allowed to be given by arbitrary real vectors.
  We now discuss how our condition measures (and thereby the iteration complexity) can for rational instances be effectively bounded in terms of the encoding length.
  We will focus our attention on r_θ and φ since the other condition measures β, R_θ, and N can be straightforwardly bounded from their definition (see <ref>).
  Throughout, we follow the conventions of <cit.> for the encoding length:
  we encode rational numbers (and rational vectors) in binary, and write · for the encoding length.
  
  We first consider the distance of θ to the boundary of the Newton polytope (<ref>).
  In <ref>, we prove the following upper bound on the distance to the boundary for well-conditioned rational instances:
  
      log_2 r_θ^-1≤ 6n^2 max_i ∈ [k] ω_i + θ.
  
  This bound implies that the iteration complexity of the interior-point method in <ref> is bounded by a polynomial in the encoding length of the instance.
  In the (not necessarily commutative) setting of <cit.>, where Ω⊆^n is integral, a first-order method was found which solves the scaling problem in (1/ϵ, R_θ) iterations.
  They also developed a second-order method for the unconstrained GP problem based on the recently introduced notion of robustness whose iteration complexity is (log(1/δ), R_θ/r_θ, n) (cf. <cit.>).
  Our results therefore improve upon both, as we have a logarithmic dependence on 1/ϵ (for the scaling problem) and 1/δ (for the geometric program), and logarithmic dependence on R_θ/r_θ.
  
  We provide a bound similar to <ref> on the facet gap. For rational instances,
  
      log_2 φ^-1≤ (6n^2 + 1) max_i ∈ [k] ω_i.
  
  This bound implies that the iteration complexity of the interior-point method in <ref> is bounded by a polynomial in the encoding length of the instance (without any dependence on θ).
  
  
  
  
  
  
  The preceding bounds allow us to compare the performance of <ref> and <ref> on well-conditioned instances.
  
  
  
  
  
  
  
  
  We find that the second algorithm typically has lower iteration complexity, since it is independent of the encoding length of θ while the dependence on the other parameters is comparable.
  We note that the first algorithm has the advantage that by running the main stage for a sufficient number of iterations we can approximate the geometric program to arbitrary precision (see discussion below <ref>).
  This is not the case for the second algorithm, which depends nontrivially on the desired accuracy.
  
  
  
  The general bounds on the condition measures in terms of the encoding length can be improved under a combinatorial hypothesis.
  Let us say that an instance is totally unimodular if the exponents ω_i are all integral and the matrix A whose columns are given by the ω_i is totally unimodular, i.e., every subdeterminant is ± 1 or 0.
  Then the facet gap can be polynomially bounded as (see <ref>)
  
      φ^-1≤ n^3/2.
  
  We can similarly bound the distance to the boundary for well-conditioned instances as r_θ^-1≤ 2^θ n^3/2.
  The latter bound appears in <cit.> in the special case where θ = 0⃗; there, the quantity r_θ is known as the weight margin.
  The total unimodularity also implies a polynomial bound on R_θ and N.
  As such, for totally unimodular instances, the interior point algorithm in <ref> can solve the unconstrained GP problem in Õ(√(k)log( 1/δ) ) iterations and the scaling problem in Õ(√(k)log( 1/ϵ)) iterations.
  The Õ notation hides a poly(input length) term inside the logarithm.
  
  
  
  As an important source of totally unimodular instances, suppose that G is a directed graph with vertex set V=[n], edge set E of size k, and edge weights q_ij>0 for ij ∈ E.
  Since the incidence matrix of a directed graph is totally unimodular <cit.>, the associated geometric program
  
      F_G,θ(x) = log∑_ij ∈ E q_ij e^x_i - x_j - θ x
  
  is totally unimodular.
  
  Many widely studied applications fall into this setting.
  For example, recall the matrix scaling problem from <ref>.
  If G is a complete bipartite directed graph, then <ref> recovers the matrix scaling objective function in <ref> up to a trivial change of variables y→ -y.
  Thus our interior point algorithm requires Õ(√(k)log( 1/ϵ)) iterations for finding an ϵ-approximate (r⃗, c⃗)-scaling of a non-negative matrix with k non-zero entries (if such a scaling exists).
  The matrix balancing problem can similarly be modeled by taking G to be a complete directed graph.
  Unconstrained GPs of the form <ref> can in general be related to nonlinear flow problems on directed graphs <cit.>.
  
  The iteration complexity that we obtain for matrix scaling and balancing slightly improves over (but is essentially the same as) the one given in <cit.> for an interior-point method designed specifically for these problems.
  It is natural to ask whether we can also meet the time complexity of the latter, which relied on a slightly different objective function and a clever implementation of approximate Newton iterations by using Laplacian solvers.
  
  We leave this question for future investigation.
  
  
  
  
  
   §.§ Organization of the paper
  
  
  The rest of this paper is organized as follows.
  In <ref> we discuss the condition numbers defined in <ref> in detail and show how they imply diameter bounds on (approximate) minimizers of the GP.
  In <ref> we explain how to use these diameter bounds together with the general framework of interior-point methods to prove <ref> and their corollaries.
  In <ref>, we give a priori bounds on the condition numbers in terms of the encoding length of the input and we also provide better condition number bounds when the geometric program is totally unimodular.
  
  
  
  
   §.§ Acknowledgments
  
  
  We would like to thank Daniel Dadush for inspiring discussions, and Sander Gribling for helpful feedback.
  MW acknowledges support through an NWO Veni grant no. 680-47-459.
  PB was partially funded by the European Research Council (ERC) under the European's Horizon 2020 research and innovation programme (grant agreement No 787840).
  
  
  
  
  § CONDITION MEASURES AND DIAMETER BOUNDS
  
  
  In this section, we discuss the condition measures defined in <ref> in more detail and show how they imply diameter bounds on the geometric program.
  Throughout, we fix an instance of the unconstrained GP or scaling problem with Ω = {ω_1, …, ω_k}⊆^n, q⃗∈_++^k, and shift θ∈Ω.
  Recall from <ref> that the objective function F_θ^n → is given by
  
      F_θ(x⃗)
      = log∑_i=1^k q_ie^ω_i - θx⃗.
  
  We denote its infimum by F_θ^* = inf_x⃗∈^n F_θ(x⃗).
  The promise that θ∈Ω guarantees that F_θ^* is finite.
  We further note that
  
      F_θ(x) = F_θ(x+h)     ∀ h ∈ W^⊥,
  
  where W denotes the linear span of the ω_i - θ in ^n.
  Since θ∈Ω, this is the same as the direction vector space of Ω and hence independent of θ.
  <Ref> implies that we can restrict the optimization problem to W.
  
  
  
  
   §.§ Well-conditioned instances
  
  
  We first consider the case that the instance is well-conditioned.
  Recall that this means that θ is in the relative interior of the Newton polytope, so r_θ > 0, where
  
      r_θ = d(θ, ∂Ω) = max{ r ≥ 0 : B(θ, r) ∩Ω⊆Ω}
  
  denotes the distance from θ to the (relative) boundary of the Newton polytope, as in <ref>.
  We have the following useful dual expression.
  
  
  Let θ∈Ω.
  Then,
  
      r_θ
      = min_x⃗∈ W 
       x_2=1max_u ∈Ω u - θx⃗
      = min_x⃗∈ W ∖{0}max_i ∈ [k]ω_i - θx⃗/ x_2.
  
  
  
  The second equality is clear.
  To see the first equality, note that for any vector x∈ W with x_2=1, max_u ∈Ω u - θx⃗ is the distance from θ to the face of Ω determined by the vector x.
  Now minimizing over all such x results in the shortest distance from θ to any face of the polytope Ω, that is, in r_θ.
  
  
  Alternatively, <ref> can be proved by using polar duality.
  We now state our diameter bound for well-conditioned instances.
  In addition to the distance r_θ, we also need the quantity
  
      β = q⃗_1/min_i∈ [k] q_i,
  
  from <ref> which captures the condition of the coefficients q in the GP.
  
  
    Let θ∈Ω.
    For all x∈ W with norm x_2 > log(cβ)/r_θ, where c>0, there exists i_0 ∈ [k] such that
    
      q_i_0 e^ω_i_0 - θ x > c  q_1.
  
    In particular, F_θ(x) > F_θ(0) + log c.
  
  
    Let x⃗∈ W be such that x_2 > log(cβ)/r_θ.
    By <ref>,
    
      r_θ≤max_i∈[k]ω_i - θ x/ x_2,
  
    and hence there exists i_0 ∈ [k] such that
    
      ω_i_0 - θ x ≥ r_θ x_2 > log(cβ).
  
    This establishes the first claim, since now
    
      q_i_0 e^ω_i_0 - θ x > q_i_0 e^log(cβ) = c q_i_0β≥ c  q_1.
  
    The second claim follows from this, since e^F_θ(x)≥ q_i_0 e^ω_i_0 - θ x and e^F_θ(0) =  q_1.
  
  
  
    Let θ∈Ω.
    Then there exists x∈ W with x_2 ≤logβ/r_θ such that
    
      F_θ(x⃗) = F_θ^*.
  
  
  
  In the case where Ω⊆{0,1}^n and q=(1,…,1) is the all-ones vector, the diameter bound x⃗_2 ≤n/r_θ was obtained in <cit.>.
  Ref. <cit.> improves this bound to x⃗_2 ≤log k/r_θ for general Ω but the same q (a special case of <ref>).
  
  
  
  
   §.§ General instances
  
  
  In this subsection we allow θ to be an arbitrary point in the Newton polytope.
  Here, the central quantity is the facet gap of Ω, which we recall was defined as the largest constant φ>0 such that
  
      d(ω,  F) ≥φ
  
  for any facet F ⊆Ω and ω∈Ω∖ F (see <ref>).
  
  The following theorem improves upon <cit.>, as we will discuss below <ref>.
  Its proof follows essentially the same argument, with a slight modification that also avoids the recursion and leads to a slightly better bound.
  
  
    For any 0<δ<2β and θ∈Ω, there exists x∈ W such that
    
      x_2 ≤m/φlog( 2 β/δ)
  
    and
    
      F_θ(x⃗) ≤ F_θ^* + δ,
  
    where m = Ω≤ n.
  
  
    To start, choose vectors a⃗_j ∈ W with a⃗_j_2 = 1 and scalars b_j ∈ for j ∈ J some finite index set, such that the Newton polytope is defined by
    
      Ω = {p⃗∈Ω :  p a_j≤ b_j   ∀ j ∈ J }.
  
    We assume each inequality defines a facet of the polytope.
    Define the normal cone N_ω at a vertex ω to be N_ω = {∑_j ∈ J_ω c_j a_j : c_j ≥ 0 } where J_ω = { j ∈ J : a_jω = b_j } is the set of tight constraints at ω.
    It is well-known that W = ⋃_ω N_ω, where ω ranges over the vertices of Ω (the normal fan is complete).
    
  
    Now fix θ∈Ω and let x⃗^* ∈ W be such that
    
      F_θ(x⃗^*) ≤ F_θ^* + δ/2.
  
    Then x^* ∈ N_ω' for some vertex ω' ∈Ω of Ω, hence there exists a subset J' ⊆ J_ω'⊆ J and non-negative numbers {c_j}_j ∈ J' such that x^* = ∑_j ∈ J' c_j a_j. By Carathéodory's theorem, we may assume |J'| ≤ m =  W.
    Now define
    
      Δ := 1/φlog( 2 β/δ),
  
    which is positive by the assumption that δ<2β, and set
    
      x⃗ := ∑_j ∈ J'min(c_j, Δ) a⃗_j.
  
    Since a⃗_j_2 = 1, we have x⃗_2 ≤J'·Δ≤ m Δ, so x satisfies the desired norm bound.
  
    To complete the proof, it therefore suffices to show that
    
      F_θ(x⃗) ≤ F_θ(x⃗^*) + δ/2.
  
    We start by setting c_j' = min(c_j, Δ) for convenience, so that x = ∑_j∈ J' c'_j a_j.
    Let J_0 consist of those j ∈ J' such that c_j' ≠ c_j, i.e., c_j > Δ and c'_j = Δ.
    We may assume there exists at least one j_0 ∈ J_0; otherwise, c_j ≤Δ for every j ∈ J', so we have x = x^* and <ref> holds trivially.
    Now consider the intersection of Ω with the face defined by the constraints J',
    
      Ω' = {ω∈Ω : a⃗_jω = b_j   ∀ j ∈ J' },
  
    If ω∈Ω∖Ω', then ω∉Ω', and
    
      ω x - ω' x
           = ∑_j ∈ J' c'_j ω-ω'a_j
        = ∑_j ∈ J' c'_j ( ωa_j - b_j ) 
         ≤ c'_j_0( ωa_j_0 - b_j_0)
        = Δ( ωa_j_0 - b_j_0) 
         ≤ -φΔ
        = log(δ/2β).
  
    The first inequality holds since each term in the sum is non-positive.
    The second inequality follows from the observation that the distance from ω to the affine span of the facet defined by a_j_0 and b_j_0 is
    
      b_j_0 - ωa_j_0/a_j_0_2
        = b_j_0 - ωa_j_0≥φ
  
    by definition of the facet gap.
    So we obtain for ω∈Ω∖Ω' that
    
      β e^ω-ω' x≤δ/2.
  
    On the other hand, if ω∈Ω', then
    
      ω - θx⃗    = ω - θx⃗^* - ∑_j ∈ J_0 (c_j - c'_j) ω - θa⃗_j≤ω - θx⃗^*
  
    since c_j ≥ c_j' and θa⃗_j≤ b_j = ωa⃗_j for all j∈ J'.
    Therefore, we now obtain
    
      F_θ(x) 
           = log( ∑_i : ω_i ∈Ω' q_i e^ω_i - θ x)
         + log( 1 + ∑_i : ω_i ∉Ω' q_i e^ω_i - θ x/∑_i : ω_i ∈Ω' q_i e^ω_i - θ x) 
         ≤log( ∑_i : ω_i ∈Ω' q_i e^ω_i - θ x)
         + ∑_i : ω_i ∉Ω' q_i e^ω_i - θ x/∑_i : ω_i ∈Ω' q_i e^ω_i - θ x
         ≤log( ∑_i : ω_i ∈Ω' q_i e^ω_i - θ x)
         + ∑_i : ω_i ∉Ω' q_i e^ω_i - θ x/q_i' e^ω' - θ x
      
        
           ≤log( ∑_i : ω_i ∈Ω' q_i e^ω_i - θx^*)
         + δ/2
         ≤ F_θ(x^*) + δ/2.
  
    In the second inequality we denote by i'∈[k] an index such that ω_i' = ω', observing that ω' ∈Ω'.
    The third inequality follows from <ref>.
  
  
  In contrast with the diameter bound for well-conditioned instances, which is in terms of the distance of θ to the boundary of the Newton polytope, the diameter bound in <ref> is independent of the shift θ.
  However, the facet gap is not an intrinsic property of the Newton polytope Ω but rather depends on the entire set of exponents Ω, so the same is true for the diameter bounds in terms of the facet gap.
  The following example shows that this is necessary.
  
  
    Consider for φ∈(0,1/2] the instance with Ω = {0,φ,1}⊆, q=(1,1,1) ∈^3, and θ=0.
    It is clear that Ω = [0,1] and that Ω has facet gap equal to φ.
    Furthermore, we have
    
      F_θ(x) = log( 1 + e^φ x + e^x ) ≥ 0
  
    and lim_x→-∞ F_θ(x) = 0, so F^*_θ = 0.
    On the other hand,
    
      F_θ(x) ≥log( 1 + e^φ x),
  
    so any δ-approximate minimizer for δ∈(0,1) must satisfy x ≥ -x ≥1/φlog1/2δ.
    
    
    
    
    
    
    
    
  
  
  We now explain how <ref> implies the diameter bound of <cit.>.
  We first recall a definition from <cit.>.
  
  
    Let P ⊆^n be an integral polytope.
    The unary facet complexity (P) is the smallest integer M ≥ 0 such that P can be described as the intersection of the affine span of P with half-spaces p a ≤ b, where a ∈^n, b ∈, and a_∞≤ M.
  
  
  The following proposition shows that the facet gap can be bounded in terms of the unary facet complexity.
  
  
    Let Ω⊆^n.
    Then the facet gap φ of Ω satisfies
    
      1/φ≤√(n)·(Ω).
  
  
  
    For any facet F ⊂Ω there exists a corresponding half-space · a ≤ b defined by a∈^n, b∈, and a_∞≤(Ω).
    Then the affine span of the facet is given by F = Ω∩ H, where H is the affine hyperplane
    
      H = { p ∈^n :  a p = b }.
  
    As a consequence, the distance from any ω∈Ω∖ F to F can be lower bounded by the distance of ω to the affine hyperplane H, that is,
    
      d(ω,  F)
        ≥b -  a ω/ a_2
        =  a ω' -  a ω/ a_2≥1/√(n)·(Ω),
  
    where ω' is an arbitrary point in Ω∩ F.
    To see the inequality, note that the numerator is positive and an integer since a, ω, ω' ∈^n, so at least 1, whereas the denominator is at most √(n)·(Ω).
  
  
  Thus, <ref> imply the following diameter bound:
  For integral Ω⊆^n, there exists a δ-approximate minimizer of F_θ of norm
  
      x_2
      
      ≤ n^3/2(Ω) log( 2 k max q_i/min q_i/δ)
      ≤ n^3/2(Ω) ( 2 L_p + log( 2 k/δ) ),
  
  where L_p = max_i log q_i and we used that β≤ k max q_i/min q_i≤ k e^2 L_p.
  The right-hand side bound is essentially the original diameter bound from <cit.> with a logarithmically improved dependence on n.
  The middle bound is very similar to a bound stated in an older version of <cit.>.
  
  
  
  
  § INTERIOR-POINT METHODS AND COMPLEXITY ANALYSIS
  
  
  In this section, we show that approximate minimizers of F_θ may be found efficiently using interior-point methods (IPM).
  The idea is to rewrite the geometric program as a linear optimization over a (more complicated) convex domain, for which we know an explicit self-concordant barrier functional.
  The domain and the corresponding barrier will be slightly different in the well-conditioned and the general case.
  
  
  
  
   §.§ Background: the barrier method
  
  
  We recall the standard interior-point formalism for solving a convex program
  
      minimize     c⃗p⃗
      subject to     p⃗∈ D,
  
  where c⃗∈ E and D⊆ E is a closed convex set of some Euclidean space E, and ·· is the inner product on E.
  We follow the exposition in <cit.> and omit most proofs;
  another source on interior-point methods is <cit.>.
  
  Let us first fix some notation and language.
  We denote by  the optimal value of <ref>, and we say p⃗_δ∈ D is a δ-minimizer of <ref> if
  
      c⃗p⃗_δ≤+δ.
  
  We say a functional Ψ(D)→ is twice continuously differentiable if its gradient and Hessian, which we shall always denote by
  
      g(p⃗)=Ψ(p⃗),      H(p⃗)=^2Ψ(p⃗),
  
  are well-defined at any point p⃗∈(D), and H(p⃗) depends continuously on p⃗.
  Recall that such a function is strictly convex if for any p⃗∈ D, the Hessian H(p⃗) is positive definite.
  In this case, the Hessian H(p⃗) defines a local norm on E for any p⃗∈ D:
  for v ∈ E, we write
  
      v_(p) = √(vH(p⃗) v)  .
  
  We also write B_p^∘(p⃗,1) = { p' ∈ E : p'-p_(p) < 1 } for the open ball with radius 1 centered at some point p∈ D, measured in the local norm ·_(p) at the same point.
  The following notion is central in interior-point methods.
  
  
    Let D ⊆ E be closed convex with non-empty interior.
    A (strongly non-degenerate) self-concordant barrier functional for D is a strictly convex and twice continuously differentiable function Ψ(D) →, satisfying the following additional properties:
    
    
    * For any p⃗∈(D), the open ball B_p⃗^∘(p⃗,1) is contained in (D).
    Moreover, for any p⃗'∈ B_p⃗^∘(p⃗,1), we have
    
      1 - p' - p_(p)≤ v_(p')/ v_(p)≤1/1 - p' - p_(p)  for all v⃗∈ E ∖{0⃗}.
  
    
    * The complexity parameter ν of the barrier, defined by
      
      ν:=sup {H(p)^-1 g(p)_(p)^2  :  p ∈(D) },
  
      is finite.
    
  
  
  One can show that a self-concordant barrier Ψ blows up at the boundary of its domain:
  if p_i∈(D) converges to p∈∂ D, then Ψ(p_i)→∞ and g(p_i)_2→∞ for i→∞; see <cit.>.
  An instructive example is the barrier Ψ(p) = -log p for the half-line _+ ⊆, which has complexity parameter ν=1.
  Self-concordance can also be defined in terms of an estimate of the third derivatives by the second derivatives.
  
  We now return to the convex program in <ref> and suppose that the domain D is bounded and admits a self-concordant barrier functional Ψ as above.
  Standard barrier methods consist of a main stage and a preliminary stage.
  In the main stage, one follows the central path, which consists of the minimizers z⃗(η) ∈(D) of the self-concordant functionals
  
      Ψ_η(p⃗):=ηc⃗p⃗+Ψ(p⃗)
  
  for every η∈_++.
  These minimizers exist, since the domain is bounded and Ψ blows up at its boundary, and they are unique, since Ψ is strictly convex.
  It is well-known (cf. <cit.>) that
  
      c⃗z⃗(η)≤+ν/η,
  
  so following the central path as η→∞ guarantees convergence of z⃗(η) to a minimizer z⃗ of the objective.
  The preliminary stage is used beforehand to find a point sufficiently close to the central path to start the main stage.
  
  The main stage is described in <ref>.
  One assumes to have a starting parameter η_0, and a starting point p⃗_0 ∈(D), which is an approximate minimizer of Ψ_η_0, so in particular close to z⃗(η_0).
  Then, for i ≥ 1, one chooses an appropriate η_i > η_i-1 such that a single Newton step for the function Ψ_η_i at point p_i-1 produces a point p_i that is guaranteed to remain close to the central path.
  Since Ψ_η_i(p) = η_i c + Ψ(p) = η_i c + g(p) and ^2 Ψ_η_i(p) = ^2 Ψ(p) = H(p),
  the point p_i obtained by taking a single Newton step is given by
  
      p_i = p_i-1 - (^2 Ψ_η_i(p_i-1))^-1Ψ_η_i(p_i-1) = p_i-1 - H(p_i-1)^-1 (η_i c + g(p_i-1)).
  
  If we write
  
      α_i(p) := H(p)^-1(η_i c + g(p))_(p),
  
  then the length of the Newton step, measured in the local norm at p_i-1, is α_i(p_i-1).
  Furthermore, one can show that α_i(p) is directly related to the distance of p to the minimizer z(η_i) of Ψ_η_i (cf. <cit.>).
  Therefore, by choosing the η_i such that α_i(p_i) stays small, we guarantee that the iterates p_i remain close to the central path.
  This is achieved by first estimating α_i(p_i-1) in terms of α_i-1(p_i-1), the ratio η_i / η_i-1, and the complexity parameter ν of the barrier, and then bounding α_i(p_i) in terms of α_i(p_i-1) using self-concordance <cit.>.
  Provided η_i →∞ as i →∞, <ref> suggests that the p_i converge to a minimizer of the objective.
  A suitable choice of the η_i, along with a quantitative guarantee on the precision achieved by any particular p⃗_i is given by the following theorem.
  
  
  
  
  Let Ψ(D) → be a strongly non-degenerate self-concordant barrier functional for D with complexity parameter ν≥ 1.
  Let η_0 > 0 be given, and suppose p⃗_0 ∈(D) satisfies
  
      α_0(p_0) = H(p⃗_0)^-1(η_0c⃗+g(p⃗_0))_(p_0)≤1/9.
  
  Then the iterations of <ref> are well-defined and we have, for all i∈[T], that α_i(p_i) ≤1/9, p_i - z(η_i)_(z(η_i))≤1/5, and c p_i≤ + 6/5η_iν.
  
  In particular, for T ≥ 10 √(ν)log ( 6/5ν/η_0 δ ), <ref> returns a point p_T ∈(D) satisfying
  
      c⃗p⃗_T≤ + δ.
  
  
  
  The goal of the preliminary stage is to find a starting point and a starting parameter satisfying the hypotheses of <ref>.
  The algorithm is presented in <ref>.
  One starts from an arbitrary point p_0'∈(D) and follows the central path associated with the objective -g⃗(p⃗'_0) and the same self-concordant barrier.
  This objective is chosen because p⃗_0' is the minimizer of -μg⃗(p⃗_0')p⃗ + Ψ(p⃗) when μ=1, i.e., p⃗_0' is exactly on the central path at time 1.
  Now one decreases the parameter μ, rather than increasing it, until one obtains an approximate minimizer of Ψ = Ψ_0.
  Finally, one chooses an appropriate η_0>0 and performs a single Newton step for Ψ_η_0 that is guaranteed to yield a point p_0 satisfying <ref>.
  Only this last step depends on the objective c of the convex program (<ref>).
  The following definition and theorem bound the number of iterations of <ref> and give a lower bound on η_0.
  
  
  
  
    Let D ⊆ E be a compact convex subset, and let p⃗∈(D).
    The symmetry of D with respect to p⃗ is defined by
    
      p = max { a ≥ 0  : p⃗ + a (p⃗ - D) ⊆ D }.
  
  
  
  If L is an affine line through p⃗, then L ∩ D consists of two chords from p⃗ to the boundary of D; the symmetry parameter p⃗ is the smallest possible ratio of the lengths of the smallest and longest chord.
  Therefore, the symmetry is always at most 1, and from this description, it is also clear that one can bound the symmetry by providing a ball centered at p⃗ contained in the interior of D, and another ball centered at p⃗ containing all of D; see <ref>.
  
  
    Let Ψ(D) → be a strongly non-degenerate self-concordant barrier functional for D with complexity parameter ν≥ 1, let p⃗_0' ∈(D) be a starting point, and let c ∈ E be the objective.
    Then <ref> with this choice of starting point p'_0 outputs a vector p⃗_0 ∈(D) and η_0 > 0 satisfying <ref>, i.e.,
    
      H(p_0)^-1 (η_0 c + g(p_0))_(p_0)≤1/9,
  
    after at most
    
      log(18ν(1+1/p⃗_0'))/-log(1-1/8√(ν))≤
        
        
        
        
        8√(ν)log( 36ν/p⃗_0')
  
    iterations. 
    Moreover, we have the lower bound η_0 ≥1/12 (V - ), where V = max_p⃗∈ D c⃗p⃗.
  
  Together, <ref> can be summarized as follows:
  
  
    
    Let D ⊆ E be a compact convex subset with non-empty interior.
    Assume Ψ(D) → is a strongly non-degenerate self-concordant barrier functional for D with complexity parameter ν≥ 1.
    Furthermore, for c⃗∈ E, define =min_p⃗∈ D c⃗p⃗ and V=max_p⃗∈ D c⃗p⃗.
    Finally, let 0 < δ < V- be the desired precision and let p'_0 ∈(D) be a starting point for the preliminary stage.
    Then, <ref> outputs a point p⃗_0 ∈(D) and a parameter η_0 ≥1/12(V-) satisfying the hypotheses of <ref>.
    <Ref> with inputs p⃗_0, η_0 and T ≥ 10 √(ν)log(6/5ν/η_0 δ) outputs a point p⃗_T satisfying
    
      c p_T - ≤δ.
  
    The total number of iterations is upper bounded by
    
      18 √(ν)log( 36ν/p⃗_0'V-/δ)
  
    and each iteration involves computing the gradient and Hessian of the self-concordant barrier Ψ and basic matrix arithmetic.
  
  
  
  
  
   §.§ Barrier method for unconstrained geometric programming
  
  
  We now return to our concrete situation, and show how to apply the general framework to the unconstrained GP problem.
  Fix Ω = {ω_1, …, ω_k}⊆^n, q⃗∈_++^k, and a shift θ∈Ω.
  Following the general strategy outlined above, we first relate the geometric program to the minimization of a linear function over a compact convex domain.
  For R>0, define
  
      D_θ,R = { (x,z,t) ∈ W ×^k × :    ∑_i=1^k z_i ≤ 1,    q_i e^ω_i-θ x≤ z_i e^t   ∀ i∈[k], 
         t ≤log(5k q_1),    x_2 ≤ R }.
  
  Here we recall that W is the span of the vectors ω_i - θ or, equivalently, the direction vector space of Ω.
  
  Note (x,z,t)∈ D_θ, R implies z_i>0 for all i∈[k].
  The convexity of the domain D_θ,R follows from the convexity of the exponential map and of the ℓ_2-norm ball.
  Let c=(0,…,0; 0,…,0;1).
  Then, any point p=(x,z,t) ∈ D_θ,R consists of a vector x with norm x_2 ≤ R and value
  
      F_θ(x) = log∑_i=1^k q_i e^ω_i-θ x≤log∑_i=1^k z_i e^t ≤ c p = t.
  
  In fact, if (x,z,t) is a δ-approximate minimizer of (<ref>) with domain D_θ,R and the above objective, then x is a δ-approximate minimizer of F_θ(x), restricted to vectors of norm x_2 ≤ R.
  This is implied by the following lemma.
  
  
  For any R>0, we have
  
      :=
        min_(x,z,t) ∈ D_θ,R t    =
        min_ x_2 ≤ R F_θ(x) 
      
        V :=
        max_(x,z,t)∈ D_θ,R t    =
        log(5k  q_1).
  
  As a consequence,
  
      log(5k)
        
        ≤ V - ≤
        log(5kβ)
  
  
  
  For the first claim, note that <ref> implies that
  
      ≥min_ x_2 ≤ R F_θ(x).
  
  Now consider a minimizer x of the right-hand side, which we by <ref> can take in W.
  Then, t := F_θ(x) is such that
  
      t ≤ F_θ(0) = log q_1 ≤log (5 k  q_1),
  
  and if we set z_i := q_i e^ω_i-θ x - t then
  
      ∑_i=1^k z_i = ∑_i=1^k q_i e^ω_i-θ x e^-t = e^F_θ(x) e^-F_θ(x) = 1.
  
  Thus we find that (x,z,t) ∈ D_θ,R, with t = F_θ(x), and <ref> follows.
  
  To see that <ref> holds, note that the upper bound V ≤log(5k q_1) follows directly by the constraint on the t variable, and is achieved for the point
  
      p = ( 0,…,0; 1/k, …, 1/k; log(5k  q_1) ).
  
  Now <ref> follows from the preceding, along with the estimate
  
      logmin_i∈[k] q_i ≤ F_θ^* ≤≤ F_θ(0) = log q_1,
  
  where the lower bound on F_θ^* is from <ref>.
  
  
  The key to applying interior-point methods to unconstrained geometric programming is the following result, which gives an explicit barrier functional for D_θ,R.
  It is well-known to experts and follows from standard barrier functionals and combination rules.
  
  
  The compact domain D_θ,R⊆ W ×^k × has non-empty interior.
  Moreover, it admits the self-concordant barrier functional
  
      Ψ_θ,R(x,z,t)
        =    - ∑_i=1^k log z_i
            - ∑_i=1^k log( log z_i - ω_i - θx + t - log q_i ) 
         - log( log(5k q_1) - t )
            - log( 1 - ∑_i=1^k z_i )
            - log( R^2 -  x_2^2 ),
  
  with complexity parameter ν=2k+3.
  
  
    It is clear that D_θ,R has non-empty interior (for example, <ref> below gives a point in the interior).
    We now derive the barrier functional.
    It is well-known that the epigraph of the exponential, given by
    
      {(y,z) ∈× :  e^y ≤ z },
  
    admits the self-concordant barrier functional (y,z) ↦ - log z - log(log z - y), with complexity parameter 2; see <cit.>.
    Recall also that the logarithmic barrier functional τ↦ -logτ for the half line _+ ⊆ has complexity parameter 1.
    Then the closed convex set
    
      {(y,z,τ) ∈^k ×^k × :  e^y_i≤ z_i  for all  i∈[k],  τ≥ 0 }
  
    is simply the product of k copies of the epigraph of the exponential and the half line, so a barrier functional Ψ' is given by the sum of the barrier functionals for each term in the product (cf. <cit.>), i.e.,
    
      Ψ'(y, z, τ) = - ∑_i=1^k log z_i - ∑_i=1^k log(log z_i - y_i) - logτ.
  
    The complexity parameter is then at most the sum of the individual complexity parameters, i.e., 2k + 1.
    Next, note that
    
      {(x,z,t) ∈ W ×^k × :  q_i e^ω_i-θx≤ z_i e^t  for all  i∈[k],   t ≤log(5k  q_1) }
  
    is the preimage of <ref> under the injective affine transformation
    
      A  W ×^k ×→^k ×^k ×,    (x,z,t) ↦(ω_1-θx - t + log q_1, …
             …, ω_k-θx - t + log q_k;   z_1, …, z_k;  log(5k q_1) - t ),
  
    
    
    
    
    hence by <cit.> admits the self-concordant barrier functional
    
      (Ψ' ∘ A)(x,z,t)
           = - ∑_i=1^k log z_i - ∑_i=1^k log(log z_i - ω_i-θx + t - log q_i ) 
         - log( log(5k q_1) - t )
  
    with the same complexity parameter 2k+1.
    Finally, we may incorporate the linear constraint ∑_i=1^k z_i ≤ 1 by adding the logarithmic barrier -log(1 - ∑_i=1^k z_i), and the ℓ_2-norm constraint x_2 ≤ R by adding the barrier -log(R^2 -  x_2^2); see <cit.>.
    This increases the complexity parameter to 2k+3 and results in the desired domain and barrier.
  
  
  Next we need to bound the symmetry of a suitable starting point.
  For this, we will use the following lemma.
  
  
    Let D ⊆ E be a closed convex subset, and let p∈ D.
    Suppose that r < R are two radii such that
    B(p, r) ⊆ D ⊆ B(p,R),
    where the closed balls are taken with respect to an arbitrary norm on E.
    Then, D is bounded, p∈(D), and
    
      p ≥r/R.
  
  
  
    Clearly D is bounded and contains p in its interior.
    For the symmetry claim, note that for any u∈ D, we have u ∈ B(p, R), so p - u ∈ B(0, R), and hence
    
      p + r/R (p - u) ∈ B(p, r) ⊆ D.
  
    This shows that
    
      p + r/R (p - D) ⊆ D,
  
    which implies the desired lower bound on the symmetry (cf. <ref>).
  
  
  One important aspect of <ref> is the freedom in choosing a norm; in particular, we do not assume that the norm comes from the inner product on E.
  We will now use this freedom to bound the symmetry of the following starting point:
  
      p'_0 = ( 0,…,0; 1/2k, …, 1/2k; log(4k q_1) ),
  
  which is clearly contained in the interior of D_θ,R.
  
  
  
  
  
  
  
  
  
  For any R>0, we can bound the symmetry of D_θ,R with respect to the point p'_0 by
  
      1/p'_0≤ 10max( R_θ R, k, log(4kβ) ),
  
  where we recall that R_θ = max_i∈[k]ω_i - θ_2 as defined in <ref>.
  
  
    We wish to apply <ref> using the following norm on W ×^k ×:
    
      (x,z,t) := max{ x_2/R, 2/3 z_∞,  t/log(4kβ)}.
  
    We first show that
    
      (x,z,t) - p'_0≤ 1
  
    for any (x,z,t) ∈ D_θ,R.
    By definition x_2 ≤ R.
    Moreover, z_i > 0, so
    
      2/3z_i - 1/2k≤2/3( z_i + 1/2k)
        ≤2/3( ∑_i=1^k z_i + 1/2k)
        ≤2/3( 1 + 1/2k)
        ≤ 1.
  
    Moreover, by <ref> it holds that
    
      logmin_i∈[k] q_i ≤ F_θ^* ≤≤ t ≤ V = log (5k  q_1),
  
    hence
    
      t - log(4k q_1)/log(4kβ)   ≤max{log (5k q_1) - log(4k q_1),  log(4k q_1) - logmin_i∈[k] q_i }/log(4kβ)
         = max{log5/4, log(4kβ) }/log(4kβ)≤ 1.
  
    Thus we have proved <ref>.
  
    We now show that D_θ,R contains any point (x,z,t) ∈ W ×^k × in the ball
    
      (x,z,t) - p'_0≤1/10max(R_θ R, k, log(4kβ))
        < 1/10.
  
    
    The latter implies that x_2 ≤R/10≤ R, so x certainly satisfies the norm bound.
    Moreover, <ref> ensures that
    x_2 ≤1/10 R_θ,
    and so
    
      q_i e^ω_i-θ x≤ q_i e^R_θ x_2≤ q_i e^1/10≤ e^1/10 q_1
  
    for all i∈ [k].
    
    Next, we also have 2/3z_i - 1/2k≤1/10k, hence
    
      7/20k≤ z_i ≤13/20k,
  
    which implies that
    
      ∑_i=1^k z_i ≤13/20≤ 1.
  
    Finally, note that <ref> entails
    
      t - log(4k q_1)/log(4kβ)≤1/10log(4kβ),
  
    hence t - log(4k q_1)≤1/10, which implies that
    
    
      log(e^-1/104 k q_1)
        ≤ t ≤
        log(e^1/104 k q_1)
        ≤log(5 k q_1).
  
    On the one hand, this yields the desired upper bound on t.
    On the other hand, the lower bound, along with the lower bound in <ref>, implies that
    
      z_i e^t
        ≥7/20k e^-1/104 k q_1
        = 7/5 e^-1/10 q_1
        ≥ e^1/10 q_1.
  
    Together, <ref> show that q_i e^ω_i-θ x≤ z_i e^t, as desired.
    Thus we have proved that (x,z,t) ∈ D_θ,R for any point in the ball (<ref>).
    Now <ref> implies the bound on the symmetry.
  
  
  In the remainder we consider two different situations.
  For general instances, we choose R according to a given lower bound on the facet gap, using <ref>.
  In the well-conditioned case, where θ is contained in the relative interior of the Newton polytope, we see that the upper bound on the z_i variables already leads to a bounded domain;
  this allows us to obtain an algorithm that is independent of any explicit radius bound.
  
  
  
  
   §.§ General instances
  
  
  Suppose the facet gap of the instance is lower bounded by some φ_0>0.
  Then, <ref> show that for δ<4β and
  
      R = n/φ_0log( 2 β/δ/2)
  
  the value of the convex program (<ref>) with objective c=(0,…,0;0,…,0;1) and domain D_θ,R is at most
  
      = min_ x_2 ≤ R F_θ(x) ≤ F_θ^* + δ/2.
  
  Therefore, in order to obtain a δ-approximate minimizer for the geometric program, it suffices to find a δ/2-approximate minimizer of the convex program (<ref>).
  The latter is achieved by <ref>, which is an interior-point algorithm for the self-concordant barrier functional Ψ_θ,R derived above.
  Its iteration complexity is bounded by the following theorem.
  
  
  
  [restated]
  
  
    The result follows from applying <ref> to find a δ/2-approximate minimizer, with the closed convex domain D_θ,R, the self-concordant barrier functional Ψ_θ,R from <ref> with complexity parameter ν=2k+3, the symmetry bound given by <ref>, and the starting point (<ref>), along with the estimate log(5k) ≤ V - ≤log(5kβ) from <ref> and the bound R_θ = max_i ω_i - θ_2 ≤ N = max_i≠ jω_i - ω_j_2 which holds for any θ∈Ω.
    
    
    
    
  
  
  If all the inputs for <ref> are rational and encoded in binary, then q⃗_1, β, and φ_0 are at most exponentially large in the encoding length.
  Since the iteration complexity depends logarithmically (or even doubly logarithmically) on these quantities, the resulting iteration complexity is at most polynomial in the encoding length of the input.
  See <ref> for details.
  
  
  
  
   §.§ Well-conditioned instances
  
  
  Now assume the instance is well-conditioned, so θ is contained in the relative interior of the Newton polytope.
  Here, we consider
  
      D_θ = { (x,z,t) ∈ W ×^k × :    ∑_i=1^k z_i ≤ 1,    q_i e^ω_i-θ x≤ z_i e^t   ∀ i∈[k], 
         t ≤log(5k q_1) },
  
  which looks just like D_θ,R except that we omitted the norm bound on x.
  We claim that the two domains coincide for any
  
      R ≥log(5kβ)/r_θ.
  
  Indeed, if there were some (x,z,t) ∈ D_θ with x_2 > R then <ref> would show that q_i_0 e^ω_i_0 - θ x > 5k  q_1 for some i_0∈[k].
  This is a contradiction, since for any (x,z,t)∈ D_θ we have
  
      q_i_0 e^ω_i_0 - θ x≤∑_i=1^k q_i e^ω_i-θ x≤∑_i=1^k z_i e^t ≤ e^t ≤ 5 k  q_1.
  
  Thus we see that, indeed, D_θ = D_θ,R for any R as in <ref>.
  
  As a consequence, the value of the convex program for the domain D_θ is exactly equal to F_θ^*, as follows from <ref>.
  Moreover, the domain D_θ is bounded and satisfies the symmetry bound given in <ref>, namely,
  
      1/p'_0≤
      10max( log(5kβ) R_θ/r_θ, k, log(4kβ) )
      = 10max( log(5kβ) R_θ/r_θ, k )
  
  Moreover, since D_θ no longer depends explicitly on the radius bound, we can use the self-concordant barrier functional
  
      Ψ_θ(x,z,t)
        =    - ∑_i=1^k log z_i
        - ∑_i=1^k log( log z_i - ω_i - θx + t - log q_i ) 
         - log( log(5k q_1) - t )
        - log( 1 - ∑_i=1^k z_i )
  
  with complexity parameter ν=2k+2.
  Using this modification we readily obtain an interior-point algorithm for well-conditioned instances.
  Importantly, this algorithm does not explicitly depend on r_θ or any other condition measure.
  By contrast, <ref> required as input a lower bound on the facet gap.
  The algorithm is stated in <ref>, and the following theorem gives a precise iteration bound.
  
  
  
  [restated]
  
  
    Apply <ref> to find a δ-approximate minimizer, with the closed convex domain D_θ, the self-concordant barrier functional Ψ_θ given in <ref> with complexity parameter ν=2k+2, the symmetry bound given in <ref>, and the starting point (<ref>), along with the estimate on (V - ) from <ref>.
    
    
    
  
  
  As in the situation of <ref>, if all the inputs in <ref> are rational, then the iteration complexity is again at most polynomial in the encoding length of the inputs.
  Again see <ref> for details.
  
  
  
  
   §.§ Geometric programming and scaling
  
  
  
  In this section, we show that in order to solve the scaling problem with precision ϵ > 0, it suffices to solve the corresponding unconstrained geometric program with some precision δ = δ(ϵ).
  The results in this section are well-known (see, e.g., <cit.> or <cit.>), but stated and proven for completeness.
  
  
    For any ω_1, …, ω_k, θ∈^n and q∈_++^k, the function
    
      F_θ^n →,    F_θ(x) = log∑_i=1^k q_i e^ω_i - θx
  
    is L-smooth with L = R_θ^2, where R_θ = max_i ω_i - θ_2.
    Recall that this means that its gradient is L-Lipschitz or, equivalently, that its Hessian has eigenvalues ≤ L.
  
  
    The gradient ∇ F_θ(x) ∈^n is given by
    
      ∇ F_θ(x) = ∑_i=1^k q_i e^ω_i - θx (ω_i - θ)/∑_i=1^k q_i e^ω_i - θx.
  
    Therefore, its Hessian ∇^2 F_θ(x)^n →^n is given by
    
      ∇^2 F_θ(x)
        
        
        
        
        
        
        
        = ∑_i=1^k q_i e^ω_i - θx (ω_i - θ)(ω_i - θ)^T/∑_i=1^k q_i e^ω_i - θx
        -  (∇ F_θ(x))(∇ F_θ(x))^T.
  
    Hence we see that the eigenvalues of the Hessian can be upper bounded by the eigenvalues of the left-hand side matrix, since the matrix that is subtracted is positive semidefinite.
    As the left-hand side matrix is a convex combination of the rank-one matrices (ω_i - θ)(ω_i - θ)^T, we can bound its eigenvalues by R_θ^2
  
  
  The following proposition then shows that the scaling problem can be solved by solving the corresponding geometric program with sufficient precision.
  
  
    Assume that θ∈Ω, and let x∈^n be such that F_θ(x) ≤ F_θ^* + δ for some δ>0.
    Then,
    
      F_θ(x⃗)_2^2/2 R_θ^2≤δ.
  
    In particular, to solve the scaling problem with precision ϵ>0 it suffices to find a solution for the unconstrained GP with accuracy δ = ϵ^2 / (2 R_θ^2).
  
  
    A standard argument shows that an L-smooth function can always be decreased in controlled way by following a gradient step.
    Namely, if we define x' = x - 1/L∇ F_θ(x) then, using Taylor's expansion to second order and bounding the quadratic contribution using smoothness,
    
      F_θ(x') - F_θ(x)
        ≤ - 1/L F_θ(x⃗)_2^2 + 1/2L F_θ(x⃗)_2^2
        = -1/2L F_θ(x⃗)_2^2.
  
    As x is a δ-approximate minimizer of F_θ, we must have
    
      1/2L F_θ(x⃗)_2^2 ≤δ.
  
    The desired bound follows since we have L=R_θ^2 by <ref>.
  
  
  <Ref> follow directly from <ref>, respectively, by using <ref>.
  Interestingly, the above results also hold in the more general `non-commutative' setting discussed in <ref>; see <cit.> for details.
  
  
  
  
  § BOUNDS ON CONDITION MEASURES
  
  
  In this section, we give bounds on the condition measures from <ref> for rational instances in terms of their binary encoding length.
  These bounds show that our interior-point algorithms have polynomial iteration complexity.
  We also explain how to obtain tighter estimates under a total unimodularity assumption on the Newton polytope.
  Throughout this section, we follow the conventions of <cit.>:
  we encode rational numbers and vectors in binary, and write · for the encoding length.
  
  
  
  
   §.§ General bounds
  
  
  We first give lower bounds on r_θ and φ, the distance of θ to the boundary of the Newton polytope and the facet gap of Ω, respectively.
  All other condition measures can be directly bounded in terms of the input length.
  The following bound on r_θ implies <ref> in the introduction.
  
  
    Let Ω⊆^n and θ∈^n∩Ω.
    Then,
    
      log_2 1/r_θ≤ 6n^2 max_i ∈ [k] ω_i + θ - n.
  
    If θ = 0⃗, the upper bound can be improved to 3n^2 max_i ∈ [k] ω_i - n.
  
  
    The polytope Ω has vertex complexity at most ν := max_i ∈ [k] ω_i, so by <cit.>, it has facet complexity at most ϕ := 3 n^2 ν.
    This means that the polytope can be defined by inequalities of the form · a ≤ b for a∈^n, b∈ with encoding length a +  b ≤ϕ.
  
    As a consequence, if F is any facet of Ω then its distance to θ can be lower bounded as
    
      d(θ, F) ≥
          d(θ,  F) ≥b - θ a/ a_2
  
    for certain a∈^n, b∈ with a +  b ≤ϕ.
    
    Now we have a_2 ≤ 2^ a - n by <cit.>, while b - θ a is a positive rational number with denominator of absolute value at most 2^ a +  b + θ≤ 2^ϕ + θ.
    We conclude that the distance from θ to the facet F is at least
    
      b - θ a/ a_2≥1/2^ϕ + θ 2^ a - n≥1/2^2ϕ + θ - n =
          1/2^6 n^2 max_i ω_i + θ - n.
  
    Since the facet was arbitrary this implies the desired bound.
  
    If θ=0, then we can instead estimate
    
      b - θ a/ a_2 =
          b/ a_2≥1/2^ b 2^ a - n≥1/2^ϕ - n≥1/2^3 n^2 max_i ω_i - n,
  
    which proves the second claim.
  
  
  A completely similar argument shows the following lemma, which implies <ref> in the introduction.
  
  
    Let Ω⊆^n.
    Then the facet gap φ of Ω satisfies
    
      log_2 1/φ≤ (6n^2 + 1) max_i ∈ [k] ω_i - n.
  
  
  
    The argument is exactly the same as in the proof of <ref>, but with θ replaced by any ω_i not on the facet under consideration, noting that the proof in fact established a lower bound on the distance to the affine span of the facet.
  
  
  Finally, we show that the unary facet complexity of an integral polytope can be similarly bounded in terms of the encoding length.
  Via <ref>, this also implies a bound on the facet gap, albeit with a worse polynomial scaling in the dimension n.
  
  
  
    Let Ω⊆^n. Then the unary facet complexity of Ω satisfies
    
      log_2 (Ω) ≤ 3 n^3 max_i ∈ [k] ω_i - n.
  
  
  
    Again by <cit.>, the polytope Ω may be described by inequalities of the form p a ≤ b with a ∈^n, b ∈ of total encoding length a +  b ≤ϕ := 3n^2 max_i∈[k] ω_i.
    Multiplying by the denominators of a gives a' ∈^n, b' ∈ such that a' has encoding length at most nϕ = 3n^3 max_i∈[k] ω_i.
    Now the desired inequality follows from the bound a'_∞≤a'_2 ≤ 2^a'-n.
  
  
  
  
  
   §.§ Total unimodularity
  
  
  We now show how to improve the bounds given above in case the set of exponents Ω satisfies a total unimodularity hypothesis.
  This is the case in many interesting applications, including the geometric programs (<ref>) associated with directed graphs, which in particular capture the matrix scaling and matrix balancing problems.
  
  
    An integer matrix A ∈^n × k is called totally unimodular if every square submatrix of A has determinant 0, 1 or -1.
    We say that Ω={ω_1,⋯,ω_k}⊆^n is totally unimodular if the associated matrix
    
      A_Ω = [ ω_1 | ⋯| ω_k ]
  
    with columns ω_1,…,ω_k is totally unimodular.
  
  
  
  If Ω is totally unimodular, every ω_i has entries only in {±1,0}.
  Therefore, we can bound the radius of the smallest enclosed ball around any θ∈Ω, as well as the diameter of the Newton polytope by
  
      R_θ = min_i∈[k]ω_i - θ_2 ≤ N = max_i≠ jω_i - ω_j_2 ≤ 2√(n).
  
  We now show that the inverse distance to the boundary and the inverse facet gap can similarly be upper bounded by a polynomial in n, which is an exponential improvement over the general bounds of <ref>.
  The proposition establishes in particular <ref> in the introduction.
  
  
    Let Ω⊆^n be totally unimodular.
    Then the unary facet complexity (Ω) is at most n.
    As a consequence, the facet gap φ of Ω satisfies
    
      φ≥ n^-3/2.
  
    Furthermore, if θ∈^n∩Ω, then
    
      r_θ≥ 2^-θ  n^-3/2.
  
    If θ=0, the latter lower bound can be improved to n^-3/2.
  
  
  
    Assume first that Ω is a full-dimensional polytope.
    Then every facet of Ω is the convex hull of some affinely independent v⃗_1, …, v⃗_n ∈Ω.
    By Cramer's rule, the affine hyperplane spanned by the facet consists of all x ∈^n such that
    
      [      1      1      …      1;    x_1                     ;      ⋮ v⃗_⃗1⃗      … v⃗_⃗n⃗;    x_n                      ] = 0.
  
    Expanding the determinant along the first column gives the linear equation
    
      ∑_i=1^n (-1)^i  (D_i) x_i = - (D_0)
  
    where D_i is obtained by deleting the (i+1)-th row from the matrix
    
      D =
          [     1     …     1; v_1,1     … v_n,1;     ⋮           ⋮; v_1,n     … v_n,1;       ].
  
    For i,j∈[n], let D_i^j be obtained by deleting the first row and the j-th column from D_i; then expanding the determinant (D_i) along the first row gives
    
      (D_i)≤∑_j=1^n (D_i^j)≤ n
  
    since D_i^j is a submatrix of A_Ω and hence submodular.
    By replacing the equality in <ref> by an inequality and varying over all facets, we obtain a complete set of defining inequalities for the polytope.
    This shows that the unary facet complexity (Ω) is at most n.
    The lower bound on the facet gap now follows at once using <ref>.
  
    We now consider an arbitrary θ∈^n in the interior of Ω and bound its distance to the boundary.
    Set a⃗ = [(D_1), …, (D_n)]^T and b = -(D_0), so that the hyperplane defined by <ref> reads x a = b.
    The distance from θ to the facet is then lower bounded by
    
      b - θ a/a_2≥b - θ a/n^3/2,
  
    where we used that a_2 ≤√(n) a_∞≤ n^3/2 by <ref>.
    Note that θ a ≠ b, since θ is not contained in the hyperplane.
    Moreover, a∈^n and b∈.
    Therefore, if θ = 0 then b - θ a =  b is an integer (in fact, equal to 1 by total unimodularity), while in general it is a rational number with denominator at most 2^θ.
    In either case we obtain the desired lower bound on r_θ.
  
    Finally, suppose that Ω has dimension r < n.
    Then there exists a set of vectors U = {u⃗_1, …, u⃗_n-r} in {0⃗, e⃗_1, …, e⃗_n} such that (Ω∪ U) has dimension n.
    Moreover, Ω∪ U is still totally unimodular.
    
    Hence by the previous part of the proof, (Ω∪ U) has unary facet complexity at most n.
    Every facet of Ω is now the intersection of some facet of (Ω∪ U) with the affine span of Ω, so the unary facet complexity of Ω is also at most n.
    Furthermore, since the distance from θ to any facet of Ω is at least as large as the distance from θ to any facet of (Ω∪ U) not containing θ, we also inherit the lower bound on r_θ.
  
  
  The lower bound r_0⃗^-1≥ n^-3/2 when θ = 0⃗ already appears in <cit.> as a lower bound on the weight margin γ(π) of a representation π: (n) →(V) whose weights are exactly Ω.
  The proof given there is similar to the one we give (as well as to the proof of <cit.>, which is also a key ingredient for <ref>):
  both use Cramer's rule to express equations for facets of Ω in terms of subdeterminants of the matrix A_Ω, which are bounded by the total unimodularity.
  
  The following corollary specializes <ref> to the totally unimodular case, using <ref> and the lower bound on the facet gap from <ref>.
  
  
    There is an interior-point algorithm (<ref>) that, given as input an instance of the unconstrained GP problem with shift and totally unimodular Ω⊆^n, returns x⃗_δ∈^n such that F_θ(x⃗_δ) ≤ F_θ^* + δ within
    
      O( √(k)log( k n 1/δlog( kβ/δ) ) )
          = Õ( √(k)log( 1/δ) )
  
    iterations.
    Similarly, given an instance of the scaling problem with totally unimodular Ω⊆^n, the same algorithm returns x⃗_ϵ∈^n such that F_θ(x⃗_ϵ)_2 ≤ϵ within
    
      O( √(k)log( k n 1/ϵlog( knβ/ϵ) ) )
          
          = Õ( √(k)log( 1/ϵ) )
  
    iterations.
    Here, the notation Õ hides poly(input) terms inside the logarithm.
  
  
  In particular, this theorem applies to matrix scaling, as discussed below <ref>, by using the following geometric program which is totally unimodular:
  
      F_θ(x,y)
      = log∑_i,j q_ij e^x_i -  y_j -  r x +  c y
      = log( ∑_i,j q_ij e^x_i -  y_j) -  r x +  c y.
  
  Here, slightly stronger bounds can be obtained:
  the diameter of the Newton polytope is N=2 and the facet gap satisfies φ≥ n^-1/2, since the unary facet complexity of the Newton polytope is in fact equal to 1 <cit.>.
  However, this does not impact the iteration count up to logarithmic factors in the encoding length.
  
  For matrix scaling, the state of the art for general matrices is a recent interior-point method given in <cit.>, which obtains an iteration complexity of
  
      Õ(√(k)log( q⃗_1/ϵ))
  
  to find an (r,c)-scaling of a nonnegative matrix.
  They use an objective that is slightly different from our F_θ, namely
  
      f̃_θ(x,y) = ∑_i,j q_ij e^x_i -  y_j -  r x +  c y,
  
  that is, the `shift' is done additively instead of in the exponent.
  We see that the iteration complexity in <ref> slightly improves over <ref>.
  
  
  amsplain
  
  