Deriving Duality for l_{p}-norm Optimization Using Conic Optimization

Image Technical Report 9904

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.

Tamás Terlaky

Faculty of Technical Mathematics and Informatics, Delft University of Technology, NL-2600 GA Delft, The Netherlands,

                          T.Terlaky@its.tudelft.nl.

December 99

Abstract

In this paper, we formulate the l_{p}-norm optimization problem as a conic optimization problem and derive its standard duality properties.

We first define an ad hoc closed convex cone L and derive its dual. We express then the standard l_{p}-norm optimization primal problem as a conic problem involving L. Using convex conic duality, we derive the dual of this problem and prove the well-known regularity properties of this primal-dual pair, i.e. zero duality gap and dual attainment.

Keywords. l_{p}-norm optimization, conic optimization, duality

1 Introduction

l_{p}-norm optimization problems form an important class of convex problems, which includes as special cases linear programming, quadratic programming, quadratically constrained quadratic programming and l_{p}-norm approximation problems.

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

This research has been carried out during a visit to the Delft University of Technology supported by a grant from the Communauté Française de Belgique.

Some duality results are known for l_{p}-norm optimization. Namely, a pair of feasible primaldual l_{p}-norm optimization problems satisfies the weak duality property, has a zero duality gap and has its dual optimum objective attained by a feasible solution.

These results were first obtained by Peterson and Ecker [PE70a, PE67, PE70b] and later simplified by Terlaky [Ter85]. The aim of this paper is to derive these results using the machinery of convex conic duality, which simplifies further the proofs.

In order to use this setting, we define an appropriate convex cone that allows us to express l_{p}-norm optimization problems as conic programs. In order to analyze duality for this problem, we first study some properties of this cone (closedness, interior) and determine its dual cone, which happens to have nearly the same structure.

We apply then the general duality theory for conic optimization to our programs [Stu97], to prove the above mentioned duality results about l_{p}-norm optimization.

This leads in our opinion to clearer proofs, the specificity of the problem being confined to the convex cone we use in our formulation. Moreover, the reason why this problem has better duality properties than a general conic problem becomes clear: this is essentially due to the existence of a strictly interior primal solution. However, such an interior solution does not always exist and a reduction procedure involving an equivalent regularized problem has to be introduced to prove the results in the general case.

2 The L cone

Definition 1 Let p ∈ ℝ^{n} with p_{i} > 1. We define the following set

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

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

\frac{|x|}{0} = \begin{cases}+∞ & if x ≠ 0 \\ 0 & if x = 0 \end{cases} .

This means that (x, 0, κ) ∈ L^{p} implies x = 0. We start by proving that L^{p} is a convex cone.

Theorem 1 L^{p} is a convex cone.

Proof. Let us first introduce the following function

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

With the convention mentioned above, its effective domain is ℝ^{n} ×ℝ_{++} ∪(0, 0). It is straightforward to check that f_{p} is positively homogeneous, i.e. f_{p}(λx, λθ) = λf_{p}(x, θ) for λ ≥ 0. Moreover, f_{p} is subadditive, i.e. f_{p}(x + x′, θ + θ′) ≤ f_{p}(x, θ) + f_{p}(x′, θ′). In order to show it, we only need to prove the following inequality:

\frac{|x|^{p_{i}}}{θ^{p_{i}−1}} + \frac{|x′|^{p_{i}}}{θ′^{p_{i}−1}} ≥ \begin{matrix}|x + x′| & p_{i} \\ (θ + θ′) & p_{i}−1 \end{matrix} .

First observe that this inequality is obviously true if θ or θ′ is equal to 0. When θ and θ′ are both different from 0, we use the well known fact that x^{p_{i}} is a convex function on ℝ_{+}, implying that λa^{p_{i}} + λ′a′^{p_{i}} ≥ (λa + λ′a′)^{p_{i}} for any nonnegative a, a′, λ and λ′ satisfying λ + λ′ = 1. Choosing a = \frac{1}{θ} |x|, a′ = \frac{1}{θ′} |x′|, λ = \frac{θ}{θ+θ′} and λ′ = \frac{θ′}{θ+θ′}, we find that

