An extended conic formulation for geometric optimization

Image Technical Report 0006

François Glineur^{∗}

Service de Mathématique et de Recherche Opérationnelle,

Faculté Polytechnique de Mons, Rue de Houdain, 9, B-7000 Mons, Belgium,

 Francois.Glineur@fpms.ac.be.

May 2000

∗The author is supported by a grant from the F.N.R.S. (Belgian National Fund for Scientific Research).

Abstract

The author has recently proposed a new way of formulating two classical classes of structured convex problems, geometric and l_{p}-norm optimization^{1}, using dedicated convex cones [Gli99, GT00]. This approach has some advantages over the traditional formulation: it simplifies the proofs of the well-known associated duality properties (i.e. weak and strong duality) and the design of a polynomial algorithm becomes straightforward. These new proofs rely on the general duality theory valid for convex problems expressed in conic form [SW70, Stu00] and the work on polynomial interior-point methods by Nesterov and Nemirovsky [NN94].

In this paper, we make a step towards the description of a common framework that would include these two classes of problems. Indeed, we introduce an extended variant of the cone for geometric optimization used in [Gli99] and show it is equally suitable to formulate this class of problems. This new cone has the additional advantage of being very similar to the cone used for l_{p}-norm optimization, which opens the way to a common generalization.

Keywords. geometric optimization, conic optimization, duality theory.

Contents

1 Introduction 3 1.1 Geometric optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2 Conic optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.3 Aim of the paper . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

2 The geometric cone 6 2.1 The dual geometric cone (G)^{∗} . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

3 A conic formulation 10 3.1 Modelling geometric optimization . . . . . . . . . . . . . . . . . . . . . . . . . 10 3.2 Deriving the dual . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

4 Concluding remarks 12

1These classes of problems are usually known for historical reasons under the names of geometric and l_{p}- norm programming. However, because of the strong connection of the term ”programming” with computer science, we prefer to use the more natural word ”optimization”.

1 Introduction

1.1 Geometric optimization

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. They can be expressed as follows: let R = {0, 1, 2, …, r} and I = {1, 2, …, n} and 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, defined 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).

Although not convex itself (choose for example G_{0} : t ↦ t^{1/2} as the objective, which is not a convex function), a geometric optimization problem can be easily transformed into a convex problem, for which a Lagrangean dual can be explicitly written. This transformation uses the following change of variables:

