A conic formulation for l_{p}-norm optimization^{∗}

Image Technical Report 0005

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

Department of Computing and Software,

McMaster University, Hamilton, Ontario, L8S 4L7, Canada

     Terlaky@mcmaster.ca.

May 2000

∗This research has been partly carried at the Delft University of Technology, while the first author was visiting the SSOR department, supported by a grant from the Communauté Française de Belgique.

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

Abstract

In this paper, we formulate the l_{p}-norm optimization problem as a conic optimization problem, derive its standard duality properties and show it can be solved in polynomial time.

We first define an ad hoc closed convex cone L^{p}, study its properties and derive its dual. This allows us to express the standard l_{p}-norm optimization primal problem as a conic problem involving L^{p}. Using convex conic duality and our knowledge about L^{p}, we proceed to derive the dual of this problem and prove the well-known regularity properties of this primal-dual pair, i.e. zero duality gap and primal attainment. Finally, we prove that the class of l_{p}-norm optimization problems can be solved up to a given accuracy in polynomial time, using the framework of interior-point algorithms and self-concordant barriers.

Keywords. l_{p}-norm optimization, conic optimization, duality theory, interior-point methods, self-concordant barrier

Contents

1 Introduction 3 1.1 Problem definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2 Structure of the paper . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

2 Conic optimization 4 2.1 Conic problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.2 Dual conic problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.3 Duality theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

3 Cones for l_{p}-norm optimization 7 3.1 The L^{p} cone . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 3.2 The dual cone . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

4 Duality for the l_{p}-norm optimization problem 14 4.1 Conic formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 4.2 Duality properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 4.3 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

5 Complexity 21

6 Concluding remarks 23

1 Introduction

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

A few interesting duality results are known for l_{p}-norm optimization. Namely, a pair of feasible primal-dual l_{p}-norm optimization problems satisfies the weak duality property, which is a mere consequence consequence of convexity, but can also be shown to satisfy two additional properties that cannot be guaranteed in the general convex case: the optimum duality gap is equal to zero and at least one feasible solution attains the optimum primal objective. These results were first presented by Peterson and Ecker [7, 6, 8] and later greatly simplified by Terlaky [12], using standard convex duality theory (e.g. the convex Farkas theorem).

The aim of this paper is to derive these results in a completely different setting, using the machinery of conic convex duality. This new approach has the advantage of further simplifying the proofs and giving some insight about the reasons why this class of problems has better properties than a general convex problem. We also show that this class of optimization problems can be solved up to a given accuracy in polynomial time, using the theory of selfconcordant barriers in the framework of interior-point algorithms [5, 1].

1.1 Problem definition