\frac{θ}{θ + θ′} (\frac{|x|}{θ})^{p_{i}} + \frac{θ′}{θ + θ′} (\frac{|x′|}{θ′})^{p_{i}} ≥ (\frac{θ}{θ + θ′} \frac{|x|}{θ} + \frac{θ′}{θ + θ′} \frac{|x′|}{θ′})^{p_{i}}
\frac{1}{θ + θ′} (\frac{|x|^{p_{i}}}{θ^{p_{i}−1}} + \frac{|x′|^{p_{i}}}{θ′^{p_{i}−1}} ) ≥ (\frac{|x| + |x′|}{θ + θ′})^{p_{i}}
\frac{|x|^{p_{i}}}{θ^{p_{i}−1}} + \frac{|x′|^{p_{i}}}{θ′^{p_{i}−1}} ≥ \begin{matrix}(|x| + |x′|) & p_{i} \\ (θ + θ′) & p_{i}−1 \end{matrix} ≥ \begin{matrix}|x + x′| & p_{i} \\ (θ + θ′) & p_{i}−1 \end{matrix} .

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

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

L^{p} is thus the epigraph of a convex positively homogeneous function, hence a convex cone. □

We would like to compute the interior of this cone. According to Lemma 7.3 in [Roc70] we have

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

Using the fact that int dom f_{p} = ℝ^{n} × ℝ_{++}, we find that

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

We also notice that in the special case where p_{i} = 2 for all i, our cone L^{p} becomes

L^{(2,··· ,2)} = {(x, θ, κ) ∈ ℝ^{n} × ℝ_{+} × ℝ_{+} | ∑_{i=1}^{n} x_{i}^{2} ≤ 2θκ} ,

which is the hyperbolic or rotated second-order cone. We are now going to determine the dual cone of L^{p}. We first introduce a useful inequality, which lies at the heart of duality for the L cones.

Lemma 1 Let a, b ∈ ℝ_{+}, α, β > 1 and \frac{1}{α} + \frac{1}{β} = 1. We have the inequality

\frac{a^{α}}{α} + \frac{b^{β}}{β} ≥ ab ,

with equality if and only if a^{α} = b^{β}.

Proof. This is an application of the well-known weighted arithmetic-geometric inequality on a^{α} and b^{β} with weights \frac{1}{α} and \frac{1}{β} (whose sum is equal to one). This gives

\frac{a^{α}}{α} + \frac{b^{β}}{β} ≥ (a^{α})^{1/α}(b^{β})^{1/β} = ab .

□

For ease of notation, we also introduce the switched cone L_{s} as the L cone with its last two components exchanged, i.e.

(x, θ, κ) ∈ L_{s}^{p} ⇔ (x, κ, θ) ∈ L^{p} .

We are now ready to describe the dual of L^{p}.

Theorem 2 (Dual of L) Let p, q ∈ ℝ^{n} such that p_{i}, q_{i} > 1 and \frac{1}{p_{i}} + \frac{1}{q_{i}} = 1 for each i. The dual of L^{p} is L_{s}^{q}.

Proof. By definition of the dual cone, we have

(L^{p})^{∗} = {v^{∗} ∈ ℝ^{n} × ℝ × ℝ | v^{T} v^{∗} ≥ 0 for all v ∈ L^{p}} .

We start by showing that L_{s}^{q} ⊆ (L^{p})^{∗}. Let v^{∗} = (x^{∗}, θ^{∗}, κ^{∗}) ∈ L_{s}^{q} and v = (x, θ, κ) ∈ L^{p}. We are going to prove that v^{T} v^{∗} ≥ 0, which will imply the desired inclusion. The case when θ = 0 is easily handled: we have then x = 0 implying v^{T} v^{∗} = κκ^{∗} ≥ 0. Similarly we can eliminate the case where κ^{∗} = 0. In the remaining cases, we use the definitions of L and L_{s} to get

f_{p}(x, θ) = ∑_{i=1}^{n} \frac{|x_{i}|^{p_{i}}}{p_{i}θ^{p_{i}−1}} ≤ κ and f_{q}(x^{∗}, κ^{∗}) = ∑_{i=1}^{n} \frac{|x_{i}^{∗}|^{q_{i}}}{q_{i}κ^{∗}^{q_{i}−1}} ≤ θ^{∗} .

