Proving strong duality for geometric optimization using a conic formulation

François Glineur^{∗}

                         Francois.Glineur@fpms.ac.be

Service de Mathématique et de Recherche Opérationnelle, Faculté Polytechnique de Mons, Rue de Houdain, 9, B-7000 Mons, Belgium.

Abstract

Geometric optimization^{1} is an important class of problems that has many applications, especially in engineering design. In this article, we provide new simplified proofs for the well-known associated duality theory, using conic optimization. After introducing suitable convex cones and studying their properties, we model geometric optimization problems with a conic formulation, which allows us to apply the powerful duality theory of conic optimization and derive the duality results valid for geometric optimization.

Keywords: geometric optimization, duality theory, conic optimization.

1 Introduction

Geometric optimization forms an important class of problems that enables practitioners to model a large variety of real-world applications, mostly in the field of engineering design.

Although not convex itself, a geometric optimization problem can be easily transformed into a convex problem, for which a Lagrangean dual can be explicitly written. Several duality results are known for this pair of problems, some being mere consequences of convexity (e.g. weak duality), others being specific to this particular class of problems (e.g. the absence of a duality gap).

These properties were first studied in the sixties, and can be found for example in the reference book of Duffin, Peterson and Zener [2]. The aim of this paper is to derive these results using the machinery of duality for conic optimization, which has in our opinion the advantage of simplifying and clarifying the proofs.

In order to use this setting, we start by defining an appropriate convex cone that allows us to express geometric optimization problems as conic programs. The first step we take consists in studying some properties of this cone (e.g. closedness) and determine its dual. We are then in position to apply the general duality theory for conic optimization [9, 10] to our problems and find in a rather seamless way the various well-known duality theorems of geometric optimization.

∗The author is a research fellow supported by a grant from the F.N.R.S. (Belgian National Fund for Scientific Research). This research was partly carried out during a visit to the SSOR department of the Delft University of Technology supported by a grant from the Communauté Française de Belgique.

1This class of problems is usually known as geometric programming, for historical reasons. However, because of the strong connection of the term ”programming” with computer science, we prefer to use the more natural word ”optimization”.

This paper is organized as follows: Section 2 introduces conic optimization and outlines the associated duality theory, while we define and study in Section 3 the convex cones needed to model geometric optimization. Section 4 constitutes the main part of this article and presents new proofs of several duality theorems based on conic duality. Finally, we provide in Section 5 some hints on how to establish the link between our results and the classical theorems found in the literature, as well as some concluding remarks.

2 Conic optimization

In this section, we describe conic optimization and the associated duality theory. The results are well-known and we will skip most of the proofs (they can be found for example in the Ph.D. thesis of Sturm [10], which has been recently published in [11]). Conic optimization deals with a class of problems that is essentially equivalent to the class of convex problems, i.e. minimization of a convex function over a convex set. However, formulating a convex problem in a conic way often gives a new insight about it, especially when dealing with duality.

2.1 Conic problems

The basic ingredient we need is a convex cone.

Definition 2.1 A set K is a cone if and only if it is closed under nonnegative scalar multiplication, i.e.

x ∈ K ⇒ λx ∈ K for all λ ∈ ℝ_{+} .

Recall that a set is convex if and only if it contains the whole segment joining any two of its points. Establishing convexity is easier for cones than for general sets, because of the following elementary theorem (see e.g. [7]):

Theorem 2.1 A cone K is convex if and only if it is closed under addition, i.e.

x ∈ K and y ∈ K ⇒ x + y ∈ K .

In order to avoid some technical nuisances, the convex cones we are going to consider will be required to be closed, pointed and solid, according to the following definitions:

Definition 2.2 A cone K is solid if and only if int K ≠ ∅.

Definition 2.3 A cone K is pointed if and only if K ∩ −K = {0}.

These two properties basically mean that K is a full-dimensional cone that does not contain any straight line passing through the origin.

We are now in position to define a conic optimization problem: let K ⊆ ℝ^{n} a pointed, solid, closed convex cone. The (primal) conic optimization problem is

inf_{x} c^{T} x s.t. Ax = b and x ∈ K ,  (CP)

where x ∈ ℝ^{n} is the column vector we are optimizing, A is a m×n matrix and b, c are column vectors belonging respectively to ℝ^{m} and ℝ^{n}. This problem can be viewed as the minimization of a linear function over the intersection of a convex cone and an affine subspace. At this stage, we would like to emphasize the fact that although our cone K is closed, it may happen that the infimum in (CP) is not attained (some examples of this situation will be given in Subsection 4.4).

It is well-known that this class of problems is equivalent to the class of convex problems, see e.g. [6]. However, the usual Lagrangean dual of a conic problem can be expressed very nicely in a conic form, using the notion of dual cone.

2.2 Dual conic problems

Definition 2.4 The dual of a cone K ⊆ ℝ^{n} is defined by

K^{∗} = {x^{∗} ∈ ℝ^{n} | x^{T} x^{∗} ≥ 0 for all x ∈ K} .

The dual of a cone is always a closed convex cone. However, we have the stronger theorem

Theorem 2.2 If K is a solid, pointed, closed convex cone, its dual K^{∗} is another solid, pointed, closed convex cone. Moreover, the dual of K^{∗} is equal to K.

Indeed, the notions of solidness and pointedness are dual to each other [10, Corollary 2.1], while closedness is essential for (K^{∗})^{∗} = K to hold (we have in fact (K^{∗})^{∗} = cl K without the closedness assumption on K [7, Theorem 14.1]).

The dual of our primal conic problem (CP) is defined by

sup_{(y,s)} b^{T} y s.t. A^{T} y + s = c and s ∈ K^{∗} ,  (CD)

where y ∈ ℝ^{m} and s ∈ ℝ^{n} are the column vectors we are optimizing, the other quantities A, b and c being the same as in (CP). It is immediate to notice that this dual problem has the same kind of structure as the primal problem, i.e. it also involves optimizing a linear function over the intersection of a convex cone and an affine subspace. The only differences are the direction of the optimization (maximization instead of minimization) and the way the affine subspace is described. It is also possible to show that the dual of this dual problem is equivalent to the primal problem, using the fact that (K^{∗})^{∗} = K.

2.3 Duality theory

The two conic problems of this primal-dual pair are strongly related to each other, as demonstrated by the following theorems.

Theorem 2.3 (Weak duality) Let x a feasible (i.e. satisfying the constraints) solution for (CP), and (y, s) a feasible solution for (CD). We have

b^{T} y ≤ c^{T} x ,

equality occurring if and only if the following orthogonality condition is satisfied:

x^{T} s = 0 .

This theorem shows that any primal (resp. dual) feasible solution provides an upper (resp. lower) bound for the dual (resp. primal) problem. Its proof is quite easy to obtain: elementary manipulations give

c^{T} x − b^{T} y = x^{T} c − (Ax)^{T} y = x^{T} (A^{T} y + s) − x^{T} A^{T} y = x^{T} s ,

this last inner product being always nonnegative because of x ∈ K, s ∈ K^{∗} and Definition 2.4 of the dual cone K^{∗}.

Denoting by p^{∗} and d^{∗} the optimum objective values of problems (CP) and (CD), this theorem implies that p^{∗} − d^{∗} ≥ 0. This nonnegative quantity is called the duality gap. Under certain circumstances, it can be proved to be equal to zero, which shows that the optimum values of problems (CP) and (CD) are equal. Before describing the conditions guaranteeing such a situation, called strong duality, we need to introduce the notion of strictly feasible point.

Definition 2.5 A point x (resp. (y, s)) is said to be strictly feasible for the primal (resp. dual) problem if and only if it is feasible and belongs to the interior of the cone K (resp. K^{∗}), i.e.

Ax = b and x ∈ int K (resp. A^{T} y + s = c and s ∈ int K^{∗}) .

Moreover, we will say that the primal (resp. dual) problem is unbounded if p^{∗} = −∞ (resp. d^{∗} = +∞), that it is infeasible if there is no feasible solution, i.e. when p^{∗} = +∞ (resp. d^{∗} = −∞), and that it is attained if the optimum objective value p^{∗} (resp. d^{∗}) is achieved by at least one feasible primal (resp. dual) solution.

Theorem 2.4 (Strong duality) If the dual problem (CD) admits a strictly feasible solution, we have either

⋄ an infeasible primal problem (CP) if the dual problem (CD) is unbounded, i.e. p^{∗} = d^{∗} = +∞

⋄ a feasible primal problem (CP) if the dual problem (CD) is bounded. Moreover, in this case, the primal optimum is finite and attained with a zero duality gap, i.e. there is at least an optimal feasible solution x^{∗} such that c^{T} x^{∗} = p^{∗} = d^{∗}.

The first case in this theorem (see e.g. [10, Theorem 2.7] for a proof) is a simple consequence of Theorem 2.3, and does not really depend on the existence of a strictly feasible solution for the dual, as opposed to the second case which relies on the existence of such a point. It is also worth to mention that boundedness of the dual problem (CD), defining the second case, is implied by the existence of a feasible primal solution, because of the weak duality theorem (however, the converse implication is not true in general, since a bounded dual problem can admit an infeasible primal problem ; an example of this situation is provided in Subsection 4.4).

This theorem is important, because it provides us with way to identify when both the primal and the dual problems have the same optimal value, and when this optimal value is attained by one of the problems. Obviously, this result can be dualized, meaning that the existence of a strictly feasible primal solution implies a zero duality gap and dual attainment. The combination of these two theorems leads to the following well-known and very useful corollary:

Corollary 2.1 If both the primal and the dual problems admit a strictly feasible point, we have a zero duality gap and attainment for both problems, i.e. the same finite optimum objective value is attained for both problems.

When the dual problem has no strictly feasible point, nothing can be said about the duality gap (which can happen to be strictly positive) and about attainment of the primal optimum objective value. However, even in this situation, we can prove an alternate version of the strong duality theorem involving the notion of primal problem subvalue. The idea behind this notion is to allow a small constraint violation in the infimum defining the primal problem (CP).

Definition 2.6 The subvalue of primal problem (CP) is given by

p^{−} = lim_{ϵ→0^{+}} [ inf_{x} c^{T} x s.t. ∥Ax − b∥ < ϵ and x ∈ K ]

