Approximating geometric optimization with l_{p}-norm optimization

Image Technical Report 0008

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.

November 2000

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

Abstract

In this article, we demonstrate how to approximate geometric optimization with l_{p}- norm optimization. These two categories of problems are well known in structured convex optimization. We describe a family of l_{p}-norm optimization problems that can be made arbitrarily close to a geometric optimization problem, and show that the dual problems for these approximations are also approximating the dual geometric optimization problem. Finally, we use these approximations and the duality theory for l_{p}-norm optimization to derive simple proofs of the weak and strong duality theorems for geometric optimization.

Keywords. geometric optimization, l_{p}-norm optimization, approximation, duality.

Contents

1 Introduction 3

2 Approximating geometric optimization 4 2.1 An approximation of the exponential function . . . . . . . . . . . . . . . . . . 4 2.2 An approximation using l_{p}-norm optimization . . . . . . . . . . . . . . . . . . 5

3 Deriving duality properties 6 3.1 Duality for l_{p}-norm optimization . . . . . . . . . . . . . . . . . . . . . . . . . 6 3.2 A dual for the approximate problem . . . . . . . . . . . . . . . . . . . . . . . 8 3.3 Duality for geometric optimization . . . . . . . . . . . . . . . . . . . . . . . . 9

4 Concluding remarks 10

1 Introduction

Let us start by introducing the primal l_{p}-norm optimization problem [PE70a, Ter85], which is basically a slight modification of a linear optimization problem where the use of l_{p}-norms applied to linear terms is allowed within the constraints. In order to state its formulation in the most general setting, we need to introduce the following sets: let K = {1, 2, …, r}, I = {1, 2, …, n} and let {I_{k}}_{k∈K} be a partition of I into r classes. The problem data is given by two matrices A ∈ ℝ^{m×n} and F ∈ ℝ^{m×r} (whose columns will be denoted by a_{i}, i ∈ I and f_{k}, k ∈ K) and four column vectors b ∈ ℝ^{m}, c ∈ ℝ^{n}, d ∈ ℝ^{r} and p ∈ ℝ^{n} such that p_{i} > 1 ∀i ∈ I. Our primal problem consists in optimizing a linear function of a column vector y ∈ ℝ^{m} under a set of constraints involving l_{p}-norms of linear forms, and can be written as

sup b^{T} y s.t. ∑_{i∈I_{k}} \frac{1}{p_{i}} |c_{i} − a_{i}^{T} y|^{p_{i}} ≤ d_{k} − f_{k}^{T} y ∀k ∈ K .  (Pl_{p})

It is not too difficult to see that this problem is a generalization of several well-known convex optimization problems: linear optimization corresponds to the case where n = 0, while linearly and quadratically constrained convex quadratic problems can be modelled using a reformulation of the quadratic terms as 2-norms [Ter85]. Problems of approximation in l_{p}- norm can also be easily modelled, such as the problems described in [NN94, Ter85].

The purpose of this note is to show that this category of problems can be used to approximate another famous class of problems known as geometric optimization [DPZ67]. Using the same notations as above for sets K and I_{k}, k ∈ K, matrix A and vectors b, c and a_{i}, i ∈ I, this category of problems can be stated as

sup b^{T} y s.t. ∑_{i∈I_{k}} e^{a_{i}^{T} y−c_{i}} ≤ 1 ∀k ∈ K .  (PG)

This formulation differs slightly from the traditional formulation of geometric optimization with respect to the following two aspects:

⋄ The vector of variables that is traditionally considered is not y ∈ ℝ^{m} but rather the strictly positive vector t ∈ ℝ_{++}^{m} defined by t_{j} = e^{y_{j}}, ∀j ∈ {1, 2, …, m}. With this convention, the constraints in (PG) can be written as

∑_{i∈I_{k}} C_{i} ∏_{j=1}^{m} t_{j}^{a_{ij}} ≤ 1