Dividing respectively by θ and κ^{∗} and adding we find

∑_{i=1}^{n}(\frac{|x_{i}|^{p_{i}}}{p_{i}θ^{p_{i}}} + \frac{|x_{i}^{∗}|^{q_{i}}}{q_{i}κ^{∗}^{q_{i}}} ) ≤ \frac{κ}{θ} + \frac{θ^{∗}}{κ^{∗}} .  (2.1)

Applying Lemma 1 to each pair \frac{|x_{i}|}{θ}, \frac{|x_{i}^{∗}|}{κ^{∗}} we get

∑_{i=1}^{n} \frac{|x_{i}|}{θ} \frac{|x_{i}^{∗}|}{κ^{∗}} ≤ \frac{κ}{θ} + \frac{θ^{∗}}{κ^{∗}} ,  (2.2)

which is equivalent to

∑_{i=1}^{n} |x_{i}| |x_{i}^{∗}| ≤ κκ^{∗} + θθ^{∗} .

Finally, noting that x_{i}x_{i}^{∗} ≥ − |x_{i}| |x_{i}^{∗}| we conclude that

v^{T} v^{∗} = x_{i}^{T} x_{i}^{∗} + κκ^{∗} + θθ^{∗} = ∑_{i=1}^{n} x_{i}x_{i}^{∗} + κκ^{∗} + θθ^{∗} ≥ ∑_{i=1}^{n} − |x_{i}| |x_{i}^{∗}| + κκ^{∗} + θθ^{∗} ≥ 0 , (2.3)

showing that L_{s}^{q} ⊆ (L^{p})^{∗}. Let us prove now the reverse inclusion, i.e. (L^{p})^{∗} ⊆ L_{s}^{q}. Let v^{∗} = (x^{∗}, θ^{∗}, κ^{∗}) ∈ (L^{p})^{∗}. We have to show that v^{∗} ∈ L_{s}^{q}, using that v^{T} v^{∗} ≥ 0 for every v = (x, θ, κ) ∈ L^{p}. Choosing v = (0, 0, 1), we have v^{T} v^{∗} = κ^{∗} ≥ 0. We distinguish the cases κ^{∗} = 0 and κ^{∗} > 0. If κ^{∗} = 0, we have that v^{T} v^{∗} = x^{T} x^{∗}+θθ^{∗} ≥ 0 for every v = (x, θ, κ) ∈ L^{p}. Choosing θ = 1 and κ ≥ f_{p}(x, 1) for any x ∈ ℝ^{n}, we find that x^{T} x^{∗} + θ^{∗} ≥ 0 for all x ∈ ℝ^{n}, which implies x^{∗} = 0 and θ^{∗} ≥ 0 and thus v^{∗} ∈ L_{s}^{q}. When κ^{∗} > 0, we can always choose a v ∈ L^{p} such that

\frac{|x_{i}|^{p_{i}}}{θ^{p_{i}}} = \frac{|x_{i}^{∗}|^{q_{i}}}{κ^{∗}^{q_{i}}} , x_{i}x_{i}^{∗} ≤ 0 and f_{p}(x, θ) = ∑_{i=1}^{n} \frac{|x_{i}|^{p_{i}}}{p_{i}θ^{p_{i}−1}} = κ .  (2.4)

Writing

0 ≤ \frac{v^{T} v^{∗}}{θκ^{∗}} = (\frac{x}{θ})^{T} (\frac{x^{∗}}{κ^{∗}} )^{T} + \frac{θ^{∗}}{κ^{∗}} + \frac{κ}{θ}

= ∑_{i=1}^{n} \frac{x_{i}}{θ} \frac{x_{i}^{∗}}{κ^{∗}} + \frac{θ^{∗}}{κ^{∗}} + \frac{κ}{θ}

= ∑_{i=1}^{n} −\frac{|x_{i}|}{θ} \frac{|x_{i}^{∗}|}{κ^{∗}} + \frac{θ^{∗}}{κ^{∗}} + \frac{κ}{θ} ,