(a similar definition is holding for the dual subvalue d^{−}).

It is readily seen that this limit always exists (possibly being +∞), because the feasible region of the infimum shrinks as ϵ tends to zero, which implies that its optimum value is a nonincreasing function of ϵ. Moreover, the inequality p^{−} ≤ p^{∗} holds, because all the feasible regions of the infima defining p^{−} as ϵ tends to zero are larger than the actual feasible region of problem (CP).

The case p^{−} = +∞, which implies that primal problem (CP) is infeasible (since we have then p^{∗} ≥ p^{−} = +∞), is called primal strong infeasibility, and essentially means that the affine subspace defined by the linear constraints Ax = b is strongly separated from cone K. We are now in position to state the following alternate strong duality theorem:

Theorem 2.5 (Strong duality, alternate version) We have either

⋄ p^{−} = +∞ and d^{∗} = −∞ when primal problem (CP) is strongly infeasible and dual problem (CD) is infeasible.

⋄ p^{−} = d^{∗} in all other cases.

This theorem (see e.g. [10, Theorem 2.6] for a proof) states that there is no duality gap between p^{−} and d^{∗}, except in the rather exceptional case of primal strong infeasibility and dual infeasibility. Note that the second case covers situations where the primal problem is infeasible but not strongly infeasible (i.e. p^{−} < p^{∗} = +∞).

To conclude this section, we would like to mention the fact that all the properties and theorems described in this section can be easily extended to the case of several conic constraints involving disjoint sets of variables.

Note 2.1 Namely, having to satisfy the constraints x^{i} ∈ K^{i} for all i ∈ {1, 2, …, k}, where K^{i} ⊆ ℝ^{n_{i}}, we will simply consider the Cartesian product of these cones K = K^{1} × K^{2} × ⋯ × K^{k} ⊆ ℝ^{∑_{i=1}^{k} n_{i}} and express all these constraints simultaneously as x ∈ K with x = (x^{1}, x^{2}, …, x^{k}).

3 Cones for geometric optimization

Let us introduce the geometric cone G^{n}, which will allow us to give a conic formulation of geometric optimization problems.

3.1 The geometric cone G^{n}

Definition 3.1 Let n ∈ ℕ. The geometric cone G^{n} is defined by

G^{n} = \{(x, θ) ∈ ℝ_{+}^{n} × ℝ_{+} | ∑_{i=1}^{n} e^{− \frac{x_{i}}{θ}} ≤ 1\}

using in the case of a zero denominator the following convention:

e^{− \frac{x_{i}}{0}} = 0 .

We observe that this convention results in (x, 0) ∈ G^{n} for all x ∈ ℝ_{+}^{n}. As special cases, we mention that G^{0} is the nonnegative real line ℝ_{+}, while G^{1} is easily shown to be equal to the 2-dimensional nonnegative orthant ℝ_{+}^{2}.

In order to use the powerful duality theory of convex optimization outlined in the previous section, we first prove that G^{n} is a convex cone. We are going to use the well-known weighted arithmetic-geometric mean inequality, which we recall here as a lemma:

Lemma 3.1 Let x ∈ ℝ_{++}^{n} and δ ∈ ℝ_{++}^{n} such that ∑_{i=1}^{n} δ_{i} = 1. We have

∏_{i=1}^{n} x_{i}^{δ_{i}} ≤ ∑_{i=1}^{n} δ_{i}x_{i} ,

equality occurring if and only if all x_{i}’s are equal.

This result is easily proved, applying for example Jensen’s inequality [7, Theorem 4.3] to the convex function x ↦ e^{x}.

Theorem 3.1 G^{n} is a convex cone.

Proof . To prove that a set is a convex cone, it suffices to show that it is closed under addition and nonnegative scalar multiplication (Definition 2.1 and Theorem 2.1). Indeed, if (x, θ) ∈ G^{n}, (x′, θ′) ∈ G^{n} and λ ≥ 0, we have

∑_{i=1}^{n} e^{− \frac{λx_{i}}{λθ}} = \begin{cases}∑_{i=1}^{n} e^{− \frac{x_{i}}{θ}} ≤ 1 & if λ > 0 \\ 0 ≤ 1 & if λ = 0 \end{cases}

which shows that λ(x, θ) ∈ G^{n}. Looking now at (x, θ) + (x′, θ′), we first consider the case θ > 0 and θ′ > 0 and write

∑_{i=1}^{n} e^{− \frac{x_{i}+x′_{i}}{θ+θ′}} = ∑_{i=1}^{n} (e^{− \frac{x_{i}}{θ}} )^{\frac{θ}{θ+θ′}} (e^{− \frac{x′_{i}}{θ′}} )^{\frac{θ′}{θ+θ′}} ;

using now Lemma 3.1 on each term of the sum with vector (e^{− \frac{x_{i}}{θ}} , e^{− \frac{x′_{i}}{θ′}}) and weights (\frac{θ}{θ+θ′} , \frac{θ′}{θ+θ′}), satisfying \frac{θ}{θ+θ′} + \frac{θ′}{θ+θ′} = 1, we have

∑_{i=1}^{n} e^{− \frac{x_{i}+x′_{i}}{θ+θ′}} ≤ ∑_{i=1}^{n} \frac{θ}{θ + θ′} (e^{− \frac{x_{i}}{θ}}) + \frac{θ′}{θ + θ′} (e^{− \frac{x′_{i}}{θ′}})

= \frac{θ}{θ + θ′} ∑_{i=1}^{n} e^{− \frac{x_{i}}{θ}} + \frac{θ′}{θ + θ′} ∑_{i=1}^{n} e^{− \frac{x′_{i}}{θ′}}

≤ \frac{θ}{θ + θ′} 1 + \frac{θ′}{θ + θ′} 1 = 1 ,

while in the case of θ′ = 0 we have

∑_{i=1}^{n} e^{− \frac{x_{i}+x′_{i}}{θ+θ′}} = ∑_{i=1}^{n} e^{− \frac{x_{i}+x′_{i}}{θ}} ≤ ∑_{i=1}^{n} e^{− \frac{x_{i}}{θ}} ≤ 1

(the case θ = 0 is similar). We have thus shown that (x + x′, θ + θ′) ∈ G^{n} in all cases, and therefore that G^{n} is a convex cone. □

We now proceed to prove some properties of the geometric cone G^{n}.

Theorem 3.2 G^{n} is closed.

Proof . Let {(x^{k}, θ^{k})} a sequence of points in ℝ^{n+1} such that (x^{k}, θ^{k}) ∈ G^{n} for all k and lim_{k→∞}(x^{k}, θ^{k}) = (x^{∞}, θ^{∞}). In order to prove that G^{n} is closed, it suffices to show that (x^{∞}, θ^{∞}) ∈ G^{n}. Let us distinguish two cases:

⋄ θ^{∞} > 0. Using the easily proven fact that functions (x_{i}, θ) ↦ e^{− \frac{x_{i}}{θ}} are continuous on ℝ_{+} × ℝ_{++}, we have that

∑_{i=1}^{n} e^{− \frac{x^{∞}_{i}}{θ^{∞}}} = ∑_{i=1}^{n} lim_{k→∞} e^{− \frac{x^{k}_{i}}{θ^{k}}} = lim_{k→∞} ∑_{i=1}^{n} e^{− \frac{x^{k}_{i}}{θ^{k}}} ≤ 1 ,

which implies (x^{∞}, θ^{∞}) ∈ G^{n}.

⋄ θ^{∞} = 0. Since (x^{k}, θ^{k}) ∈ G^{n}, we have x^{k} ≥ 0 and thus x^{∞} ≥ 0, which implies that (x^{∞}, 0) ∈ G^{n}.

In both cases, (x^{∞}, θ^{∞}) is shown to belong to G^{n}, which proves the claim. □

In order to use the strong duality theorem, we now proceed to identify the interior of the geometric cone.

Theorem 3.3 The interior of G^{n} is given by

int G^{n} = \{(x, θ) ∈ ℝ_{++}^{n} × ℝ_{++} | ∑_{i=1}^{n} e^{− \frac{x_{i}}{θ}} < 1\} .

Proof . A point x belongs to the interior of a set S if and only if there exists an open ball centered at x entirely included in S. Let (x, θ) ∈ G^{n}. We first note that (x, 0) cannot belong to int G^{n}, because every open ball centered at (x, 0) contains a point with a negative θ component, which does not belong to the cone G^{n}. Suppose θ > 0 and the inequality in the definition of G^{n} is satisfied with equality, i.e.

∑_{i=1}^{n} e^{− \frac{x_{i}}{θ}} = 1 .

Every open ball centered at (x, θ) contains a point (x′, θ′) with x′ < x and θ′ > θ, which satisfies then

∑_{i=1}^{n} e^{− \frac{x′_{i}}{θ′}} > ∑_{i=1}^{n} e^{− \frac{x_{i}}{θ}} = 1

and is thus outside of G^{n}, implying (x, θ) ∉ int G^{n}. We now show that all the remaining points that do not satisfy one of the two conditions mentioned above, i.e. the points with θ > 0 satisfying the strict inequality, belong to the interior of G^{n}. Let (x, θ) one of these points, and B(ϵ) the open ball centered at (x, θ) with radius ϵ. Restricting ϵ to sufficiently small values (i.e. choosing ϵ < θ), we have for all points (x′, θ′) ∈ B(ϵ)

x_{i} − ϵ ≤ x′_{i} ≤ x_{i} + ϵ and 0 < θ − ϵ ≤ θ′ ≤ θ + ϵ ,

which implies

\frac{x′_{i}}{θ′} ≥ \frac{x − ϵ}{θ + ϵ} and thus ∑_{i=1}^{n} e^{− \frac{x′_{i}}{θ′}} ≤ ∑_{i=1}^{n} e^{− \frac{x_{i}−ϵ}{θ+ϵ}} for all (x′, θ′) ∈ B(ϵ) .  (3.1)

Taking the limit of the last right-hand side when ϵ → 0, we find

lim_{ϵ→0} ∑_{i=1}^{n} e^{− \frac{x_{i}−ϵ}{θ+ϵ}} = ∑_{i=1}^{n} e^{− \frac{x_{i}}{θ}} < 1