(with C_{j} = e^{−c_{i}} ∀i ∈ I), where the expression on the left-hand side is called a posynomial (this name comes from the fact that it bears some resemblance with a polynomial whose coefficients are positive, since C_{j} > 0). However, formulation (PG), while being completely equivalent, presents the additional advantage of being convex and is thus much more suitable for analysis (notably from the point of view of duality).

⋄ The traditional formulation deals with a posynomial objective. However, it can be replaced by a linear objective without any loss of generality, as shown in [Kla74, Kla76, Gli99].

We will start by presenting in Section 2 an approximation of the exponential function, which central in the definition of the constraints of a geometric optimization problem. This will allow us to present a family of l_{p}-norm optimization problems which can be made arbitrarily close to a primal geometric optimization problem. We derive in Section 3 a dual problem for this approximation, and show that the limiting case for these dual approximations is equivalent to the traditional dual geometric optimization problem. Using this family of pairs of primal-dual problems and the weak and strong duality theorems for l_{p}-norm optimization, we will then show how to derive the corresponding theorems for geometric optimization in a simple manner. Section 4 will conclude and present some topics for further research.

2 Approximating geometric optimization

In this section, we will show how geometric optimization problems can be approximated with l_{p}-norm optimization.

2.1 An approximation of the exponential function

A key ingredient in our approach is the function that will be used to approximate the exponential terms that arise within the constraints of (PG). Let α ∈ ℝ_{++} and let us define

g_{α} : ℝ_{+} ↦ ℝ_{+} : x ↦ |1 − \frac{x}{α}|^{α} .

We have the following lemma relating g_{α}(x) to e^{−x}:

Lemma 2.1 For any fixed x ∈ ℝ_{+}, we have that

g_{α}(x) ≤ e^{−x} ∀α ≥ x and e^{−x} < g_{α}(x) + α^{−1} ∀α > 0 ,  (2.1)

equality occurring in the first inequality if and only if x = 0. Moreover, we have

lim_{α→+∞} g_{α}(x) = e^{−x} .

Proof . Let us fix x ∈ ℝ_{+}. When 1 < α < x, we only have to prove the second inequality in (2.1), which is straightforward: we have e^{−x} < e^{−α} < α^{−1} < g_{α}(x) + α^{−1}, where we used the obvious inequalities e^{α} > α and g_{α}(x) > 0. Assuming α ≥ x for the rest of this proof, we define the auxiliary function h : ℝ_{++} ↦ ℝ : α ↦ log f_{α}(x). Using the Taylor expansion of log(1 − x) around x = 0

log(1 − x) = − ∑_{i=1}^{∞} \frac{x^{i}}{i} for all x such that |x| ≤ 1  (2.2)

we have

h(α) = α log|1 − \frac{x}{α}| = α log(1 − \frac{x}{α}) = − ∑_{i=1}^{∞} \frac{x^{i}}{iα^{i−1}} = −x − ∑_{i=2}^{∞} \frac{x^{i}}{iα^{i−1}}  (2.3)

(where we used the fact that \frac{x}{α} ≤ 1 to write the Taylor expansion). It is now clear that h(α) ≤ −x, with equality if and only if x = 0, which in turn implies that g_{α}(x) ≤ e^{−x}, with equality if and only if x = 0, which is the first inequality in (2.1).

The second inequality is equivalent, after multiplication by e^{x}, to

1 < e^{x}g_{α}(x) + e^{x}α^{−1} ⇔ 1 − e^{x}α^{−1} < e^{x}e^{h_{α}(x)} ⇔ 1 − e^{x}α^{−1} < e^{x+h_{α}(x)} .

This last inequality trivially holds when its left-hand side is negative, i.e. when α ≤ e^{x}. When α > e^{x}, we take the logarithm of both sides, use again the Taylor expansion (2.2) and the expression for h_{α}(x) in (2.3) to find

log(1 − e^{x}α^{−1}) < x + h_{α}(x) ⇔ − ∑_{i=1}^{∞} \frac{e^{x}^{i}}{iα^{i}} < − ∑_{i=2}^{∞} \frac{x^{i}}{iα^{i−1}} ⇔ 0 < ∑_{i=1}^{∞} \frac{1}{α^{i}} (\frac{e^{xi}}{i} − \frac{x^{i+1}}{i + 1}) .

