key: cord-0047264-4g8qhrh6
authors: Akian, Marianne; Allamigeon, Xavier; Boyet, Marin; Gaubert, Stéphane
title: A Convex Programming Approach to Solve Posynomial Systems
date: 2020-06-06
journal: Mathematical Software - ICMS 2020
DOI: 10.1007/978-3-030-52200-1_24
sha: edaca79b01a57f84d10043695d1603f28e1c3e1f
doc_id: 47264
cord_uid: 4g8qhrh6

We exhibit a class of classical or tropical posynomial systems which can be solved by reduction to linear or convex programming problems. This relies on a notion of colorful vectors with respect to a collection of Newton polytopes. This extends the convex programming approach of one player stochastic games.

A posynomial is a function of the form

where the variable x = (x 1 , . . . , x n ) is a vector with real positive entries, A is a finite subset of vectors of R n , and the c a are positive real numbers. Here for any a ∈ R n , we denote by a i the i-th coordinate of a. The set A is called the support of P , also denoted by S P , its elements are called the exponents of the posynomial and the c a its coefficients. Unlike polynomials, posynomials can have arbitrary exponents. They arise in convex optimization, especially in geometric and entropic programming [6] and in polynomial optimization [7] . They also arise in the theory of nonnegative tensors [8, 11] , in risk sensitive control [3] and game theory [1] .

A tropical posynomial is a function of the form

where ·, · is the usual dot product of R n , the c a are now real coefficients, and x = (x 1 , . . . , x n ) can take its values in R n . The terminology used comes from the tropical (or max-plus) semi-field, whose additive law is the maximum and the multiplicative law is the usual sum.

In this paper, we are interested in solving (square) classical posynomial systems, that are of the form 

with x ∈ (R >0 ) n , and the P i are classical posynomials. We will also study the tropical counterpart,

with now x ∈ R n , and the P trop i are tropical posynomials (hereafter we shall write P i instead of P trop i , for brevity). The optimality equations of Markov decision processes [13] are special cases of tropical posynomial systems. More general tropical posynomial systems arise in the performance analysis of timed discrete event systems, see [2] .

Solving (square) posynomial systems is in general NP-hard (Sect. 2). However, we identify a tractable subclass. The tropical version can be solved exactly in polynomial time by reduction to a linear program (Sect. 3), whereas the classical version can be solved approximately by reduction to a geometric program (Sect. 4). Our approach is based on a notion of colorful interior of a collection of cones. A point is in the colorful interior if it is a positive linear combination of vectors of these cones, and if at least one vector of every cone is needed in such a linear combination. Our reductions are valid when the colorful interior of the cone generated by the supports of the posynomials is nonempty, and when a point in this interior is known. As special cases, we recover the linear programming formulation of Markov decision processes, and the geometric programming formulation of risk sensitive problems. Properties of the colorful interior and related open problems are discussed in Sect. 5.

The following two results show that the feasibility problems for classical or tropical posynomial systems are NP-hard, even with integer exponents. Proposition 1. Solving a square tropical posynomial system is NP-hard.

Proof. We reduce 3-SAT to the problem (2). Let us consider a Boolean formula in conjunctive normal form C 1 ∧ · · · ∧ C p made of p clauses, each one of them using three out of n real variables x 1 , . . . , x n (p, n ∈ N).

We introduce the following tropical posynomial system in the 2n+2p variables (x 1 , . . . , x n , y 1 , . . . , y n , z 1 . . . , z p , s 1 , . . . , s p ), with the same number of equations:

This system can be constructed in polynomial time from the Boolean formula. The first 2n equations ensure that for all i ∈ [n], x i ∈ {0, 1} and that x i and y i have opposite logical values. The next p equations express that for all j ∈ [p], the variable z j has the same Boolean value as the clause C j , with the notation x i ∈ C j (resp. ¬x i ∈ C j ) if the variable x i occurs positively (resp. negatively) in the clause C j . The last equations ensure that z j = 1 for all j ∈ [p]. The instance C 1 ∧ · · · ∧ C p is satisfiable if and only if this system admits a solution.

Theorem 2. Solving a square classical posynomial system is NP-hard.

Proof. We modify the previous construction to obtain a square posynomial system over R 2n+2p

, along the lines of Maslov's dequantization principle [12] or Viro's method [14] :