(because of the continuity of functions (x_{i}, θ) ↦ e^{− \frac{x_{i}}{θ}} on ℝ_{+}×ℝ_{++}). Therefore we can assume the existence of a value ϵ^{∗} such that

∑_{i=1}^{n} e^{− \frac{x_{i}−ϵ^{∗}}{θ+ϵ^{∗}}} < 1 ,

which because of (3.1) will imply that

∑_{i=1}^{n} e^{− \frac{x′_{i}}{θ′}} < 1

for all (x′, θ′) ∈ B(ϵ^{∗}). This inequality, combined with θ′ > 0, is sufficient to prove that the open ball B(ϵ^{∗}) is entirely included in G^{n}, hence that (x, θ) ∈ int G^{n}. □

Theorem 3.4 G^{n} is solid and pointed.

Proof . The fact that 0 ∈ G^{n} ⊆ ℝ_{+}^{n+1} implies that G^{n} ∩ −G^{n} = {0}, i.e. G^{n} is pointed (Definition 2.3). To prove it is solid (Definition 2.2), we simply provide a point belonging to its interior, for example (e, \frac{1}{n}) (where e stands for the all-one vector). We have then

∑_{i=1}^{n} e^{− \frac{x_{i}}{θ}} = ne^{−n} < 1 ,

because e^{n} > n for all n ∈ ℕ, and therefore (e, \frac{1}{n}) ∈ int G^{n}. □

To summarize, G^{n} is a solid pointed close convex cone, hence suitable for conic optimization.

3.2 The dual geometric cone (G^{n})^{∗}

In order to express the dual of a conic problem involving the geometric cone G^{n}, we need to find an explicit description of its dual.

Theorem 3.5 The dual of G^{n} is given by

(G^{n})^{∗} = \{(x^{∗}, θ^{∗}) ∈ ℝ_{+}^{n} × ℝ | θ^{∗} ≥ ∑_{i|x_{i}^{∗}>0} x_{i}^{∗} log \frac{x_{i}^{∗}}{∑_{i=1}^{n} x_{i}^{∗}} \} .

Proof . Using Definition 2.4 for the dual cone, we have

(G^{n})^{∗} = {(x^{∗}, θ^{∗}) ∈ ℝ^{n} × ℝ | (x, θ)^{T} (x^{∗}, θ^{∗}) ≥ 0 for all (x, θ) ∈ G^{n}}

(the ^{∗} superscript on variables x^{∗} and θ^{∗} is a reminder of their dual nature). This condition on (x^{∗}, θ^{∗}) is equivalent to saying that the following infimum

δ(x^{∗}, θ^{∗}) = inf x^{T} x^{∗} + θθ^{∗} s.t. (x, θ) ∈ G^{n} .

has to be nonnegative. Let us distinguish the cases θ = 0 and θ > 0: we have that

δ(x^{∗}, θ^{∗}) = min{δ_{1}(x^{∗}, θ^{∗}), δ_{2}(x^{∗}, θ^{∗})}

with