t_{j} = e^{y_{j}} for all j ∈ {1, 2, …, m} ,  (1.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 (1.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 this property here but rather derive it from the fact that problem (TPG) can be cast as a conic optimization problem (see Subsection 3.1). Moreover, following others [Kla74, RT98], 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. Problems in the form (TPG) (and (PG)) can be easily expressed in this format [Gli99, Section 5.1] and all the results we are going to obtain about problem (LPG) can be easily translated back to these more traditional settings, so that we can concentrate our attention on formulation (LPG) without any loss of generality.

The dual problem for (LPG) can be written as follows

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

where x ∈ ℝ_{+}^{n} is the vector of nonnegative dual variables we have to optimize.

Several duality results are known for the primal-dual pair (LPG)–(LDG), 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 late sixties, and can be found for example in the book of Duffin, Peterson and Zener [RJDZ67].

1.2 Conic optimization

Conic optimization^{2} 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 has the advantage of providing a very symmetric form for the dual problem and often gives a new insight about its structure.

The basic ingredient of conic optimization is a convex cone. Recall that a set C is a cone if and only if it is closed under nonnegative scalar multiplication, i.e. if x ∈ C ⇒ λx ∈ C for all λ ∈ ℝ_{+}. Moreover, a set is convex if and only if it contains the whole segment joining any two of its points. However, when dealing with cones, this assumption is equivalent to closedness under addition, i.e. cone C is convex if x ∈ C and y ∈ C ⇒ x + y ∈ C.

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 additional definitions:

Definition 1.1 A cone C is solid if and only if int C ≠ ∅ (where int S denotes the interior of set S).

Definition 1.2 A cone C is pointed if and only if C ∩ −C = {0}.

These two properties basically mean that C 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 C ⊆ ℝ^{n} a pointed, solid, closed convex cone. The (primal) conic optimization problem is defined as

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

where x ∈ ℝ^{n} is the column vector we are optimizing and the problem data is given by cone C, a m × n matrix A and two column vectors b and c 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.

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

2Proofs for the theorems stated in this subsection can be found e.g. in [SW70, Stu00].

Definition 1.3 The dual of a cone C ⊆ ℝ^{n} is defined by

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

The following theorem stipulates that the dual of a cone is always a closed convex cone.

Theorem 1.1 If C is a closed convex cone, its dual C^{∗} is another closed convex cone. Moreover, the dual (C^{∗})^{∗} of C^{∗} is equal to C.

Closedness is essential for (C^{∗})^{∗} = C to hold (without the closedness assumption on C, we only have (C^{∗})^{∗} = cl C where cl S denotes the closure of set S). The additional notions of solidness and pointedness also behave well when taking the dual of a convex cone (indeed, these two properties are dual to each other).

Theorem 1.2 If C is a solid, pointed, closed convex cone, its dual C^{∗} is another solid, pointed, closed convex cone.

The dual of our primal conic problem (CP) can be stated as

sup_{(y,s)} b^{T} y s.t. A^{T} y + s = c and s ∈ C^{∗} ,  (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 a translation of the range space of A^{T}, while primal involved a translation of the null space of A). It is also possible to show that the dual of this dual problem is equivalent to the primal problem, using the fact that (C^{∗})^{∗} = C.

The two conic problems of this primal-dual pair are strongly related to each other, as demonstrated by several duality theorems. In order to keep this presentation short, we only cite the most basic of these theorems, called the weak duality property:

Theorem 1.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.

1.3 Aim of the paper

In [Gli99], the author starts by defining an appropriate convex cone that allows him to express geometric optimization problems as conic programs, his aim being to apply the general duality theory for conic optimization [SW70, Stu00] to these problems and prove in a seamless way the various well-known duality theorems of geometric optimization. The goal of this paper is to introduce a variation of this convex cone that keeps its ability to model geometric optimization problems but bears more resemblance with the cone that was introduced for l_{p}-norm optimization [GT00], hinting for a common generalization of these two families of cones.

This paper is organized as follows: following this brief introduction to geometric and conic optimization, Section 2 introduces the convex cones needed to model geometric optimization and studies some of their properties. Section 3 constitutes the main part of this article and demonstrates how the above-mentioned cones enable us to model primal and dual geometric optimization problems in a seamless fashion. Modelling the primal problem with our first cone is rather straightforward and writing down its dual is immediate, but some work is needed to prove the equivalence with the traditional formulation of a dual geometric optimization problem. Finally, concluding remarks in Section 4 provide some insight about the relevance of our approach and hint at some possible ways to make use of it.

2 The geometric cone

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

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

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

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} and κ ∈ ℝ_{+}. As a special case, we mention that G^{0} is the 2-dimensional nonnegative orthant ℝ_{+}^{2}.

In order to use the conic formulation described in the previous section, we first prove that G^{n} is a convex cone.

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

Proof. Let us first introduce the following function

f_{n} : ℝ_{+}^{n} × ℝ_{+} ↦ ℝ_{+} : (x, θ) ↦ ∑_{i=1}^{n} θe^{− \frac{x_{i}}{θ}} .

With the convention mentioned above, its effective domain is ℝ_{+}^{n+1}. It is straightforward to check that f_{n} is positively homogeneous, i.e. f_{n}(λx, λθ) = λf_{n}(x, θ) for λ ≥ 0. Moreover, f_{n} is subadditive, i.e. f_{n}(x + x′, θ + θ′) ≤ f_{n}(x, θ) + f_{n}(x′, θ′). In order to show this property, we can work on each term of the sum separately, which means that we only need to prove the following inequality for all x, x′ ∈ ℝ and θ, θ′ ∈ ℝ_{+}:

θe^{− \frac{x}{θ}} + θ′e^{− \frac{x′}{θ′}} ≥ (θ + θ′)e^{− \frac{x+x′}{θ+θ′}} .

First observe that this inequality holds when θ = 0 or θ′ = 0. For example, when θ = 0, we have to check that θ′e^{− \frac{x′}{θ′}} ≥ θ′e^{− \frac{x+x′}{θ′}}, which is a consequence of the fact that x ↦ e^{−x} is a decreasing function. When θ + θ′ > 0, let us recall the well-known fact that x ↦ e^{−x} is a convex function on ℝ_{+}, implying that λe^{−a} + λ′e^{−a′} ≥ e^{−(λa+λa′)} for any nonnegative a, a′, λ and λ′ satisfying λ + λ′ = 1. Choosing a = \frac{x}{θ}, a′ = \frac{x′}{θ′}, λ = \frac{θ}{θ+θ′} and λ′ = \frac{θ′}{θ+θ′}, we find that

\frac{θ}{θ+θ′} e^{− \frac{x}{θ}} + \frac{θ′}{θ+θ′} e^{− \frac{x′}{θ′}} ≥ e^{− \frac{θ}{θ+θ′} \frac{x}{θ} − \frac{θ′}{θ+θ′} \frac{x′}{θ′}} ,

which, after multiplying by (θ + θ′), lead to the desired inequality

θe^{− \frac{x}{θ}} + θ′e^{− \frac{x′}{θ′}} ≥ (θ + θ′)e^{− \frac{x+x′}{θ+θ′}} .

Positive homogeneity and subadditivity imply that f_{n} is a convex function. Since f_{n}(x, θ) ≥ 0 for all x ∈ ℝ_{+}^{n} and θ ∈ ℝ_{+}, we notice that G^{n} is the epigraph of f_{n}, i.e.

epi f_{n} = {(x, θ, κ) ∈ ℝ_{+}^{n} × ℝ_{+} × ℝ | f_{n}(x, θ) ≤ κ} = G^{n} .

G^{n} is thus the epigraph of a convex positively homogeneous function, hence a convex cone [Roc70]. □

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

Theorem 2.2 G is closed.

Proof. Let {(x^{k}, θ^{k}, κ^{k})} a sequence of points in ℝ_{+}^{n+2} such that (x^{k}, θ^{k}, κ^{k}) ∈ G^{n} for all k and lim_{k→∞}(x^{k}, θ^{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} θ^{∞}e^{− \frac{x^{∞}_{i}}{θ^{∞}}} = ∑_{i=1}^{n} lim_{k→∞} θ^{k}e^{− \frac{x^{k}_{i}}{θ^{k}}} = lim_{k→∞} ∑_{i=1}^{n} θ^{k}e^{− \frac{x^{k}_{i}}{θ^{k}}} ≤ lim_{k→∞} κ^{k} = κ^{∞} ,

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

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

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

It is also interesting to identify the interior of this cone.

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

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

Proof. According to Lemma 7.3 in [Roc70] we have

int G^{n} = int epi f_{n} = {(x, θ, κ) | (x, θ) ∈ int dom f_{n} and f_{n}(x, θ) < κ} .

The above-stated result then simply follows from the fact that int dom f_{n} = ℝ_{++}^{n+1}. □

Corollary 2.1 The cone G^{n} is solid.

Proof. It suffices to prove that there exists at least one point that belongs to int G^{n} (Definition 1.1). Taking for example the point (e, \frac{1}{n}, 1), where e stands for the n-dimensional all-one vector, we have

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

and therefore (e, \frac{1}{n}, 1) ∈ int G^{n}. □

We also have the following fact:

Theorem 2.4 G^{n} is pointed.

Proof. The fact that 0 ∈ G^{n} ⊆ ℝ_{+}^{n+2} implies that G^{n} ∩ −G^{n} = {0}, i.e. G^{n} is pointed (Definition 1.2). □

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

2.1 The dual geometric cone (G)^{∗}

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 2.5 The dual of G^{n} is given by

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

Proof. Using Definition 1.3 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). We first note that in the case θ = 0, we may choose any x ∈ ℝ_{+}^{n} and κ ∈ ℝ_{+} and have (x, 0, κ) ∈ G^{n}, which means that the product

(x, θ, κ)^{T} (x^{∗}, θ^{∗}, κ^{∗}) = x^{T} x^{∗} + θθ^{∗} + κκ^{∗} = x^{T} x^{∗} + κκ^{∗}

has to be nonnegative for all (x, κ) ∈ ℝ_{+}^{n+1} and is easily seen to imply that x^{∗} and κ^{∗} are nonnegative. We may now suppose θ > 0, (x^{∗}, κ^{∗}) ≥ 0 and write

x^{T} x^{∗} + θθ^{∗} + κκ^{∗} ≥ 0 for all (x, θ, κ) ∈ G^{n}
⇔ x^{T} x^{∗} + θθ^{∗} + (θ ∑_{i=1}^{n} e^{− \frac{x_{i}}{θ}} )κ^{∗} ≥ 0 for all (x, θ) ∈ ℝ_{+}^{n} × ℝ_{++}

⇔ θ^{∗} ≥ −\frac{x^{T} x^{∗}}{θ} − κ^{∗} ∑_{i=1}^{n} e^{− \frac{x_{i}}{θ}} for all (x, θ) ∈ ℝ_{+}^{n} × ℝ_{++}

⇔ θ^{∗} ≥ −t^{T} x^{∗} − κ^{∗} ∑_{i=1}^{n} e^{−t_{i}} for all t ∈ ℝ_{+}^{n}

⇔ θ^{∗} ≥ − ∑_{i=1}^{n}(t_{i}x_{i}^{∗} + κ^{∗}e^{−t_{i}}) for all t ∈ ℝ_{+}^{n} ,

where we have defined t_{i} = \frac{x_{i}}{θ} for convenience. We now proceed to seek the greatest possible lower bound on θ^{∗}, examining each term of the sum separately: we have thus to seek the minimum of

t_{i}x_{i}^{∗} + κ^{∗}e^{−t_{i}} .

The derivative of this quantity with respect to t_{i} being equal to x_{i}^{∗} − κ^{∗}e^{−t_{i}}, we have a minimum when t_{i} = − log \frac{x_{i}^{∗}}{κ^{∗}}, but we have to take into account the fact that t_{i} has to be nonnegative, which leads us to distinguish the following three cases

⋄ κ^{∗} = 0: in this case, the minimum is always equal to 0,

⋄ κ^{∗} > 0 and x_{i}^{∗} ≤ κ^{∗}: in this case, the minimum is attained for a nonnegative t_{i} and is equal to −x_{i}^{∗} log \frac{x_{i}^{∗}}{κ^{∗}} +x_{i}^{∗}, this quantity being taken as equal to zero in the case of x_{i}^{∗} = 0,

⋄ κ^{∗} > 0 and x_{i}^{∗} > κ^{∗}: in this case, the minimum value for a nonnegative t is attained for t = 0 and is equal to κ^{∗}.

These three cases can be summarized with

inf_{t_{i}>0}(t_{i}x_{i}^{∗} + κ^{∗}e^{−t_{i}}) = \begin{cases}−x_{i}^{∗} log \frac{x_{i}^{∗}}{κ^{∗}} + x_{i}^{∗} & when x_{i}^{∗} < κ^{∗} \\ κ^{∗} & when x_{i}^{∗} ≥ κ^{∗} \end{cases} .

Since all of these lower bounds can be simultaneously attained with a suitable choice of t, we can state the final defining inequalities of our dual cone as

x^{∗} ≥ 0, κ^{∗} ≥ 0 and θ^{∗} ≥ ∑_{0<x_{i}^{∗}<κ^{∗}}(x_{i}^{∗} log \frac{x_{i}^{∗}}{κ^{∗}} − x_{i}^{∗}) − ∑_{x_{i}^{∗}≥κ^{∗}} κ^{∗} .

□

As a special case, since G^{0} = ℝ_{+}^{2}, we check that (G^{0})^{∗} = (ℝ_{+}^{2})^{∗} = ℝ_{+}^{2}, as expected.

Note 2.1 It can be easily checked that the lower bound on θ^{∗} appearing in the definition is always nonpositive, 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+2} and (ℝ_{+}^{n+2})^{∗} = ℝ_{+}^{n+2}, we immediately have that (G^{n})^{∗} ⊇ ℝ_{+}^{n+2}, because taking the dual of a set inclusion reverses its direction.

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

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

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

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

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

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

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