From the first 2n equations, the variables x i and y i range over {2, 1/2}, the values 2 and 1/2 respectively encode the true and false Boolean values. The variable y i = 1/x i corresponds to the Boolean negation of x i . Since each clause has precisely three literals, using the p next equations, we deduce that the variable z j takes one of the values {1/2, 3/4, 1} if the clause C j is satisfied, and that it takes the value 1/4 otherwise. The last p equations impose that z j can take any value in (1/3, ∞). We deduce that the formula C 1 ∧ · · · ∧ C p is satisfied if and only if the posynomial system that we have obtained in this way admits a solution in R 2n+2p

.

Given tropical posynomials P 1 , . . . , P n , we write the system (2) as P (x) = 0, where P := (P 1 , . . . , P n ). The support of this system, denoted S, is defined as the disjoint union i∈[n] S Pi of the supports of the posynomials P i . By disjoint union, we mean the coproduct in the category of sets (these supports may have non-empty intersections, and they may even coincide).

We say that a vector y in the (convex) conic hull cone(S) is colorful if, for all μ ∈ (R 0 ) S ,

In other words, a vector y ∈ R n is colorful if it arises as a nonnegative combination of the exponents of P , but also if all such combinations make use of at least one exponent of each of the tropical posynomials P 1 , . . . , P n . In this way, if we think of S P1 , . . . , S Pn as colored sets, we need all the colors to decompose a colorful vector y over these. Moreover, by Carathéodory's theorem, every vector in the conic hull cone(S) can be written as a positive linear combination of an independent family of vectors of S. Hence, when y is a colorful vector, it is obtained as a positive linear combination of precisely one vector a i in each color class S Pi , and the family a 1 , . . . , a n must be a basis. (If not, Carathéodory's Theorem would imply that y is a positive linear combination of a proper subset of {a 1 , . . . , a n }, so that y could not be a colorful vector.) Given a vector y, we consider the following linear program:

Remark that the feasibility set of this linear program consists of the vectors x ∈ R n satisfying P (x) 0. In other words, it can be thought of as a relaxation of the system P (x) = 0. The following theorem shows that this relaxation provides a solution of P (x) = 0 if y is a colorful vector.

Assume that y is a colorful vector, and that the linear program (LP(y)) is feasible. Then, the linear program (LP(y)) has an optimal solution, and any optimal solution x satisfies P (x) = 0.

Proof. Since the feasibility set of (LP(y)), F := {x ∈ R n : P (x) 0}, is nonempty, we can consider its recession cone, which is given by C = {x ∈ R n : ∀a ∈ S, a, x 0}. As a colorful vector, y belongs to the polyhedral cone generated by the vectors a ∈ S, so y, x 0 for all x ∈ C. By the Minkowski-Weyl theorem, F is a Minkowski sum of the form P + C where P is a polytope, i.e., every feasible point x can be written as x = x + x with x ∈ P and x ∈ C. Since y, x 0, the maximum of the objective function x → y, x over the polyhedron F is attained (by an element of P).

Let x ∈ R n be an optimal solution of (LP(y)). From the strong duality theorem, the dual linear program admits an optimal solution (μ a ) a∈S ∈ (R 0 ) S which satisfies y = a∈S μ a a and μ a (c a + a, x ) = 0 for all a ∈ S. Since y is a colorful vector, for all i ∈ [n], there is some a i ∈ S Pi such that μ ai > 0. We then get that, for all i ∈ [n], P i (x ) c ai + a i , x = 0. As a result, P (x ) = 0.

We next provide a geometric condition ensuring that the linear program (LP(y)) is feasible regardless of the coefficients c a . We say that the tropical posynomial function P has pointed exponents if its support is contained in an open halfspace, i.e. there exists z ∈ R n such that ∀a ∈ S, a, z < 0. Our interest for pointed systems comes from the following property: Proposition 4. The inequality problem P (x) 0 has a solution x ∈ R n regardless of the coefficients of P if and only if P has pointed exponents.

Proof. Suppose that for all values of (c a ) a∈S , there exists x ∈ R n such that

Suppose now that P has pointed exponents. Then there is some z ∈ R n such that for all a ∈ S, we have a, z < 0. We define λ := max a∈S (−c a )/ a, z so that ∀a ∈ S, c a + a, λz 0 and therefore for all i ∈ [n], P i (λz) 0.

