Reading Notes on Chapter 2
In the front of this chapter, defining some concepts of mathematical such as, convex set, affine function, etc. For more detail about these, please referring to Wiki.
2.1 Mathematical background: convex optimization
2.1.1 Convex sets and convex functions
Definition 2.1.1 (Convex set)
A set S ⊆ R^n is convex if ax+(1-a)y ∈ S whenever x,y ∈S and a ∈[0,1]. Since ax+(1-a)y, for a ∈[0,1], describes the line segment between x and y, a convex set can be pictorially depicted as Figure 2.1: given any two points x,y ∈ S, the line segment between x and y lies entirely in S.
Definition 2.1.2 (Convex hull)
The convex hull of set S, denoted by Co(S), is the smallest convex set that contains S, and contains all convex combinations of points S, i.e., see Figure 2.2 for an example.
Definition 2.1.3 (Convex function)
A function f(x): S⊆ R^n →R is a convex function if S is a convex set and the following inequality holds for any x,y∈S and a ∈[0,1]:
f(a(x)+(1-a)y) ≤ a f(x) + (1-a) f(y);
f(x) is strictly convex if the above inequality is strict for all a∈[0,1] and x ≠ y. Pictorially, f(x) looks like a bowl, as shown in Figure 2.3.
Definition 2.1.4 (Concave function)
The concave function is like a opposite direction with convex function. as shown in Figure 2.4.
Definition 2.1.5 (Affine function)
Affine Functions in 1D:
An affine function is a function composed of a linear function + a constant and its graph is a straight line. The general equation for an affine function in 1D is: y = Ax + c.
An affine function demonstrates an affine transformation which is equivalent to a linear transformation followed by a translation. In an affine transformation there are certain attributes of the graph that are preserved. These include:
- If three points all belong to the same line then under an affine transformation those three points will still belong to the same line and the middle point will still be in the middle.
- Parrallel lines remain parrallel.
- Concurrent lines remain concurrent.
- The ratio of length of line segments of a given line remains constant.
- The ratio of areas of two triangles remains constant.
- Ellipses remain ellipses and the same is true for parabolas and hyperbolas.
The next are some conditions used for verify the convexity of a function.
Result 2.1.1 (First-order condition I)
Let f : S ⊂ R →R be a function defined over a convex S. If f is differentiable and the derivative f'(x) is non-decreasing in S, f(x) is convex (strictly convex) over S.
Result 2.1.2 (First-order condition II)
If x is one-dimensional, this condition implies that the tangent of the function at any point lies below the function, as shown in Figure 2.5.
f(y)≥f(x)+∇f(x)(y-x), for any x≠y, x,y∈R. (2.1)
Result 2.1.3 (Second-order condition)
If f is a twice differentiable function defined over the convex set S. Then, f is a convex (strictly convex) function if the Hessian matrix H with H_ij is positive semidfinite (positive definite) over S.
Result 2.1.4 (Strict separation theorem)
If there is exist an point not contained in S, then there will be a hyper-plane separate the point from the S.
2.1.2 Convex optimization
Definition 2.1.6 (Local maximizer and global maximizer)
If f(x*) is maximizer within a limited range of point x*, then it’s local maximizer, if it’s maximum over the whole domain of function, then it’ s global maximizer.
If f(x) is a continous function over a compact set S, then f(x) achieves its maximum over this set.
If f(x) is differentiable, then any local maximizer x* in the interior of S ⊆ R^n, satisfies
∇f(x*) =0. (2.3)
If f(x) is a concave function over S, condition (2.3) is also sufficient for x* to be a local maximizer.
If f(x) is concave, then a local amximizer is also a global maximizer. In genral, multiple global maximizers may exist. If f(x) is strictly concave, the global maximizer x* is unique.
Results 2.16 and 2.17 hold for convex functions if the max in the optimization problem 2.2 is replaced by min, and maximizer is replaced by minimizer in Results 2.1.6 and 2.17.
If f(x) is a differentiable function over set S and x* is a maximizer of the function, then
∇f(x*) dx ≤ 0
for any feasible direction dx, where a non-zero vector dx is called a feasible direction if there exists α such that x + adx ∈ S for any 0 ≤ a ≤ α .
Further, if f(x) is a concave function, then x* is a maximizer if and only if
∇f(x*) δx ≤0
for any δx such that x*+ δx ∈ S.
D(λ,μ) is a convex function and D(λ,μ) ≥ f*. which means that the dual function is an upper bound on the maximum of the optimization problem (2.4)-(2.6). we can optimize over λ and μ to obtain the best upper bound, which yields the following minimization problem, called the Lagrange dual problem:
inf D(λ ,μ). over λ>=0, (2.7)
Let d* be the minimum of the dual problem, then the difference between d* and f* is called the duality gap. If the gap is zero, we say strong duality holds if d*=f*. So we can solve either the primal problem or the dual problem to obtain f*. A simple yet frequently used condition to check strong duality is Slater’s condition.
Theorem 2.1.2 (Slater’s condition)
Strong duality holds if the following conditions are true:
- f(x) is a concave function and h_i(x) are convex function;
- g_j(x) are affine functions;
- there exists an x that belongs to the relative interior of S such that h_i(x) < 0 for all i and g_j(x) =0 for all j.
2.2 Resource allocation as utility maximization
The goal of resource allocation is to solve the following optimization problem, called Network Utility Maximization (NUM):
2.2.1 Utility functions and fairness