The primal l_{p}-norm optimization problem can be defined as follows. 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 B ∈ ℝ^{m×r} (whose columns will be denoted by a_{i}, i ∈ I and b_{k}, k ∈ K) and four column vectors η ∈ ℝ^{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 η^{T} y s.t. ∑_{i∈I_{k}} \frac{1}{p_{i}} |c_{i} − a_{i}^{T} y|^{p_{i}} ≤ d_{k} − b_{k}^{T} y ∀k ∈ K .  (P)

It is readily seen that this formulation is quite general. Indeed,

⋄ linear optimization problems can be modelled by taking n = 0 (and thus I_{k} = ∅ ∀k ∈ K),

which gives

sup η^{T} y s.t. B^{T} y ≤ d ,

⋄ l_{p}-norm approximation problems correspond to the case b_{k} = 0 ∀k ∈ K, described in [7, 12] and [5, Section 6.3.2],

⋄ a convex quadratic constraint Q(y) ≤ 0 with Q(y) = \frac{1}{2}y^{T} Cy + f^{T} y + g ≤ 0 (where C is positive semidefinite) is equivalent to \frac{1}{2} ∥H^{T} y∥^{2} ≤ −f^{T} y −g, where H is a m×s matrix such that C = HH^{T} (whose columns will be denoted by h_{i}), and can be modelled as

∑_{i=1}^{s} \frac{1}{2} |h_{i}^{T} y|^{2} ≤ −g − f^{T} y ,

which has the same form as the constraints of problem (P) with p_{i} = 2 and c_{i} = 0. This implies that linearly and quadratically constrained convex quadratic optimization problems can be modelled as l_{p}-norm optimization problems (since a convex quadratic objective can be modelled using an additional variable, a linear objective and a convex quadratic constraint).

Defining a vector q ∈ ℝ^{n} such that \frac{1}{p_{i}} + \frac{1}{q_{i}} = 1 for all i ∈ I, the dual problem for (P) can be defined as (see e.g. [12])

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 + Bz = η and z ≥ 0 , \\ z_{k} = 0 ⇒ x_{i} = 0 ∀i ∈ I_{k} . \end{matrix} (D)

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 (P), this problem has a simpler feasible region (mostly defined by linear equalities and nonnegativity constraints) at the price of a highly nonlinear objective.

1.2 Structure of the paper

The rest of this paper is organized as follows. We recall in Section 2 the results of conic optimization theory that are necessary for our purpose. In order to use this setting, we define in Section 3 an appropriate convex cone that will allow us to express l_{p}-norm optimization problems as conic programs. We also study some aspects of this cone (closedness, interior, dual). We are then in position to formulate the primal-dual pair (P)–(D) using a conic formulation and apply in Section 4 the general duality theory for conic optimization, in order to prove the above-mentioned duality results about l_{p}-norm optimization. Section 5 deals with algorithmic complexity issues and presents a self-concordant barrier construction for our problem. We conclude with some remarks in Section 6.

2 Conic optimization

In this section, we describe the formulation of a primal-dual pair of conic optimization problems and state some results from the associated duality theory (this material is quite classical and proofs can be found e.g. in [10, 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 has the advantage of providing a very symmetric form for the dual problem and often gives a new insight about its structure.

2.1 Conic problems

The basic ingredient we need is a convex cone.

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

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

Moreover, it is convex if and only if it is closed under addition, i.e.

x ∈ C and y ∈ C ⇒ x + y ∈ C .

Recall that a set is convex if and only if it contains the whole segment joining any two of its points. It is straightforward to prove that this is equivalent to closedness under addition in the special case of cones.

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 C is solid if and only if int C ≠ ∅ (where int S denotes the interior of set S).

Definition 2.3 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. At this stage, we would like to emphasize the fact that although our cone C is closed, it may happen that the infimum in (CP) is not attained (an example of this situation will be given in Subsection 4.3).

It is well-known that this class of problems is equivalent to the class of convex problems, see e.g. [5]. 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.

2.2 Dual conic problems

Definition 2.4 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 2.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 2.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) is defined by

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

2.3 Duality theory

The two conic problems of this primal-dual pair are strongly related to each other, as demonstrated by the following duality theorems. First, we start with the so-called weak duality property: using the linear constraints of problems (CP) and (CD), we can write the following elementary chain of equalities

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 .

Noting that the last inner product is always nonnegative when x ∈ C, s ∈ C^{∗} (because of Definition 2.4 of the dual cone C^{∗}), we have

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. Denoting by p^{∗} and d^{∗} the optimum objective values of problems (CP) and (CD), this theorem implies that p^{∗} − d^{∗} ≥ 0. This nonnegative quantity, called the duality gap, can be different from zero in the general case. However, under certain circumstances, it will be possible to prove it is equal to zero, which implies then that the optimum values of problems (CP) and (CD) are equal. Before describing the conditions that can guarantee 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 C (resp. C^{∗}), i.e.

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

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 (obviously, infeasible and unbounded problems cannot be attained).

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 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 really relies on this hypothesis. 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.

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 solution for a bounded primal problem 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.

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} ∈ C^{i} for all i ∈ {1, 2, …, k}, where C^{i} ⊆ ℝ^{n_{i}}, we will simply consider the Cartesian product of these cones C = C^{1}×C^{2}×⋯×C^{k} ⊆ ℝ^{∑_{i=1}^{k} n_{i}} and express all these constraints simultaneously as x ∈ C with x = (x^{1}, x^{2}, …, x^{k}). The dual cone of C will be expressed by

C^{∗} = (C^{1})^{∗} × (C^{2})^{∗} × ⋯ × (C^{k})^{∗} ⊆ ℝ^{∑_{i=1}^{k} n_{i}} ,

as implied by the following theorem :

Theorem 2.5 Let C^{1} and C^{2} two closed convex cones, and C = C^{1} × C^{2} their Cartesian product. Cone C is also a closed convex cone, and its dual C^{∗} is given by

C^{∗} = (C^{1})^{∗} × (C^{2})^{∗} .

3 Cones for l_{p}-norm optimization

Let us now introduce the L^{p} cone, which will allow us to give a conic formulation of l_{p}-norm optimization problems.

3.1 The L^{p} cone

Definition 3.1 Let n ∈ ℕ and 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 convention means that if (x, θ, κ) ∈ L^{p}, θ = 0 implies x = 0^{n}. We start by proving that L^{p} is a convex cone.

Theorem 3.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^{n} × 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 for all x, x′ ∈ ℝ and θ, θ′ ∈ ℝ_{+}:

\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 ℝ_{+} for p_{i} ≥ 1, 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. □

In order to characterize strictly feasible points, we would like to identify the interior of this cone.

Theorem 3.2 The interior of L^{p} is given by

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

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

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

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

Corollary 3.1 The cone L^{p} is solid.

Proof. It suffices to prove that there exists at least one point that belongs to int L^{p}, for example by taking the point (e, 1, n), where e stands for an n-dimensional the all-one vector. Indeed, we have ∑_{i=1}^{n} \frac{|1|^{1}}{p_{i}1^{p_{i}−1}} = ∑_{i=1}^{n} \frac{1}{p_{i}} < ∑_{i=1}^{n} 1 = n. □

Note 3.1 When n = 0, our cone L^{p} is readily seen to be equivalent to the two-dimensional positive orthant ℝ_{+}^{2}. 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 usually called the hyperbolic or rotated second-order cone [4, 11](it is a simple linear transformation of the usual second-order cone).

To illustrate our purpose, we provide in Figure 1 the three-dimensional graphs of the boundary surfaces of L^{(5)} and L^{(2)} (corresponding to the case n = 1).

Figure 1: The boundary surfaces of L^{(5)} and L^{(2)} (in the case n = 1).

3.2 The dual 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 L^{p} cones [12, 5]. In order to keep the exposition selfcontained, we also include its proof.

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

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

with equality holding 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}^{p} as the L^{p} 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 3.3 (Dual of L^{p}) Let p, q ∈ ℝ_{++}^{n} such that \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^{p} and L_{s}^{q} 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 the resulting inequalities 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{θ^{∗}}{κ^{∗}} .  (3.1)

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