f_{n} : ℝ_{+}^{n} × ℝ_{+} ↦ ℝ : (x^{∗}, κ^{∗}) ↦ ∑_{0<x_{i}^{∗}<κ^{∗}}(x_{i}^{∗} log \frac{x_{i}^{∗}}{κ^{∗}} − x_{i}^{∗}) − ∑_{x_{i}^{∗}≥κ^{∗}} κ^{∗} ,

which implies that f_{n} is convex (by definition of a convex function). Hence we can apply Lemma 7.3 in [Roc70] 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} × ℝ_{++}. □

3 A conic formulation

This is the main section of this paper, where we show how a primal-dual pair of geometric optimization problems can be modelled using the G^{n} and (G^{n})^{∗} cones.

3.1 Modelling geometric optimization

Let us restate here for convenience the definition of the standard primal geometric optimization problem:

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

where functions g_{k} are defined by

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

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,

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

and finally to

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

where e is the all-one vector in ℝ^{r}, n_{k} = #I_{k} and two additional vectors of fictitious variables v, w ∈ ℝ^{r} have 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 \\ w \end{matrix}) , Ã = (A 0 0) , b̃ = b, c̃ = (\begin{matrix}c \\ e \\ e \end{matrix}) and K^{∗} = G^{n_{1}} × G^{n_{2}} × ⋯ × G^{n_{r}} ,