using the case of equality of Lemma 1 on the pairs \frac{|x_{i}|}{θ}, \frac{|x_{i}^{∗}|}{κ^{∗}} and the choice of v in (2.4),

= − ∑_{i=1}^{n}(\frac{|x_{i}|^{p_{i}}}{p_{i}θ^{p_{i}}} + \frac{|x_{i}^{∗}|^{q_{i}}}{q_{i}κ^{∗}^{q_{i}}} ) + \frac{θ^{∗}}{κ^{∗}} + \frac{κ}{θ}

= \frac{θ^{∗}}{κ^{∗}} − ∑_{i=1}^{n} \frac{|x_{i}^{∗}|^{q_{i}}}{q_{i}κ^{∗}^{q_{i}}} ,

and finally multiplying by κ^{∗} leads to

∑_{i=1}^{n} \frac{|x_{i}^{∗}|^{q_{i}}}{q_{i}κ^{∗}^{q_{i}−1}} ≤ θ^{∗} ,

i.e. v^{∗} ∈ L_{s}^{q}, showing that (L^{p})^{∗} ⊆ L_{s}^{q} and thus (L^{p})^{∗} = L_{s}^{q}. □

The dual of a L cone is thus equal, up to a permutation of two variables, to another L cone with a dual set of exponents.

Corollary 1 We also have (L_{s}^{p})^{∗} = L^{q}, (L^{q})^{∗} = L_{s}^{p} and (L_{s}^{q})^{∗} = L^{p}.

Proof. Obvious considering both the symmetry between L and L_{s} and the symmetry between p and q. □

Corollary 2 L^{p} and L_{s}^{q} are closed.

Proof. Starting with (L^{p})^{∗} = L_{s}^{q} and taking the dual of both sides, we find ((L^{p})^{∗})^{∗} = (L_{s}^{q})^{∗}. Since (L_{s}^{q})^{∗} = L^{p} by Corollary 1 and ((L^{p})^{∗})^{∗} = cl L^{p} [Roc70, page 121], we have cl L^{p} = L^{p}, hence L^{p} is closed. The switched cone L_{s}^{q} is obviously also closed. □

We can also provide a direct proof of the closedness of L^{p}: using the fact that it is the epigraph of f_{p}, it is enough to show that f_{p} is a lower semicontinuous function [Roc70, Theorem 7.1]. Being convex, f_{p} is continuous on the interior of its effective domain, i.e. when θ > 0. When θ = 0, we have to prove that

lim_{(x,θ)→(x^{0},0)} f_{p}(x, θ) ≥ f_{p}(x^{0}, 0) .

On the one hand, if x_{i}^{0} ≠ 0 for some index i, we have that f_{p}(x^{0}, 0) = +∞ but also that lim_{(x,θ)→(x^{0},0)} f_{p}(x, θ) = +∞, hence the inequality is true. On the other hand, if x^{0} = 0, we have to check that lim_{(x,θ)→(0,0)} f_{p}(x, θ) ≥ f_{p}(0, 0) = 0, which is obviously also true. From this we can conclude that f_{p} is lower semicontinuous and L^{p} is closed. Please note however that f_{p} is not continuous in (0, 0). Choosing an arbitrary positive constant K and taking for example x_{i} = (Kp_{i})^{1/p_{i}}θ^{1/q_{i}}, so that x → 0 when θ → 0, we have that lim_{θ→0} f(x(θ), θ) = nK ≠ f(0, 0) = 0. The limit of f_{p} at (0, 0) can indeed take any positive value^{1}.

The next theorem describes the cases where two vectors from L^{p} and L_{s}^{q} are orthogonal, which will be used in the study of the duality properties.

Theorem 3 Let v = (x, θ, κ) ∈ L^{p} and v^{∗} = (x^{∗}, θ^{∗}, κ^{∗}) ∈ L_{s}^{q}. We have v^{T} v^{∗} = 0 if and only if