This last inequality holds since each of the coefficients between parentheses can be shown to be strictly positive: writing the well-known inequality e^{a} > \frac{a^{n}}{n!} for a = xi and n = i + 1, we find

e^{xi} > \frac{(xi)^{i+1}}{(i + 1)!} ⇔ \frac{e^{xi}}{i} > \frac{x^{i+1}}{(i + 1)} \frac{i^{i}}{i!} ⇒ \frac{e^{xi}}{i} > \frac{x^{i+1}}{i + 1} ⇔ \frac{e^{xi}}{i} − \frac{x^{i+1}}{i + 1} > 0

(where we used i^{i} ≥ i! to derive the third inequality).

To conclude this proof, we note that (2.3) implies that lim_{α→+∞} h(α) = −x, which gives lim_{α→+∞} f_{α}(x) = e^{−x}, as announced. This last property can also be easily derived from the two inequalities in (2.1). □

The first inequality in (2.1) and the limit of g_{α}(x) are well-known, and are sometimes used as definition for the real exponential function, while the second inequality in (2.1) is much less common.

2.2 An approximation using l_{p}-norm optimization

The formulation of the primal geometric optimization problem (PG) relies heavily on the exponential function. Since Lemma 2.1 shows that it is possible to approximate e^{−x} with increasing accuracy using the function g_{α}, we can consider using this function to formulate an approximation of problem (PG). The key observation we make here is that this approximation can be expressed as a l_{p}-norm optimization problem.

Indeed, let us fix α ∈ ℝ_{++} and write the approximate problem

sup b^{T} y s.t. ∑_{i∈I_{k}}(g_{α}(c_{i} − a_{i}^{T} y) + α^{−1}) ≤ 1 ∀k ∈ K .  (PG_{α})

We note that this problem is a restriction of the original problem (PG), i.e. that any y that is feasible for (PG_{α}) is also feasible for (PG), with the same objective value. This is indeed a direct consequence of the second inequality in (2.1), which implies for any y feasible for (PG_{α})

∑_{i∈I_{k}} e^{c_{i}−a_{i}^{T} y} < ∑_{i∈I_{k}}(g_{α}(c_{i} − a_{i}^{T} y) + α^{−1}) ≤ 1 .

We need now to transform the expressions g_{α}(c_{i} − a_{i}^{T} y) + α^{−1} to fit the format of the constraints of a l_{p}-norm optimization problem. Assuming that α > 1 for the rest of this paper, we write

∑_{i∈I_{k}}(g_{α}(c_{i} − a_{i}^{T} y) + α^{−1}) ≤ 1 ⇔ ∑_{i∈I_{k}} g_{α}(c_{i} − a_{i}^{T} y) ≤ 1 − n_{k}α^{−1}

⇔ ∑_{i∈I_{k}} |1 − \frac{c_{i} − a_{i}^{T} y}{α} |^{α} ≤ 1 − n_{k}α^{−1}
⇔ ∑_{i∈I_{k}} |α − c_{i} + a_{i}^{T} y|^{α} ≤ α^{α}(1 − n_{k}α^{−1})

⇔ ∑_{i∈I_{k}} \frac{1}{α} |c_{i} − α − a_{i}^{T} y|^{α} ≤ α^{α−1}(1 − n_{k}α^{−1})

(where n_{k} is the number of elements in I_{k}), which allows us to write (PG_{α}) as

sup b^{T} y s.t. ∑_{i∈I_{k}} \frac{1}{α} |c_{i} − α − a_{i}^{T} y|^{α} ≤ α^{α−1}(1 − n_{k}α^{−1}) ∀k ∈ K .  (PG′_{α})

This is indeed a l_{p}-norm optimization in the form (Pl_{p}): dimensions m, n and r are the same in both problems, sets I, K and I_{k} are identical, the vector of exponents p satisfies p_{i} = α > 1 for all i ∈ I, matrix A and vector b are the same for both problems while matrix F is equal to zero. The only difference consists in vectors c̃ and d, which satisfy c̃_{i} = c_{i} − α and d_{k} = α^{α−1}(1 − n_{k}α^{−1}).

