Chapter 14  Unconstrained and Constrained Optimization Problems

Shuguang Cui^‡, Anthony Man-Cho So^♮, and Rui Zhang^♮

^‡ Texas A&M University, College Station, USA

^♮ The Chinese University of Hong Kong, Hong Kong, China

^♮ National University of Singapore, Singapore

In the first section of this chapter, we will give an overview of the basic mathematical tools that are useful for analyzing both unconstrained and constrained optimization problems. In order to allow the readers to focus on the applications of these tools and not to be burdened with too many technical details, we shall state most of the results without proof. However, the readers are strongly encouraged to refer to the texts [1, 2, 3, 4] for expositions of these results and other further developments. In the second section, we provide three application examples to illustrate how we could apply the optimization techniques to solve real-world problems, with a focus on communications, networking, and signal processing. In the last section, several exercise questions are given to help the audience gain a deeper understanding of the material.

14.1    Basics of Convex Analysis

The notion of convexity plays a very important role in both the theoretical and algorithmic aspects of optimization. Before we discuss the relevance of convexity in optimization, let us first introduce the notions of convex sets and convex functions and state some of their properties.

Definition 14.1.1. Let S ∈ ℝⁿ be a set. We say that

1.  S is affine if αx + (1 − α)y ∈ S whenever x, y ∈ S and α ∈ ℝ;

2.  S is convex if αx + (1 — a)y ∈ S whenever x, y ∈ S and α ∈ [0,1].

Given x, y ∈ ℝⁿ and a ∈ ℝ, the vector z = αx + (1 − α)y is called an affine combination of x and y. If α ∈ [0,1], then z is called a convex combination of x and y.

Geometrically, when x and y are distinct points in ℝⁿ, the set

$L=\left\{\mathbf{z}\in {ℝ}^n:\mathbf{z}=\alpha \mathbf{x}+\left(1-\alpha \right)\mathrm{y},\alpha \in ℝ\right\}$

of all affine combinations of x and y is simply the line determined by x and y; and the set

$S=\left\{z\in {ℝ}^n:\mathbf{z}=\alpha \mathbf{x}+\left(1-\alpha \right)\mathbf{y},\alpha \in \left[0,1\right]\right\}$

is the line segment between x and y. By convention, the empty set $\cancel{0}$ is convex.

It is clear that one can generalize the notion of affine (resp. convex) combination of two points to any finite number of points. In particular, an affine combination of the points x₁,…,x_k ∈ ℝⁿ is a point $z={\displaystyle {\sum }_{i=1}^k{\alpha }_i{X}_i}$, where ${\displaystyle {\sum }_{i=1}^k{\alpha }_i=1}$. Similarly, a convex combination of the points x₁,…, x_k ∈ ℝⁿ is a point $z={\displaystyle {\sum }_{i=1}^k{\alpha }_i{X}_i}$, where ${\displaystyle {\sum }_{i=1}^k{\alpha }_i=1}$ and α₁,…, a_k ≥ 0.

Here are some sets in Euclidean space whose convexity can be easily established by first principles:

Example 14.1.1. (Some Examples of Convex Sets)

1.  Non-negative Orthant: ${ℝ}_{+}^n=\left\{x\in {ℝ}^n:\text{x}\ge 0\right\}$.

2.  Hyperplane: H (s, c) = {x ∈ ℝⁿ : s^T x = c}.

3.  Halfspaces: H⁺(s, c) = {x ∈ ℝⁿ : s^Tx ≤ c}, H⁻(s, c) = {x ∈ ℝⁿ : s^Tx ≥ c}.

4.  Euclidean Ball: B(x̄, r) = {x ∈ ℝⁿ : ‖x − x̄|‖₂ ≤ r}.

5.  Ellipsoid: E(x̄, Q, r) = {x ∈ ℝⁿ : (x − x̄)^TQ(x − x̄) ≤ r²}, where Q is an n × n symmetric, positive definite matrix (i.e., x^TQx ̎ 0 for all x ∈ ℝⁿ {0}), and is denoted by Q ≻ 0.?

6.  Simplex: $\text{Δ}=\left\{{\displaystyle {\sum }_{i=0}^n{\alpha }_i{\text{x}}_{\text{i}}:{\displaystyle {\sum }_{i=0}^n{\alpha }_i=1,{\alpha }_i\ge 0\text{for}i\text{=0,1,}\cdots ,n}}\right\}$, where x₀, x₁,…,x_n are vectors in ℝⁿ such that the vectors x₁ −x₀, x₂ − x₀,…, x_n − x₀ are linearly independent (equivalently, the vectors x₀, x₁,…, x_n are affinely independent).

7.  Positive Semidefinite Cone:

${\mathcal{S}}_{+}^n=\{A\in {ℝ}^{n\times n}:A$ = {A ∈ ℝ^{n × n} : A is symmetric and x^TAx ≥ 0 for all x ∈ ℝⁿ} (a symmetric matrix A ∈ ℝℝ^{n × n} is said to be positive semidefinite if x^T Ax ≥ 0 for all x ∈ ℝⁿ, and is denoted by A ≳ 0).

□

Let us now turn to the notion of a convex function.

Definition 14.1.2. Let S ∈ ℝⁿ be a nonempty convex set, and let f: S → ℝ be a real-valued function.

1.  We say that f is convex on S if

$f\left(\alpha {\mathrm{x}}_1+\left(1-\alpha \right){\mathrm{x}}_2\right)\le \alpha f\left({\mathrm{x}}_1\right)+\left(1-\alpha \right)f\left({\mathrm{x}}_2\right)$

(14.1)

for all x₁, x₂ ∈ S and α ∈ [0,1]. We say that f is concave if −f is convex.

2.  We say that f is strictly convex on S if

$f\left(\alpha {\mathrm{x}}_1+\left(1-\alpha \right){\mathrm{x}}_2\right)<\alpha f\left({\mathrm{x}}_1\right)+\left(1-\alpha \right)f\left({\mathrm{x}}_2\right)$

for all x₁, x₂ ∈ S and α ∈ (0,1).

3.  The epigraph of f is the set epi(f ) = {(x, r) ∈ S × ℝ : f (x) ≤ r}.

The relationship between convex sets and convex functions can be summarized as follows:

Proposition 14.1.1. Let f be as in Definition 14.1.2. Then, f is convex (as a function) iff epi(f) is convex (as a set in S × ℝ).

Let r ∈ ℝ be arbitrary. A set closely related to the epigraph is the so-called r—level set of f, which is defined as L(r) = {x ∈ ℝⁿ : f (x) ≤ r}. It is clear that if f is convex, then L(r) is convex for all r ∈ ℝ. However, the converse is not true, as illustrated by the function x ↦ x³. A function f: S → ℝ whose domain is convex and whose r-level sets are convex for all r ∈ ℝ is called quasi-convex.

One of the most desirable features of convexity is the following:

Proposition 14.1.2. Consider the optimization problem:

$\begin{array}{c}\mathrm{minimize}f\left(\mathrm{x}\right)\\ \mathrm{subject}\mathrm{to}\mathrm{x}\in S,\end{array}$

where S ∈ ℝⁿ is a convex set and f : S → ℝ is convex. Then, any local minimum of f is also a global minimum¹.

Now, let S ∈ ℝⁿ be an open convex set, and let f: S → ℝ be an arbitrary function. When f has suitable degree of differentiability, we can characterize its convexity by its gradient or Hessian. Specifically, we have the following:

Theorem 14.1.1. Let S ∈ ℝⁿ be an open convex set, and let f : S → ℝ be a differentiable function on S. Then, fs convex on S iff

$f\left({\mathrm{x}}_1\right)\ge f\left({\mathrm{x}}_2\right)+{\left(\nabla f\left({\mathrm{x}}_2\right)\right)}^T\left({\mathrm{x}}_1-{\mathrm{x}}_2\right)$

for all x₁, x₂ ∈ S. Furthermore, if f is twice continuously differentiable function on S, then f is convex on S iff ∇²f (x) is positive semidefinite for all x ∈ S.

Sometimes it may be difficult to verify directly from the definition whether a given function is convex or not. However, a function can often be obtained as a composition of several, more elementary functions. When each of those elementary functions is convex, it is natural to ask whether their composition is also convex. In general, the answer is no. On the other hand, here are some transformations that preserve convexity.

Theorem 14.1.2. Let S ∈ ℝⁿ be a nonempty convex set. Then, the following hold:

1.  (Non-negative Combinations) Let f₁,…,f_m : S → ℝ be convex functions, and let α₁,…, α_m ≥ 0. Then, the function ${\displaystyle {\sum }_{i=1}^m{\alpha }_i{f}_i}$ is convex on S.

2.  (Pointwise Supremum) Let {f_i}_i∈I be an arbitrary family of convex functions on S. Then, the pointwise supremum f = sup_i∈I fi is convex on S.

3.  (Affine Composition) Let f: ℝⁿ → ℝ be a convex function and A: ℝ^m → ℝⁿ be an affine mapping². then, the function f o A: ℝ^m → ℝⁿ given by (f ∘ A)(x) = f (A(x)) is convex on ℝ^m.

4.  (Composition with an Increasing Convex Function) Let f : S → ℝ be a convex function, and let g : ℝ → ℝ be an increasing convex function. Then, the function g ∘ f : S → ℝ defined by (g ∘ f)(x) = g(f (x)) is convex on S.

5.  (Restriction on Lines) Let f : S → ℝ be a function. Given x₀ ∈ S and h ∈ ℝⁿ, define the function $f_{x_0,h}:ℝ\to ℝ{{\displaystyle \cup }}^{\text{}}\{ + \infty \}$ by

${\tilde{f}}_{x_0,h}(t) = \{\begin{array}{ll}f(x_0 + th)\hfill & if{x}_0 + th\in S,\hfill \\ + \infty \hfill & otherwise.\hfill \end{array}$

Then, f is convex on S iff ${\tilde{f}}_{{\text{x}}_0,\text{h}}$ is convex on ℝ for any x₀ ∈ S and h ∈ ℝⁿ.

Let us now illustrate an application of Theorem 14.1.2.

Example 14.1.2. Let f: ℝ^{m × x} → ℝ₊ be given by f(X) = ‖X‖₂, where ‖·‖₂ denotes the spectral norm or largest singular value of the m × n matrix X. By the Courant-Fischer theorem (see, e.g., [5]), we have

$f\left(\mathrm{X}\right)=\sup \left\{u^{T}X\mathrm{v}:{\Vert u\Vert }_2=1,{\Vert v\Vert }_2=1\right\}.$

(14.2)

Now, for each u ∈ ℝ^m and v ∈ ℝⁿ with ‖u‖₂ = ‖v‖₂ = 1, define the function f_{u, v} :ℝ^{m × n} → ℝ by

$f_{\mathrm{u},\mathrm{v}}\left(X\right)=u^{T}X\mathrm{v}.$

Note that f_{u, v} is a convex (in fact, linear) function of X for each u, v. Hence, it follows from (14.2) that f is a pointwise supremum of a family of linear functions of X. By Theorem 14.1.2, this implies that f is convex.

14.2    Unconstrained vs. Constrained Optimization

14.2.1    Optimality Conditions for Unconstrained Optimization

One of the most fundamental problems in optimization is to derive conditions for identifying potential optimal solutions to an optimization problem. Typically, such conditions, which are known as optimality conditions, would enable us to reduce the original optimization problem to that of checking the validity of certain geometric conditions, or to that of checking the consistency of certain system of inequalities. As an illustration and to motivate our discussion, let us first consider a univariate, twice continuously differentiable function f: ℝ → ℝ. Recall from basic calculus that if x̄ ∈ ℝ is a local minimum of f, then we must have

$\frac{df\left(x\right)}{dx}|{}_{x=\overline{x}}=0.$

(14.3)

In other words, condition (14.3) is a necessary condition for x̄ to be a local minimum. However, it is not a sufficient condition, as an x̄ ∈ ℝ that satisfies (14.3) can be a local maximum or just a stationary point. In order to certify that x̄ is indeed a local minimum, one could check, in addition to (14.3), whether

$\frac{d^{2}f\left(x\right)}{d{x}^2}|{}_{x=\overline{x}}>0.$

(14.4)

In particular, condition (14.4) is a sufficient condition for x̄ to be a local minimum.

In the above discussion, conditions (14.3) and (14.4) together yield a system of inequalities whose solutions are local minima of the function f. Alternatively, they can be viewed as stating the geometric fact that there is no descent direction in a neighborhood of a local minimum. In particular, the former is an algebraic interpretation of local optimality, while the latter is a geometric interpretation. It is worth noting that each interpretation has its own advantage. Indeed, the geometric interpretation can often help us gain intuitions about the problem at hand, and the algebraic interpretation would help to make those intuitions precise. Thus, it is good to keep both interpretations in mind.

To derive optimality conditions for the local minima of a multivariate twice continuously differentiable function f : ℝⁿ → ℝ, we first recall that ∇f (x), the gradient of f at x ∈ ℝⁿ, is the direction of steepest ascent at x. Thus, if ∇f (x) ≠ 0, then starting at x, we can proceed in the direction −∇f (x) and achieve a smaller function value. More specifically, we have the following

Proposition 14.2.1. Suppose that f: ℝⁿ → ℝ is continuously differentiable at x̄ ∈ ℝⁿ. If there exists a d ∈ ℝⁿ such that ∇ (f (x̄))^T d < 0, then there exists an α₀ > 0 such that f (x̄ + αd) < f (x̄) for all a ∈ (0, α₀). In other words, d is a descent direction of f at x̄.

Using Proposition 14.2.1, we can establish the following:

Corollary 14.2.1. (First Order Necessary Condition for Unconstrained Optimization) Suppose that f : ℝⁿ → ℝ is continuously differentiable at x̄ ∈ ℝⁿ. If x̄ is a local minimum, then we have ▽f (x̄) = 0. In particular, we have = ∅.

Similar to the univariate case, even if x̄ ∈ ℝ0 satisfies ∇f (x̄) = 0, we cannot conclude that x̄ is a local minimum. For instance, consider the function f : ℝ² → ℝ given by $f\left(x^1,x^2\right)=-x_1^2-\left(x-x_2\right)$. Then, we have

$\nabla f\left(\mathrm{x}\right)=-2\left(2x_1-x_2,x_2-x_1\right).$

In particular, the (unique) solution to ▽f (x) = 0 is x̄₁ = x̄₂ =0. However, as can be easily verified, the point (x̄₁, x̄₂) = (0,0) is a global maximum of f.

The above example shows that some extra conditions are needed in order to guarantee that a solution to the equation ∇f(x) = 0 is a local minimum of f. for instance, we have the following proposition, which states that if f is convex at x̄, then the necessary condition in Corollary 14.2.1 is also sufficient³:

Proposition 14.2.2. Suppose that f: ℝⁿ → ℝ is continuously differentiable and convex at x̄. Then, x̄ is a global minimum iff ∇f (x̄) = 0.

Alternatively, if ∇f (x̄) = 0 and ∇²f (x̄), the Hessian of f at x̄, is positive definite, then x̄ is a local minimum. Specifically, we have the following proposition,

which generalizes the corresponding result for the univariate case (cf. (14.3) and (14.4)).

Proposition 14.2.3. (Second Order Sufficient Condition for Unconstrained Optimization) Suppose that f : ℝⁿ → ℝ is twice continuously differentiable at x̄ ∈ ℝⁿ. If ∇f (x̄) = 0 and ∇²f (x̄) is positive definite, then x̄ is a local minimum.

Let us now illustrate the above results with an example.

Example 14.2.1. Let f : ℝⁿ → ℝ be defined by $f\left(\text{x}\right)=\frac{1}{2}{\text{x}}^T{\text{Qx+c}}^T\text{x}$, where Q ∈ Sⁿ and c ∈ ℝⁿ are given. Then, f is continuously differentiable, and we have ∇ f(x) = Qx + c and V²f(x) = Q. Now, if f is convex, or equivalently, if Q ≥ 0, then by Proposition 14.2.2, any x̄ ∈ ℝⁿ that satisfies Qx̄ + c = 0 will be a global minimum of f. Note that in this case, we cannot even conclude from Proposition 14.2.3 that x̄ is a local minimum of f, since we only have Q ⪰ 0. On the other hand, suppose that Q ≻ 0. Then, Q is invertible, and by Proposition 14.2.3, the point x̄ = − Q⁻¹c is a local minimum of f. However, since f is convex, Proposition 14.2.2 allows us to draw a stronger conclusion, namely, the point x̄ = − Q⁻¹c is in fact the unique global minimum.

14.2.2    Optimality Conditions for Constrained Optimization

After deriving optimality conditions for unconstrained optimization problems, let us turn our attention to constrained optimization problems of the form

$\underset{\mathrm{x}\in S}{\min }f\left(\mathrm{x}\right),$

(14.5)

where S is a nonempty subset of ℝⁿ. Note that due to the constraint x ∈ S, even if x̄ ∈ ℝⁿ satisfies ∇f (x̄) = 0 and ∇²f (x̄) ≻ 0, it may not be a solution to (14.5), since x̄ need not lie in 0. Similarly, a local minimum x̄ of f over S need not satisfy ∇f (x̄) = 0, since all the descent directions of f at x̄ may lead to points that do not lie in S. Thus, in order to derive optimality conditions for (14.5), we need to consider not only the set of descent directions at x̄, i.e.,

$D=\left\{d\in {ℝ}^n:\nabla f{\left(\overline{x}\right)}^{T}d<0\right\},$

(14.6)

but also the set of feasible directions at x̄, i.e.,

$F=\left\{\mathrm{d}\in {ℝ}^n\left\{0\right\}:\mathrm{there}\mathrm{exists}\mathrm{an}{\alpha }_0>0\mathrm{such}\mathrm{that}\overline{x}+\alpha \mathrm{d}\in S\mathrm{for}\mathrm{all}\alpha \in \left(0,{\alpha }_0\right)\right\}.$

(14.7)

We emphasize that in order for d ∈ F, the entire open line segment {x̄ + αd : ∈ (0, α₀)} must belong to S. This is to ensure that whenever d ∈ D, one can find a feasible solution x̄′ ∈ S with f (x̄′) < f (x̄) by proceeding from x̄ in the direction d. Indeed, by Proposition 14.2.1, if d ∈ D, then there exists an α₁ > 0 such that f (x̄ + αd) < f (x̄) for all α ∈ (0, α₁). However, if x̄ + αd ∈ S for any α ∈ (0, α₁), then we cannot rule out the local minimality of x̄, even if x̄ + αd ∈ S for some α ̄ α₁.

As the following proposition shows, the sets D and F provide a necessary, and under some additional assumptions, even sufficient condition for optimality.

Proposition 14.2.4. Consider Problem (14.5). Suppose that f : ℝⁿ → ℝ is continuously differentiable at x̄ ∈ S. If x̄ is a local minimum, then we have D ∩ F = ∅. Conversely, suppose that (i) D ∩ F = ∅, (ii) f is convex at x̄, and (iii) there exists an ϵ ̄ 0 such that d = x − x̄ ∈ F for any x ∈ S ∩ B°(x̄, ϵ). Then, x̄ is a local minimum of f over S.

REMARKS: Condition (iii) is to ensure that the entire line segment {x̄ + α(x − x̄) : α ∈ [0,1]} lies in S for any x ∈ S ∩ B°(x̄, ϵ), so that d = x − x̄ ∈ F; see the remark after (14.7).

So far we have only discussed optimality conditions for a very general class of optimization problems, i.e., problems of the form (14.5). In particular, we derived a necessary condition for local optimality in terms of the sets D and F, namely that D ∩ F = ∅. However, such a condition is largely geometric, and it is not as easy to manipulate as algebraic conditions (e.g., a system of inequalities). On the other hand, as we will show below, if the feasible region has more structure, then one can circumvent such difficulty and derive algebraic optimality conditions. To begin, let us consider the following class of optimization problems:

$\begin{array}{ll}\mathrm{minimize}\hfill & f\left(\mathrm{x}\right)\hfill \\ \mathrm{subject}\mathrm{to}\hfill & g_i\left(\mathrm{x}\right)\le 0fori=1,\dots ,m,\hfill \\ \hfill & \mathrm{x}\in X,\hfill \end{array}$

(14.8)

where f: ℝⁿ → ℝ and g_i : ℝⁿ → ℝ are continuously differentiable functions, and X is a nonempty open subset of ℝⁿ (usually we take X = ℝⁿ). We then have the following:

Proposition 14.2.5. Let S = {x ∈ X : g_i(x) ≤ 0 for i = 1,…, m} be the feasible region of problem (14.8), and let x̄ ∈ S. Define

$I=\left\{i\in \left\{1,\dots ,m\right\}:g_i\left(\overline{x}\right)=0\right\}$

to be the index set for the active or binding constraints. Furthermore, define

$\begin{array}{l}G=\left\{\mathrm{d}\in {ℝ}^n:\nabla g_i{\left(\overline{x}\right)}^T\mathbf{d}<0\mathrm{for}i\in I\right\},\\ \overline{G}=\left\{\mathbf{d}\in {ℝ}^n\left\{0\right\}:\nabla g_i{\left(\overline{x}\right)}^T\mathrm{d}<0\mathrm{for}i\in I\right\}.\end{array}$

(14.9)

Then, we have G ∈ F ∈ G̅, where F is defined in (14.7). Moreover, if the functions g_i, where i ∈ I, are strictly convex (resp. concave) at x̄, then F = ∈ (resp. F = G̅).

Using Proposition 14.2.4 and Proposition 14.2.5, we can establish the following geometric optimality condition for (14.8):

Corollary 14.2.2. Let S be the feasible region of problem (14.8). Let x̄ ∈ S, and define I = {i ∈ {1,…, m} : g_i(x̄) = 0}. If x̄ is a local minimum, then D ∩ G = ∅, where D is defined in (14.6) and G is defined in (14.9).

The intuition behind Corollary 14.2.2 is quite straightforward. Indeed, suppose that d ∈ D ∩ G. Then, by Proposition 14.2.1, there exists an α₀ > 0 such that f (x̄ + αd) < f (x̄) and g_i(x̄ + αd) g_i(x̄) = 0 for all i ∈ I and α ∈ (0, α₀). Moreover, by the continuity of the functions g₁,…, g_m, for sufficiently small α > 0, we have g_i(x̄ + αd) > 0 for all i ∈ I. It follows that there exists an α₁ > 0 such that x̄ + αd ∈ S and f (x̄ + αd) < f (x̄) for all α ∈ (0, α₁). In other words, x is not a local minimum.

The upshot of Corollary 14.2.2 is that it allows us to derive optimality conditions for (14.8) that is more algebraic in nature. Specifically, Corollary 14.2.2, together with Farkas’ lemma, yields the following:

Theorem 14.2.1. (Karush–Kuhn–Tucker Necessary Conditions) Let x̄ ∈ S be a local minimum of problem (14.8), and let I = {i G m} : g_i(x̄) = 0} be the index set for the active constraints. Suppose that the family {∇g_i(x̄)}_i∈I of vectors is linearly independent. Then, there exist ū₁,…, ū_m ∈ ℝ such that

$\begin{array}{rrrr}\hfill \nabla f\left(\overline{x}\right)+{\displaystyle \sum _{i=1}^m{\overline{u}}_i\nabla g_i\left(\overline{x}\right)}& \hfill =& \hfill 0,& \hfill \\ \hfill {\overline{u}}_i{g}_i\left(\overline{x}\right)& \hfill =& \hfill 0& \hfill fori=1,\dots ,m,\\ \hfill {\overline{u}}_i& \hfill \ge & \hfill 0& \hfill fori=1,\dots .m.\end{array}$

(14.10)

We say that x̄ ∈ ℝⁿ is a KKT point if (i) x̄ ∈ S and (ii) there exist Lagrange multipliers ū₁,…, ū_m such that (x̄, ū₁,…, ū_m) satisfies the system (14.10).

Note that if the gradient vectors of the active constraints are not linearly independent, then the KKT conditions are not necessary for local optimality, even when the optimization problem is convex. This is demonstrated in the following example.

Example 14.2.2. Consider the following optimization problem:

$\begin{array}{ll}\mathrm{minimize}\hfill & x_1\hfill \\ \mathrm{subject}\mathrm{to}\hfill & {\left(x_1-1\right)}^2+{\left(x_2-1\right)}^2\le 1,\hfill \\ \hfill & {\left(x_1-1\right)}^2+{\left(x_2+1\right)}^2\le 1.\hfill \end{array}$

(14.11)

Since there is only one feasible solution (i.e., (x₁, x₂) = (1, 0)), it is naturally optimal. Besides the primal feasibility condition, the KKT conditions of (14.11) are given by

$\begin{array}{c}\left[\begin{array}{c}1\\ 0\end{array}\right]+2u_1\left[\begin{array}{c}{x}_1-1\\ x_2-1\end{array}\right]+2u_2\left[\begin{array}{c}{x}_1-1\\ x_2+1\end{array}\right]=\mathbf{0},\\ u_1\left({\left(x_1-1\right)}^2+{\left(x_2-1\right)}^2-1\right)=0,\\ u_2\left({\left(x_1-1\right)}^2+{\left(x_2+1\right)}^2-1\right)=0.\\ u_1,u_2\ge 0\end{array}$

However, it is clear that there is no solution (u_l,u₂) ≥ 0 to the above system when (x₁, x₂) = (1,0).

□

Let us now illustrate Theorem 14.2.1 with an example.

Example 14.2.3. (Optimization of a Matrix Function) Let A ≻ 0 and b > 0 be given. Consider the following problem:

$\begin{array}{ll}\mathrm{minimize}\hfill & -\log \det \left(Z\right)\hfill \\ \mathrm{subject}\mathrm{to}\hfill & \mathrm{tr}\left(AZ\right)\le b,\hfill \\ \hfill & Z\succ 0.\hfill \end{array}$

(14.12)

Note that (14.12) is of the form (14.8), since we may write (14.12) as

$\begin{array}{ll}\mathrm{minimize}\hfill & -\log \det \left(Z\right)\hfill \\ \mathrm{subject}\mathrm{to}\hfill & \mathrm{tr}\left(AZ\right)\le b,\hfill \\ \hfill & Z\in S_{++}^n,\hfill \end{array}$

and ${\text{S}}_{++}^n\in {ℝ}^{n\left(n+2\right)/2}$ is an open set. Now, it is known that for X ≻ 0,

$\nabla \log \det \left(\text{X}\right)={\text{X}}^{-1},\nabla \text{tr}\left(\text{AX}\right)=\text{A;}$

see, e.g., [6]. Hence, the KKT conditions associated with (14.12) are given by

$\begin{array}{r}\mathrm{tr}\left(AZ\right)\le b,Z\succ 0,\left(a\right)\\ -Z^{-1}+uA=0,u\ge 0,\left(b\right)\\ u\left(\mathrm{tr}\left(AZ\right)-b\right)=0,\left(c\right)\end{array}$

Condition (a) is simply primal feasibility. Condition (c) is known as complementarity. As we shall see later, condition (b) can be interpreted as feasibility with respect to a certain dual of (14.12).

□

Note that Theorem 14.2.1 applies only to inequality-constrained optimization problems of the form (14.8). However, by extending the geometric arguments used to prove Corollary 14.2.2, one can establish similar necessary optimality conditions for optimization problems of the form

$\begin{array}{lll}\mathrm{minimize}\hfill & f\left(x\right)\hfill & \hfill \\ \mathrm{subject}\mathrm{to}\hfill & g_i\left(x\right)\le 0\hfill & \mathrm{for}i=1,\dots ,m_1\hfill \\ \hfill & h_j\left(x\right)=0\hfill & \mathrm{for}j=1,\dots ,m_2\hfill \\ \hfill & x\in X,\hfill & \hfill \end{array}$

(14.13)

where f,g₁,…, g_m1,, h₁,…, h_m2 : ℝⁿ → ℝ are continuously differentiable functions, and X is a nonempty open subset of ℝⁿ. Specifically, we have the following:

Theorem 14.2.2. (Karush–Kuhn–Tucker Necessary Conditions) Let S be the feasible region of Problem (14.13). Suppose that x̄ ∈ S is a local minimum of problem (14.13), with I = {i ∈ {1,…,m₁} : g_i (x̄) = 0} being the index set for the active constraints. Furthermore, suppose that x̄ is regular, i.e., the family ${\left\{{\nabla }_{gi}\left(\overline{\text{x}}\right)\right\}}_{i\in I}\cup {\left\{\nabla h_j\left(\overline{\text{x}}\right)\right\}}_{j=1}^{m_2}$ of vectors is linearly independent. Then, there exist ${\overline{\upsilon }}_1,\cdots ,{\overline{\upsilon }}_{m1}\in ℝ$ and ${\overline{w}}_1,\cdots ,{\overline{w}}_{m2}k\in ℝ$ such that

$\begin{array}{cccc}\nabla f\left(\overline{x}\right)+{\displaystyle \sum _{i=1}^{m_1}{\overline{v}}_i\nabla g_i\left(\overline{x}\right)}+{\displaystyle \sum _{j=1}^{m_2}{\overline{w}}_i\nabla h_j\left(\overline{x}\right)}& =& \mathit{0},& \\ {\overline{v}}_i{g}_i\left(\overline{x}\right)& =& 0& fori=1,\dots ,m_1,\\ {\overline{v}}_i& \ge & 0& fori=1,\dots ,m_1.\end{array}$

(14.14)

As demonstrated in Exercise 14.2.2, the linear independence of the gradient vectors of the active constraints is generally needed to guarantee the existence of Lagrange multipliers. However, such a regularity condition is not always easy to check. As it turns out, there are other forms of regularity conditions, a more well-known of which is the following:

Theorem 14.2.3. Suppose that in Problem (14.13), the functions $g_1,\dots ,g_{m_1}$ are convex and $h_1,\dots ,h_{m_2}$ are linear. Let x̄ ∈ S be a local minimum, and let I = {i ∈ {1,…,m₁} : g_i(x̄) = 0}. If the Slater condition is satisfied, i.e., if there exists an x′ ∈ S such that g_i(x′) < 0 for all i ∈ I, then x̄ satisfies the KKT conditions (14.14).

Another setting in which the existence of Lagrange multipliers is guaranteed is the following:

Theorem 14.2.4. Suppose that in Problem (14.13), the functions $g_1,\dots ,g_{m_1}$ are concave and $h_1,\dots ,h_{m_2}$ are linear. Let x̄ ∈ S be a local minimum. Then, x̄ satisfies the KKT conditions (14.14).

In particular, Theorem 14.2.4 implies that when all the constraints in problem (14.13) are linear, one can always find Lagrange multipliers for any local minimum of problem (14.13).

So far we have only discussed necessary optimality conditions for constrained optimization problems. Let us now turn our attention to sufficient conditions. The following theorem can be viewed as an extension of the first order sufficient condition in Proposition 14.2.2 to the constrained setting.

Theorem 14.2.5. Suppose that in Problem (14.13), the functions $g_1,\dots ,g_{m_1}$ are convex, $h_1,\dots ,h_{m_2}$ are linear, and X = ℝⁿ. Let x̄ ∈ ℝⁿ be feasible for (14.13). If there exist vectors v̄ ∈ R^mi and $\overline{\text{w}}\in {ℝ}^{m_2}$ such that (x̄, v̄, w̄) satisfies the KKT conditions (14.14), then x̄ is a global minimum.

To demonstrate the usage of the above results, let us consider the following example:

Example 14.2.4. (Linear Programming) Consider the standard form linear programming (LP):

$\begin{array}{ccc}\mathrm{minimize}& f\left(x\right)\equiv c^{T}x& \\ \mathrm{subject}\mathrm{to}& h_j\left(x\right)\equiv a_j{}^{T}x-b_j=0& \mathrm{for}j=1,\dots ,m,\\ & g_i\left(x\right)\equiv -x_i\le 0& \mathrm{for}i=1,\dots ,n,\end{array}$

(14.15)

where a₁,…, a_m, c ∈ ℝⁿ and b₁,…, b_m ∈ ℝ. Since

$\begin{array}{ccc}\nabla f\left(x\right)& =c,& \\ \nabla g_i\left(x\right)& =-e_i& \mathrm{for}i=1,\dots ,n,\\ \nabla h_i\left(x\right)& =a_j& \mathrm{for}j=1,\dots ,m,\end{array}$

the KKT conditions associated with (14.15) are given by

$\begin{array}{cccc}c-{\displaystyle \sum _{i=1}^n{v}_i{e}_i}+{\displaystyle \sum _{j=1}^m{w}_j{a}_j}& =& 0,& \\ x_i{v}_i& =& 0& \mathrm{for}i=1,\dots ,n,\\ v_i& \ge & 0& \mathrm{for}i=1,\dots ,n,\\ a_j{}^{T}x& =& b& \mathrm{for}j=1,\dots ,m,\\ x_i& \ge & 0& \mathrm{for}i=1,\dots ,n.\end{array}$

The above system can be written more compactly as follows:

$\begin{array}{cccccc}Ax& =& b,& x& \ge 0,& \left(a\right)\\ A^{T}w+c& =& v,& v& \ge 0,& \left(b\right)\\ x^{T}v& =& 0,& & & \left(c\right)\end{array}$

where A is an m × n matrix whose j-th row is a_j, where j = 1,…, m. Readers who are familiar with the theory of linear programming will immediately recognize that (a) is primal feasibility, (b) is dual feasibility, and (c) is complementarity. In particular, when we apply Theorem 14.2.4 to Problem (14.15), we obtain the strong duality theorem of linear programming.

14.2.3    Lagrangian Duality

Given an optimization problem $\mathcal{P}$ (the primal problem), we can associate with it a dual problem whose properties are closely related to those of $\mathcal{P}$. To begin our investigation, consider the following primal problem:

$\begin{array}{lllll}{v}_p^{\ast }\hfill & =\hfill & \inf \hfill & f\left(x\right)\hfill & \hfill \\ \hfill & \hfill & \mathrm{subject}\mathrm{to}\hfill & g_i\left(x\right)\le 0\hfill & \mathrm{for}i=1,\dots ,m_1,\hfill \\ \left(P\right)\hfill & \hfill & \hfill & h_j\left(x\right)=0\hfill & \mathrm{for}j=1,\dots ,m_2,\hfill \\ \hfill & \hfill & \hfill & x\in X.\hfill & \hfill \end{array}$

Here, f, $g_1,\cdots g_{m_1}$, $h_1,\cdots h_{m_2}:{ℝ}^n\to ℝ$ are arbitrary functions, and X is an arbitrary nonempty subset of ℝⁿ. For the sake of brevity, we shall write the first two sets of constraints in (P) as g(x) ≤ 0 and h(x) = 0, where $\text{g:}{ℝ}^n\to {ℝ}^{m_1}$ is given by $\text{g}\left(\text{x}\right)=\left({\text{g}}_1\left(\text{x}\right),\cdots ,g_{m_1}\left(\text{x}\right)\right)$ and $\text{h:}{ℝ}^n\to {ℝ}^{m_2}$ is given by $\left({\text{h}}_1\left(\text{x}\right)\text{,}\cdots {\text{,h}}_{m_2}\left(\text{x}\right)\right)$.

Now, the Lagrangian dual problem associated with (P) is the following problem:

$\begin{array}{lllll}\hfill & v_d^{\ast }\hfill & =\hfill & \sup \hfill & \theta \left(u,v\right)\equiv {\inf }_{x\in X}L\left(x,u,v\right)\hfill \\ \left(D\right)\hfill & \hfill & \hfill & \mathrm{subject}\mathrm{to}\hfill & u\ge 0.\hfill \end{array}$

Here, $L:{ℝ}^n\times {ℝ}^{m_1}\times {ℝ}^{m_2}\to ℝ$ is the Lagrangian function given by

$L\left(x,u,v\right)=f\left(x\right)+{\displaystyle \sum _{i=1}^m{u}_i{g}_i\left(x\right)}+{\displaystyle \sum _{j=1}^{m_2}{u}_i{h}_i\left(x\right)}=f\left(x\right)+u^{T}g\left(x\right)+v^{T}h\left(x\right).$

(14.16)

Observe that the above formulation can be viewed as a penalty function approach, in the sense that we incorporate the primal constraints g(x) ≤ 0 and h(x) = 0 into the objective function of (D) using the Lagrange multipliers u and v. Also, since the set X is arbitrary, there can be many different Lagrangian dual problems for the same primal problem, depending on which constraints are handled as g(x) ≤ 0 and h(x) = 0, and which constraints are treated by X. However, different choices of the Lagrangian dual problem will in general lead to different outcomes, both in terms of the dual optimal value as well as the computational efforts required to solve the dual problem.

Let us now investigate the relationship between (P) and (D). For any x̄ ∈ X and $\left(\overline{u},\overline{v}\right)\in {ℝ}_{+}^{m_1}\times {ℝ}^{m_2}$, we have

$\underset{x\in X}{\inf }L\left(x,\overline{u},\overline{v}\right)\le f\left(\overline{x}\right)+{\overline{u}}^{T}g\left(\overline{x}\right)+{\overline{v}}^{T}h\left(\overline{x}\right)\le \underset{u\ge 0}{\sup }L\left(\overline{x},u,v\right).$

This implies that

$\underset{u\ge 0}{\sup }\underset{x\in X}{\inf }L\left(x,u,v\right)\le \underset{x\in X}{\inf }\underset{u\ge 0}{\sup }L\left(x,u,v\right).$

(14.17)

In particular, we have the following weak duality theorem, which asserts that the dual objective value is always a lower bound on the primal objective value:

Theorem 14.2.6. (Weak Duality) Let x̄ be feasible for (P) and (ū, v̄) be feasible for (D). Then, we have θ(ū, v̄) ≤ f (x̄). In particular, if ${\upsilon }_d^{*}=+\infty$, then (P) has no feasible solution.

Given the primal–dual pair of problems (P) and (D), the duality gap between them is defined as $\Delta ={\upsilon }_p^{*}-{\upsilon }_d^{*}$. By Theorem 14.2.6, we always have Δ ≥ 0. It would be nice to have Δ = 0 (i.e., zero duality gap). However, as the following example shows, this is not true in general.

Example 14.2.5. Consider the following problem from [1, Example 6.2.2]:

$\begin{array}{ll}\mathrm{minimize}\hfill & f\left(x\right)\equiv -2x_1+x_2\hfill \\ \mathrm{subject}\mathrm{to}\hfill & h\left(x\right)\equiv x_1+x_2-3=0,\hfill \\ \hfill & x\in X,\hfill \end{array}$

(14.18)

where X ∈ ℝ² is the following discrete set:

$X=\left\{\left(0,0\right),\left(0,4\right),\left(4,4\right)\left(4,0\right),\left(1,2\right),\left(2,1\right)\right\}.$

By enumeration, we see that the optimal value of (14.18) is −3, attained at the point (x₁, x₂) = (2,1). Now, one can verify that the Lagrangian function is given by

$\begin{array}{l}\theta \left(v\right)=\underset{x\in X}{\min }\left\{-2x_1+x_2+v\left(x_1+x_2-3\right)\right\}\\ =\{\begin{array}{ll}-4+5v\hfill & \mathrm{for}v\le -1,\hfill \\ -8+v\hfill & \mathrm{for}-1\le v\le 2,\hfill \\ -3v\hfill & \mathrm{for}v\ge 2.\hfill \end{array}\end{array}$

It follows that max_v θ(ν) = −6, which is attained at v = 2. Note that the duality gap in this example is Δ = −3 − (−6) = 3 > 0.

The above example raises the important question of when the duality gap is zero. It turns out that there is a relatively simple answer to this question. Before we proceed, let us introduce the following definition:

Definition 14.2.1. We say that (x̄, ū, v̄) is a saddle point of the Lagrangian function L defined in (14.16) if the following conditions are satisfied:

1.  x̄ ∈ X,

2.  ū ≥ 0, and

3.  for all x ∈ X and $\left(u,v\right)\in {ℝ}^{m_1}\times {ℝ}^{m_2}$, we have

$L\left(\overline{x},u,v\right)\le L\left(\overline{x},\overline{u},\overline{v}\right)\le L\left(x,\overline{u},\overline{v}\right).$

In particular, observe that (x̄, ū, v̄) is a saddle point of L if x̄ minimizes L over X when (u, v) is fixed at (ū, v̄), and that (ū, v̄) maximizes L over all ${ℝ}^{m_1}\times {ℝ}^{m_2}$ with u ≥ 0 when x is fixed at x̄.

We are now ready to state the following theorem:

Theorem 14.2.7. (Saddle Point Optimality Conditions) The point (x̄, ū, v̄) with x̄ ∈ X and ū ≥ 0 is a saddle point of L iff

1.  L(x̄, ux̄, vx̄) = min_x∈X L(X, ū, v̄),

2.  g(x̄) ≤ 0 and h(x̄) = 0, and

3.  ū^Tg(x̄) = 0.

Moreover, the point (x̄, ū, v̄) is a saddle point of L iff x̄ and (ū, v̄) are the optimal solutions to (P) and (D), respectively, with f (x̄) = θ(ū, v), i.e., there is no duality gap.

In other words, the existence of a saddle point (x̄, ū, v̄) of L implies that

$\underset{\mathrm{x}\in X}{\inf }L\left(x,\overline{u},\overline{v}\right)=L\left(\overline{x},\overline{u},\overline{v}\right)=\underset{u\ge 0}{\sup }L\left(\overline{x},u,v\right),$

which in turn implies that

$\underset{u\ge 0}{\sup }\underset{\mathrm{x}\in X}{\inf }L\left(x,u,v\right)=\underset{\mathrm{x}\in X}{\inf }\underset{u\ge 0}{\sup }L\left(x,u,v\right),$

i.e., inequality (14.17) holds with equality, and ${\upsilon }_p^{*}={\upsilon }_d^{*}$.

Now, if we want to apply Theorem 14.2.7 to certify that the duality gap between (P) and (D) is zero, we need to produce a saddle point of the Lagrangian function L, which is not always an easy task. The following theorem, which is an application of Sion’s minimax theorem [7] (see [8] for an elementary proof), provides an easy-to-check sufficient condition for certifying zero duality gap.

Theorem 14.2.8. Let L be the Lagrangian function defined in (14.16). Suppose that

1.  X is a compact convex subset of ℝⁿ,

2.  (u, v) ↦ L (x, u, v) is continuous and concave on ${ℝ}_{+}^{m_1}\times {ℝ}^{m_2}$ for each x ∈ X, and

3.  x ↦ L (x, u, v) is continuous and convex on X for each $\left(u,v\right)\in {ℝ}_{+}^{m_1}\times {ℝ}^{m_2}$.

Then we have.

$\underset{u\ge 0}{\sup }\underset{\mathrm{x}\in X}{\inf }L\left(x,u,v\right)=\underset{\mathrm{x}\in X}{\inf }\underset{u\ge 0}{\sup }L\left(x,u,v\right).$

Let us now illustrate some of the above results with an example.

Example 14.2.6. (Semidefinite Programming) Consider the following standard form semidefinite programming (SDP):

$\begin{array}{ll}\inf \hfill & f\left(Z\right)\equiv \mathrm{tr}\left(CZ\right),\hfill \\ \mathrm{subject}\mathrm{to}\hfill & h_i\left(Z\right)\equiv b_j-\mathrm{tr}\left(A_{j}Z\right)=0\mathrm{for}j=1,\dots ,m,\hfill \\ \hfill & Z\in X\equiv S_{+}^n,\hfill \end{array}$

(14.19)

where C, A₁,…, A_m ∈ ℝ^{n × n} are symmetric matrices, b₁,…, b_m ∈ ℝ and $S_{+}^n$ is the set of n × n symmetric positive semidefinite matrices. The Lagrangian dual associated with (14.19) is given by

$\sup \theta \left(v\right)\equiv \underset{Z\in S_{+}^n}{\inf }\left\{\mathrm{tr}\left(CZ\right)+{\displaystyle \sum _{j=1}^m{v}_j\left(b_j-\mathrm{tr}\left(A_{j}Z\right)\right)}\right\}.$

(14.20)

Now, for any fixed v ∈ ℝ^m, we have

$\theta \left(v\right)=\{\begin{array}{ll}{b}^{T}v\hfill & \mathrm{if}\mathrm{C}-{\displaystyle \sum _{j=1}^m{v}_j{A}_j\in S_{+}^n,}\hfill \\ -\infty \hfill & \mathrm{otherwise}.\hfill \end{array}$

(14.21)

To see this, let $U\Lambda U^T$ be the spectral decomposition of $C-{\displaystyle {\sum }_{j=1}^m{\upsilon }_j{A}_{\text{j}}}$, and suppose that Λ_ii < 0 for some i = 1,…, n. Consider the matrix $Z\left(\alpha \right)=\alpha U{\text{e}}_{\text{i}}{\text{e}}_{\text{i}}{}^{T}U$. Clearly, we have $Z\left(\alpha \right)\in S_{+}^n$ for all α > 0. Moreover, as α → ∞, we have

$\begin{array}{l}\mathrm{tr}\left(\left(C-{\displaystyle \sum _{j=1}^m{v}_j{A}_j}\right)Z\left(\alpha \right)\right)=\alpha \cdot \mathrm{tr}\left(\left(U\text{Λ}{U}^T\right)\left(U{e}_i{e}_i{}^T{U}^T\right)\right)\\ =\alpha \cdot \mathrm{tr}\left(\text{Λ}{e}_i{e}_i{}^T\right)=\alpha {\text{Λ}}_{ii}\to -\infty ,\end{array}$

whence

$\theta \left(v\right)=b^{T}v+\underset{Z\in S_{+}^n}{\inf }\mathrm{tr}\left(\left(C-{\displaystyle \sum _{j=1}^m{v}_j{A}_j}\right)Z\right)=-\infty .$

On the other hand, if $C-{\displaystyle {\sum }_{j-1}^m{\upsilon }_j{A}_{\text{j}}\in S_{+}^n}$, then we have tr $\left(\left(C-{\displaystyle {\sum }_{j=1}^m{\upsilon }_j{A}_j}\right)Z\right)\ge 0$ for any $Z\in S_{+}^n$. It follows that θ(ν) = b^Tv in this case (by taking, say, Z = 0).

Now, using (14.21), we see that (14.20) is equivalent to

$\begin{array}{ll}\sup \hfill & b^{T}v\hfill \\ \mathrm{subject}\mathrm{to}\hfill & C-{\displaystyle \sum _{j=1}^m{v}_j{A}_j}\in S_{+}^n,\hfill \end{array}$

(14.22)

which is known as a dual standard form SDP.

14.3    Application Examples

In the past decade optimization techniques, especially convex optimization techniques, have been widely used in various engineering fields such as industrial engineering, mechanical engineering, and electrical engineering. For electrical engineering in particular, optimization techniques have been applied to solve problems in communications [9, 10, 11, 12, 13, 14], networking [15, 16, 17, 18, 19], signal processing [20, 22], and even circuit design [23]. In this section, we briefly go through several examples in communications, networking, and signal processing to illustrate how we could apply the results introduced in the previous section to solve real-world problems.

Example 14.3.1. (Power Allocation Optimization in Parallel AWGN Channels) Consider the transmission over n parallel AWGN channels. The ith channel, i ∈ {1,…, n}, is characterized by the channel power gain, h_i ≥ 0, and the additive Gaussian noise power, σ_i > 0. Let the transmit power allocated to the ith channel be denoted by p_i ≥ 0. The maximum information rate that can be reliably transmitted over the ith channel is given by [24]

$r_i=\log \left(1+\frac{h_i{p}_i}{{\sigma }_i}\right).$

(14.23)

Given a constraint P on the total transmit power over n channels, i.e., ${\displaystyle {\sum }_{i=1}^n{p}_i\le P}$, we want to optimize the allocated power p₁,…,p_n such that the sum rate of n channels, ${\displaystyle {\sum }_{i=1}^n{r}_i}$, is maximized. This problem is thus formulated as

$\begin{array}{ll}\mathrm{maximize}\hfill & {\displaystyle {\sum }_{i=1}^n\log \left(1+\frac{h_i{p}_i}{{\sigma }_i}\right)}\hfill \\ \mathrm{subject}\mathrm{to}\hfill & {\displaystyle {\sum }_{i=1}^n{p}_i\le P,}\hfill \\ \hfill & p_i\ge 0\mathrm{for}i=1,\dots ,n.\hfill \end{array}$

(14.24)

For convenience, we rewrite the above problem equivalently as

$\begin{array}{ll}\mathrm{maximize}\hfill & f\left(p\right)\equiv -{\displaystyle {\sum }_{i=1}^n\log \left(1+\frac{h_i{p}_i}{{\sigma }_i}\right)}\hfill \\ \mathrm{subject}\mathrm{to}\hfill & h\left(p\right)\equiv {\displaystyle {\sum }_{i=1}^n{p}_i-P\le 0,}\hfill \\ \hfill & \begin{array}{l}{g}_i\left(p\right)\equiv -p_i\le 0\mathrm{for}i=1,\dots ,n,\\ p\in {ℝ}^n,\end{array}\hfill \end{array}$

(14.25)

where p = [p₁,…,p_n]^T. It is easy to verify that f(p) is convex, and h(p), g₁(p),…,g_n(p) are all affine and thus convex. According to Theorem 14.2.5, if we can find a set of feasible solutions p̄ = [p̄₁,…, p̄_n] ∈ ℝⁿ for the above constrained minimization problem as well as a set of u ≥ 0 and v_i ≥ 0, i = 1,…, n such that the following KKT conditions are satisfied,

$\begin{array}{ccccc}\nabla f\left(\overline{p}\right)+u\nabla h\left(\overline{p}\right)+{\displaystyle \sum _{i=1}^n{v}_i\nabla g_i\left(\overline{p}\right)}& =& 0,& & \left(\mathrm{a}\right)\\ uh\left(\overline{p}\right)& =& 0,& & \left(\mathrm{b}\right)\\ v_i{g}_i\left(\overline{p}\right)& =& 0,& \mathrm{for}i=1,\dots ,n,& \left(\mathrm{c}\right)\end{array}$

(14.26)

then we can claim that p̄ is a global minimum for this problem. Suppose that u > 0. From (b), it follows that h(p̄) = 0, i.e., ${\displaystyle {\sum }_{i=1}^n{\overline{p}}_i=P}$. From (a), it follows that

${\overline{p}}_i=\frac{1}{u-v_i}-\frac{{\sigma }_i}{h_i}\mathrm{for}i=1,\dots ,n.$

(14.27)

Suppose that p̄_i > 0. From (c), it follows that v_i = 0. Then from (14.27), it follows that ${\overline{p}}_i=\frac{1}{u}-\frac{{\sigma }_i}{{}^{h_i}}>0$. Clearly, if this inequality holds, the corresponding p̄_i will satisfy both (a) and (c). Otherwise, the preassumption of p̄_i > 0 cannot be true and the only feasible value for p̄_i is p̄_i = 0. In this case, since $\frac{1}{u}-\frac{{\sigma }_i}{{}^{h_i}}\le 0$, we can always find a v_i ≥ 0 such that p̄_i = 0 holds in (14.27). To summarize, for any u > 0, the set of feasible values for p̄_i that satisfy both (a) and (c) are given by

${\overline{p}}_i={\left(\frac{1}{u}-\frac{{\sigma }_i}{h_i}\right)}^{+}\mathrm{for}i=1,\dots ,n,$

(14.28)

where (x)+ = max(0, x) for x ∈ ℝ. Furthermore, recall that this set of p̄_i’s needs to satisfy ${\displaystyle {\sum }_{i=1}^n{\overline{p}}_i=P}$, i.e.,

${\displaystyle \sum _{i=1}^n{\left(\frac{1}{u}-\frac{{\sigma }_i}{h_i}\right)}^{+}=P.}$

(14.29)

Note that for any P > 0, in the above equation there exists a unique positive root of u (which can be found numerically by a simple bisection search over the interval 0 < u <max_i(h_i/σ_i)). With the root of u, the corresponding p̄_i’s given in (14.28) satisfy all the KKT conditions in (a), (b), and (c), and are thus the global optimal solutions for Problem (14.25). It is worth noting that the structure for the optimal power allocation in (14.28) is known as the “water-filling” solution [24].

Example 14.3.2. (Transmit Optimization for MIMO AWGN Channels with Per-Antenna Power Constraints) Consider the transmission over a MIMO AWGN channel with n transmitting antennas and m receiving antennas. The propagation channel from the transmitter to the receiver is represented by a real matrix, H ∈ ℝ^m×n, in which all the columns are assumed to be “non-empty”, i.e., there is at least one element in each column being non-zero. The additive noises at m receiving antennas are assumed to be i.i.d. Gaussian random variables with zero mean and unit variance. The transmit signals from the ith antenna, i ∈ {1,…, n}, are denoted by x_i(t) ∈ ℝ, t = 0, 1,…, which are subject to a per-antenna average power constraint P_i, i.e., E {(x_i(t))² } ≤ P_i, where E {·} denotes the expectation. Let $Z\in S_{+}^n$ denote the transmit covariance matrix, i.e., Z = E {x(t) (x(t))^T}, where x(t) = [x₁(t),…,x_n(t)]^T. The set of per-antenna transmit power constraints can then be expressed as

$\mathrm{tr}\left(A_{i}Z\right)\le P_i\mathrm{for}i=1,\dots ,n,$

(14.30)

where A_i ∈ ℝ^n×n is a matrix with all zero elements expect for the ith diagonal element being one.

For any transmit covariance matrix $Z\in S_{+}^n$, the maximum transmit rate over the MIMO AWGN channel is given by [25]

$r=logdet\left(I+HZ{H}^T\right),$

(14.31)

where I denotes an identity matrix. The problem of our interest here is to maximize the rate r over $Z\in S_{+}^n$ subject to the set of per-antenna transmit power constraints, which can be equivalently formulated as

$\begin{array}{ccc}{v}_p^{\ast }=& \mathrm{minimize}& f\left(Z\right)\equiv -\log \det \left(I+HZ{H}^T\right)\\ & \mathrm{subject}\mathrm{to}& g_i\left(Z\right)\equiv \mathrm{tr}\left(A_{i}Z\right)-P_i\le 0\mathrm{for}i=1,\dots ,n,\\ & & Z\in S_{+}^n.\end{array}$

(14.32)

In the following, we apply the Lagrangian duality to solve the above problem. The Lagrangian function for this problem is given by

$L\left(Z,u\right)=f\left(Z\right)+{\displaystyle \sum _{i=1}^n{u}_i{g}_i\left(Z\right)=-\log \det \left(I+HZ{H}^T\right)}+{\displaystyle \sum _{i=1}^n{u}_i\left(\mathrm{tr}\left(A_{i}Z\right)-P_i\right)},$

(14.33)

where $u={\left[u_1,\cdots ,u_n\right]}^T\in {ℝ}_{+}^n$. The Lagrangian dual problem associated with problem (14.32) is then given by

$\begin{array}{lll}{v}_d^{\ast }=\hfill & \mathrm{maximize}\hfill & \theta \left(u\right)\equiv {\min }_{Z\in S_{+}^n}L\left(Z,u\right)\hfill \\ \hfill & \mathrm{subject}\mathrm{to}\hfill & u\ge \mathbf{0.}\hfill \end{array}$

(14.34)

It can be verified that the conditions listed in Theorem 14.2.8 are all satisfied for the Lagrangian function L(Z, u) given in (14.33). We thus conclude that v*_p = v*_d, i.e., the duality gap for Problem (14.32) is zero. Accordingly, we can solve this problem equivalently by solving its dual problem (14.34), as shown next.

First, we solve the minimization problem in (14.34) to obtain the dual function θ(u) for any given u ≥ 0. Observe that θ(u) can be explicitly written as

$\theta \left(u\right)=\underset{Z\in S_{+}^n}{\min }-\log \det \left(I+HZ{H}^T\right)+\mathrm{tr}\left(A_{u}Z\right)-{\displaystyle \sum _{i=1}^n{u}_i{P}_i}$

(14.35)

where $A_u={\displaystyle {\sum }_{i=1}^n{u}_i{A}_i}$ is a diagonal matrix with the ith diagonal element equal to u_i, i = 1,…,n. Note that for the minimization problem in the above, the optimal solution for Z is independent of the term ${\displaystyle {\sum }_{i=1}^n{u}_i{P}_i}$, which thus can be ignored. To solve this minimization problem, we first observe that if any diagonal element in A_u, say, u_i, i ∈ {1,…,n}, is equal to zero, then the minimum value for this problem becomes −∞, which is attained by, e.g., taking $Z=\alpha 1_i{1}_i^T$, where 1_i denotes an n × 1 vector with all zero elements except for the ith element being one, and letting α → ∞. Next, we consider the case where all u_i’s are greater than zero. In this case, A_u is full-rank and thus its inverse exists. By defining a new variable $\overline{Z}=A_u^{1/2}Z{A}_u^{1/2}\in S_{+}^n$ and using the fact that tr(AB) = tr(BA), the minimization problem in (14.35) can be rewritten as

$\underset{\overline{Z}\in S_{+}^n}{\min }-\log \det \left(I+H{A}_u^{-1/2}\overline{Z}{A}_u^{-1/2}{H}^T\right)+\mathrm{tr}\left(\overline{Z}\right).$

(14.36)

Let the SVD of $H{A}_u^{-1/2}$ be denoted by

$H{A}_u^{-1/2}=U\text{Λ}{V}^T,$

(14.37)

where U ∈ ℝ^{m × m} and V ∈ ℝ^{n × n} are unitary matrices, and Λ ∈ ℝ^m×n is a diagonal matrix with the diagonal elements being denoted by λ₁,…,λ_k, k = min(m, n), and λ_i ≥ 0, i = 1,…, k. Substituting (14.37) into (14.36) and using the fact that log det (I + AB) = log det (I + BA) yield

$\underset{\overline{Z}\in S_{+}^n}{\min }-\log \det \left(I+\text{Λ}{V}^T\overline{Z}V{\text{Λ}}^T\right)+\mathrm{tr}\left(\overline{Z}\right).$

(14.38)

By letting Ẑ = V^TZ̄V and using the fact that tr (Z̄)→ = tr (Z̄), we obtain an equivalent problem of (14.38) as

$\underset{\widehat{Z}\in S_{+}^n}{\min }-\log \det \left(I+\text{Λ}\tilde{Z}{\text{Λ}}^T\right)+\mathrm{tr}\left(\widehat{Z}\right).$

(14.39)

Recall the Hadamard’s inequality [24], which states that for any $X\in S_{+}^m$, det $(X)\le {\displaystyle {\prod }_{i=1}^m{X}_{ii}}$, iff X is a diagonal matrix, where X_ii denotes the ith diagonal element of X, i = 1,…, m. Applying this result to Problem (14.39), it follows that the minimum value for this problem is attained iff Ẑ is a diagonal matrix. Let the diagonal elements of Ẑ be denoted by p₁,…,p_n. Since $\widehat{Z}\in S_{+}^n$, Problem (14.39) can be simplified as

$\begin{array}{ll}\mathrm{minimize}\hfill & -{\displaystyle {\sum }_{i=1}^n\log \left(1+{\text{λ}}_i^2{p}_i\right)}+{\displaystyle {\sum }_{i=1}^n{p}_i}\hfill \\ \mathrm{subject}\mathrm{to}\hfill & p_i\ge 0\mathrm{for}i=1,\dots ,n.\hfill \end{array}$

(14.40)

Note that in the above problem, for convenience we have assumed that λ_i = 0, for i = k + 1,…, n. Similar to Exercise 14.3.1, the global minimum for the above problem can be shown to be the following water-filling solution:

$p_i={\left(1-\frac{1}{{\text{λ}}_i^2}\right)}^{+}fori=1,\dots ,n.$

(14.41)

To summarize, for any given u > 0, the optimal solution for the minimization problem in (14.35) is given by

$Z_u=A_u^{-1/2}V\widehat{Z}{V}^T{A}_i^{-1/2},$

(14.42)

where $\widehat{Z}$ is a diagonal matrix with the diagonal elements given in (14.41). Moreover, the dual function θ(u) in (14.35) can be simplified to be

$\theta \left(u\right)\{\begin{array}{cc}\begin{array}{l}-{\displaystyle {\sum }_{i=1}^k{\left(\log \left({\text{λ}}_i^2\right)\right)}^{+}}+{\displaystyle {\sum }_{i=1}^k{\left(1-\frac{1}{{\text{λ}}_i^2}\right)}^{+}}-{\displaystyle {\sum }_{i=1}^n{u}_i{P}_i}\\ -\infty \end{array}& \begin{array}{l}\mathrm{if}u>0\\ \mathrm{otherwise},\end{array}\end{array}$

(14.43)

where λ₁,…, λ_k are related to u via (14.37).

Next, we solve the dual problem (14.34) by maximizing the dual function θ(u) in (14.43) over u ≥ 0. The corresponding dual optimal solution of u then leads to the optimal solution of Z_u in (14.42) for the primal problem (14.32). Since v*_d = v*_p ≥ 0, in fact we only need to consider the maximization of θ(u) over u > 0 in (14.43). However, due to the coupled structure of λ_i’s and u_i’s shown in (14.37), it is not evident whether θ(u) in (14.43) is differentiable over u_i’s for u > 0. As a result, conventional decent methods to find the global minimum for differentiable convex functions such as Newton’s method are ineffective for our problem at hand. Thus, we resort to an alternative method, known as subgradient based method, to handle the non-differentiable function θ(u). First, we introduce the definition of subgradient for an arbitrary real-valued function z(x) defined over a nonempty convex set S ∈ ℝⁿ. We assume that z(x) has a finite maximum. However, z(x) need not be continuously differentiable nor have an analytical expression for its differential. In this case, a vector v ∈ ℝⁿ is called the subgradient of z(x) at point x = x₀ if for any x ∈ S, the following inequality holds:

$z\left(\mathrm{x}\right)\le z\left({\mathrm{x}}_0\right)+{\mathrm{v}}^T\left(\mathrm{x}-{\mathrm{x}}_0\right).$

(14.44)

If at any point x ∈ S a corresponding subgradient v for z(x) is attainable, then the maximum of z(x) can be found via an iterative search over x ∈ S based on v (see, e.g., the ellipsoid method [26]). Since 0(u) is defined over a convex set u > 0 and has a finite maximum, the dual problem (14.34) can thus be solved by a subgradient based method. Next, we show that the subgradient of θ(u) at any point u > 0 is given by [tr (A₁Z_u) − P₁,…, tr (A_nZ_u) − P_n]^T, where Z_u is given in (14.42). Suppose that at any two points u > 0 and u′ > 0, θ(u) and θ(u′) are attained by Z = Z_u and Z = Z′_u, respectively. Then, we have the following inequalities:

$\begin{array}{l}\theta \left(u^{\prime }\right)=L\left({Z^{\prime }}_u,u^{\prime }\right)\\ =\underset{z\in S_{+}^n}{\min }L\left(Z,u^{\prime }\right)\\ \le L\left(Z_u,u^{\prime }\right)\\ =-\log \det \left(I+H{Z}_u{H}^T\right)+\left[\mathrm{tr}\left(A_1{Z}_u\right)-P_1,\dots ,\mathrm{tr}\left(A_n{Z}_u\right)-P_n\right]u^{\prime }\\ =-\log \det \left(I+H{Z}_u{H}^T\right)+\left[\mathrm{tr}\left(A_1{Z}_u\right)-P_1,\dots ,\mathrm{tr}\left(A_n{Z}_u\right)-P_n\right]u\\ +\left[\mathrm{tr}\left(A_1{Z}_u\right)-P_1,\dots ,\mathrm{tr}\left(A_n{Z}_u\right)-P_n\right]\left(u^{\prime }-u\right)\\ =L\left(Z_u,u\right)\left[\mathrm{tr}\left(A_1{Z}_u\right)-P_1,\dots ,\mathrm{tr}\left(A_n{Z}_u\right)-P_n\right]\left(u^{\prime }-u\right)\\ =\theta \left(u\right)\left[\mathrm{tr}\left(A_1{Z}_u\right)-P_1,\dots ,\mathrm{tr}\left(A_n{Z}_u\right)-P_n\right]\left(u^{\prime }-u\right),\end{array}$

from which the subgradient of θ(u) follows.

Last, we can verify that the optimal primal and dual solutions, Z_u given in (14.42) and the corresponding u > 0 satisfy (a) of the following KKT conditions:

$\begin{array}{c}\nabla f\left(Z_u\right)+{\displaystyle \sum _{i=1}^n{u}_i\nabla g_i\left(Z_u\right)}=0,\left(\mathrm{a}\right)\\ u_i{g}_i\left(Z_u\right)=0fori=1,\dots ,n,\left(b\right)\end{array}$

(14.45)

while since u > 0, from (b) it follows that g_i(Z_u) = 0, i.e., tr(A_i Z_u) = P_i must hold for i = 1,…,n. Thus, all transmit antennas should transmit with their maximum power levels with the optimal transmit covariance matrix Z_u, which is consistent with the observation that the subgradient of the dual function θ(u) at the optimal dual solution of u should vanish to 0.

Example 14.3.3. (Power Efficient Beamforming in Two-Way Relay Network via SDP Relaxation) In this example, we illustrate how an originally nonconvex problem can be solved via convex techniques. As shown in Figure 14.1, we consider a two-way relay channel (TWRC) consisting of two source nodes, S1 and S2, each with a single antenna and a relay node, R, equipped with M antennas, M ≥ 2. It is assumed that the transmission protocol of TWRC uses two consecutive equal-duration time slots for one round of information exchange between S1 and S2 via R. During the first time slot, both S1 and S2 transmit concurrently to R, which linearly processes the received signal and then broadcasts the resulting signal to S1 and S2 during the second time slot. It is also assumed that perfect synchronization has been established among S1, S2, and R prior to data transmission. The received baseband signal at R in the first time slot is expressed as

${\mathrm{y}}_R\left(n\right)=h_1\sqrt{p_1}{s}_1\left(n\right)+h_2\sqrt{p_2}{s}_2\left(n\right)+z_R\left(n\right)$

(14.46)

where y_R(n) ∈ ℂ^M is the received signal vector at symbol index n, n = 1,…,N, with N denoting the total number of transmitted symbols during one time slot; h₁ ∈ ℂ^M and h₂ ∈ ℂ^M represent the channel vectors from S1 to R and from S2 to R, respectively, which are assumed to be constant during the two time slots; s₁(n) and s₂(n) are the transmitted symbols from S1 and S2, respectively, with E {|s₁(n)|} = 1, E {|s₂(n)|} = 1, and |·| denoting the absolute value for a complex number; p₁ and p₂ denote the transmit powers of S1 and S2, respectively; and z_R(n) ∈ ℂ^M is the receiver noise vector, independent over n, and without loss of generality, it is assumed that z_R(n) has a circular symmetric complex Gaussian (CSCG) distribution with zero mean and identity covariance matrix, denoted by z_R(n) ~ $\mathcal{C}$$\mathcal{N}$(0, I), ${\forall }_n$. Upon receiving the mixed signal from S1 and S2, R processes it with amplify-and-forward (AF) relay operation, also known as linear analogue relaying, and then broadcasts the processed signal to S1 and S2 during the second time slot. Mathematically, the linear processing (beamforming) operation at the relay can be concisely represented as

${\mathrm{x}}_R\left(n\right)=A{y}_R\left(n\right),n=1,\dots ,N$

(14.47)

Figure 14.1:  The two-way multi antenna relay channel.

where x_R(n) ∈ ℂ^M is the transmitted signal at R, and A ∈ ℂ^{M × M} is the relay processing matrix.

Note that the transmit power of R can be shown equal to

$\begin{array}{l}{p}_R\left(A\right)=\mathrm{E}\left[\mathrm{tr}\left({\mathrm{x}}_R\left(n\right){\mathrm{x}}_R^H\left(n\right)\right)\right]\\ ={\Vert A{h}_1\Vert }_2^2{p}_1+{\Vert A{h}_2\Vert }_2^2{p}_2+\mathrm{tr}\left(A{A}^H\right).\end{array}$

(14.48)

We can assume w.l.o.g. that channel reciprocity holds for TWRC during uplink and downlink transmissions, i.e., the channels from R to S1 and S2 during the second time slot are given as ${\text{h}}_1^T$ and ${\text{h}}_2^T$, respectively. Thus, the received signals at S1 can be written as

$\begin{array}{l}{y}_1\left(n\right)=h_1^T{\mathrm{x}}_R\left(n\right)+z_1\left(n\right)\\ =h_1^{T}A{h}_1\sqrt{p_1}{s}_1\left(n\right)+h_1^{T}A{h}_2\sqrt{p_2}{s}_2\left(n\right)+h_1^{T}A{z}_R\left(n\right)+z_1\left(n\right)\end{array}$

(14.49)

for n = 1,…, N, where z₁(n)’s are the independent receiver noise samples at S1, and it is assumed that z₁(n) ~ $\mathcal{C}$$\mathcal{N}$(0, 1), ∀n. Note that on the right-hand side of (14.49), the first term is the self-interference of S1, while the second term contains the desired message from S2. Assuming that both ${\mathbf{\text{h}}}_1^T{\mathbf{\text{Ah}}}_1$ and ${\mathbf{\text{h}}}_1^T{\mathbf{\text{Ah}}}_2$ are perfectly known at S1 via training-based channel estimation prior to data transmission, S1 can first subtract its self-interference from y₁(n) and then coherently demodulate s₂(n). The above practice is known as analogue network coding (ANC). From (14.49), subtracting the self-interference from y₁(n) yields

${\tilde{y}}_1\left(n\right)={\tilde{h}}_{21}\sqrt{p_2}{s}_2\left(n\right)+{\tilde{z}}_1\left(n\right),n=1,\dots ,N$

(14.50)

where ${\tilde{\mathbf{h}}}_{21}={\text{h}}_1^T{\mathbf{\text{Ah}}}_2$, and ${\tilde{z}}_1\left(n\right)~\mathcal{C}\mathcal{N}\left(0,{\Vert A^H{h}_1^{*}\Vert }_2^2+1\right)$, where * denotes the complex conjugate. From (14.50), for a given A, the maximum achievable SNR for the end-to-end link from S2 to S1 via R, denoted by γ₂₁, is given as

${\gamma }_{21} = \frac{|h_1^{T}A{h}_2{|}^2{p}_2}{\Vert A^H{h}_1^{\ast }{\Vert }_2^2 + 1}$

(14.51)

Similarly, it can be shown that the maximum SNR ϓ₁₂ for the link from S1 to S2 via R is given as

${\gamma }_{12} = \frac{|h_2^{T}A{h}_1{|}^2{p}_1}{\Vert A^H{h}_2^{\ast }{\Vert }_2^2 + 1}.$

(14.52)

Now we minimize the relay transmission power given in (14.48), under the constraints that the achievable SNRs ϓ₂₁ and ϓ₁₂ over the two directions are above two target values, ϓ̄₁ and ϓ̄₂. As such, the optimization can be formulated as

$\begin{array}{ll}{\text{minimize}}_{\text{A}}\hfill & p_R: = \Vert A{h}_1{\Vert }_2^2{p}_1 + \Vert A{h}_2{\Vert }_2^2{p}_2 + \text{tr}(A{A}^H)\hfill \\ \text{subject}\text{to}\hfill & |h_1^{T}A{h}_2{|}^2\ge \frac{{\overline{\gamma }}_1}{p_2}\Vert A^H{h}_1^{\ast }{\Vert }_2^2 + \frac{{\overline{\gamma }}_1}{p_2}\hfill \\ \hfill & |h_2^{T}A{h}_1{|}^2\ge \frac{{\overline{\gamma }}_2}{p_1}\Vert A^H{h}_2^{\ast }{\Vert }_2^2 + \frac{{\overline{\gamma }}_2}{p_1},\hfill \end{array}$

(14.53)

For the convenience of analysis, we further modify the above problem as follows. First, let Vec(Q) be a K² x 1 vector associated with a K × K square matrix Q = [q₁,…, q_K ]^T, where q_k ∈ ℂ^K ,k = 1,…, K, by the rule of Vec$\left(\text{Q}\right)={\left[{\text{q}}_1^T,\cdots ,{\text{q}}_K^T\right]}^T$. Next, with b = Vec(A) and $\Theta =p_1{\text{h}}_1{\text{h}}_1^H+p_2{\text{h}}_2{\text{h}}_2^H+\text{I}$, we can express p_R in the objective function of (14.53) as $p_R=\text{tr}\left(A\Theta A^H\right)={\Vert \Phi \text{b}\Vert }_2^2$, with $\Phi ={\left(\text{diag}\left({\Theta }^T,{\Theta }^T\right)\right)}^{\frac{1}{2}}$, where diag(A, B) denotes a block-diagonal matrix with A and B as the diagonal square matrices. Similarly, let ${\text{f}}_1=\text{Vec}\left({\text{h}}_1{\text{h}}_2^T\right)$ and ${\text{f}}_2=\text{Vec}\left({\text{h}}_2{\text{h}}_1^T\right)$. Then, from (14.53) it follows that ${\left|{\text{h}}_1^T{\text{Ah}}_2\right|}^2={\left|{\text{f}}_1^T\text{b}\right|}^2$ and ${\left|{\text{h}}_2^T{\text{Ah}}_1\right|}^2={\left|{\text{f}}_2^T\text{b}\right|}^2$. Furthermore, by defining

${\mathbf{h}}_i=\left[\begin{array}{cccc}{\mathrm{h}}_i\left(1,1\right)& 0& {\mathrm{h}}_i\left(2,1\right)& 0\\ 0& {\mathrm{h}}_i\left(1,1\right)& 0& {\mathrm{h}}_i\left(2,1\right)\end{array}\right],i=1,2,$

we have $\Vert A^H{h}_i^{*}{\Vert }_2^2 = \Vert h_{i}b{\Vert }_2^2,$, i=1,2. Using the above transformations, (14.53) can be rewritten as

$\begin{array}{ll}{\text{minimize}}_b\hfill & p_R: = \Vert \text{Φ}b{\Vert }_2^2\hfill \\ \text{subject}\text{to}\hfill & |f_1^{T}b{|}^2\ge \frac{{\overline{\gamma }}_1}{p_2}\Vert h_{1}b{\Vert }_2^2 + \frac{{\overline{\gamma }}_1}{p_2}\hfill \\ \hfill & |f_2^{T}b{|}^2\ge \frac{{\overline{\gamma }}_2}{p_1}\Vert h_{2}b{\Vert }_2^2 + \frac{{\overline{\gamma }}_2}{p_1}.\hfill \end{array}$

(14.54)

The above problem can be shown to be still nonconvex. However, in the following, we show that the exact optimal solution could be obtained via a relaxed SDP problem.

We first define $E_0 = {\Phi }^H\Phi ,E_1 = \frac{p_2}{{\tilde{\gamma }}_1}{f}_1^T - h_1^H{h}_1$ and $E_2 = \frac{p_2}{{\tilde{\gamma }}_2}{f}_2^{*}{f}_2^T - h_2^H{h}_2$. Since standard semidefinite programming (SDP) formulations only involve real variables and constants, we introduce a new real matrix variable as X = [b_R; b_I] × [b_R; b_I]^T, where b_R = Re(b) and b_I = Im (b) are the real and imaginary parts of b, respectively. To rewrite the norm representations at (14.54) in terms of X, we need to rewrite E₀, E₁, and E₂, as expanded matrices F₀, F₁, and F₂, respectively, in terms of their real and imaginary parts. Specifically, to write out F₀, we first define the short notations Φ_R = Re(Φ) and Φ_I = Im(Φ); then we have

$F_0=\left[\begin{array}{cc}{\mathbf{\Phi }}_R^T{\mathbf{\Phi }}_R+{\mathbf{\Phi }}_I^T{\mathbf{\Phi }}_I& {\mathbf{\Phi }}_I^T{\mathbf{\Phi }}_R-{\mathbf{\Phi }}_R^T{\mathbf{\Phi }}_I\\ {\mathbf{\Phi }}_R^T{\mathbf{\Phi }}_I-{\mathbf{\Phi }}_I^T{\mathbf{\Phi }}_R& {\mathbf{\Phi }}_R^T{\mathbf{\Phi }}_R+{\mathbf{\Phi }}_I^T{\mathbf{\Phi }}_I\end{array}\right].$

The expanded matrices F₁ and F₂ can be generated from E₁ and E₂ in a similar way, where the two terms in E₁ or E₂ could first be expanded separately then summed together.

As such, problem (14.54) can be equivalently rewritten as

$\begin{array}{ccc}{\mathrm{minimize}}_X& p_R:=\mathrm{tr}\left(F_{0}X\right)& \\ \mathrm{subject}\mathrm{to}& \mathrm{tr}\left(F_{1}X\right)\ge 1,& \mathrm{tr}\left(F_{2}X\right)\ge 1,\mathrm{X}\succcurlyeq 0,\\ & \mathrm{rank}\left(\mathrm{X}\right)=1.& \end{array}$

(14.55)

The above problem is still not convex given the last rank-one constraint. However, if we remove such a constraint, this problem is relaxed into a convex SDP problem as shown below.

$\begin{array}{ll}{\mathrm{minimize}}_X\hfill & p_R:=\mathrm{tr}\left(F_{0}X\right)\hfill \\ \mathrm{subject}\mathrm{to}\hfill & \mathrm{tr}\left(F_{1}X\right)\ge 1,\mathrm{tr}\left(F_{2}X\right)\ge 1,\mathrm{X}\succcurlyeq 0.\hfill \end{array}$

(14.56)

Given the convexity of the above SDP problem, the optimal solution could be efficiently found by various convex optimization methods. Note that SDP relaxation usually leads to an optimal X for problem (14.56) that is of rank r with r ≥ 1, which makes it impossible to reconstruct the exact optimal solution for Problem (14.54) when r > 1. A commonly adopted method in the literature to obtain a feasible rank-one (but in general suboptimal) solution from the solution of SDP relaxation is via “randomization” (see, e.g., [27] and references therein). Fortunately, we show in the following that with the special structure in Problem (14.56), we could efficiently reconstruct an optimal rank-one solution from its optimal solution that could be of rank r with r > 1, based on some elegant results derived for SDP relaxation in [28]. In other words, we could obtain the exact optimal solution for the nonconvex problem in (14.55) without losing any optimality, and as efficiently as solving a convex problem.

Theorem 14.3.1. Assume that an optimal solution X* of rank r > 1 has been found for Problem (14.56), we could efficiently construct another feasible optimal solution X** of rank one, i.e., X** is the optimal solution for both (14.55) and (14.56).

Proof: Please refer to [21].

Note that the above proof is self-constructive, based on which we could easily obtain a routine to obtain an optimal rank-one solution for Problem (14.55) from X*. Then we could map the solution back to obtain an optimal solution for the problem in (14.53).

14.4    Exercises

Exercise 14.4.1. Please indicate whether the following sets are convex or not.

1.  $\left\{x\text{:}\frac{{\text{a}}^T\text{x} - \text{b}}{{\text{c}}^T\text{x }+ \text{d}}\le 1;c^{T}x+d<\text{0}\right\}$ ;

2.  {X : Ax = b, ‖x‖₂ = 1};

3.  {X : X₁₁a₀ + X₂₂a₁ ⪰ 0, a₀ ∈ Sⁿ, a₁ ∈ Sⁿ}; (X_ij stands for the ijth element in matrix X)

4.  {X : a^TXa = 1}

Exercise 14.4.2. Please indicate whether the following functions are convex or concave or neither.

1.  $f\left(\mathbf{\text{x}}\right)={\sup }_w\left\{\log {\displaystyle {\sum }_{i=1}^n{e}^{\frac{x_i}{w}}}\right\}$;

2.  f (x) = −(x₁x₂x₃)^1/3, x > 0;

3.  f (X) = lo gdet (A^TXA) ; X ≻ 0;

4.  $f\left(\mathbf{\text{x}}\right)={\text{x}}^{T}A\text{x+2x}-5,A=\left[\begin{array}{cc}0& 1\\ 1& 0\end{array}\right]$.

Exercise 14.4.3. With the following problem formulation, answer the followup questions.

$\begin{array}{l}\begin{array}{ll}\mathrm{minimize}\hfill & -\left(x_1+x_2\right)\hfill \\ \mathrm{subject}\mathrm{to}\hfill & {\Vert {\mathbf{a}}_1\mathbf{x}\Vert }_2\le 1,\hfill \\ \hfill & {\Vert {\mathbf{a}}_2\mathbf{x}-{\mathbf{b}}_2\Vert }_2\le 1,\hfill \end{array}\\ \mathrm{where}\mathrm{x}={\left[x_1,{\mathbf{x}}_2\right]}^T,{\mathbf{a}}_1={\mathbf{a}}_2=\left[\begin{array}{cc}1& 0\\ 0& 1\end{array}\right],\mathrm{and}{b}_2={\left[1,0\right]}^T.\end{array}$

where $f\left(\text{x}\right)={\text{x}}^{T}A\text{x}+2\text{x}-5,A=\left[\begin{array}{cc}0& 1\\ 1& 0\end{array}\right]$, and b₂ = [1,0]^T.

1.  Is this problem convex?

2.  Does Slater’s constraint condition hold?

3.  What is the optimal solution for this problem? (Hint: Try to solve this problem graphically if the KKT conditions are hard to solve.)

4.  What is the optimal objective value for the dual problem?

5.  What is the optimal value for the dual variable associated with the second constraint?

Exercise 14.4.4. Given the optimization problem shown in Exercise 14.4.3, please reformulate it as a semidefinite programming (SDP) problem, then derive the dual problem of the resulting SDP problem.

Exercise 14.4.5. With the following optimization problem, answer the followup questions.

$\begin{array}{ll}{\mathrm{maximize}}_P\hfill & {\displaystyle \sum _{i=1}^n\log \left(1+\frac{P_i}{{\delta }_i}\right)}\hfill \\ \mathrm{subject}\mathrm{to}\hfill & {\displaystyle \sum _{i=1}^n{P}_i=P_{total},}\hfill \\ \hfill & \mathrm{P}\ge 0,\hfill \end{array}$

where P = [P₁,…, P_n]^T, and δ_i > 0, i = 1,…, n.

1.  Is KKT sufficient for us to get the optimal solution for the above problem?

2.  Is KKT necessary for the optimal solution?

3.  Please write out the KKT conditions for this problem.

4.  Please solve the general form of optimal P_i’s.

5.  If n = 3, δ₁ = 2, δ₂ = 10, δ₃ = 5, and P_total = 10, what are the optimal P_i values?

Exercise 14.4.6. Let 1 <m <n be integers, and let A be an m × n matrix with full row rank. Furthermore, let c ∈ ℝⁿ and $\mathbf{\text{Q}}\in {\mathbf{\text{S}}}_{++}^n$ be given. Consider the following optimization problem:

$\begin{array}{cc}\mathrm{minimize}& \frac{1}{2}{\mathbf{x}}^T\mathbf{Qx}+{\mathbf{c}}^T\mathbf{x}\\ \mathrm{subject}\mathrm{to}& \mathbf{Ax}=\mathbf{0.}\end{array}$

(14.57)

1.  Explain why the KKT conditions are necessary and sufficient for (14.57).

2.  Write down the KKT conditions associated with (14.57). Hence, express the optimal solution to (14.57) in closed form.

Exercise 14.4.7. Let f : ℝⁿ → ℝⁿ be a differentiable convex function. Consider the following problem:

$\begin{array}{cc}\mathrm{minimize}& f\left(\mathbf{x}\right)\\ \mathrm{subject}\mathrm{to}& \mathbf{x}\ge \mathbf{0.}\end{array}$

(14.58)

Show that x̄ ∈ ℝⁿ is an optimal solution to (14.58) iff it satisfies the following system:

$\begin{array}{ccc}\nabla f\left(\overline{\mathbf{x}}\right)& \ge & \mathbf{0},\\ \overline{\mathbf{x}}& \ge & \mathbf{0},\\ {\overline{\mathbf{x}}}^T\nabla f\left(\overline{\mathbf{x}}\right)& =& 0.\end{array}$

Exercise 14.4.8. This problem is concerned with finding the minimum-volume enclosing ellipsoid of a set of vectors.

1.  Let u ∈ ℝ ⁿ be fixed, and define the function g:S ⁿℝ₊ $g\left(X\right)={\Vert Xu\Vert }_2^2$ Find ∇_g(X).

2.  Let V = {v¹,…, v^m} ∈ ℝⁿ be a set of vectors that span ℝⁿ. Consider the following problem:

$\begin{array}{ccc}\inf & -\log \det \left(\mathbf{X}\right)& \\ \mathrm{subject}\mathrm{to}& {\Vert {\mathbf{Xv}}^{\mathrm{i}}\Vert }_2^2\le 1& i=1,\dots ,m,\\ & \mathbf{X}\in {\mathbf{S}}_{++}^n.& \end{array}$

(14.59)

Let X̄ be an optimal solution to (14.59) (it can be shown that such an X̄ exists). Write down the KKT conditions that X̄ must satisfy.

3.  Suppose that m = n and vⁱ = e_i for i = 1,…,n, where e_i is the i-th standard basis vector. Using the above result, determine the optimal solution to (14.59) and find the corresponding Lagrange multipliers.

Exercise 14.4.9. Let a ∈ ℝⁿ, b ∈ ℝ and c ∈ ℝⁿ be such that a, c > 0 and b > 0. Consider the following problem:

$\begin{array}{ll}\mathrm{minimize}\hfill & {\displaystyle \sum _{i=1}^n\frac{c_i}{x_i}}\hfill \\ \mathrm{subject}\mathrm{to}\hfill & {\displaystyle \sum _{i=1}^n{\mathbf{a}}_i{x}_i=b,}\hfill \\ \hfill & \mathbf{x}\ge \mathbf{0.}\hfill \end{array}$

(14.60)

1.  Let u₁ ∈ ℝ and u₂ ∈ ℝⁿ be the Lagrange multipliers associated with the equality and inequality constraints, respectively. Write down the KKT conditions associated with (14.60).

2.  Give explicit expressions for x̄ ∈ ℝⁿ, ū₁ ∈ ℝ and ū₂ ∈ ℝⁿ such that (x̄, ū₁, ū₂) satisfies the KKT conditions above.

3.  Is the solution X ∈ Rⁿ found above an optimal solution to (14.60)? Explain.

References

[1]  M. S. Bazaraa, H. D. Sherali, and C. M. Shetty, Nonlinear Programming: Theory and Algorithms, 2nd ed., ser. Wiley-Interscience Series in Discrete Mathematics and Optimization. New York: John Wiley & Sons, Inc., 1993.

[2]  D. P. Bertsekas, Nonlinear Programming, 2nd ed. Belmont, Massachusetts: Athena Scientific, 1999.

[3]  S. Boyd and L. Vandenberghe, Convex Optimization. Cambridge: Cambridge University Press, 2004, available online at http://www.stanford.edu/~boyd/cvxbook/.

[4]  D. G. Luenberger and Y. Ye, Linear and Nonlinear Programming, 3rd ed., ser. International Series in Operations Research and Management Science. New York: Springer Science+Business Media, LLC, 2008, vol. 116.

[5]  R. A. Horn and C. R. Johnson, Matrix Analysis. Cambridge: Cambridge University Press, 1985.

[6]  M. Brookes, “The Matrix Reference Manual,” 2005, available online at http://www.ee.ic.ac.uk/hp/staff/dmb/matrix/intro.html.

[7]  M. Sion, “On General Minimax Theorems,” Pacific Journal of Mathematics, vol. 8, no. 1, pp. 171–176, 1958.

[8]  H. Komiya, “Elementary Proof for Sion’s Minimax Theorem,” Kodai Mathematical Journal, vol. 11, no. 1, pp. 5–7, 1988.

[9]  S. Cui, A. J. Goldsmith, and A. Bahai, “Energy-constrained modulation optimization,” IEEE Transactions on Wireless Communications, vol. 4, no. 5, pp. 2349–2360, September 2005.

[10]  S. Cui, M. Kisialiou, Z.-Q. Luo, and Z. Ding, “Robust blind multiuser detection against signature waveform mismatch based on second order cone programming,” IEEE Transactions on Wireless Communications, vol. 4, no. 4, pp. 1285–1291, July 2005.

[11]  R. Zhang and Y.-C. Liang, “Exploiting multi-antennas for opportunistic spectrum sharing in cognitive radio networks,” IEEE Journal of Selected Topics in Signal Processing, vol. 2, no. 1, pp. 88–102, Feb. 2008.

[12]  W. Yu and R. Lui, “Dual methods for nonconvex spectrum optimization of multicarrier systems,” IEEE Transactions on Communications, vol. 54, no. 7, pp. 1310–1322, July 2006.

[13]  L. Zhang, R. Zhang, Y.-C. Liang, Y. Xin, and S. Cui, “On the relationship between the multi-antenna secrecy communications and cognitive radio communications,” IEEE Transactions on Communications, vol. 58, no. 6, pp. 1877–1886, June 2010.

[14]  R. Zhang, S. Cui, and Y.-C. Liang, “On ergodic sum capacity of fading cognitive multiple-access and broadcast channels,” IEEE Transactions on Information Theory, vol. 55, no. 11, pp. 5161–5178, November 2009.

[15]  M. Chiang, “Balancing transport and physical layers in wireless multihop networks: Jointly optimal congestion control and power control,” IEEE Journal on Selected Areas in Communications, vol. 23, no. 1, pp. 104–116, January 2005.

[16]  J. Xiao, S. Cui, Z. Q. Luo, and A. J. Goldsmith, “Joint estimation in sensor networks under energy constraint,” IEEE Transactions on Signal Processing, vol. 54, no. 2, pp. 413–422, February 2005.

[17]  A. So and Y. Ye, “Theory of semidefinite programming for sensor network localization,” Mathematical Programming, vol. 109, pp. 367–384, 2007.

[18]  S. Cui and A. J. Goldsmith, “Cross-layer design in energy-constrained networks using cooperative MIMO techniques,” EURASIP’s Signal Processing Journal, Special Issue on Advances in Signal Processing-based Cross-layer Designs, vol. 86, pp. 1804–1814, August 2006.

[19]  R. Madan, S. Cui, S. Lall, and A. Goldsmith, “Modeling and optimization of transmission schemes in energy-constrained wireless sensor networks,” IEEE/ACM Transactions on Networking, vol. 15, no. 6, pp. 1359–1372, December 2007.

[20]  Z. Quan, S. Cui, H. V. Poor, and A. Sayed, “Collaborative wideband sensing for cognitive radios,” IEEE Signal Processing Magazine special issue on cognitive radios, vol. 25, no. 6, pp. 60–73, January 2009.

[21]  R. Zhang, Y.-C. Liang, C.-C. Chai, and S. Cui, “Optimal beamforming for two-way multi-antenna relay channel with analogue network coding,” IEEE Journal on Selected Areas of Communications, vol. 27, no. 6, pp. 699–712, June 2009.

[22]  R. Zhang and S. Cui, “Cooperative interference management with miso beamforming,” IEEE Transactions on Signal Processing, vol. 58, no. 10, pp. 5450–5458, October 2010.

[23]  S. P. Boyd, S.-J. Kim, D. D. Patil, and M. A. Horowitz, “Digital Circuit Optimization via Geometric Programming,” Operations Research, vol. 53, no. 6, pp. 899–932, November 2005.

[24]  T. Cover and J. Thomas, Elements of Information Theory. New York: Wiley, 1991.

[25]  I. E. Telatar, “Capacity of multi-antenna Gaussian channels,” Eur. Trans. Telecommun., vol. 10, no. 6, pp. 585–595, November 1999.

[26]  R. G. Bland, D. Goldfarb, and M. J. Todd, “The ellipsoid method: a survey,” Operations Research, vol. 29, no. 6, pp. 1039–1091, November 1981.

[27]  Z.-Q. Luo and W. Yu, “An introduction to convex optimization for communications and signal processing,” IEEE Journal of Selected Topics in Signal Processing, vol. 24, no. 8, pp. 1426–1438, August 2006.

[28]  Y. Ye and S. Zhang, “New results on quadratic minimization,” SIAM J. Optim., vol. 14, pp. 245–267, 2003.

¹Recall that for a generic optimization problem ${\min }_{\text{x}\in S\in {ℝ}^n}$ f(x), a point x* ∈ S is called a global minimum if f(x*) ≤ f(x) for all x ∈ S. On the other hand, if there exists an ϵ > 0 such that the point x* ∈ S satisfies f(x*) ≤ f(x) for all x ∈ S ∩ B°(x*, ϵ), then it is called a local minimum. Here, B°(x̄, ϵ) = denotes the open ball centered at x̄ ∈ ℝⁿ of radius ϵ > 0.

²A map A : ℝ^m → ℝⁿ is said to be affine if there exists an n × m matrix B and a vector d ∈ ℝⁿ such that A(x) = Bx + d for all x ∈ ℝ^m.

³Let S be a nonempty convex subset of ℝⁿ. We say that f : S → ℝ is convex at x̄ ∈ S if f(αx̄ + (1 − α)x) ≤ αf (x̄) + (1 − α)f (x) for all a ∈ (0, 1) and x ∈ S. Note that a function f: S → ℝ can be convex at a particular point x̄ ∈ S without being convex on S.