κ^{∗}(f_{p}(x, θ) − κ) = 0  (2.5a)
θ(f_{q}(x^{∗}, κ^{∗}) − θ^{∗}) = 0  (2.5b)
κ^{∗} \frac{|x_{i}|^{p_{i}}}{θ^{p_{i}−1}} = θ \frac{|x_{i}^{∗}|^{q_{i}}}{κ^{∗}^{q_{i}−1}}  (2.5c)
x_{i}x_{i}^{∗} ≤ 0 for all i .  (2.5d)

Proof. When θ > 0 and κ^{∗} > 0, a careful reading of the first part of the proof of Theorem 2 shows that equality occurs if and only if all conditions in (2.5) are fulfilled. Namely, (2.5a) and (2.5b) are responsible for equality in (2.1), (2.5c) ensures that we are in the case of equality of Lemma 1 for inequality (2.2) and the last condition (2.5d) is necessary for equality in (2.3).

When θ = 0 but κ^{∗} > 0, we have x = 0 and thus v^{T} v^{∗} = κκ^{∗}. This quantity is zero if and only if κ = 0, which is equivalent in this case to f_{p}(x, θ) = κ and occurs if and only if (2.5a) is satisfied (all the other conditions being trivially fulfilled). A similar reasoning takes care of the case θ > 0, κ^{∗} = 0.

Finally, when θ = κ^{∗} = 0, we have x = x^{∗} = 0 and v^{T} v^{∗} = 0, while the set of conditions (2.5) is also always satisfied. □

3 Duality for the l_{p}-norm optimization problem

Let K = {1, 2, …, r} and I = {1, 2, …, n}. Let {I_{k}}_{k∈K} be a partition of I into r classes. Moreover, let A ∈ ℝ^{m×n}, B ∈ ℝ^{m×r}, η ∈ ℝ^{m}, c ∈ ℝ^{n} and d ∈ ℝ^{r}. We will also use the following notation: v_{I} (resp. M_{I}) denotes the restriction of column vector v (resp. matrix M) to the components (resp. rows) whose indices belong to set I. The primal l_{p}-norm optimization problem is the following

inf ψ(x, z) = c^{T} x + d^{T} z + ∑_{k=1}^{r} z_{k} ∑_{i∈I_{k}} \frac{1}{p_{i}} |\frac{x_{i}}{z_{k}} |^{p_{i}} s.t. Ax + Bz = η and z ≥ 0 . (P)

The variables are x ∈ ℝ^{n} and z ∈ ℝ^{r}. Introducing an extra vector v ∈ ℝ^{r}, we reformulate (P) as

inf c^{T} x + d^{T} z + e^{T} v s.t. Ax + Bz = η, z_{k} ∑_{i∈I_{k}} \frac{1}{p_{i}} |\frac{x_{i}}{z_{k}} |^{p_{i}} ≤ v_{k} ∀k ∈ K and z ≥ 0 , (P’)

1However, taking x proportional to θ, namely x_{i} = K_{i}θ, we have lim_{θ→0} f(x(θ), θ) = f(0, 0) = 0, i.e. f_{p} is continuous on its restrictions to lines passing through the origin.

where e stands for the all-one vector. This program is indeed equivalent to (P), since in every optimal solution to (P’) v_{k} must be equal to its lower bound. (P’) can be again reformulated using L cones as

inf c^{T} x + d^{T} z + e^{T} v s.t. Ax + Bz = η, (x_{I_{k}}, z_{k}, v_{k}) ∈ L^{p_{I_{k}}} ∀k ∈ K .  (P_{c})

This problem being a conic optimization problem in its standard form, we can easily derive its dual and find

sup η^{T} y s.t. A^{T} y + x^{∗} = c, B^{T} y + z^{∗} = d, v^{∗} = e, (x_{I_{k}}^{∗}, z_{k}^{∗}, v_{k}^{∗}) ∈ L_{s}^{q_{I_{k}}} ∀k ∈ K . (D_{c})

Let us simplify this dual problem. Using the equality constraint to express x^{∗}, z^{∗} and v^{∗} in terms of y

x_{i}^{∗} = c_{i} − a_{i}^{T} y, z_{k}^{∗} = d_{k} − b_{k}^{T} y, v_{k}^{∗} = 1 ,  (3.1)