We have thus shown how to approximate a geometric optimization problem with a standard l_{p}-norm optimization problem. Solving this problem for a fixed value of α will give a feasible solution to the original geometric optimization problem. Letting α tend to +∞, the approximations g_{α}(c_{i} − a_{i}^{T} y) will be more and more accurate, and the corresponding feasible regions will approximate the feasible region of (PG) better and better. We can thus expect the optimal solutions of problems (PG′_{α}) to tend to an optimal solution of (PG). Indeed, this is the most common situation, but it does not happen in all the cases, as will be explained in the next section.

3 Deriving duality properties

The purpose of this section is to study the duality properties of our geometric optimization problem and its approximations. Namely, using the duality properties of l_{p}-norm optimization problems, we will derive the corresponding properties for geometric optimization, using our family of approximate problems.

3.1 Duality for l_{p}-norm optimization

Defining a vector q ∈ ℝ^{n} such that \frac{1}{p_{i}} + \frac{1}{q_{i}} = 1 for all i ∈ I, the dual problem for (Pl_{p}) consists in finding two vectors x ∈ ℝ^{n} and z ∈ ℝ^{r} that maximize a highly nonlinear objective while satisfying some linear equalities and nonnegativity constraints [Ter85, GT00]:

inf ψ(x, z) = c^{T} x + d^{T} z + ∑_{\begin{matrix}k∈K \\ z_{k}>0 \end{matrix}} z_{k} ∑_{i∈I_{k}} \frac{1}{q_{i}} |\frac{x_{i}}{z_{k}} |^{q_{i}} s.t. \{ \begin{matrix}Ax + F z = b and z ≥ 0 , \\ z_{k} = 0 ⇒ x_{i} = 0 ∀i ∈ I_{k} . \end{matrix} (Dl_{p})

We note that a special convention has been taken to handle the case when one or more components of z are equal to zero: the associated terms are left out of the first sum (to avoid a zero denominator) and the corresponding components of x have to be equal to zero. When compared with the primal problem (Pl_{p}), this problem has a simpler feasible region at the price of a more complicated (but convex) objective.

We have the following duality properties for the pair of problems (Pl_{p})–(Dl_{p}) (these results were first obtained by Peterson and Ecker [PE70a, PE67, PE70b], see also [GT00] for simpler alternative proofs using conic duality) :

Theorem 3.1 (Weak duality) If y is feasible for (Pl_{p}) and (x, z) is feasible for (Dl_{p}), we have ψ(x, z) ≥ b^{T} y.

Theorem 3.2 (Strong duality) If both problems (Pl_{p}) and (Dl_{p}) are feasible, the primal optimal objective value is attained with a zero duality gap, i.e.

p^{∗} = max b^{T} y s.t. ∑_{i∈I_{k}} \frac{1}{p_{i}} |c_{i} − a_{i}^{T} y|^{p_{i}} ≤ d_{k} − f_{k}^{T} y ∀k ∈ K

= inf ψ(x, z) s.t. \{ \begin{matrix}Ax + F z = b and z ≥ 0 \\ z_{k} = 0 ⇒ x_{i} = 0 ∀i ∈ I_{k} \end{matrix} = d^{∗} .

The weak duality property is a rather straightforward consequence of the convexity of the problem, and is shared by all the convex optimization problems. This contrasts with the absence of a duality gap and the guaranteed attainment of the primal optimal objective value, which are due to the specific structure of l_{p}-norm optimization problems (i.e. they do not hold for a general convex problem, where a strictly positive duality gap and/or non-attainment for both problems may occur [SW70, Stu00]).

We would like to bring the reader’s attention to an interesting special case of dual l_{p}-norm optimization problem. When all p_{i}’s are equal to p and when matrix F is identically equal to 0, i.e. when there are no pure linear terms in the constraints, problem (Dl_{p}) becomes

inf ψ(x, z) = c^{T} x + d^{T} z + \frac{1}{q} ∑_{\begin{matrix}k∈K \\ z_{k}>0 \end{matrix}} z_{k}^{1−q} ∑_{i∈I_{k}} |x_{i}|^{q} s.t. \{ \begin{matrix}Ax = b and z ≥ 0 , \\ z_{k} = 0 ⇒ x_{i} = 0 ∀i ∈ I_{k} . \end{matrix} (Dl′_{p})

This kind of formulation arises in problems of approximation in l_{p}-norm, see [NN94, Section 6.3.2] and [Ter85, Section 11, page 98].

Since variables z_{k} do not appear any more in the linear constraints but only in the objective function ψ(x, z), we may try to find a closed form for their optimal value. Looking at one variable z_{k} at a time and isolating the corresponding terms in the objective, one finds d_{k}z_{k} + \frac{1}{q}z_{k}^{1−q} ∑_{i∈I_{k}} |x_{i}|^{q}, whose derivative is equal to d_{k} + \frac{1−q}{q} z_{k}^{−q} ∑_{i∈I_{k}} |x_{i}|^{q}. One easily sees that this quantity admits a single maximum when

z_{k} = (p d_{k})^{− \frac{1}{q}} ∥x_{I_{k}}∥_{q}

(where ∥·∥_{p} corresponds to the usual p-norm defined by ∥x∥_{p} = (∑_{i} |x_{i}|^{p})^{\frac{1}{p}} and x_{I_{k}} denotes the vector made of the components of x whose indices belong to I_{k}), which always satisfies the nonnegativity constraint in (Dl′_{p}) and gives after some straightforward computations a value of

d_{k}z_{k} + \frac{1 − q}{q} z_{k}^{−q} ∑_{i∈I_{k}} |x_{i}|^{q} = … = (1 + \frac{p}{q})d_{k}z_{k} = p d_{k}z_{k} = (p d_{k})^{\frac{1}{p}} ∥x_{I_{k}}∥_{q}

for the two corresponding terms in the objective. Our dual problem (Dl′_{p}) becomes then

inf ψ(x) = c^{T} x + ∑_{k∈K}(p d_{k})^{\frac{1}{p}} ∥x_{I_{k}}∥_{q} s.t. Ax = b ,  (Dl′′_{p})

a great simplification when compared to (Dl′_{p}). One can check that the special treatment for the case z_{k} = 0 is well handled: indeed, z_{k} = 0 happens when x_{I_{k}} = 0, and the implication that is stated in the constraints of (Dl′_{p}) is thus satisfied.

3.2 A dual for the approximate problem

We are now going to write the dual for the approximate problem (PG′_{α}). Since we are in the case where F = 0 and all p_{i}’s are equal to α, we can use the simplified version of the dual problem (Dl′′_{p}) and write

inf ψ_{α}(x) = c^{T} x − αe_{n}^{T} x + ∑_{k∈K} (α α^{α−1}(1 − n_{k}α^{−1}))^{\frac{1}{α}} ∥x_{I_{k}}∥_{β} s.t. Ax = b

(where e_{n} is a notation for the all-one n-dimensional column vector and β > 1 is a constant such that \frac{1}{α} + \frac{1}{β} = 1), which can be simplified to give

inf ψ_{α}(x) = c^{T} x − αe_{n}^{T} x + α ∑_{k∈K}(1 − n_{k}α^{−1})^{\frac{1}{α}} ∥x_{I_{k}}∥_{β} s.t. Ax = b .  (DG_{α})

We observe that the constraints and thus the feasible region of this problem are independent from α, which only appears in the objective function ψ_{α}(x). Intuitively, since problems (PG′_{α}) become closer and closer to (PG) as α tends to +∞, the corresponding dual problems (PG′_{α}) should approximate the dual of (PG) better and better. It is thus interesting to write down the limiting case for these problems, i.e. find the limit of ψ_{α} when α → +∞. Looking first at the terms that are related to single set of indices I_{k}, we write

ψ_{k,α}(x) = c_{I_{k}}^{T}x_{I_{k}} − αe_{n_{k}}^{T}x_{I_{k}} + α(1 − n_{k}α^{−1})^{\frac{1}{α}} ∥x_{I_{k}}∥_{β}
= c_{I_{k}}^{T}x_{I_{k}} − αe_{n_{k}}^{T}x_{I_{k}} + α ∥x_{I_{k}}∥_{1} − α ∥x_{I_{k}}∥_{1} + α(1 − n_{k}α^{−1})^{\frac{1}{α}} ∥x_{I_{k}}∥_{β}
= c_{I_{k}}^{T}x_{I_{k}} + α [∥x_{I_{k}}∥_{1} − e_{n_{k}}^{T}x_{I_{k}}] + α [(1 − n_{k}α^{−1})^{\frac{1}{α}} ∥x_{I_{k}}∥_{β} − ∥x_{I_{k}}∥_{1}]
= c_{I_{k}}^{T}x_{I_{k}} + α [∥x_{I_{k}}∥_{1} − e_{n_{k}}^{T}x_{I_{k}}] + \frac{β}{β − 1} [(1 − n_{k}α^{−1})^{\frac{1}{α}} ∥x_{I_{k}}∥_{β} − ∥x_{I_{k}}∥_{1}]

(where we used at the last line the fact that α = \frac{β}{β−1}). When α tends to +∞ (and thus β → 1), we have

lim_{\begin{matrix}α→+∞ \\ β→1 \end{matrix}} ψ_{k,α}(x) = c_{I_{k}}^{T}x_{I_{k}} + lim_{α→+∞} α [∥x_{I_{k}}∥_{1} − e_{n_{k}}^{T}x_{I_{k}}] + lim_{\begin{matrix}α→+∞ \\ β→1 \end{matrix}} \frac{β}{β − 1} [(1 − n_{k}α^{−1})^{\frac{1}{α}} ∥x_{I_{k}}∥_{β} − ∥x_{I_{k}}∥_{1}]

= c_{I_{k}}^{T}x_{I_{k}} + lim_{α→+∞} α [∥x_{I_{k}}∥_{1} − e_{n_{k}}^{T}x_{I_{k}}] + lim_{β→1} \frac{∥x_{I_{k}}∥_{β} − ∥x_{I_{k}}∥_{1}}{β − 1}

The last term in this limit is equal to the derivative of the real function m_{k} : β ↦ ∥x_{I_{k}}∥_{β} at the point β = 1. We can check without difficulties that

m′_{k}(β) = \frac{∥x_{I_{k}}∥_{β}^{\frac{1}{β} −1}}{β^{2}} [β ∑_{\begin{matrix}i∈I_{k} \\ x_{i}>0 \end{matrix}} |x_{i}|^{β} log |x_{i}| − ∥x_{I_{k}}∥_{1} log ∥x_{I_{k}}∥_{1}] ⇒ m′_{k}(1) = ∑_{\begin{matrix}i∈I_{k} \\ x_{i}>0 \end{matrix}} |x_{i}| log \frac{|x_{i}|}{∥x_{I_{k}}∥_{1}} ,

which gives

lim_{\begin{matrix}α→+∞ \\ β→1 \end{matrix}} ψ_{k,α}(x) = c_{I_{k}}^{T}x_{I_{k}} + lim_{α→+∞} α [∥x_{I_{k}}∥_{1} − e_{n_{k}}^{T}x_{I_{k}}] + ∑_{\begin{matrix}i∈I_{k} \\ x_{i}>0 \end{matrix}} |x_{i}| log \frac{|x_{i}|}{∥x_{I_{k}}∥_{1}} .

It is easy to see that ∥x_{I_{k}}∥_{1} − e_{n_{k}}^{T}x_{I_{k}} ≥ 0, with equality if and only if x_{I_{k}} ≥ 0. This means that the limit of our objective ψ_{k,α}(x) will be +∞ unless x_{I_{k}} ≥ 0. An objective equal to +∞ for a minimization problem can be assimilated to an unfeasible problem, which means that the limit of our dual approximations (DG_{α}) admits the hidden constraint x_{I_{k}} ≥ 0. Gathering now all terms in the objective, we eventually find the limit of problems (DG_{α}) when α → +∞ to be

inf ϕ(x) = 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 ,  (DG)

which is exactly the dual geometric optimization problem one can find in the literature [Kla74, Kla76, Gli99].

3.3 Duality for geometric optimization

Before we start to prove duality results for geometric optimization, we make a technical assumption on problem (PG), whose purpose will become clear further in this section: we will assume that n_{k} ≥ 2 for all k ∈ K, i.e. forbid problems where a constraint is defined with a single exponential term. This can be done without any loss of generality, since a constraint of the form e^{a_{i}^{T} y−c_{i}} ≤ 1 can be equivalently rewritten as e^{a_{i}^{T} y−c_{i}−log 2} + e^{a_{i}^{T} y−c_{i}−log 2} ≤ 1.

Let us now state the weak duality theorem for geometric optimization:

Theorem 3.3 (Weak duality) If y is feasible for (PG) and x is feasible for (DG), we have ϕ(x) ≥ b^{T} y.

Proof . Our objective is to prove this theorem using our family of approximate problems (PG′_{α})– (DG_{α}). We first note that x is feasible for (DG_{α}) for every α, since the only constraints for this family of problems are the linear constraints Ax = b, which are also present in (DG). The situation is a little different on the primal side: the first inequality in (2.1) and feasibility of y for (PG) imply

∑_{i∈I_{k}} g_{α}(c_{i} − a_{i}^{T} y) ≤ ∑_{i∈I_{k}} e^{a_{i}^{T} y−c_{i}} ≤ 1 ,

with equality if and only if c_{i} −a_{i}^{T} y = 0 for all i ∈ I_{k}. But this cannot happen, since we would have ∑_{i∈I_{k}} e^{a_{i}^{T} y−c_{i}} = ∑_{i∈I_{k}} 1 = n_{k} > 1, because of our assumption on n_{k}, which contradicts the feasibility of y. We can conclude that the following strict inequality holds for all k ∈ K:

∑_{i∈I_{k}} g_{α}(c_{i} − a_{i}^{T} y) < 1 .

Since the set K is finite, this means that there exists a constant M such that for all α ≥ M,

∑_{i∈I_{k}} g_{α}(c_{i} − a_{i}^{T} y) ≤ 1 − n_{k}α^{−1} ∀k ∈ K ,

which in turn implies feasibility of y for problems (PG′_{α}) as soon as α ≥ M. Feasibility of both y and x for their respective problem allows us to apply the weak duality Theorem 3.1 of l_{p}-norm optimization to our pair of approximate problems (PG′_{α})–(DG_{α}), which implies ψ_{α}(x) ≥ b^{T} y for all α ≥ M. Taking now the limit of ψ_{α}(x) for α tending to +∞, which is finite and equal to ϕ(x) since x ≥ 0, we find that ϕ(x) ≥ b^{T} y, which is the announced inequality. □

The strong duality theorem for geometric optimization is stated below. We note that contrary to the class of l_{p}-norm optimization problems, attainment cannot be guaranteed for any of the primal and dual optimum objective values.

Theorem 3.4 If both problems (PG) and (DG) are feasible, their optimum objective values p^{∗} and d^{∗}are equal.

Proof . As shown in the proof of the previous theorem, the existence of a feasible solution for (PG) and (DG) implies that problems (PG′_{α}) and (DG_{α}) are both feasible for all α greater than some constant M. Denoting by p_{α}^{∗} (resp. d_{α}^{∗}) the optimal objective value of problem (PG′_{α}) (resp. (DG_{α})), we can thus apply the strong duality Theorem 3.2 of l_{p}-norm optimization to these pairs of problems to find that p_{α}^{∗} = d_{α}^{∗} for all α ≥ M. Since all the dual approximate problems p_{α}^{∗} = d_{α}^{∗} share the same feasible region, it is clear that the optimal value corresponding to the limit of the objective ψ_{α} when α → +∞ is equal to the limit of the optimal objective values d_{α}^{∗} for α → +∞. Since the problem featuring this limiting objective has been shown to be equivalent to (DG) in Section 3.2 (including the hidden constraint x ≥ 0), we must have d^{∗} = lim_{α→+∞} d_{α}^{∗}. On the other hand, Theorem 3.2 guarantees for each of the problems (PG′_{α}) the existence of an optimal solution y_{α} that satisfies b^{T} y_{α} = p_{α}^{∗}. Since each of these solutions is also a feasible solution for (PG) (since problems (PG′_{α}) are restrictions of (PG)), which shares the same objective function, we have that the optimal objective value of (PG) p^{∗} is at least equal to b^{T} y_{α} for all α ≥ M, which implies p^{∗} ≥ lim_{α→+∞} b^{T} y_{α} = lim_{α→+∞} p_{α}^{∗} = lim_{α→+∞} d_{α}^{∗} = d^{∗}. Combining this last inequality with the easy consequence of the weak duality Theorem 3.3 that states d^{∗} ≥ p^{∗}, we end up with the announced equality p^{∗} = d^{∗}. □

The reason why attainment of the primal optimum objective value cannot be guaranteed is that the sequence y_{α} may not have a finite limit point: indeed, it may happen that one or more components of y_{α} tend to infinity as α → +∞ (see e.g. the third example in [Gli99, Section 4.4]).

4 Concluding remarks

In this paper, we have shown that the important class of geometric optimization problems can be approximated with l_{p}-norm optimization.

We have indeed described a parameterized family of primal and dual l_{p}-norm optimization problems, which can be made arbitrarily close to the geometric primal and dual problems. It is worth to note that the primal approximations are restrictions of the original geometric primal problem, sharing the same objective function, while the dual approximations share essentially the same constraints as the original geometric dual problem (except for the nonnegativity constraints) but feature a different objective.

Another possible approach would be to work with relaxations instead of restrictions on the primal side, using the first inequality in (2.1) instead of the second one, leading to the following problem:

sup b^{T} y s.t. ∑_{i∈I_{k}} g_{α}(c_{i} − a_{i}^{T} y) ≤ 1 ∀k ∈ K .

However, two problems arise in this setting:

⋄ the first inequality in (2.1) is only valid when α ≥ x, which means we would have to add a set of explicit linear inequalities c_{i} −a_{i}^{T} y ≤ α to our approximations, which would make them and their dual problems more difficult to handle,

⋄ following the same line of reasoning as in the proof of Theorem 3.2, we would end up with another family of optimal solutions y_{α} for the approximate problems; however, since all of these problems are relaxations, we would have no guarantee that any of the optimal vectors y_{α} are feasible for the original primal geometric optimization problem, which would prevent us to conclude that the duality gap is equal to zero. This would only show that there is a family of asymptotically feasible solutions with their objective values tending to the objective value of the dual, a fact that is always true in convex optimization (see e.g. the notion of subinfimum in [SW70, Stu00]).

To conclude, we note that our approximate problems belong to a very special subcategory of l_{p}-norm optimization problem, since they satisfy F = 0. It might be fruitful to investigate which class of generalized geometric optimization problems can be approximated with general l_{p}-norm optimization problems, a topic we leave for further research.

References

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

[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, to appear in Annals of Operations Research.

[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, submitted to Journal of Optimization Theory and Applications.

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

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

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

[PE67] E. L. Peterson and J. G. Ecker, Geometric programming: Duality in quadratic programming and l_{p} approximation II, SIAM Journal on Applied Mathematics 13 (1967), 317–340.

[PE70a] E. L. Peterson and J. G. Ecker, Geometric programming: Duality in quadratic programming and l_{p} approximation I, Proceedings of the International Symposium of Mathematical Programming (Princeton, New Jersey) (H. W. Kuhn and A. W. Tucker, eds.), Princeton University Press, 1970.

[PE70b] E. L. Peterson and J. G. Ecker, Geometric programming: Duality in quadratic programming and l_{p} approximation III, Journal on Mathematical Analysis and Applications 29 (1970), 365–383.

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

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

[Ter85] T. Terlaky, On l_{p} programming, European Journal of Operations Research 22 (1985), 70–100.