∑_{i=1}^{n} \frac{|x_{i}|}{θ} \frac{|x_{i}^{∗}|}{κ^{∗}} ≤ \frac{κ}{θ} + \frac{θ^{∗}}{κ^{∗}} ,  (3.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^{T} x^{∗} + κκ^{∗} + θθ^{∗} = ∑_{i=1}^{n} x_{i}x_{i}^{∗} + κκ^{∗} + θθ^{∗} ≥ ∑_{i=1}^{n} − |x_{i}| |x_{i}^{∗}| + κκ^{∗} + θθ^{∗} ≥ 0 , (3.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 first ensure that 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}} = κ .  (3.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 3.1 on the pairs \frac{|x_{i}|}{θ}, \frac{|x_{i}^{∗}|}{κ^{∗}} and the choice of v in (3.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^{p} cone is thus equal, up to a permutation of two variables, to another L^{p} cone with a dual vector of exponents.

Corollary 3.2 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^{p} and L_{s}^{q} and the symmetry between p and q. □

Corollary 3.3 L^{p} and L_{s}^{q} are solid and pointed.

Proof. We have already proved that L^{p} is solid which, for obvious symmetry reasons, implies that its switched counterpart L_{s}^{q} is also solid. Since pointedness is the property that is dual to solidness (Theorem 2.2), noting that L^{p} = (L_{s}^{q})^{∗} and L_{s}^{q} = (L^{p})^{∗} is enough to prove that L^{p} and L_{s}^{q} are also pointed. □

Corollary 3.4 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 3.2 and ((L^{p})^{∗})^{∗} = cl L^{p} [9, page 121], we have cl L^{p} = L^{p}, hence L^{p} is closed. The switched cone L_{s}^{q} is obviously closed as well. □

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 [9, 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, θ) = +∞, since the term \frac{|x_{i}|^{p_{i}}}{p_{i}θ^{p_{i}−1}} tends to +∞ when (x_{i}, θ) tends to (x_{i}^{0}, 0), 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.

Note however that f_{p} is not continuous in (0, 0). Choosing an arbitrary positive constant C and defining for example x_{i}(θ) = (Cp_{i})^{1/p_{i}}θ^{1/q_{i}}, so that x(θ) → 0 when θ → 0, we have that lim_{θ→0} f(x(θ), θ) = nC ≠ f(0, 0) = 0. The limit of f_{p} at (0, 0) can indeed take any positive value^{1}.

Note 3.2 As special cases, we note that when n = 0, (L^{p})^{∗} is equivalent ℝ_{+}^{2}, which is the usual dual for L^{p} = ℝ_{+}^{2}. In the case of p_{i} = 2 ∀i, we find

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

which is the expected result. Note that apart from these two special cases, L^{p} is in general not self-dual.

1However, taking x(θ) proportional to θ, namely x_{i}(θ) = C_{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.

Note 3.3 (Self-duality of L^{p} cones with n = 1) Figure 2, representing L^{( \frac{5}{4} )}, illustrates our point: up to a permutation of variables, it is equal to (L^{(5)})^{∗} (since \frac{1}{5} + \frac{1}{5/4} = 1) and is different from L^{(5)}. However, in the particular case where n = 1, this difference is not as great as it could be. Namely, one can show easily that L^{(p)} and its dual are equal up to a simple rescaling of some of the variables. Indeed, we have

(x, θ, κ) ∈ L^{(p)} ⇔ |x|^{p} ≤ pκθ^{p−1}
⇔ |x|^{q} ≤ p^{\frac{q}{p}} κ^{\frac{q}{p}} θ^{(p−1) \frac{q}{p}}

using \frac{q}{p} = q \frac{1}{p} = q(1 − \frac{1}{q}) = q − 1 and (p − 1)\frac{q}{p} = (1 − \frac{1}{p})q = \frac{1}{q}q = 1

⇔ |x|^{q} ≤ p^{q−1}κ^{q−1}θ
⇔ |x|^{q} ≤ q(pκ)^{q−1} \frac{θ}{q} ⇔ (x, \frac{θ}{q} , pκ) ∈ L_{s}^{(q)} = (L^{(p)})^{∗} .

Figure 2: The boundary surface of L^{( \frac{5}{4} )} and L^{(5)} (in the case n = 1).

Our last theorem in this section describes the cases where two vectors from L^{p} and L_{s}^{q} are orthogonal to each other, which will be used in the study of the duality properties.

Theorem 3.4 (orthogonality conditions) Let v = (x, θ, κ) ∈ L^{p} and v^{∗} = (x^{∗}, θ^{∗}, κ^{∗}) ∈ L_{s}^{q}. We have v^{T} v^{∗} = 0 if and only if the following set of conditions holds

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

Proof. When θ > 0 and κ^{∗} > 0, a careful reading of the first part of the proof of Theorem 3.3 shows that equality occurs if and only if all conditions in (3.5) are fulfilled. Namely, (3.5a) and (3.5b) are responsible for equality in (3.1), (3.5c) ensures that we are in the case of equality of Lemma 3.1 for inequality (3.2) and the last condition (3.5d) is necessary for equality in (3.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 (3.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 (3.5) is also always satisfied. □

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

This is the main section , where we show how a primal-dual pair of l_{p}-norm optimization problems can be modelled using the L^{p} and L_{s}^{q} cones and how this allows us to derive the relevant duality properties.

4.1 Conic formulation

Let us restate here for convenience the definition of the standard primal l_{p}-norm optimization problem.

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

(where K = {1, 2, …, r}, I = {1, 2, …, n}, {I_{k}}_{k∈K} is a partition of I into r classes, A ∈ ℝ^{m×n} and B ∈ ℝ^{m×r} (whose columns will be denoted by a_{i}, i ∈ I and b_{k}, k ∈ K), y ∈ ℝ^{m}, η ∈ ℝ^{m}, c ∈ ℝ^{n}, d ∈ ℝ^{r} and p ∈ ℝ^{n} such that p_{i} > 1 ∀i ∈ I).

Let us now model problem (P) with a conic formulation. The following notation will be used: 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. We introduce an auxiliary vector of variables x^{∗} ∈ ℝ^{n} to represent the argument of the power functions, namely we let

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

and we also need additional variables z^{∗} ∈ ℝ^{r} for the linear term forming the right-hand side of the inequalities

z_{k}^{∗} = d_{k} − b_{k}^{T} y for all k ∈ K or, in matrix form, z^{∗} = d − B^{T} y .

Our problem is now equivalent to

sup η^{T} y s.t. A^{T} y + x^{∗} = c, B^{T} y + z^{∗} = d and ∑_{i∈I_{k}} \frac{1}{p_{i}} |x_{i}^{∗}|^{p_{i}} ≤ z_{k}^{∗} ∀k ∈ K ,

where we can easily plug our definition of the L^{p} cone

sup η^{T} y s.t. A^{T} y + x^{∗} = c, B^{T} y + z^{∗} = d and (x_{I_{k}}^{∗}, 1, z_{k}^{∗}) ∈ L^{p^{k}} ∀k ∈ K

(where for convenience we defined vectors p^{k} = (p_{i} | i ∈ I_{k}) for k ∈ K). We finally introduce an additional vector of fictitious variables v^{∗} ∈ ℝ^{r} whose components are fixed to 1 by linear constraints to find

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

(where e stands again for the all-one vector). Rewriting the linear constraints with a single matrix equality, we end up with

sup η^{T} y s.t. (\begin{matrix}A^{T} \\ B^{T} \\ 0 \end{matrix} ) y + (\begin{matrix}x^{∗} \\ z^{∗} \\ v^{∗} \end{matrix}) = (\begin{matrix}c \\ d \\ e \end{matrix}) and (x_{I_{k}}^{∗}, v_{k}^{∗}, z_{k}^{∗}) ∈ L^{p^{k}} ∀k ∈ K ,  (P_{c})

which is exactly a conic optimization problem in the dual^{2} form (CD), using variables (ỹ, s̃), data (Ã, b̃, c̃) and a cone C^{∗} such that

ỹ = y, s̃ = (\begin{matrix}x^{∗} \\ z^{∗} \\ v^{∗} \end{matrix}) , Ã = (A B 0) , b̃ = η, c̃ = (\begin{matrix}c \\ d \\ e \end{matrix}) and C^{∗} = L^{p^{1}} × L^{p^{2}} × ⋯ × L^{p^{r}} ,

where C^{∗} 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 L^{p} proved in the previous section, it is straightforward to show that C^{∗} is a solid, pointed, closed convex cone whose dual is

(C^{∗})^{∗} = C = L_{s}^{q^{1}} × L_{s}^{q^{2}} × ⋯ × L_{s}^{q^{r}} ,

another solid, pointed, closed convex cone (where we have defined a vector q ∈ ℝ^{n} such that \frac{1}{p_{i}} + \frac{1}{q_{i}} = 1 for all i ∈ I and vectors q^{k} such that q^{k} = (q_{i} | i ∈ I_{k}) for k ∈ K). This allows us to derive a dual problem to (P_{c}) in a completely mechanical way and find the following conic optimization problem, expressed in the primal form (CP):

inf (c^{T} d^{T} e^{T} ) (\begin{matrix}x \\ z \\ v \end{matrix}) s.t. (A B 0) (\begin{matrix}x \\ z \\ v \end{matrix}) = η and (x_{I_{k}}, v_{k}, z_{k}) ∈ L_{s}^{q^{k}} for all k ∈ K ,

which is equivalent to

inf c^{T} x + d^{T} z + e^{T} v s.t. Ax + Bz = η and (x_{I_{k}}, v_{k}, z_{k}) ∈ L_{s}^{q^{k}} for all k ∈ K ,  (D_{c})

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

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

keeping in mind the convention on zero denominators that in effect implies z_{k} = 0 ⇒ x_{I_{k}} = 0. Finally, we can remove the v variables from the formulation since they are only constrained by the sum inequalities which have to be tight at any optimal solution. We can thus directly incorporate these sums into the objective function, which leads to

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 + Bz = η and z ≥ 0 , \\ z_{k} = 0 ⇒ x_{i} = 0 ∀i ∈ I_{k} . \end{matrix}

Unsurprisingly, the dual formulation (D) we have just found without much effort is exactly the standard form for a dual l_{p}-norm optimization problem [12].

2This is the reason why we added a ^{∗} superscript to the notation of our additional variables, in order to emphasize the duality correspondence with the associated primal variables.

4.2 Duality properties

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

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

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

Proof. Let y and (x, z) be feasible for (P) and (D). Choosing v_{k} = f_{q^{k}}(x_{I_{k}}, z_{k}) for all k ∈ K, we have that (x, z, v) is feasible for (D_{c}) with the same objective function, i.e. with c^{T} x + d^{T} z + e^{T} v = ψ(x, z). Moreover, computing (x^{∗}, z^{∗}, v^{∗}) from y in order to satisfy the linear constraints in (P_{c}), i.e. according to

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

we have that (x^{∗}, z^{∗}, v^{∗}, y) is feasible for (P_{c}). The standard weak duality property for the conic pair (P_{c})–(D_{c}) from Theorem 2.3 then states that c^{T} x + d^{T} z + e^{T} v ≥ η^{T} y, which in turn implies ψ(x, z) ≥ η^{T} y.

We proceed now to investigate the equality conditions. At the optimum, variables v_{k} must assume their lower bounds so that we can still assume that v_{k} = f_{q^{k}}(x_{I_{k}}, z_{k}) holds for all k ∈ K. We also keep variables (x^{∗}, z^{∗}, v^{∗}) defined by (4.2). From Theorem 2.3, we know that equality can only occur if the primal and dual vectors of variables are orthogonal to each other for each conic constraint, 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}}^{∗}, v_{k}^{∗}, z_{k}^{∗})^{T} ∈ L^{p^{k}} and (x_{I_{k}}, v_{k}, z_{k}) ∈ L_{s}^{q^{k}}, Theorem 3.4 gives us the necessary and sufficient conditions for equality to happen

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

for all i ∈ I_{k} and k ∈ K. The second condition is always satisfied while the other three conditions can be readily simplified using (4.2) to give the announced inequalities (4.1). □

The weak duality property is a rather straightforward consequence of the convexity of the problems, and in fact can be proved without too many difficulties without sophisticated tools from duality theory. However, this is not the case with the next theorem, which deals with a strong duality property.

In the case of a general pair of primal and dual conic problems, the duality gap at the optimum is not always equal to zero, neither are the primal or dual optimum objective values always attained by feasible solutions. However, it is well-known that 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 equal zero but attainment of the optimum objective value can only be guaranteed for the primal problem.

In the course of our proof, we will need to use the well-known Goldman-Tucker theorem [3] for linear programming, which we restate here for reference.

Theorem 4.2 (Goldman Tucker) Let us consider the following primal-dual pair of linear optimization problems in standard form:

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 (ŷ, ŝ) to the dual problem satisfies ŝ_{B} = 0.

This partition is called the optimal partition^{3}. Moreover, there exists at least an optimal primal-dual solution (x̂, ŷ, ŝ) such that x̂ + ŝ > 0, hence satisfying x̂_{B} > 0 and ŝ_{N} > 0. Such a pair is called a strictly complementary pair.

The strong duality theorem for l_{p}-norm optimization we are about to prove is the following:

Theorem 4.3 (Strong duality) If both problems (P) and (D) are feasible, the primal optimal objective value is attained with a zero duality gap, i.e.

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

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

Proof. Theorem 2.4 tells us that zero duality gap and primal attainment are guaranteed by the existence of a strictly interior dual feasible solution (excluding the case of an unbounded dual). Let (x, z) be a feasible solution for (D). We would like to complement it with a vector v such that the corresponding solution (x, z, v) is strictly feasible for the conic formulation (D_{c}).

Since cone C is the cartesian products of the set of cones L_{s}^{q^{k}} for k ∈ K, we need in fact for (x, z, v) to be a strictly feasible solution of (D_{c}) that (x_{I_{k}}, z_{k}, v_{k}) ∈ int L_{s}^{q^{k}} holds for all k ∈ K. Using now Theorem 3.2 to identify the interior of the L_{s}^{q} cones, we see that both conditions v_{k} > f_{p^{k}}(x_{I_{k}}, z_{k}) and z_{k} > 0 have to be valid for all k ∈ K.

Since vector v contains only free variables and is not constrained by the linear constraints, it is always possible to choose it such that v_{k} > f_{p^{k}}(x_{I_{k}}, z_{k}) for all k ∈ K. However, the situation is much different for z: it is unfortunately not always possible to find a strictly positive z, since it may happen that the linear constraints combined with the nonnegativity constraint on z force one or more of the components z_{k} to be equal to zero for all primal feasible solutions. Here is an outline of the three-step strategy we are going to follow:

a. Since some components of z may prevent the existence of a strictly feasible solution to (D_{c}), we are going to define a restricted version of (D_{c}) where those problematic components of z and the associated variables x have been removed. Hopefully, this restricted problem (D_{r}) will not behave too differently from the original because the zero components of z and x did not play a crucial role in it. b. Since this restricted problem will now admit a strictly feasible solution, its dual problem

3This optimal partition can be computed in polynomial time by interior-point methods.

(P_{r}) (which is a problem in primal form) has a duality gap equal to zero with its optimal objective value attained by some solution.

c. The last step of our proof will be to convert this optimal solution with a zero duality gap for the restricted primal problem (P_{r}) into an optimal solution for the original primal problem (P_{c}).

The whole procedure can be summarized with the following diagram:

(P) ≡  (P_{c})  ⟷^{Weak}  (D_{c})  ≡ (D)
c. ↕  ↕ a.

(P_{r})

Strong (zero gap)

⟷

(D_{r})

↓ (Attainment) b.

↑

(Strictly feasible)

Let us first identify the problematic z_{k}’s that are identically equal to zero for all feasible solutions. This can be done by solving the following linear optimization problem:

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

This problem has the same feasible region as our dual problem (D) (actually, its feasible region can be slightly larger from the point of view of the x variables, since the special constraints z_{k} = 0 ⇒ x_{I_{k}} = 0 have been omitted, but this does not have any effect on our reasoning). We are thus looking for components of z that are equal to zero on the whole feasible region of (LP).

Since this problem has a zero objective function, all its feasible solutions are optimal and we can therefore deduce that if a variable z_{k} is zero for all feasible solutions to problem (LP), it is zero for all optimal solution to problem (LP). In order to use the Goldman-Tucker theorem, we also write the dual^{4} of problem (LP):

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

Both (LP) and (DLP) are feasible (the former because (D) is assumed to be feasible, the latter because (y, z^{∗}) = (0, 0) is always a feasible solution), which means 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 z_{i} that are identically zero on the feasible regions of problems (LP) and (D). We are thus now ready the apply the strategy outlined above.

a. Let us introduce the reduced primal-dual pair of l_{p}-norm optimization problems where variables z_{k} and x_{I_{k}} with k ∈ N have been removed. We start with the dual problem

inf c_{I_{B}}^{T}x_{I_{B}} + d_{B}^{T}z_{B} + e^{T} v_{B} s.t. A_{I_{B}}x_{I_{B}} + B_{B}z_{B} = η, (x_{I_{k}}, v_{k}, z_{k}) ∈ L_{s}^{q^{k}} ∀k ∈ B , (D_{r})

where I_{B} stands for ∪_{k∈B}I_{k}. It is straightforward to check that this problem is completely equivalent to problem (D_{c}), since the variables z_{N} and x_{I_{N}} we removed, being forced to zero for all feasible solutions, had no contribution to the objective or to the linear constraints in (D_{c}).

4Although problem (LP) is not exactly formulated in the standard form used to state Theorem 4.2, the same results hold in the case of a general linear optimization problem

The corresponding conic constraints become (0, v_{k}, 0) ∈ L_{s}^{q^{k}} ⇔ v_{k} ≥ 0, which imply at the optimum that v_{k} = 0, showing that variables v_{N} can also be safely removed without changing the optimum objective value. We can thus conclude that inf (D_{r}) = inf (D_{c}) = inf (D).

b. Because of the second part of the Goldman-Tucker theorem, there is at least one feasible solution to (LP) such that z_{B} > 0. Combining the (x_{I_{B}}, z_{B}) part of this solution with a vector v_{B} with sufficiently large components gives us a strictly feasible solution for (D_{r}) (z_{k} > 0 and v_{k} > f_{q^{k}}(x_{I_{k}}, z_{k}) for all k ∈ B), which is exactly what we need to apply our strong duality Theorem 2.4. Let us first write down the dual problem of (D_{r}), the restricted primal:

sup η^{T} y s.t. \{ \begin{matrix}A_{I_{B}}^{T}y + x_{I_{B}}^{∗} = c_{I_{B}}, B_{B}^{T} y + z_{B}^{∗} = d_{B}, v_{B}^{∗} = e, \\ (x_{I_{k}}^{∗}, v_{k}^{∗}, z_{k}^{∗}) ∈ L^{p^{k}} ∀k ∈ B . \end{matrix}  (P_{r})

We cannot be in the first case of Theorem 2.4, since unboundedness of (D_{r}) would imply unboundedness of the original problem (D) which in turn would prevent the existence of a feasible primal solution (simple consequence of the weak duality theorem). We can thus conclude that there exists an optimal solution to (P_{r}) (x̂_{I_{B}}^{∗}, ẑ_{B}^{∗}, v̂_{B}^{∗}, ŷ) such that η^{T} ŷ = max (P_{r}) = inf (D_{r}).

c. Combining the results obtained so far, we have proved that max (P_{r}) = inf (D). The last step we need to perform is to prove that max (P) = max (P_{r}), i.e. that the optimum objective of (P) is attained and that it is equal to the optimal objective value of (P_{r}). Unfortunately, the apparently most straightforward way to do this, namely using the optimal solution ŷ we have at hand for problem (P_{r}), does not work since it is not necessarily feasible for problem (P_{c}). The reason is that (P_{c}) contains additional conic constraints (the ones corresponding to k ∈ N) which are not guaranteed to be satisfied by the optimal solution ŷ of the restricted problem. We can however overcome this difficulty by perturbing this solution by a suitably chosen vector such that

⋄ feasibility for the constraints k ∈ B is not lost,

⋄ feasibility for the constraints k ∈ N can be gained.

Let us consider (x̄, z̄, ȳ, z̄^{∗}), a strictly complementary solution to the primal-dual pair (LP)–(DLP) whose existence is guaranteed by the Goldman-Tucker theorem. We have thus z̄_{N}^{∗} > 0 and z̄_{B}^{∗} = 0. Since all primal solutions have a zero objective, the optimal dual objective value also satisfies η^{T} ȳ = 0. Summarizing the properties of ȳ obtained so far, we can write

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

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

x_{I_{B}}^{∗} = c_{I_{B}} − A_{I_{B}}^{T}y = c_{I_{B}} − A_{I_{B}}^{T} ŷ  = x̂_{I_{B}}^{∗}  (using A_{I_{B}}^{T} ȳ = 0)
z_{B}^{∗} = d_{B} − B_{B}^{T} y = d_{B} − B_{B}^{T} ŷ  = ẑ_{B}^{∗}  (using B_{B}^{T} ȳ = 0)
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} ȳ = z̄_{N}^{∗} > 0) .

The conic constraints corresponding to k ∈ B remain valid for all λ, since the associated variables do not vary with λ. Considering now the constraints for k ∈ N, we see that x_{I_{N}}^{∗} does not depend on λ, while z_{N}^{∗} can be made arbitrarily large by increasing λ, due

to the fact that z̄_{N}^{∗} > 0. Choosing a sufficiently large λ, we can force (x_{I_{k}}^{∗}, 1, z_{k}^{∗}) ∈ L_{s}^{q^{k}} for k ∈ N and thus make (x^{∗}, v^{∗}, z^{∗}, y) feasible for (P_{c}). Obviously, we also have that y is feasible for (P) with the same objective value.

Evaluating this objective value, we find that η^{T} y = η^{T} ŷ + λη^{T} ȳ = η^{T} ŷ = max (P_{r}), i.e. the feasible solution y we constructed has the same objective value for (P_{c}) and (P) as ŷ for (P_{r}). This proves that max (P_{r}) ≤ sup (P), which combined with our previous results gives d^{∗} = inf (D) = η^{T} ŷ = max (P_{r}) ≤ sup (P) = p^{∗}. Finally, using the weak duality of Theorem 4.1, i.e. p^{∗} ≤ d^{∗}, we obtain d^{∗} = inf (D) = η^{T} ŷ = sup (P) = p^{∗}, which implies that ŷ is optimum for (P), sup (P) = max (P) and finally the desired result p^{∗} = max (P) = inf (D) = d^{∗}.

□

4.3 Examples

We conclude this section by providing a few examples of the possible situations that can arise for a couple of primal-dual l_{p}-norm optimization problems. Let us consider the following problem data:

r = 1, K = {1}, n = 1, I_{1} = {1}, m = 1, A = 1, B = 0, c = 5, d ∈ ℝ, η = 1, p = 3

(d_{1} is left unspecified), which translates into the following primal problem:

sup y_{1} s.t. \frac{1}{3} |5 − y_{1}|^{3} ≤ d_{1} .

Noting q = \frac{3}{2}, we can also write down the dual

inf 5x_{1} + d_{1}z_{1} + z_{1} \frac{1}{3/2} |\frac{x_{1}}{z_{1}} |^{3/2} s.t. x_{1} = 1, z_{1} ≥ 0, z_{1} = 0 ⇒ x_{1} = 0 .

This pair of problems can readily be simplified to

sup y_{1} s.t. |5 − y_{1}| ≤ \sqrt[3]{3d_{1}} and inf 5 + d_{1}z_{1} + \frac{2}{3\sqrt{z_{1}}} s.t. z_{1} > 0

⋄ When d = 9, our primal constraint becomes |5 − y_{1}| ≤ 3, which gives a primal optimum equal to y_{1} = 8. Looking at the dual, we have

9z_{1} + \frac{2}{3\sqrt{z_{1}}} = \frac{1}{3}(27z_{1}) + \frac{2}{3}(\frac{1}{\sqrt{z_{1}}} ) ≤ (27z_{1})^{\frac{1}{3}} (\frac{1}{\sqrt{z_{1}}} )^{\frac{2}{3}} = 3

(using the weighted arithmetic-geometric mean), which shows that the dual optimum is also equal to 8, and is attained for (x, z) = (1, \frac{1}{9}). This is the most common situation: both optimum values are finite and attained, with a zero duality gap.

⋄ When d = 0, our primal constraint becomes |5 − y_{1}| ≤ 0, which implies that the only feasible solution is y_{1} = 5, giving a primal optimum equal to 5. The dual optimum value is then inf 5 + \frac{2}{3\sqrt{z_{1}}} = 5, equal to the primal but not attained (z_{1} → +∞). This shows that there are problems for which the dual optimum is not attained, i.e. we do not have the perfect duality of linear optimization (one can observe that in this case the primal had no strict interior).

⋄ Finally, when d = −1, the primal becomes infeasible while the dual is unbounded (take again z → +∞).

5 Complexity

The goal of this section is to prove it is possible to solve an l_{p}-norm optimization problem up to a given accuracy in polynomial time. According to the theoretical framework of Nesterov and Nemirovksy [5], in order to solve the conic problem from Section 2

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

we only need to find a computable self-concordant barrier for the cone C.

Definition 5.1 A convex function f : int C ↦ ℝ is called a self-concordant barrier for the cone C ⊆ ℝ^{n} with parameter θ if and only if f is three times continuously differentiable on int C, f(x) → +∞ when x → ∂C and f satisfies the following two conditions

∇^{3}f(x)[h, h, h] ≤ 2 (h^{T} ∇^{2}f(x)h)^{\frac{3}{2}}
∇f(x)^{T} (∇^{2}f(x))^{−1}∇f(x) ≤ θ

for all x ∈ int C and h ∈ ℝ^{n}.

We have the remarkable result [5]

Theorem 5.1 Given a self-concordant barrier for the cone C ⊆ ℝ^{n} with parameter θ and a feasible interior starting point x_{0} ∈ int C, a short-step interior-point algorithm can solve problem (CP) up to ϵ accuracy within

O (\sqrt{θ} log \frac{c^{T} x_{0} − p^{∗}}{ϵ} ) iterations,

such that at each iteration the self-concordant barrier and its first and second derivatives have to be evaluated and a linear system has to be solved in ℝ^{n}.

We are now going to describe a self-concordant barrier that allows us to solve conic problems involving our L^{p} cone (we follow an approach similar to the one used in [13]). The following convex cone

{(x, y) ∈ ℝ × ℝ_{+} | |x|^{p} ≤ y}

(with p > 1) admits the well-known self-concordant barrier

f_{p} : ℝ × ℝ_{++} ↦ ℝ : (x, y) ↦ −2 log y − log(y^{2/p} − x^{2})

with parameter 4 (see [5, Propostion 5.3.1]). Let n ∈ ℕ, p ∈ ℝ^{n} and I = {1, 2, …, n}. We have that

{(x, y) ∈ ℝ^{n} × ℝ_{+}^{n} | |x|_{i}^{p} ≤ y_{i} ∀i ∈ I}

admits

f_{p} : ℝ^{n} × ℝ_{++}^{n} ↦ ℝ : (x, y) ↦ ∑_{i=1}^{n} (−2 log y_{i} − log(y_{i}^{2/p} − x_{i}^{2}))

with parameter 4n (using [5, Propostion 5.1.2]). This also implies that the set

S_{p} = \{(x, y, κ) ∈ ℝ^{n} × ℝ_{+}^{n} × ℝ | |x|_{i}^{p} ≤ y_{i} ∀i ∈ I and κ = ∑_{i=1}^{n} \frac{y_{i}}{p_{i}} \}

admits a self-concordant barrier f′_{p}(x, y, κ) = f_{p}(x, y) with parameter 4n (taking the cartesian product with ℝ essentially leaves the self-concordant barrier unchanged, taking the intersection with an affine subspace does not influence self-concordancy). Finally, we use another result from Nesterov and Nemirovsky to find a self-concordant barrier for the conic hull of S_{p}, which is defined by

H_{p} = cl \{(x, t) ∈ S_{p} × ℝ_{++} | \frac{x}{t} ∈ S_{p}\}
= cl \{(x, y, κ, θ) ∈ S_{p} × ℝ_{++} | (\frac{x}{θ}, \frac{y}{θ} , \frac{κ}{θ}) ∈ S_{p}\}
= cl \{(x, y, κ, θ) ∈ ℝ^{n} × ℝ_{+}^{n} × ℝ × ℝ_{++} | |\frac{x_{i}}{θ} |^{p} ≤ \frac{y_{i}}{θ} ∀i ∈ I and \frac{κ}{θ} = ∑_{i=1}^{n} \frac{y_{i}}{p_{i}θ} \}

= cl \{(x, y, κ, θ) ∈ ℝ^{n} × ℝ_{+}^{n} × ℝ × ℝ_{++} | \frac{|x_{i}|^{p}}{θ^{p−1}} ≤ y_{i} ∀i ∈ I and κ = ∑_{i=1}^{n} \frac{y_{i}}{p_{i}} \}

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

(to find the last equality, you have to consider accumulation points with θ = 0, which in fact must satisfy x = 0, which in turn can be seen to match exactly the convention about zero denominators we chose in Definition 3.1), and find that

h_{p} : ℝ^{n} × ℝ_{++}^{n} × ℝ × ℝ_{++} ↦ ℝ : (x, y, κ, θ) ↦ 400 (f_{p}(\frac{x}{θ}, \frac{y}{θ}) − 8n log θ)

is a self-concordant barrier for H_{p} with parameter 3200n (see [5, Proposition 5.1.4]). We now make the following interesting observation linking H_{p} to our cone L^{p}.

Theorem 5.2 The L^{p} cone is equal to the projection of H_{p} on the space of (x, κ, θ), i.e.

(x, θ, κ) ∈ L^{p} ⇔ ∃y ∈ ℝ_{+}^{n} | (x, y, κ, θ) ∈ H_{p} .

Proof. This proof is straightforward. First note that both sets take the same convention in case of a zero denominator. Let (x, θ, κ) ∈ L^{p}. Choosing y such that y_{i} = \frac{|x_{i}|}{θ^{p−1}} for all i ∈ I ensures that

∑_{i=1}^{n} \frac{y_{i}}{p_{i}} = ∑_{i=1}^{n} \frac{|x_{i}|^{p}}{p_{i}θ^{p−1}} ≤ κ

(this last inequality because of the definition of L^{p}). It is now possible to increase y_{1} until the equality κ = ∑_{i=1}^{n} \frac{y_{i}}{p_{i}} is satisfied, which shows (x, y, κ, θ) ∈ H_{p}. For the reverse inclusion, suppose (x, y, κ, θ) ∈ H_{p}. This implies that

κ = ∑_{i=1}^{n} \frac{y_{i}}{p_{i}} ≥ ∑_{i=1}^{n} \frac{|x_{i}|^{p}}{p_{i}θ^{p−1}} ,

which is exactly the defining inequality of L^{p}. □

Suppose now we have now to solve

inf_{x} c^{T} x s.t. Ax = b and x ∈ L^{p} .  (L)

In light of the previous theorem, it is equivalent to solve

inf_{(x,y)} c^{T} x s.t. Ax = b and (x, y) ∈ H_{p} ,

for which we know a self-concordant barrier with parameter 3200n. This implies that it is possible to find an approximate solution to problem (L) with accuracy ϵ in O(\sqrt{n} log \frac{1}{ϵ}) iterations. Moreover, since it is possible to compute in polynomial time the value of h_{p} and of its first two derivatives, we can conclude that problem (L) is solvable in polynomial time.

This argument is rather easy to generalize to the case of the cartesian product of several L^{p} cones dual L_{s}^{q} cones, which shows eventually that any primal or dual l_{p}-norm optimization can be solved up to a given accuracy in polynomial time.

6 Concluding remarks

In this paper, we have formulated l_{p}-norm optimization problems in a conic way and applied results from the standard conic duality theory to derive their special duality properties.

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. Moreover, the fundamental reason why this class of optimization problems has better duality properties than a general convex problem becomes clear: this is essentially due to the existence of a strictly interior dual solution (even if a reduction procedure involving an equivalent regularized problem has to be introduced when the original dual lacks a strictly feasible point).

It is also worthy to note that this is an example of nonsymmetric conic duality, i.e. involving cones that are not self-dual, unlike the very well-studied cases of linear, secondorder and semidefinite optimization.

Another advantage of this approach is the ease to prove polynomial complexity for our problems: finding a suitable self-concordant barrier is essentially all that is needed.

In the special case where all p_{i}’s are equal, one might think it is possible to derive those duality results with a simpler formulation relying on the standard cone involving p-norms, i.e. the p-cone defined as

𝕃_{p}^{n} = {(x, κ) ∈ ℝ^{n} × ℝ_{+} | ∥x∥_{p} ≤ κ} = {(x, κ) ∈ ℝ^{n} × ℝ_{+} | ∑_{i=1}^{n} |x_{i}|^{p} ≤ κ^{p}} .

However, we were note able to reach that goal, the reason being that the homogenizing variables θ and κ^{∗} appear to play a significant role in our approach and cannot be avoided.

Finally, we mention that this framework can be easily applied to other classes of structured convex problems, see for example [2] for the case of geometric optimization.

Acknowledgements. The author wishes to thank Professor Kees Roos and the SSOR department at the Delft University of Technology for their kind hospitality.

References

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

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

[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] S. Boyd M. S. Lobo, L. Vandenberghe and H. Lebret, Applications of second-order cone programming, Linear Algebra and its Applications 284 (1998), 193–228.

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

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

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

[8] , Geometric programming: Duality in quadratic programming and l_{p} approximation III, Journal on Mathematical Analysis and Applications 29 (1970), 365–383.

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

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

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

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

[13] G. Xue and Y. Ye, An efficient algorithm for minimizing a sum of p-norms, Working Paper, Department of Management Sciences 9903, The University of Iowa, Iowa City, U.S.A., September 1997.