where K^{∗} has been defined as the Cartesian product of several disjoint geometric cones, in order to deal with multiple conic constraints involving disjoint sets of variables. We also note that the fact that we have been able to model geometric optimization with a convex cone is a proof that these problems are convex.

3.2 Deriving the dual

Using properties of G and (G)^{∗} 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 1.2. 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} e^{T} ) (\begin{matrix}x \\ z \\ u \end{matrix}) s.t. (A 0 0) (\begin{matrix}x \\ z \\ u \end{matrix}) = b and (x_{I_{k}}, z_{k}, u_{k}) ∈ (G^{n_{k}})^{∗} for all k ∈ R ,

(CDG)

where x ∈ ℝ^{n}, z ∈ ℝ^{r} and u ∈ ℝ^{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 + e^{T} u s.t. \begin{cases}Ax = b, x_{I_{k}} ≥ 0, u_{k} ≥ 0 \\ z_{k} ≥ ∑\begin{matrix}i∈I_{k} \\ 0<x_{i}<u_{k} \end{matrix}(x_{i} log \frac{x_{i}}{u_{k}} − x_{i}) − ∑\begin{matrix}i∈I_{k} \\ x_{i}≥u_{k} \end{matrix} u_{k} for all k ∈ R \end{cases} ,

which can be further reduced to

inf c^{T} x + e^{T} u + ∑_{k∈R}( ∑_{\begin{matrix}i∈I_{k} \\ 0<x_{i}<u_{k} \end{matrix}}(x_{i} log \frac{x_{i}}{u_{k}} − x_{i}) − ∑_{\begin{matrix}i∈I_{k} \\ x_{i}≥u_{k} \end{matrix}} u_{k}) s.t. Ax = b, u ≥ 0 and x ≥ 0 .

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. At this point, the formulation we have is simpler than the pure conic dual but is still different from the usual geometric optimization dual problem (LDG) one can find in the literature. A little bit of calculus will help us to bridge the gap: let us fix k and consider the corresponding terms in the objective

c_{I_{k}}^{T}x_{I_{k}} + u_{k} + ∑_{\begin{matrix}i∈I_{k} \\ 0<x_{i}<u_{k} \end{matrix}}(x_{i} log \frac{x_{i}}{u_{k}} − x_{i}) − ∑_{\begin{matrix}i∈I_{k} \\ x_{i}≥u_{k} \end{matrix}} u_{k} .

We would like to eliminate variable u_{k}, i.e. find for which value of u_{k} the previous quantity is minimum. It is first straightforward to check that such a value of u_{k} must satisfy x_{i} < u_{k} for all i ∈ I_{k}, i.e. will only involve the first summation sign (since the value −u_{k} in the second sum is attained as a limit case in the first sum when x_{i} tends to u_{k} from below). Taking the derivative with respect to u_{k} and equating it to zero we find

0 = 1 + ∑_{i∈I_{k}} x_{i} \frac{u_{k}}{x_{i}} (−\frac{x_{i}}{u_{k}^{2}} ) = 1 − \frac{∑_{i∈I_{k}} x_{i}}{u_{k}}, which implies u_{k} = ∑_{i∈I_{k}} x_{i} .

Our objective terms become equal to

c_{I_{k}}^{T}x_{I_{k}} + ∑_{i∈I_{k}} x_{i} + ∑_{i∈I_{k}}(x_{i} log \frac{x_{i}}{∑_{i∈I_{k}} x_{i}} − x_{i}) = c_{I_{k}}^{T}x_{I_{k}} + ∑_{i∈I_{k}} x_{i} log \frac{x_{i}}{∑_{i∈I_{k}} x_{i}} ,

and leads to the following simplified dual problem

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

which is, as we expected, the traditional form of a dual geometric optimization problem. This confirms the perfect relevance of our pair of primal-dual geometric cones as a tool to model the class of geometric optimization problems.

4 Concluding remarks

In this paper, we have formulated geometric optimization problems in a conic way using some suitably defined convex cones G^{n} and (G^{n})^{∗}. This approach has the following advantages:

⋄ Classical results from the standard conic duality theory can be applied to derive the duality properties of a pair of geometric optimization problems, including weak and strong duality. This was done in [Gli99, GT00] and can be done here in a very similar fashion. This leads in our opinion to clearer proofs, the specificity of the class of problems under study being confined to the convex cone used in the formulation.

⋄ Proving that geometric optimization problems can be solved in polynomial time can now be done rather easily: finding a suitable (i.e. computable) self-concordant barrier for cones G^{n} and (G^{n})^{∗} is essentially all that is needed.

⋄ Unlike the cones described in [Gli99], the pair of cones we have introduced in this paper bears some strong similarities with the cones used in [GT00] for l_{p}-norm optimization:

L^{p} = \{(x, θ, κ) ∈ ℝ^{n} × ℝ_{+} × ℝ_{+} | ∑_{i=1}^{n} \frac{|x_{i}|^{p_{i}}}{p_{i}θ^{p_{i}−1}} ≤ κ\} .

We believe this is the first step towards the design of a common framework that would encompass geometric optimization, l_{p}-norm optimization and several other kinds of structured convex problems and that would allow the easy derivation of the associated duality properties.

References

[Gli99] Fr. Glineur, Proving strong duality for geometric optimization using a conic formulation, IMAGE Technical Report 9903, Faculté Polytechnique de Mons, Mons, Belgium, October 1999.

[GT00] Fr. Glineur and T. Terlaky, A conic formulation for lp-norm optimization, IMAGE Technical Report 0005, Faculté Polytechnique de Mons, Mons, Belgium, May 2000.

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

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

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

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

[RT98] C. Roos and T. Terlaky, Nonlinear optimization, Delft University of Technology, The Netherlands, 1998, Course WI387.

[Stu00] J. F. Sturm, Primal-dual interior-point approach to semidefinite programming, High performance optimization (T. Terlaky H. Frenk, C. Roos and S. Zhang, eds.), Applied optimization, vol. 33, Kluwer Academic Press, 2000.

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