where a_{i} is simply shorthand notation for A_{{i}}^{T}, i.e. the transpose of the i^{th} column of A, we find

sup η^{T} y s.t. (c_{I_{k}} − A_{I_{k}}^{T}y, 1, d_{k} − b_{k}^{T} y) ∈ L^{q_{I_{k}}} ∀k ∈ K  (D’)

and making the conic constraint explicit we finally get the usual l_{p}-norm optimization dual:

sup η^{T} y s.t. ∑_{i∈I_{k}} \frac{1}{q_{i}} |c_{i} − a_{i}^{T} y|^{q_{i}} ≤ d_{k} − b_{k}^{T} y ∀k ∈ K .  (D)

We are now able to prove the weak duality property for the l_{p}-norm optimization problem.

Theorem 4 (Weak duality) If (x, z) is feasible for (P) and y is feasible for (D), we have η^{T} y ≤ ψ(x, z). Equality occurs if and only if for all k ∈ K and i ∈ I_{k}

z_{k}(∑_{i∈I_{k}} \frac{1}{q_{i}} |c_{i} − a_{i}^{T} y|^{q_{i}} + b_{k}^{T} y − d_{k}) = 0, x_{i}(c_{i} − a_{i}^{T} y) ≤ 0, \frac{|x_{i}|^{p_{i}}}{z_{k}^{p_{i}−1}} = z_{k} |c_{i} − a_{i}^{T} y|^{q_{i}} . (3.2)

Proof. Let (x, z) and y be feasible for (P) and (D). Choosing v_{k} = f_{p_{I_{k}}} (x_{I_{k}}, z_{k}) for all k ∈ K, we have that (x, z, v) is feasible for (P_{c}) and that c^{T} x + d^{T} z + c^{T} v = ψ(x, z). Moreover, choosing (x^{∗}, z^{∗}, v^{∗}) according to (3.1) we have that (x^{∗}, z^{∗}, v^{∗}, y) is feasible for (D_{c}). The standard weak duality property for the conic pair { (P_{c}), (D_{c}) } then states that c^{T} + d^{T} z + c^{T} v ≥ η^{T} y, which in turn implies η^{T} y ≥ ψ(x, z).

Since it is well known that the duality gap is equal to (x, z, v)^{T} (x^{∗}, z^{∗}, v^{∗}), equality can only occur if (x, z, v) and (x^{∗}, z^{∗}, v^{∗}) are orthogonal, i.e. (x_{I_{k}}, z_{k}, v_{k})^{T} (x_{I_{k}}^{∗}, z_{k}^{∗}, v_{k}^{∗}) = 0 for all k ∈ K. Having (x_{I_{k}}, z_{k}, v_{k})^{T} ∈ L^{p_{I_{k}}} and (x_{I_{k}}^{∗}, z_{k}^{∗}, v_{k}^{∗}) ∈ L_{s}^{q_{I_{k}}}, Theorem 3 gives us the necessary and sufficient conditions for equality to happen

v_{k}^{∗}(f_{p}(x_{I_{k}}, z_{k}) − v_{k}) = 0, z_{k}(f_{q}(x^{∗}, 1) − z_{k}^{∗}) = 0, v_{k}^{∗} \frac{|x_{i}|^{p_{i}}}{z_{k}^{p_{i}−1}} = z_{k} \frac{|x_{i}^{∗}|^{q_{i}}}{v_{k}^{∗}^{q_{i}−1}} , x_{i}x_{i}^{∗} ≤ 0  (3.3)

for all i ∈ I_{k} and k ∈ K. The first condition is always satisfied because of our choice of v_{k}, while the other three conditions can be readily simplified using (3.1) to give the announced inequalities (3.2). □

In the case of a general pair of primal and dual conic problems, the duality gap is not always equal to zero, neither are the primal or dual optimum objective values always attained by feasible solutions. However, in the special case of linear optimization, we always have a zero duality gap and attainment of both optimum objective values. The status of l_{p}-norm optimization lies somewhere between these two situations: the duality gap is always zero but attainment of the optimum objective value can only be guaranteed for the dual problem, as described by the following theorem:

Theorem 5 If (P) and (D) are feasible, the dual optimum objective is attained with a zero duality gap, i.e.

d^{∗} = max η^{T} y s.t. ∑_{i∈I_{k}} \frac{1}{q_{i}} |c_{i} − a_{i}^{T} y|^{q_{i}} ≤ d_{k} − b_{k}^{T} y ∀k ∈ K
= inf ψ(x, z) s.t. Ax + Bz = η and z ≥ 0 .

Proof. Conic duality tells us that zero duality gap and dual attainment are guaranteed by the existence of a strictly interior primal feasible solution. Let (x, z) be a feasible solution for (P). It is always possible to choose v_{k} > f_{p_{I_{k}}} (x_{I_{k}}, z_{k}) for all k ∈ K such that (x, z, k) is feasible for (P_{c}). However, for (x_{I_{k}}, z_{k}, v_{k}) to belong to the interior of L^{p_{I_{k}}}, we also need z_{k} > 0. It is unfortunately not always possible to find such a z_{k}, since it may happen that z_{k} = 0 for all primal feasible solutions. Let us identify such z_{k}’s: since v_{k} can be chosen as large as needed, the only real constraint on z_{k} is z_{k} ≥ 0. If z_{k} is zero for all primal feasible solutions, it will thus also be zero for all feasible (and optimal) solutions to the following linear problem

min 0 s.t. Ax + Bz = η and z ≥ 0 .  (LP)

Let us call Z the set of all indices k such that z_{k} is 0 for all optimal solutions in (LP), and N the set of all the other indices. (Z, N) is called the optimal partition of (LP).

Let us outline the procedure we are going to follow to prove the theorem: first define a restricted version of (P_{c}) where variables z_{k} and x_{I_{k}} have been removed for all k ∈ Z. This problem has a strictly interior solution, hence its dual problem has zero duality gap and its objective is attained by some optimum solution. The last step to prove our theorem is then convert this solution for the restricted dual problem to an optimal solution for (D_{c}).

Our primal problem (P_{c}) is equivalent to

inf c_{I_{N}}^{T} x_{I_{N}} + d_{N}^{T}z_{N} + e^{T} v_{N} s.t. A_{I_{N}} x_{I_{N}} + B_{N}z_{N} = η, (x_{I_{k}}, z_{k}, v_{k}) ∈ L^{p_{I_{k}}} ∀k ∈ N , (P_{r})

where variables z_{k} and x_{I_{k}} have been removed for all k ∈ Z. We first show that this problem has a strictly feasible solution. For each k ∈ N, there exists at least one solution to (LP) for which z_{k} > 0. The Goldman-Tucker theorem [GT56] guarantees the existence of a solution (x̄, z̄) to (LP) such that z̄_{N} > 0, i.e. z̄_{k} > 0 simultaneously for every k ∈ N. Completing this vector with a sufficiently large v_{N}, we find a strictly feasible solution (x̄_{N}, z̄_{N}, v̄_{N}) to (P_{r}). Let us now derive the dual of this problem:

sup η^{T} y s.t. A_{I_{N}}^{T} y + x_{I_{N}}^{∗} = c_{I_{N}} , B_{N}^{T}y + z_{N}^{∗} = d_{N}, v_{N}^{∗} = e,  (D_{r})
(x_{I_{k}}^{∗}, z_{k}^{∗}, v_{k}^{∗}) ∈ L^{q_{I_{k}}} ∀k ∈ N .

Due to the existence of a strictly interior feasible solution to (P_{r}), the optimum objective in (D_{r}) is attained and the duality gap is zero (see e.g. [Stu97]). Since we have p^{∗} = inf (P) = inf (P_{c}) = inf (P_{r}) = max (D_{r}), all we have to do to prove the theorem is to find a way to extend the optimal solution of (D_{r}) to a solution of (D) with the same objective value. Let ỹ be an optimum solution of (D_{r}), with (x̃_{I_{N}}^{∗} , z̃_{N}^{∗}, ṽ_{N}^{∗}) given by the equality constraints (3.1). This solution is not always feasible for (D_{c}), because the constraints (x̃_{I_{k}}^{∗}, z̃_{k}^{∗}, ṽ_{k}^{∗}) ∈ L_{s}^{q_{I_{k}}} are not necessarily satisfied for k ∈ Z. We are thus going to perturb ỹ to make it feasible for (D_{c}). In order to do this, we need to study the dual of (LP), which is