As a consequence of Theorem 3 and Proposition 4, if the tropical posynomial system P (x) = 0 has pointed exponents and there exists a colorful vector, then the system admits a solution which can be found by linear programming.

A remarkable special case consists of Markov decision processes. In this framework, the set [n] represents the state space, and at each state i ∈ [n], a player has a finite set B i of available actions included in the n-dimensional simplex {p ∈ R n 0 : n j=1 p j 1}. If p ∈ B i , p j stands for the probability that the next state is j, given that the current state is i and action p is chosen by the player, so the difference 1 − n j=1 p j is the death probability in state i when this action is picked. To each action p is attached a reward c p ∈ R. Given an initial state i ∈ [n], one looks for the value v i ∈ R, which is defined as the maximum over all the strategies of the expectation of the sum of rewards up to the death time, we refer the reader to [13] for background. The value vector v = (v i ) i∈ [n] is solution of the tropical posynomial problem

This reduces to the form (2) with S Pi := B i − e i , where e i denotes the i-th element of the canonical basis of R n . We say that a Markov decision process is of discounted type if for every state i ∈ [n] there is at least one action p ∈ B j such that n j=1 p j < 1. Proposition 5. If a Markov decision process is of discounted type, then any negative vector is colorful with respect to the associated posynomial system.

Thus, we recover the linear programming approach to Markov decision processes (see [13] ), showing that the value is obtained by minimizing the function v → i∈ [n] v i subject to the constraints v i c p + p, v for i ∈ [n] and p ∈ B i .

We refer the reader to [6] for background on geometric programming. Given a collection P = (P 1 , . . . , P n ) of classical posynomials, we now deal with the system P i (x) = 1 for all i ∈ [n], which, for brevity, we denote by P (x) = 1. We keep the notation of Sect. 3 for the supports of the posynomials. Moreover, the definitions of colorful vectors and pointed exponents, which only depend on these supports, still make sense in the setting of this section. Proof. If P is nonempty, let C := {x ∈ R n | ∀a ∈ S, a, x 0, y, x 0} denote its recession cone, and let x ∈ C. Since y is a colorful vector, there exists (λ 1 , . . . , λ n ) ∈ R n >0 and a basis (a 1 , . . . , a n ) ∈ i∈[n] S Pi such that y = n i=1 λ i a i . Thus, y, x 0, and so y, x = n i=1 λ i a i , x = 0. As a consequence, since λ i > 0 for all i ∈ [n], a i , x = 0. Since (a 1 , . . . , a n ) is a basis, we get x = 0. Thus, C = {0}, and P is bounded by Minkowski-Weyl Theorem.

Given X ∈ R n , we denote by exp X the vector with entries exp X i , i ∈ [n].

Let P (x) = 1 be a posynomial system with pointed exponents, and y be a colorful vector. Then, the system has a solution x = exp X * ∈ (R >0 ) n , where X * is an arbitrary solution of the following geometric program:

where g i (X) := log a∈SP i c a e a,X .

Proof. For x ∈ R n >0 , we define X = log(x) (component-wise) so that P (x) = 1 is equivalent to solving g i (X) = 0 for all i ∈ [n]. By Hölder's inequality, the functions (g i ) i∈ [n] are convex. We define h i : X → max a∈SP i log(c a ) + a, X for i ∈ [n] and we observe that h i (X) g i (X) h i (X) + log(|S Pi |).

Since the system P (x) = 1 has pointed exponents, by Proposition 4, the polyhedron {X ∈ R n : ∀i ∈ [n], h i (X) + log(|S Pi |) 0} is nonempty. A fortiori, the feasible set of (G) is nonempty.

Let us now prove that the maximum of (G) is finite and attained, by proving that the μ-superlevel set S μ = {X ∈ R n : y, X μ and ∀i ∈ [n], g i (X) 0} of the objective function (included in the feasible set) is compact for all μ ∈ R. Closedness is direct, and we observe that for μ ∈ R, S μ ⊂ {X ∈ R n : y, X μ and ∀i ∈ [n], h i (X) 0}, but by Lemma 6, this polyhedron is bounded. Hence, (G) admits an optimal solution X . Furthermore, again by Proposition 4, there exists X such that for all i ∈ [n], h i (X)+log(|S Pi |)+1 0. Therefore, for all i ∈ [n], g i (X) < 0, which means that (G) satisfies Slater's condition. Problem (G) being convex, optimality of X is characterized by the Karush-Kuhn-Tucker conditions (see [4] ). Hence, there is a vector of nonnegative multipliers λ = (λ 1 , . . . , λ n ) such that (X , λ ) is a stationary point of the Lagrangian of (G), and the complementarity slackness conditions hold, i.e. for all i ∈ [n], λ i g i (X ) = 0. Defining Z i := a∈SP i c a e a,X > 0 for i ∈ [n], the stationarity conditions give