\{ \begin{matrix}δ_{1}(x^{∗}, θ^{∗}) = inf x^{T} x^{∗} + θθ^{∗} s.t. (x, θ) ∈ G^{n} and θ = 0 \\ δ_{2}(x^{∗}, θ^{∗}) = inf x^{T} x^{∗} + θθ^{∗} s.t. (x, θ) ∈ G^{n} and θ > 0 \end{matrix} .

The first of these infima can be rewritten as

inf x^{T} x^{∗} s.t. x ≥ 0 ,

since (x, 0) ∈ G^{n} ⇔ x ≥ 0. It is easy to see that this infimum is equal to 0 if x^{∗} ≥ 0 and to −∞ when x^{∗} ≱ 0. Since we are looking for points with a nonnegative infimum δ(x^{∗}, θ^{∗}), we will require in the rest of this proof x^{∗} to be nonnegative and only consider the second infimum, which is equal to

inf θ [\frac{x^{T} x^{∗}}{θ} + θ^{∗}] s.t. ∑_{i=1}^{n} e^{− \frac{x_{i}}{θ}} ≤ 1 and (x, θ) ∈ ℝ_{+}^{n} × ℝ_{++} .  (3.2)

Let us again distinguish two cases. When x^{∗} = 0, this infimum becomes

inf θθ^{∗} s.t. ∑_{i=1}^{n} e^{− \frac{x_{i}}{θ}} ≤ 1 and (x, θ) ∈ ℝ_{+}^{n} × ℝ_{++} ,

which is nonnegative if and only if θ^{∗} ≥ 0, since θ can take any value in the open positive interval ]0 + ∞[. On the other hand, if x^{∗} ≠ 0, we have ∑_{i=1}^{n} x_{i}^{∗} > 0 and can define the auxiliary variables w_{i}^{∗} by

w_{i}^{∗} = \frac{x_{i}^{∗}}{∑_{i=1}^{n} x_{i}^{∗}}

(in order to simplify notations). We write the following chain of inequalities

1 ≥ ∑_{i=1}^{n} e^{− \frac{x_{i}}{θ}} ≥ ∑_{i|w_{i}^{∗}>0} e^{− \frac{x_{i}}{θ}} = ∑_{i|w_{i}^{∗}>0} w_{i}^{∗} (\frac{e^{− \frac{x_{i}}{θ}}}{w_{i}^{∗}} ) ≥ ∏_{i|w_{i}^{∗}>0} (\frac{e^{− \frac{x_{i}}{θ}}}{w_{i}^{∗}} )^{w_{i}^{∗}}  (3.3)

The second inequality comes from the fact that each term of the sum is positive (we remove some terms), and the third one uses Lemma 3.1 with weights w_{i}^{∗}, noting that ∑_{i|w_{i}^{∗}>0} w_{i}^{∗} = ∑_{i=1}^{n} w_{i}^{∗} = 1. From this last inequality we derive successively

∏_{i|w_{i}^{∗}>0} e^{− \frac{x_{i}w^{∗}_{i}}{θ}} ≤ ∏_{i|w_{i}^{∗}>0} w_{i}^{∗}^{w_{i}^{∗}} ,

− ∑_{i|w_{i}^{∗}>0} \frac{x_{i}w_{i}^{∗}}{θ} ≤ ∑_{i|w_{i}^{∗}>0} w_{i}^{∗} log w_{i}^{∗} (taking the logarithms) ,

∑_{i=1}^{n} \frac{x_{i}x_{i}^{∗}}{θ} ≥ − ∑_{i|x_{i}^{∗}>0} x_{i}^{∗} log w_{i}^{∗} (multiplying by − ∑_{i=1}^{n} x_{i}^{∗}) ,

\frac{x^{T} x^{∗}}{θ} + θ^{∗} ≥ θ^{∗} − ∑_{i|x_{i}^{∗}>0} x_{i}^{∗} log w_{i}^{∗} , and finally

inf_{(x,θ)∈G^{n}|θ>0} \frac{x^{T} x^{∗}}{θ} + θ^{∗} ≥ θ^{∗} − ∑_{i|x_{i}^{∗}>0} x_{i}^{∗} log w_{i}^{∗} .

Examining carefully the chain of inequalities in (3.3), we observe that a suitable choice of (x, θ) can lead to attainment of this last infimum: namely, we need to have

⋄ ∑_{i=1}^{n} e^{− \frac{x_{i}}{θ}} = 1, for the first inequality in (3.3),

⋄ x_{i} → +∞ for all indices i such that w_{i}^{∗} = 0, in order to have e^{− \frac{x_{i}}{θ}} → 0 when w_{i}^{∗} = 0 for the second inequality in (3.3),

⋄ all terms (\frac{e^{− \frac{x_{i}}{θ}}}{w_{i}^{∗}} ) with indices such that w_{i}^{∗} > 0 equal to each other, for the third inequality in (3.3).

These conditions are compatible: summing up the constant terms, we find

\frac{e^{− \frac{x_{i}}{θ}}}{w_{i}^{∗}} (when w_{i}^{∗} > 0) = \frac{∑_{i|w_{i}^{∗}>0} e^{− \frac{x_{i}}{θ}}}{∑_{i|w_{i}^{∗}>0} w_{i}^{∗}} = ∑_{i|w_{i}^{∗}>0} e^{− \frac{x_{i}}{θ}} → ∑_{i=1}^{n} e^{− \frac{x_{i}}{θ}} = 1 ,

Figure 1: The boundary surfaces of G^{2} and its dual cone (G^{2})^{∗}.

which gives e^{− \frac{x_{i}}{θ}} = w_{i}^{∗} for all i such that w_{i}^{∗} > 0. Summarizing, we can choose x according to

\begin{cases}x_{i} = −θ log w_{i}^{∗} & when w_{i}^{∗} > 0 \\ x_{i} → +∞ & when w_{i}^{∗} = 0 \end{cases} ,

which proves that

inf_{(x,θ)∈G^{n}|θ>0} \frac{x^{T} x^{∗}}{θ} + θ^{∗} = θ^{∗} − ∑_{i|x_{i}^{∗}>0} x_{i}^{∗} log w_{i}^{∗} .  (3.4)

Since the additional multiplicative θ in (3.2) doesn’t change the sign of this infimum (because θ > 0), we may conclude that it is nonnegative if and only if

θ^{∗} − ∑_{i|x_{i}^{∗}>0} x_{i}^{∗} log w_{i}^{∗} ≥ 0 .

Combining with the special case x^{∗} = 0 and the constraint x^{∗} ≥ 0 implied by the first infimum, we conclude that the dual cone is given by

(G^{n})^{∗} = {(x^{∗}, θ^{∗}) ∈ ℝ_{+}^{n} × ℝ | θ^{∗} ≥ ∑_{i|x_{i}^{∗}>0} x_{i}^{∗} log w_{i}^{∗}} ,

as announced. □

As special cases, since G^{0} = ℝ_{+} and G^{1} = ℝ_{+}^{2}, we may check that (G^{0})^{∗} = (ℝ_{+})^{∗} = ℝ_{+} and (G^{1})^{∗} = (ℝ_{+}^{2})^{∗} = ℝ_{+}^{2}, as expected. These two cones are thus self-dual, but it is easy to see that geometric cones of higher dimension are not self-dual any more. To illustrate our purpose, we provide in Figure 1 the three-dimensional graphs of the boundary surfaces of G^{2} and (G^{2})^{∗}.

Note 3.1 Since we have 0 ≤ w_{i}^{∗} ≤ 1 for all indices i, each logarithmic term appearing in this definition is nonpositive, as well as their sum, which means that (x^{∗}, θ^{∗}) ∈ (G^{n})^{∗} as soon as x^{∗} and θ^{∗} are nonnegative. This fact could have been guessed prior to any computation: noticing that G^{n} ⊆ ℝ_{+}^{n+1} and (ℝ_{+}^{n+1})^{∗} = ℝ_{+}^{n+1}, we immediately have that (G^{n})^{∗} ⊇ ℝ_{+}^{n+1}, because taking the dual of a set inclusion reverses its direction.

Finding the dual of G^{n} was a little involved, but establishing its properties is straightforward.

Theorem 3.6 (G^{n})^{∗} is a solid, pointed, closed convex cone. Moreover, ((G^{n})^{∗})^{∗} = G^{n}.

The proof of this fact is immediate by Theorem 2.2 since (G^{n})^{∗} is the dual of a solid, pointed, closed convex cone. □

The interior of (G^{n})^{∗} is also rather easy to obtain:

Theorem 3.7 The interior of (G^{n})^{∗} is given by

int(G^{n})^{∗} = \{(x^{∗}, θ^{∗}) ∈ ℝ_{++}^{n} × ℝ | θ^{∗} > ∑_{i=1}^{n} x_{i}^{∗} log \frac{x_{i}^{∗}}{∑_{i=1}^{n} x_{i}^{∗}} \} .

Proof . We first note that (G^{n})^{∗}, a convex set, is the epigraph of the following function

f_{n} : ℝ_{+}^{n} ↦ ℝ : x ↦ ∑_{i|x_{i}^{∗}>0} x_{i}^{∗} log \frac{x_{i}^{∗}}{∑_{i=1}^{n} x_{i}^{∗}} ,

which implies that f_{n} is convex (by definition of a convex function). Hence we can apply Lemma 7.3 in [7] to get

int(G^{n})^{∗} = int epi f_{n} = {(x^{∗}, θ^{∗}) ∈ int dom f_{n} × ℝ | θ^{∗} > f_{n}(x^{∗})} ,

which is exactly our claim since int ℝ_{+}^{n} = ℝ_{++}^{n}. □

The last piece of information we need about the pair of cones (G^{n}, (G^{n})^{∗}) is its set of orthogonality conditions.

Theorem 3.8 (orthogonality conditions) Let v = (x, θ) ∈ G^{n} and v^{∗} = (x^{∗}, θ^{∗}) ∈ (G^{n})^{∗}. We have v^{T} v^{∗} = 0 if and only if one of these two sets of conditions is satisfied

θ = 0 and x_{i}x_{i}^{∗} = 0 for all i
θ > 0 and \{ \begin{matrix}∑_{i|x_{i}^{∗}>0} x_{i}^{∗} log w_{i}^{∗} & = & θ^{∗} \\ (∑_{i=1}^{n} x_{i}^{∗})e^{− \frac{x_{i}}{θ}} & = & x_{i}^{∗} for all i \end{matrix} .

Proof . To prove this fact, we merely have to reread carefully the proof of Theorem 3.5, paying attention to the cases where the infimum is equal to zero. In the first case examined, θ = 0, we have v^{T} v^{∗} = x^{T} x^{∗}. Since x and x^{∗} are two nonnegative vectors, we have v^{T} v^{∗} = 0 if and only if x_{i}x_{i}^{∗} = 0 for every index i, which gives the first set of conditions of the theorem.

When θ > 0, we first have the special case x^{∗} = 0 which gives v^{T} v^{∗} = θθ^{∗}. This quantity can only be zero if θ^{∗} = 0, i.e. when (x^{∗}, θ^{∗}) = 0. When x^{∗} ≠ 0, the proof of Theorem 3.5 shows that v^{T} v^{∗} can only be zero when the infimum (3.4) is equal to zero and attained, which implies θ^{∗} = ∑_{i|x_{i}^{∗}>0} x_{i}^{∗} log w_{i}^{∗}. However, this infimum is not always attained by a finite vector (x, θ), because of the condition x_{i} → +∞ that is required when w_{i}^{∗} = 0. The scalar product v^{T} v^{∗} is thus equal to zero only if all w_{i}^{∗}’s are positive, i.e. when all x_{i}^{∗}’s are positive: in this case, the two sets of equalities θ^{∗} = ∑_{i|x_{i}^{∗}>0} x_{i}^{∗} log w_{i}^{∗} (to have a zero infimum) and e^{− \frac{x_{i}}{θ}} = w_{i}^{∗} (to attain the infimum) must be satisfied.

Rephrasing this last equality as (∑_{i=1}^{n} x_{i}^{∗})e^{− \frac{x_{i}}{θ}} = x_{i}^{∗} to take into account the special case (x^{∗}, θ^{∗}) = 0, we find the second set of conditions of our theorem. □

4 Duality for geometric optimization

In this section, we introduce a form of geometric optimization problems that is suitable to our purpose and prove several duality properties using the previously defined primal-dual pair of convex cones. These results are well-known and can be found e.g. in [2]. However, our presentation differs and handles problems expressed in a slightly different (but equivalent) format, and hence provides results adapted to the formulation we use. We refer the reader to Subsection 5.1 where the connection is made between our results and their classical counterparts.

4.1 Conic formulation

We start with the original formulation of a geometric optimization problem (see e.g. [2]). Let R = {0, 1, 2, …, r} and I = {1, 2, …, n}. Let {I_{k}}_{k∈R} a partition of I into r + 1 classes, i.e. satisfying

∪_{k∈R}I_{k} = I and I_{k} ∩ I_{l} = ∅ for all k ≠ l .

The primal geometric optimization problem is the following:

inf G_{0}(t) s.t. t ∈ ℝ_{++}^{m} and G_{k}(t) ≤ 1 for all k ∈ R \ {0} ,  (PG)

where t is the m-dimensional column vector we want to optimize and the functions G_{k} defining the objective and the constraints are so-called posynomials, given by

G_{k} : ℝ_{++}^{m} ↦ ℝ_{++} : t ↦ ∑_{i∈I_{k}} C_{i} ∏_{j=1}^{m} t_{j}^{a_{ij}} ,

where exponents a_{ij} are arbitrary real numbers and coefficients C_{i} are required to be strictly positive (hence the name posynomial). These functions are very well suited for the formulation of constraints that come from the laws of physics or economics (either directly or using an empirical fit).

Problem (PG) is not convex (take for example G_{0} : t ↦ t^{1/2}, which is not a convex function). However, it is well-known that it can be convexified with the following change of variables:

t_{j} = e^{y_{j}} for all j ∈ {1, 2, …, m} ,  (4.1)

to become

inf g_{0}(y) s.t. g_{k}(y) ≤ 1 for all k ∈ R \ {0} .  (TPG)

The functions g_{k} are defined to satisfy g_{k}(y) = G_{k}(t) when (4.1) holds, which means

g_{k} : ℝ^{m} ↦ ℝ_{++} : y ↦ ∑_{i∈I_{k}} C_{i} ∏_{j=1}^{m} (e^{y_{j}})^{a_{ij}} = ∑_{i∈I_{k}} e^{−c_{i}+∑_{j=1}^{m} y_{j}a_{ij}} = ∑_{i∈I_{k}} e^{a_{i}^{T} y−c_{i}} ,

where the coefficient vector c ∈ ℝ^{n} is given by c_{i} = − log C_{i} and a_{i} = (a_{i1}, a_{i2}, …, a_{im})^{T} is an m-dimensional column vector. Note that unlike the original variables t and coefficients C, variables y and coefficients c are not required to be strictly positive and can take any real value.

It is straightforward to check that functions g_{k} are now convex, hence that (TPG) is a convex optimization problem. However, we will not establish convexity directly but rather derive it from the fact that problem (TPG) can be cast as a conic optimization problem. Moreover, following others [4, 1], we will not use this formulation but instead work with a slight variation featuring a linear objective:

sup b^{T} y s.t. g_{k}(y) ≤ 1 for all k ∈ R ,  (LPG)

where b ∈ ℝ^{m} and 0 has been removed from set R.

It will be shown later that problems in the form (TPG) (and (PG)) can be expressed in this format, and the results we are going to obtain about problem (LPG) will be translated back to these more traditional settings later in Subsection 5.1.

Let us now model problem (LPG) with a conic formulation. In the rest of this article, we will use the following useful convention: v_{S} (resp. M_{S}) denotes the restriction of column vector v (resp. matrix M) to the components (resp. rows) whose indices belong to set S. We introduce a vector of auxiliary variables s ∈ ℝ^{n} to represent the exponents used in functions g_{k}, more precisely we let

s_{i} = c_{i} − a_{i}^{T} y for all i ∈ I or, in matrix form, s = c − A^{T} y ,

where A is a m × n matrix whose columns are a_{i}. Our problem becomes then

sup b^{T} y s.t. s = c − A^{T} y and ∑_{i∈I_{k}} e^{−s_{i}} ≤ 1 for all k ∈ R ,

which is readily seen to be equivalent to the following, using the definition of G^{n},

sup b^{T} y s.t. A^{T} y + s = c and (s_{I_{k}}, 1) ∈ G^{#I_{k}} for all k ∈ R ,

and finally to

sup b^{T} y s.t. (\begin{matrix}A^{T} \\ 0 \end{matrix} ) y + (\begin{matrix}s \\ v \end{matrix}) = (\begin{matrix}c \\ e \end{matrix}) and (s_{I_{k}}, v_{k}) ∈ G^{n_{k}} for all k ∈ R ,  (CPG)

where e is the all-one vector in ℝ^{r}, n_{k} = #I_{k} and an additional vector of fictitious variables v ∈ ℝ^{r} has been introduced, whose components are fixed to 1 by part of the linear constraints. This is exactly a conic optimization problem, in the dual form (CD), using variables (ỹ, s̃), data (Ã, b̃, c̃) and a cone K^{∗} such that

ỹ = y, s̃ = (\begin{matrix}s \\ v \end{matrix}) , Ã = (A 0) , b̃ = b, c̃ = (\begin{matrix}c \\ e \end{matrix}) and K^{∗} = G^{n_{1}} × G^{n_{2}} × ⋯ × G^{n_{r}} ,

where K^{∗} has been defined according to Note 2.1, since we have to deal with multiple conic constraints involving disjoint sets of variables.

Using properties of G^{n} and (G^{n})^{∗} proved in the previous section, it is straightforward to show that K^{∗} is a solid, pointed, closed convex cone whose dual is

(K^{∗})^{∗} = K = (G^{n_{1}})^{∗} × (G^{n_{2}})^{∗} × ⋯ × (G^{n_{r}})^{∗} ,

another solid, pointed, closed convex cone, according to Theorem 3.6. This allows us to derive a dual problem to (CPG) in a completely mechanical way and find the following conic optimization problem, expressed in the primal form (CP):

inf (c^{T} e^{T} ) (\begin{matrix}x \\ z \end{matrix}) s.t. (A 0) (\begin{matrix}x \\ z \end{matrix}) = b and (x_{I_{k}}, z_{k}) ∈ (G^{n_{k}})^{∗} for all k ∈ R , (CDG)

where x ∈ ℝ^{n} and z ∈ ℝ^{r} are the vectors we optimize. This problem can be simplified: making the conic constraints explicit, we find

inf c^{T} x + e^{T} z s.t. Ax = b, x_{I_{k}} ≥ 0 and z_{k} ≥ ∑_{i∈I_{k}|x_{i}>0} x_{i} log \frac{x_{i}}{∑_{i∈I_{k}} x_{i}} for all k ∈ R ,

which can be further reduced to

inf c^{T} x + ∑_{k∈R} ∑_{i∈I_{k}|x_{i}>0} x_{i} log \frac{x_{i}}{∑_{i∈I_{k}} x_{i}} s.t. Ax = b and x ≥ 0 .  (LDG)

Indeed, since each variable z_{k} is free except for the inequality coming from the associated conic constraint, these inequalities must be satisfied with equality at each optimum solution and variables z can therefore be removed from the formulation. As could be expected, the dual problem we have just found using conic duality and our primal-dual pair of cones (G^{n}, (G^{n})^{∗}) corresponds to the usual dual for problem (LPG) found in the literature [5, 1]. We will also show later in Subsection 5.1 that it also allows us to derive the dual problem in the traditional formulations (PG) and (TPG).

4.2 Duality theory

We are now about to apply the various duality theorems enumerated in the previous section to geometric optimization. Our strategy will be the following: in order to prove results about the pair (LPG)–(LDG), we are going to apply our theorems to the conic primal-dual pair (CPG)–(CDG) and use the equivalence that holds between (CPG) and (LPG) and between (CDG) and (LDG). We start with the weak duality theorem.

Theorem 4.1 (Weak duality) Let y a feasible solution for primal problem (LPG) and x a feasible solution for dual problem (LDG). We have

b^{T} y ≤ c^{T} x + ∑_{k∈R} ∑_{i∈I_{k}|x_{i}>0} x_{i} log \frac{x_{i}}{∑_{i∈I_{k}} x_{i}} ,  (4.2)

equality occurring if and only if

(∑_{i∈I_{k}} x_{i})e^{a_{i}^{T} y−c_{i}} = x_{i} for all i ∈ I_{k}, k ∈ R .

Proof (the original proof can be found in [8] or [4, §1]). On the one hand, we note that y can be easily converted to a feasible solution (y, s, v) for the conic problem (CPG), simply by choosing vectors s and v according to the linear constraints. On the other hand, x can also be converted to a feasible solution (x, z) for the conic problem (CDG), admitting the same objective value, by choosing

z_{k} = ∑_{i∈I_{k}|x_{i}>0} x_{i} log \frac{x_{i}}{∑_{i∈I_{k}} x_{i}} for all k ∈ R .  (4.3)

Applying now the weak duality theorem to the conic primal-dual pair (CPG)–(CDG) with feasible solutions (x, z) and (y, s, v), we find the announced inequality

b^{T} y ≤ c^{T} x + ∑_{k∈R} ∑_{i∈I_{k}|x_{i}>0} x_{i} log \frac{x_{i}}{∑_{i∈I_{k}} x_{i}} ,

equality occurring if and only if the orthogonality conditions given in Theorem 3.8 are satisfied for each conic constraint. Since θ corresponds here to v_{k}, which is always equal to 1 because of the linear constraints, we can rule out the first set of equalities (occurring where θ = 0) and keep only the second set of conditions. The first of these equalities being always satisfied because of our choice of z_{k}, we finally conclude that equality (4.2) can occur if and only if the following set of remaining equalities is satisfied, namely

(∑_{i∈I_{k}} x_{i})e^{− \frac{s_{i}}{v_{i}}} = x_{i} for all i ∈ I_{k}, k ∈ R ,

which is equivalent to our claim because of the linear constraints on s_{i} and v_{i}. □

The following theorem is an application of the strong duality theorem, and requires therefore the existence of a specific primal feasible solution.

Theorem 4.2 If there exists a feasible solution for the primal problem (LPG) satisfying strictly the inequality constraints, i.e. a vector y such that

g_{k}(y) < 1 for all k ∈ R

we have either

⋄ an infeasible dual problem (LDG) if primal problem (LPG) is unbounded

⋄ a feasible dual problem (LDG) whose optimum objective value is attained by a feasible vector x if primal problem (LPG) is bounded. Moreover, the optimum objective values of (LPG) and (LDG) are equal.

Proof (a more classical proof can be found in [4, §2]). Choosing again vectors s and v according to the linear constraints, we find a feasible solution (y, s, v) for the primal conic problem (CPG). Moreover, recalling the description of int G^{n} given by Theorem 3.3, the conditions v_{k} = 1 > 0 and g_{k}(y) = ∑_{i∈I_{k}} e^{−s_{i}} < 1 ensure that (y, s, v) is a strictly feasible solution for (CPG). Theorem 2.4 implies then that we have either ⋄ an infeasible dual problem (CDG) if primal problem (CPG) is unbounded: this is equiv-

alent to the first part of our claim, since it is clear that (CPG) is unbounded if and only if (LPG) is unbounded and that (CDG) is infeasible if and only if (LDG) is infeasible (indeed, (x, z) feasible for (CDG) implies x feasible for (LDG), while x feasible for (LDG) implies (x, 0) feasible for (CDG)). This fact could also have been obtained as a simple consequence of Theorem 4.1.

⋄ a feasible dual problem (CDG) whose optimum objective value is attained by a feasible vector (x, z) if primal problem (CPG) is bounded. Moreover, the optimum objective values of (CPG) and (CDG) are equal. Obviously, the finite optimum objective values of (CPG) and (LPG) are equal. It is also clear that optimal variables z_{k} in (CDG) must attain the lower bounds defined by the conic constraints, as in (4.3), which implies that vector x is optimum for problem (LDG) and has the same objective value as (x, z) in (CDG). This proves the second part of our claim.

□

Let us note again that a sufficient condition for the second case of this theorem to happen is the existence of a feasible solution for the dual problem (LDG), because of the weak duality property.

The strong duality theorem can also be applied on the dual side.

Theorem 4.3 If there exists is a strictly positive feasible solution for the dual problem (LDG), i.e. a vector x such that

Ax = b and x > 0 ,

we have either

⋄ an infeasible primal problem (LPG) if dual problem (LDG) is unbounded

⋄ a feasible primal problem (LPG) whose optimum objective value is attained by a feasible vector y if dual problem (LDG) is bounded. Moreover, the optimum objective values of (LDG) and (LPG) are equal.

Proof (a traditional proof can be found in [4, §5]). As for the previous theorem, the first part of our claim is a direct consequence of Theorem 4.1, that does not really rely on the existence of a strictly positive x. Let us prove the second part of our claim and suppose that problem (LDG) is bounded. Problem (CDG) cannot be unbounded, because each feasible solution (x, z) for (CDG) leads to a feasible x for (LDG) with a lower objective (because of the conic constraints), which would also lead to an unbounded (LDG). Using the description of int(G^{n})^{∗} given by Theorem 3.7, we find that a feasible x > 0 for (LDG) can be easily converted to a strictly feasible solution (x, z) for (CDG), taking sufficiently large values for variables z_{k} (letting z_{k} = 1 for example is enough). The strong duality theorem implies thus, since (CDG) has been shown to be bounded, that problem (CPG) is feasible with an optimum objective value attained by a feasible vector (y, s, v) and equal to the dual optimum objective value of (CDG). Obviously, on the one hand, vector y is a feasible optimum solution to problem (LPG), attaining the same objective value as (y, s, v) in (CDG). On the other hand, the finite optimum objective values of (CDG) and (LDG) must be equal, even if no feasible solution is actually optimum (since x feasible for (LDG) implies (x, z) feasible for (CDG) with the same objective value and (x, z) feasible for (CDG) implies x feasible for (LDG) with a smaller or equal objective value). This is enough to prove the second part of our claim. □

To conclude this section, we prove a last theorem that involves the alternate version of the strong duality theorem. Let us introduce the following family of optimization problems, parameterized by a strictly positive parameter δ:

p̂(δ) = sup b^{T} y s.t. g_{k}(y) ≤ e^{δ} for all k ∈ R .  (LPG_{δ})

It is clear that each of these problems is a (strict) relaxation of problem (LPG), because e^{δ} > 1 for δ > 0, hence we have p̂(δ) ≥ p^{∗} for all δ. Moreover, since the feasible region of these problems shrinks as δ tends to zero, p̂(δ) is a nondecreasing function of δ and we can always define the following limit

p̂ = lim_{δ→0^{+}} p̂(δ) ,

which we will call the subvalue of problem (LPG). We have the following theorem

Theorem 4.4 If there exists a feasible solution to the dual problem (LDG), the subvalue of the primal problem (LPG) is equal to the optimum objective value of the dual problem (LDG).

Proof . We are going to show in fact that the primal subvalue p̂ is equal to the subvalue p^{−} of the primal conic optimization problem (CPG). Using Theorem 2.5 on the primal-dual conic pair (CPG)–(CDG), we will find that p^{−} = d^{∗} (the first case of the theorem cannot happen since (LDG), and hence (CDG), is feasible by hypothesis). Noting finally that the optimum objective values of (CDG) and (LDG) are equal (which has been shown in the course of the previous proof) will conclude our proof.

Let us restate the definition of the subvalue p^{−} for problem (CPG). Defining the following family of problems, parameterized by a strictly positive parameter ϵ,

sup_{(y,s,v)} b^{T} y s.t. ∥(\begin{matrix}A^{T} \\ 0 \end{matrix} ) y + (\begin{matrix}s \\ v \end{matrix}) − (\begin{matrix}c \\ e \end{matrix})∥ < ϵ, (s_{I_{k}}, v_{k}) ∈ G^{n_{k}} ∀k ∈ R ,  (CPG_{ϵ})

whose optimum objective values will be denoted by p̄(ϵ), we have

p^{−} = lim_{ϵ→0^{+}} p̄(ϵ) .

We first show that for all δ > 0, the inequality p̂(δ) ≤ p̄(ϵ) holds for some well chosen value of ϵ. Let y a feasible solution for problem (LPG_{δ}). Using the definition of g_{k}, constraints g_{k}(y) ≤ e^{δ} easily give

∑_{i∈I_{k}} e^{a_{i}^{T} y−c_{i}−δ} ≤ 1 ,

which shows that the following choice of vectors s and v

s_{i} = c_{i} − a_{i}^{T} y + δ for all i ∈ I and v_{k} = 1 for all k ∈ R

will be feasible for problem (CPG_{ϵ}) with ϵ = δ\sqrt{n}, since we have then (s_{I_{k}}, v_{k}) ∈ G^{n_{k}}∀k ∈ R and

∥(\begin{matrix}A^{T} \\ 0 \end{matrix} ) y + (\begin{matrix}s \\ v \end{matrix}) − (\begin{matrix}c \\ e \end{matrix})∥ = ∥(\begin{matrix}δ \\ 0 \end{matrix})∥ = δ\sqrt{n} .

Since every feasible solution y for (LPG_{δ}) gives a feasible solution (y, s, v) for (CPG_{ϵ}) with the same objective value, the latter problem cannot have a smaller optimum objective value and we have p̂(δ) ≤ p̄(δ\sqrt{n}). Taking the limit when δ → 0, this shows that p̂ ≤ p^{−}.

Let us now work in the opposite direction and let (y, s, v) a feasible solution to problem (CPG_{ϵ}). We have thus

∑_{i∈I_{k}} e^{− \frac{s_{i}}{v_{k}}} ≤ 1 for all k ∈ R and ∥(\begin{matrix}A^{T} y + s − c \\ v − e \end{matrix})∥ < ϵ ,

which implies

\{ \begin{matrix}|a_{i}^{T} y + s_{i} − c_{i}| < ϵ for all i ∈ I \\ |v_{k} − 1| < ϵ for all k ∈ R \end{matrix} .

We write

1 ≥ ∑_{i∈I_{k}} e^{− \frac{s_{i}}{v_{i}}} > ∑_{i∈I_{k}} e^{− \frac{c_{i}−a^{T}_{i} y+ϵ}{1−ϵ}} ,

since v_{k} > 1 − ϵ, s_{i} < c_{i} − a_{i}^{T} y + ϵ and x ↦ e^{−x} is a monotonic decreasing function. Defining ỹ = \frac{y}{1−ϵ}, we have

\frac{c_{i} − a_{i}^{T} y + ϵ}{1 − ϵ} = c_{i} − a_{i}^{T} ỹ + \frac{c_{i} + ϵ}{1 − ϵ} − c_{i}
= c_{i} − a_{i}^{T} ỹ + \frac{ϵ}{1 − ϵ} (c_{i} + 1)
≤ c_{i} − a_{i}^{T} ỹ + \frac{ϵ}{1 − ϵ} (max c_{i} + 1)
≤ c_{i} − a_{i}^{T} ỹ + \frac{Cϵ}{1 − ϵ} ,

where C = max c_{i} + 1. We have thus

1 > ∑_{i∈I_{k}} e^{− \frac{c_{i}−a^{T}_{i} y+ϵ}{1−ϵ}} ≥ ∑_{i∈I_{k}} e^{a_{i}^{T} ỹ−c_{i}− \frac{Cϵ}{1−ϵ}} = e^{− \frac{Cϵ}{1−ϵ}} ∑_{i∈I_{k}} e^{a_{i}^{T} ỹ−c_{i}} ,

which shows that

∑_{i∈I_{k}} e^{a_{i}^{T} ỹ−c_{i}} < e^{\frac{Cϵ}{1−ϵ}} ,

i.e. ỹ is a feasible solution to problem (LPG_{δ}) with δ = \frac{Cϵ}{1−ϵ}. Since this solution has an objective value b^{T} ỹ equal to b^{T} y divided by 1 − ϵ, this means that p̄(ϵ) ≤ (1 − ϵ)p̂(\frac{Cϵ}{1−ϵ}). Taking the limit when ϵ → 0, this shows that p^{−} ≤ p̂, and we may conclude that p^{−} = p̂, as announced. □

4.3 Refined duality

The properties we have proved so far about our pair of primal-dual geometric optimization problems (LPG)–(LDG) are merely more or less direct consequences of their convex nature, hence valid for all convex optimization problems. In this section, we are going further and prove a result that does not hold in the general convex case, namely we show that our pair of primal-dual problems cannot have a strictly positive duality gap.

Theorem 4.5 If both problems (LPG) and (LDG) are feasible, their optimum objective values are equal (but not necessarily attained).

Proof (the original proof can be found in [4, §7]). In Theorem 4.3, we proved the existence of a zero duality gap using some assumption on the dual, namely the existence of a strictly positive feasible vector. What we are going to show here is that if such a point does not exist, i.e. one or more components of vector x are zero for all feasible dual solutions, our primal-dual pair can be reduced to an equivalent pair of problems where these components have been removed, in other words a primal-dual pair with a strictly positive feasible dual solution and a zero duality gap.

In order to use this strategy, we start by identifying the components of x that are identically equal to zero on the dual feasible region. This can be done with the following linear optimization problem:

min 0 s.t. Ax = b and x ≥ 0 .  (PLP)

Since this problem has a zero objective function, all feasible solutions are optimal and we deduce that if a variable x_{i} is zero for all feasible solutions to problem (LDG), it is zero for all optimal solution to problem (PLP). We are going to use the well-known Goldman-Tucker theorem [3].

Theorem 4.6 (Goldman-Tucker) Let us consider the following primal-dual pair of linear optimization problems:

min c^{T} x s.t. Ax = b and x ≥ 0 and max b^{T} y s.t. A^{T} y + s = c and s ≥ 0 .

If both problems are feasible, there exists a unique partition (B, N) of the index set common to vectors x and s such that

⋄ every optimal solution x^{∗} to the primal problem satisfies x_{N}^{∗} = 0.

⋄ every optimal solution (y^{∗}, s^{∗}) to the dual problem satisfies s_{B}^{∗} = 0.

This partition is called the optimal partition. Moreover, there exists at least an optimal primal-dual solution (x^{∗}, y^{∗}, s^{∗}) such that x^{∗} + s^{∗} > 0, hence satisfying x_{B}^{∗} > 0 and s_{N}^{∗} > 0. Such a pair is called a strictly complementary pair.

Writing the dual of problem (PLP)

max b^{T} y s.t. A^{T} y + s = 0 and s ≥ 0 ,  (DLP)

we find that both (PLP) and (DLP) are feasible (the former because (LDG) is feasible, the latter because (y, s) = (0, 0) is always a feasible solution), and thus that the Goldman-Tucker theorem is applicable.

Having now the optimal partition (B, N) at hand, we observe that the index set N defines exactly the set of variables x_{i} that are identically zero on the feasible region of problem (LDG). We are now able to introduce a reduced primal-dual pair of geometric optimization problems, where variables x_{i} with i ∈ N have been removed. We start with the dual problem

inf c_{B}^{T}x_{B} + ∑_{k∈R} ∑_{i∈I_{k}∩B|x_{i}>0} x_{i} log \frac{x_{i}}{∑_{i∈I_{k}∩B} x_{i}} s.t. A_{B}x_{B} = b and x_{B} ≥ 0 .  (RDG)

It is straightforward to check that this problem is completely equivalent to problem (LDG), since the variables we removed had no contribution to the objective or to the constraints in (LDG). Indeed, there is a one-to-one correspondence preserving objective values between feasible solutions x_{B} for (RDG) and feasible solutions x for (LDG), the latter satisfying always x_{N} = 0. Our primal geometric optimization problem becomes

sup b^{T} y s.t. g_{k}^{B}(y) ≤ 1 for all k ∈ R ,  (RPG)

where functions g_{k}^{B} are now defined over the sets I_{k} ∩ B, i.e.

g_{k}^{B} : ℝ^{m} ↦ ℝ_{++} : y ↦ ∑_{i∈I_{k}∩B} e^{a_{i}^{T} y−c_{i}} .

Since the Goldman-Tucker theorem implies the existence of a feasible vector x^{∗} such that x_{B}^{∗} > 0 and x_{N}^{∗} = 0, we find that x_{B}^{∗} is a strictly positive feasible solution to (RDG), which allows us to apply Theorem 4.3. Knowing that (LPG) is feasible, problems (LDG) and (RDG) must be bounded: we are in the second case of the theorem and can conclude that problem (RPG) attains an optimum objective value equal to the optimum objective value of problem (RDG). The last thing we have to show in order to finish our proof is that the optimum values of primal problem (LPG) and its reduced version (RPG) are equal.

Let us start with ȳ, one of the optimal solutions to (RPG) that are known to exist. Our goal is thus to prove that problem (LPG) has an optimum objective value equal to b^{T} ȳ. Unfortunately, ȳ is not always feasible for problem (LPG), since the additional terms in g_{k} corresponding to indices i ∈ N result in g_{k}(ȳ) > g_{k}^{B}(ȳ) and possibly g_{k}(ȳ) > 1.

To solve this problem, we are going to perturb ȳ with a suitably chosen vector, in order to make it feasible. The existence of this perturbation vector will be again derived from the Goldman-Tucker theorem, in the following manner. Let (x^{∗}, y^{∗}, s^{∗}) a strictly complementary pair for problems (PLP)–(DLP). Since the optimum primal objective value is obviously equal to zero, we also have that the optimum dual objective b^{T} y^{∗} is equal to zero. Moreover, we have that A^{T} y^{∗} + s^{∗} = 0, which gives

A_{B}^{T}y^{∗} = −s_{B}^{∗} = 0 and A_{N}^{T} y^{∗} = −s_{N}^{∗} < 0 .

Considering a vector y defined by y = ȳ + λy^{∗}, where λ is a positive parameter that is going to tend to +∞, it is easy to check that

g_{k}(y) = g_{k}^{B}(y) + g_{k}^{N} (y)
= ∑_{i∈I_{k}∩B} e^{a_{i}^{T} y−c_{i}} + ∑_{i∈I_{k}∩N} e^{a_{i}^{T} y−c_{i}}
= ∑_{i∈I_{k}∩B} e^{a_{i}^{T} ȳ+λa_{i}^{T} y^{∗}−c_{i}} + ∑_{i∈I_{k}∩N} e^{a_{i}^{T} ȳ+λa_{i}^{T} y^{∗}−c_{i}}
= ∑_{i∈I_{k}∩B} e^{a_{i}^{T} ȳ−c_{i}} + ∑_{i∈I_{k}∩N} e^{a_{i}^{T} ȳ−c_{i}−λs_{i}^{∗}}
= g_{k}^{B}(ȳ) + ∑_{i∈I_{k}∩N} e^{a_{i}^{T} ȳ−c_{i}−λs_{i}^{∗}} ,

which means that

lim_{λ→+∞} g_{k}(y) = g_{k}^{B}(ȳ) ≤ 1 for all k ∈ R ,

since s_{i}^{∗} > 0 for all i ∈ N implies that all the exponents in the second sum are tending to −∞. Moreover, the objective value b^{T} y is equal to b^{T} ȳ+λb^{T} y^{∗} = b^{T} ȳ for all values of λ, since b^{T} y^{∗} = 0. However, this vector y is not necessarily feasible for problem (LPG) (we may have g_{k}^{B}(ȳ) = 1 for some k and thus g_{k}(y) > 1 for all λ), and cannot therefore help us in proving that its optimum objective value is equal to b^{T} ȳ. We have to use a second trick, namely to ”mix” y with a feasible solution to make it feasible.

Let y^{0} a feasible solution to problem (LPG). We know thus that

g_{k}(y^{0}) = g_{k}^{B}(y^{0}) + g_{k}^{N} (y^{0}) ≤ 1 ,

which implies

g_{k}^{B}(y^{0}) < 1

since g_{k}^{N} (y^{0}) is strictly positive. Considering now the vector y = δy^{0} + (1 − δ)ȳ + λy^{∗}, we may write

g_{k}(y) = g_{k}^{B}(y) + g_{k}^{N} (y)
= g_{k}^{B}(δy^{0} + (1 − δ)ȳ + λy^{∗}) + g_{k}^{N} (δy^{0} + (1 − δ)ȳ + λy^{∗})
= g_{k}^{B}(δy^{0} + (1 − δ)ȳ) + g_{k}^{N} (δy^{0} + (1 − δ)ȳ + λy^{∗}) ,

this last line using again the fact that A_{B}^{T}y^{∗} = 0. We have thus

lim_{λ→+∞} g_{k}(y) = g_{k}^{B}(δy^{0} + (1 − δ)ȳ)

for the same reasons as above (exponents in g_{k}^{N} tending to −∞). Since we know that functions g_{k} are convex, we have that

g_{k}^{B}(δy^{0} + (1 − δ)ȳ) ≤ δg_{k}^{B}(y^{0}) + (1 − δ)g_{k}^{B}(ȳ) < δ + (1 − δ) = 1 ,

which finally implies

lim_{λ→+∞} g_{k}(y) < 1 .

Taking now a sufficiently large value of λ, we can ensure that g_{k}(y) < 1 for all k, i.e. that y is feasible for problem (LPG). The objective value associated to such a solution is equal to

b^{T} y = δb^{T} y^{0} + (1 − δ)b^{T} ȳ + λb^{T} y^{∗} = δb^{T} y^{0} + (1 − δ)b^{T} ȳ .

Letting finally δ tend to zero, we obtain a sequence of solutions y, feasible for problem (LPG), whose objective values converge to b^{T} ȳ, the optimum objective value of the reduced problem (RPG), itself equal to the optimum objective value of the dual problem (LDG). This is enough to prove that the primal-dual pair of problems (LPG)–(LDG) has a zero duality gap. □

We also have the following corollary about the subvalue p^{−} of problem (LPG).

Corollary 4.1 When both problems (LPG) and (LDG) are feasible, the optimum objective value of problem (LPG) is equal to its subvalue.

Proof . Indeed, we have in general p^{∗} ≤ p^{−} ≤ d^{∗}. Since the last theorem implies p^{∗} = d^{∗}, we obtain p^{∗} = p^{−}. □

4.4 Summary and examples

Let us summarize the possible situations about the primal problem (LPG), and give corresponding examples to show that the results obtained so far cannot be sharpened.

⋄ In the best possible situation, the dual problem has a strictly positive solution and is bounded: our primal problem is guaranteed by Theorem 4.3 to be feasible and have at least one finite optimal solution with a zero duality gap. Taking for example

A = (\begin{matrix}1 & 0 \\ 0 & 1 \end{matrix}) , b = (\begin{matrix}1 \\ 1 \end{matrix}) , c = (\begin{matrix}0 \\ 0 \end{matrix}) and I_{1} = \{1, 2\} ,

our primal-dual pair (CPG)–(CDG) becomes

sup y_{1} + y_{2} s.t. e^{y_{1}} + e^{y_{2}} ≤ 1
inf 0 + x_{1} log \frac{x_{1}}{x_{1} + x_{2}} + x_{2} log \frac{x_{2}}{x_{1} + x_{2}}  s.t. x_{1} = 1, x_{2} = 1 and x ≥ 0 .

The only feasible dual solution is strictly positive, giving a bounded optimum objective value d^{∗} = 2 log \frac{1}{2} = −2 log 2, and we may easily check (using Lemma 3.1) that y_{1} = y_{2} = − log 2 is the only optimum primal solution, giving also p^{∗} = −2 log 2.

⋄ In the case of an unbounded dual, the primal problem has to be infeasible because of the weak duality theorem. Choosing

A = (0 1) , b = 1, c = (\begin{matrix}−1 \\ 0 \end{matrix}) and I_{1} = \{1, 2\} ,

our primal-dual pair becomes

sup y_{1} s.t. e^{1} + e^{y_{1}} ≤ 1
inf −x_{1} + x_{1} log \frac{x_{1}}{x_{1} + x_{2}} + x_{2} log \frac{x_{2}}{x_{1} + x_{2}}  s.t. x_{2} = 1 and x ≥ 0 .

The dual is unbounded: the feasible solution x = (λ, 1) for all λ > 0 has an objective value equal to −λ+λ log \frac{λ}{λ+1} +log \frac{1}{λ+1}, which is easily shown to tend to (−∞−1−∞) = −∞ when λ → +∞. The primal problem is obviously infeasible, as expected.

⋄ When both the primal and the dual problems are feasible but the dual does not have a strictly feasible solution, the duality gap is guaranteed by Theorem 4.5 to be equal to zero with a finite common optimal objective value, but not necessarily with attainment. Adding a third variable to our previous examples

A = (\begin{matrix}1 & 0 & 0 \\ 0 & 1 & 1 \\ 0 & 0 & 2 \end{matrix}) , b = (\begin{matrix}1 \\ 1 \\ 0 \end{matrix}) , c = (\begin{matrix}0 \\ 0 \\ 1 \end{matrix}) and I_{1} = \{1, 2, 3\} ,

our primal-dual pair becomes

sup y_{1} + y_{2} s.t. e^{y_{1}} + e^{y_{2}} + e^{y_{2}+2y_{3}−1} ≤ 1
inf x_{3} + ∑_{i|x_{i}>0} x_{i} log \frac{x_{i}}{∑_{i=1}^{3} x_{i}}  s.t. x_{1} = 1, x_{2} + x_{3} = 1, 2x_{3} = 0 and x ≥ 0 .

The only feasible dual solution x = (1, 1, 0) has a zero component and gives d^{∗} = −2 log 2. It is not too difficult to find a sequence of primal feasible solutions tending to y = (− log 2, − log 2, −∞) that establishes that the supremum of the primal problem is also equal to p^{∗} = −2 log 2. However, this value cannot be attained: the primal constraint implies e^{y_{1}} + e^{y_{2}} < 1, which in turn can be shown to force y_{1} + y_{2} < −2 log 2 using Lemma 3.1.

⋄ Our last example will demonstrate the worst situation that can happen: a feasible bounded dual problem with an infeasible primal problem. Taking

A = (\begin{matrix}1 & 0 & −1 \\ 0 & 1 & 0 \end{matrix}) , b = (\begin{matrix}1 \\ 0 \end{matrix}) , c = (\begin{matrix}1 \\ 0 \\ −1 \end{matrix}) and I_{1} = \{1, 2\} , I_{2} = \{3\} ,

our primal-dual pair becomes (after some simplifications in the dual objective)

sup y_{1} s.t. e^{y_{1}−1} + e^{y_{2}} ≤ 1 and e^{1−y_{1}} ≤ 1
inf x_{1} − x_{3} + x_{1} log \frac{x_{1}}{x_{1} + x_{2}}  s.t. x_{1} − x_{3} = 1, x_{2} = 0 and x ≥ 0 .

All the feasible dual solution have at least one zero component and it is not difficult to compute that d^{∗} = 1 (when x = (1, 0, 0), for example). It is also easy to check that the primal problem is infeasible: the first constraint implies e^{y_{1}−1} < 1 and thus y_{1} < 1, while the second constraint forces y_{1} ≥ 1. However, Theorem 4.4 tells us that the primal problem has a subvalue p^{−} equal to d^{∗}. Indeed, relaxing the primal problem to

sup y_{1} s.t. e^{y_{1}−1} + e^{y_{2}} ≤ e^{δ} and e^{1−y_{1}} ≤ e^{δ}

for any δ > 0, we find y_{1} < 1 + δ and y_{1} ≥ 1 − δ, implying 1 − δ ≤ p̄(δ) < 1 + δ and leading to a subvalue p^{−} equal to 1, as expected.

5 Concluding remarks

5.1 Original formulation

In Subsection 4.1, we presented a conic formulation for the primal-dual pair of geometric optimization problems (LPG)–(LDG) involving linear objective functions, which allowed us to derive several duality theorems. However, the traditional formulation of geometric optimization usually involves a posynomial objective function, as in (PG) or in (TPG), its convexified variant. In this subsection, we show that such problems can be cast as problems with a linear objective, and outline how these duality results can be translated into this traditional formulation.

Let us restate for convenience the convexified problem (TPG)

inf g_{0}(y) s.t. g_{k}(y) ≤ 1 for all k ∈ R \ {0} ,  (TPG)

which is readily seen to be equivalent to

inf e^{−y_{0}} s.t. g_{0}(y) ≤ e^{−y_{0}} and g_{k}(y) ≤ 1 for all k ∈ R \ {0} ,

introducing a new variable y_{0} to express the posynomial objective. Noticing that minimizing e^{−y_{0}} amounts to maximizing y_{0}, we can rewrite this last problem as

sup y_{0} s.t. e^{y_{0}}g_{0}(y) ≤ 1 and g_{k}(y) ≤ 1 for all k ∈ R \ {0} ,

which can now be expressed in the format of (LPG) as

sup b̃^{T} ỹ s.t. g̃_{k}(ỹ) ≤ 1 for all k ∈ R ,

where vector of variables ỹ ∈ ℝ^{m+1}, objective vector b̃ ∈ ℝ^{m+1} and posynomials g̃_{k} are defined by

ỹ = (\begin{matrix}y_{0} \\ y \end{matrix}) , b̃ = (\begin{matrix}1 \\ 0 \end{matrix}) , g̃_{0}(ỹ) = e^{y_{0}}g_{0}(y) and g̃_{k}(ỹ) = g_{k}(y) for all k ∈ R \ \{0\} .

This last definition of posynomials g̃_{k} corresponds to the following choice of column vectors ã_{i} (constants c_{i} are left unchanged):

ã_{i} = (\begin{matrix}1 \\ a_{i} \end{matrix}) for all i ∈ I_{0} and ã_{i} = (\begin{matrix}0 \\ a_{i} \end{matrix}) for all i ∈ I \ I_{0} .

It is now easy to find a dual for problem (TPG), based on the known dual for (LPG) and our special choice of ã_{i} and b̃. Defining a matrix Ã whose columns are the a_{i}’s, i.e.

Ã = \binom{1, …, 1 0, …, 0}{A} ,^{^{I_{0}} ^{I_{k} ∀k≠0}}

we find the dual problem

inf c^{T} x + ∑_{k∈R} ∑_{i∈I_{k}|x_{i}>0} x_{i} log \frac{x_{i}}{∑_{i∈I_{k}} x_{i}} s.t. Ãx = b̃ and x ≥ 0

or, equivalently,

inf c^{T} x + ∑_{k∈R} ∑_{i∈I_{k}|x_{i}>0} x_{i} log \frac{x_{i}}{∑_{i∈I_{k}} x_{i}} s.t. Ax = 0 , ∑_{i∈I_{0}} x_{i} = 1 and x ≥ 0 .

We can manipulate further the second part of the objective function

∑_{k∈R} ∑_{i∈I_{k}|x_{i}>0} x_{i} log \frac{x_{i}}{∑_{i∈I_{k}} x_{i}} = ∑_{k∈R} ∑_{i∈I_{k}|x_{i}>0}(x_{i} log x_{i} − x_{i} log ∑_{i∈I_{k}} x_{i})
= ∑_{i∈I} x_{i} log x_{i} − ∑_{k∈R}(∑_{i∈I_{k}} x_{i}) log(∑_{i∈I_{k}} x_{i}) ,

with the convention that 0 log 0 = 0, and find

inf c^{T} x + ∑_{i∈I} x_{i} log x_{i} − ∑_{k∈R\{0}}(∑_{i∈I_{k}} x_{i}) log(∑_{i∈I_{k}} x_{i}) s.t. Ax = 0 , ∑_{i∈I_{0}} x_{i} = 1 and x ≥ 0

(we could remove the term for k = 0 in the second sum because of the linear constraint ∑_{i∈I_{0}} x_{i} = 1). Noting finally that the objective of (TPG) is actually e^{−y_{0}} and not y_{0}, we find after some easy transformations the final dual problem (using c_{i} = − log C_{i})

sup ∏_{i∈I} (\frac{C_{i}}{x_{i}} )^{x_{i}} ∏_{k∈R\\{0\}}(∑_{i∈I_{k}} x_{i})^{∑_{i∈I_{k}} x_{i}} s.t. Ax = 0 , ∑_{i∈I_{0}} x_{i} = 1 and x ≥ 0 . (TDG)

This dual problem is identical to the usual formulation that can be found in the literature [2, Chapter III]. To close this discussion, we give a few hints on how to establish links between the classical theory elaborated in [2] and the results presented in Subsections 4.2 and 4.3.

The main lemma in [2, Chapter IV] is essentially our weak duality theorem with its associated set of orthogonality conditions. The first and second duality theorems from [2, Chapter III] are basically coming from Theorems 4.2 and 4.3, i.e. the application of the strong duality theorem to the primal and the dual problems (note that the hypotheses of the first duality theorem suppose primal attainment while our version only requires primal boundedness, which is a weaker condition). We also note that the notion of subinfimum in [2, Chapter VI] for the primal problem is equivalent to our concept of subvalue. Finally, the strong duality theorems in [2, Chapter VI] are closely related to our Theorem 4.5, stating that a nonzero duality gap cannot occur ; the notion of canonical problem that is heavily used in the associated proofs corresponds to the case N = ∅ in the optimal partition of problem (PLP), i.e. existence of a strictly feasible dual solution.

5.2 Conclusion

In this article, we have shown how to use the duality theory of conic optimization to derive results about geometric optimization. This process involved the introduction of a dedicated pair of convex cones G^{n} and (G^{n})^{∗}. We would like to point out that conic optimization had so far been mostly applied to self-dual cones, i.e. to linear, second-order cone and semidefinite optimization. We hope to have demonstrated here that this theory can be equally useful in the case of a less symmetric duality.

The results we obtained can be classified into two distinct categories: most of them are direct consequences of the convex nature of geometric optimization (weak and strong duality theorems), while some of them are specific to this class of problems (absence of a duality gap). The set of problems we studied differed in fact slightly from the classical formulation of geometric optimization, because of the linear objective function.

We would like to point out that this variation in the formulation was necessary since conic optimization cannot be applied directly to geometric optimization problems cast in the traditional form. Indeed, problem (PG) is not convex, which already prevents us from applying Lagrange duality, while the pair of problems (TPG)–(TDG) does not feature a linear objectives and hence is not suitable for a conic formulation. However, extension of our results to the case of a posynomial objective function is straightforward, as outlined in Subsection 5.1. We also consider the results associated to our formulation more natural than their traditional counterparts (looking for example at the structure of the linear constraints in the dual problem (LDG), which does feature the normalizing constraints present in (TDG)).

The proofs presented in this article possess in our opinion several advantages over the classical ones: in addition to being shorter, they allow us to confine the specificity of the class of problems under study to the convex cones used in the formulation. Moreover, the reason why geometric optimization has better duality properties than a general conic problem becomes clear: this is essentially due to the existence of a strictly feasible dual solution. Indeed, even if such an interior solution does not always exist, a regularization procedure involving an equivalent reduced problem can always be carried out and allows us to prove the absence of a duality gap in all cases (we note however that the property of primal attainment, satisfied when there exists a strictly feasible dual solution, is lost in this process and is thus no longer valid in the general case).

A last advantage of our conic formulation is that it allows us to benefit with minimal work from the theory of polynomial interior-point methods for convex optimization developed in [6]. Indeed, finding a computable self-concordant barrier for our geometric cone G^{n}, a topic we leave for further research, is all what is needed to build an algorithm able to solve a geometric optimization problem up to a given accuracy within a polynomial number of arithmetic operations.

Acknowledgements. The author wishes to thank Professor Tamás Terlaky for the discussions they had on this topic and for providing reference [5]. He would also like to thank Professor Kees Roos and the SSOR department at the Delft University of Technology for their kind hospitality and an anonymous referee for providing reference [11].

References

[1] D. den Hertog, F. Jarre, C. Roos, and T. Terlaky, A sufficient condition for selfconcordance, with application to some classes of structured convex programming problems, Mathematical Programming 69 (1995), 75–88.

[2] R. J. Duffin, E. L. Peterson, and C. Zener, Geometric programming, John Wiley & Sons, New York, 1967.

[3] A. J. Goldman and A. W. Tucker, Theory of linear programming, Linear Equalities and Related Systems (H. W. Kuhn and A. W. Tucker, eds.), Annals of Mathematical Studies, vol. 38, Princeton University Press, Princeton, New Jersey, 1956, pp. 53–97.

[4] E. Klafszky, Geometric programming and some applications, Ph.D. thesis, Tanulmányok, No. 8, 1974.

[5] , Geometric programming, Seminar Notes, no. 11.976, Hungarian Committee for Systems Analysis, Budapest, 1976.

[6] Y. E. Nesterov and A. S. Nemirovsky, Interior-point polynomial methods in convex programming, SIAM Studies in Applied Mathematics, SIAM Publications, Philadelphia, 1994.

[7] R. T. Rockafellar, Convex analysis, Princeton University Press, Princeton, N. J., 1970.

[8] , Some convex programs whose duals are linearly constrained, Non-linear Programming (J. B. Rosen, ed.), Academic Press, 1970.

[9] J. Stoer and Ch. Witzgall, Convexity and optimization in finite dimensions I, Springer Verlag, Berlin, 1970.

[10] J. F. Sturm, Primal-dual interior-point approach to semidefinite programming, Ph.D. thesis, Erasmus Universiteit Rotterdam, The Netherlands, 1997, published in [11].

[11] , Duality results, High Performance Optimization (H. Frenk, C. Roos, T. Terlaky, and S. Zhang, eds.), Kluwer Academic Publishers, 2000, pp. 21–60.