max η^{T} y s.t. A^{T} y = 0, B^{T} y + z^{∗} = 0 and z^{∗} ≥ 0 .  (DLP)

The Goldman-Tucker theorem also implies the existence of a strictly complementary solution to the pair of problems {(LP), (DLP)}, i.e. optimal (x̄, z̄) and (ȳ, z̄^{∗}) such that z̄+z̄^{∗} > 0. Since z̄_{Z} = 0 by definition of Z, we have z̄_{Z}^{∗} > 0. The optimal value of (LP) being 0, the optimum objective η^{T} ȳ of (DLP) is also 0. Summarizing the properties of ȳ obtained so far, we have

η^{T} ȳ = 0, A^{T} ȳ = 0, B_{N}^{T} ȳ = −z̄_{N}^{∗} ≤ 0 and B_{Z}^{T} ȳ = −z̄_{Z}^{∗} < 0 .

Let us consider y = ỹ + λȳ with λ ≥ 0 as a solution of (D_{c}) and compute the value of x^{∗} and z^{∗} given by (3.1), distinguishing the N and Z parts (we know that v^{∗} = e) :

x_{I_{N}}^{∗} = c_{I_{N}} − A_{I_{N}}^{T} y = c_{I_{N}} − A_{I_{N}}^{T} ỹ = x̃_{I_{N}}^{∗}  using A_{I_{N}}^{T} ȳ = 0
z_{N}^{∗} = d_{N} − B_{N}^{T}y ≥ d_{N} − B_{N}^{T} ỹ = z̃_{N}^{∗}  using B_{N}^{T} ȳ ≤ 0
x_{I_{Z}}^{∗} = c_{I_{Z}} − A_{I_{Z}}^{T}y = c_{I_{Z}} − A_{I_{Z}}^{T} ỹ  using A_{I_{Z}}^{T} ȳ = 0
z_{Z}^{∗} = d_{Z} − B_{Z}^{T}y = d_{Z} − B_{Z}^{T} ỹ + λz̄_{Z}^{∗}  using − B_{Z}^{T} ȳ = z̄_{Z}^{∗} > 0 .

Let us check the validity of the conic constraints for k ∈ N: knowing that ỹ is feasible for (D_{r}), we have (x̃_{I_{k}}^{∗}, 1, z̃_{k}^{∗}) ∈ L_{s}^{q_{I_{k}}} and thus (x_{I_{k}}^{∗}, 1, z_{k}^{∗}) ∈ L_{s}^{q_{I_{k}}} for k ∈ N, since z_{N}^{∗} ≥ z̃_{N}^{∗}. Considering now the constraints for k ∈ Z, we see that x_{I_{Z}}^{∗} does not depend on λ, while z_{Z}^{∗} can be made arbitrarily large by increasing λ, due to the fact that z̄_{Z}^{∗} > 0. Choosing a sufficiently large λ, we can force (x_{I_{k}}^{∗}, 1, z_{k}^{∗}) ∈ L_{s}^{q_{I_{k}}} for k ∈ Z and thus make (x^{∗}, v^{∗}, z^{∗}, y) feasible for (D_{c}).

Looking at the objective value, we find that η^{T} y = η^{T} ỹ + λη^{T} ȳ = η^{T} ỹ = max (D_{r}), i.e. the feasible solution y we constructed has the same objective value for (D_{c}) as ỹ for (D_{r}). This proves that max (D_{r}) ≤ sup (D_{c}), which combined with our previous results gives p^{∗} = inf (P) = max (D_{r}) ≥ sup (D) = d^{∗}. Finally, using the weak duality of Theorem 4, i.e. p^{∗} ≥ d^{∗}, we obtain the desired result p^{∗} = inf (P) = max (D) = d^{∗}. □

References

[GT56] 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.

[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.

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

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

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