Since y is colorful, for all i ∈ [n], λ i > 0. The complementarity slackness conditions yield g i (X ) = 0 for all i ∈ [n]. So x := exp(X ) satisfies P (x ) = 1.

Theorems 3 and 7 rely on the existence of a colorful vector. The purpose of this section is to study the properties of the set of such vectors. In fact, colorful vectors can be defined more generally from a family of n closed convex cones.

Let C = (C 1 , . . . , C n ) be a collection of n closed convex cones of R n . A vector y ∈ R n is said to be colorful if it belongs to the set

The latter set is referred to as the colorful interior of C.

Remark that Definition 1 can be recovered by taking

In what follows, we restrict to the case where the collection C is pointed, i.e. cone(C 1 ∪ · · · ∪ C n ) is a pointed cone (in the non pointed case, the colorful interior enjoys much less structure than the one proved in Theorem 10, in particular it may not even be connected). Suppose that {x ∈ R n : z, x > 0} is an open halfspace containing the (C i ) i∈ [n] . Then, as a cone, the colorful interior of C can be more simply studied from its cross-section with {x ∈ R n : x, z = 1 . The latter can be shown to coincide with the set

where for i ∈ [n], S i is the cross-section of the cone C i by {x ∈ R n : x, z = 1 . Given a collection S = (S 1 , . . . , S n ) of closed convex sets of R n−1 , we refer to the set (3) as the colorful interior of S, and denote it by colint S. We start with a lemma justifying the terminology we have chosen: . . . , S n ) be a collection of n closed convex sets of R n−1 . Then colint S is an open set included in int conv(S 1 ∪ · · · ∪ S n ).

The set colint S has appeared in a work of Lawrence and Soltan [9] , in the proof of the characterization of the intersection of convex transversals to a collection of sets. In more details, Lemma 8 and [9, Lemma 6] imply: . 1. (a) three convex sets S1 (blue), S2 (green) and S3 (orange) in R 2 and their colorful interior (white). The sets ( Si) 1 i 3 (resp. (Si) 1 i 3 ) are seen by taking convex hulls of (Si) 1 i n (resp. intersection of ( Si) 1 i 3 ) pairwise. Observe that the edges of the colorful interior are supported by tangent hyperplanes to two sets of (S1, S2, S3). (b) the colorful interior of (S1, S2, S3) is here empty, although these sets are separated (any three points in each of them are in general position), contrary to the sets (S1, S2, S3), whose intersection is seen in the center of the figure. (Color figure online)

Geometrically, every H i in Theorem 10 is a tangent hyperplane to the convex sets (S j ) j =i which separates them from the set S i . The existence (and uniqueness) of such tangent hyperplanes follows from the work of Cappell et al. [5] , see also the work of Lewis, Klee and von Hohenbalken [10] for a constructive proof. We depict on Fig. 1a three colored sets S 1 , S 2 and S 3 in R 2 with nonempty colorful interior colint (S 1 , S 2 , S 3 ), illustrating that the latter is the interior of a simplex as claimed in Theorem 10. Given a collection S = (S 1 , . . . , S n ) of n closed convex sets of R n−1 , we now discuss necessary and sufficient conditions for colint S to be nonempty. To this purpose we recall that the collection S is separated if for any choice of k n points x 1 , . . . , x k in S i1 × · · · × S i k (where i 1 , . . . , i k are pairwise distinct), the points x 1 , . . . , x k are in general position (spanning a (k − 1)-dimensional affine space). 

Then, if colint S is nonempty, the family (S i ) i∈[n] is separated.

Proposition 12 provides a necessary condition to ensure that colint S = ∅. Since for all i ∈ [n], we have S i ⊂ S i , we also obtain that the separation of (S i ) i∈ [n] is necessary as well for colint S to be nonempty. However, Fig. 1b shows that this last condition is not sufficient. We conjecture that the necessary condition stated in Proposition 12 is sufficient: Conjecture 13. Let S 1 , . . . , S n be a collection of n compact convex sets of R n−1 . Then colint S is nonempty if and only if the family (S i ) i∈[n] is separated.

We prove this conjecture in the case where n = 3 (it is also straightforward to establish for n = 2). Proof. Suppose that (S 1 , S 2 , S 3 ) is separated. We know from [10] that for all i ∈ {1, 2, 3} we have two hyperplanes (in this case affine lines) tangent to sets of the collection (S j ) j =i and inducing opposite orientation on these. Such lines cannot meet S i by separation property, so one of them, denoted H i , is such that S i ⊂ H > i and S j ⊂ H i for j = i. In particular, note that conv((S j ) j =i ) ⊂ H i . For i, j ∈ {1, 2, 3} and j = i, the hyperplane H i is not only tangent to S j but also to S j : indeed take a support y j i of H i in S j , it arises as a convex combination

we derive for all k = i, x k ∈ H k or λ k = 0, the latter being ruled out by separation. Hence, let us denote by x j i a support of hyperplane H i in S j . Note that once again from the separation of (S 1 , S 2 , S 3 ), two supports of a tangent line in two different colors cannot be equal.

If x := (a, b) T and y := (a , b ) T are two distinct vectors of R 2 , we denote x ∧ y := (ab − a b) −1 (b − b , a − a) T , the usual cross-product of two vectors in P 2 . As is customary, h 1 := x 2 1 ∧ x 3 1 (resp. h 2 := x 3 2 ∧ x 1 2 and h 3 := x 1 3 ∧ x 2 3 ) is a normal vector to H 1 (resp. H 2 and H 3 ), and h i , x + 1 = 0 is an equation defining H i . Furthermore, the intersection of H 1 and H 2 is given by s 3 := h 1 ∧ h 2 , or using the triple product formula, by

Because x 1 2 ∈ S 1 ⊂ H > 1 and x 3 2 ∈ S 3 ⊂ H 1 , we have that h 1 , x 1 2 + 1 is nonzero and ( h 1 , x 1 2 + 1)( h 1 , x 3 2 + 1) 0. As a result of (4), s 3 indeed exists and arises as a convex combination of x 3 2 and x 1 2 , so s 3 ∈ conv(S 1 ∪ S 3 ). By writing s 3 = (x 2 1 ∧ x 3 1 ) ∧ h 2 as in (4), we show likewise that s 3 is a convex combination of x 2 1 and x 3 1 , thus s 3 ∈ conv(S 2 ∪ S 3 ). This finally entails that s 3 ∈ S 3 and therefore s 3 ∈ H > 3 . It now suffices to define s 1 := h 2 ∧ h 3 and s 2 := h 3 ∧ h 1 in a similar way and consider y = (s 1 + s 2 + s 3 )/3. It is clear that y ∈ conv(S 1 ∪ S 2 ∪ S 3 ), and for all i ∈ {1, 2, 3}, y ∈ H > i , in particular y / ∈ conv((S j ) j =i ). As a consequence, y is a colorful vector for S 1 , S 2 and S 3 .

To conclude, we point out that another interesting problem is the computational complexity of determining whether the colorful interior is empty or not, in the case where the sets S i are polytopes. Remark that as a consequence of Proposition 11, if Conjecture 13 holds, then we can determine if colint S is empty in polynomial time using linear programming. Alternatively, the problem could be tackled by studying the complexity of separating a point from the colorful interior. This is tightly linked with the computation of the tangent hyperplanes of Theorem 10, for which the status of the complexity is not well understood.

The operator approach to entropy games

Performance evaluation of an emergency call center: tropical polynomial systems applied to timed petri nets

A variational formula for risk-sensitive reward

Convex Optimization

Common tangents and common transversals

Relative entropy relaxations for signomial optimization

A positivstellensatz for sums of nonnegative circuit polynomials

Spectral inequalities for nonnegative tensors and their tropical analogues

The intersection of convex transversals is a convex polytope

Common supports as fixed points

Singular values and eigenvalues of tensors: a variational approach

Maslov dequantization, idempotent and tropical mathematics: a brief introduction

Markov Decision Processes: Discrete Stochastic Dynamic Programming

Dequantization of real algebraic geometry on logarithmic paper