Convexity

We conclude this section by giving a geometrical condition which enables us to guarantee solutions are available using the above techniques. One way to guarantee good behaviour is to work with convex functions. A convex set is geometrically very simple. A set C is convex if x¹ $\in$ C, x² $\in$ C means that $\lambda$x¹ + (1 - $\lambda$)x² $\in$ C whenever 0$\le$$\lambda$$\le$1. In other words, if any line joining two points in c lies entirely in C.

You may already have met a convex function -- one in which the points above the graph of the function (the ``supergraph'') form a convex set. Equivalently, a function is convex if the line joining two points on the graph of f always lies above the graph of f.

An obvious way to generate a convex set is as the intersection of a collection of half planes; hence the set of feasible solutions of a linear programming problem forms a (possibly empty) convex set.

There are other very natural ways to generate convex sets. Let x¹, x², ..., x^k be elements of Rⁿ. It is essentially trivial to show that the set of all convex combinations of x¹, x², ..., x^k is a convex set. Here is the argument: let u = $\l$₁x¹ + $\l$₂x² +...+ $\l$_kx^k and v = $\mu_{1}^{}$x¹ + $\mu_{2}^{}$x² +...+ $\mu_{k}^{}$x^k be two convex combinations of x¹, x², ..., x^k. Write down $\l$u + (1 - $\l$)v and show that, when 0 $\leq$ $\l$ $\leq$ 1, this is also a convex combination of x¹, x², ...,  x^k.

It is of interest that the set of optimal solutions of a linear programming problem is a convex set. The next two examples discuss this:

Example 7..17   Show that if x¹, x², ..., x^k are optimal solutions of a linear programming problem, then any convex combination of x¹, x², ..., x^k is also an optimal solution.

Solution Let $\l$₁x¹ + $\l$₂x² +...+ $\l$_kx^k be any convex combination of x¹, x², ...,  x^k. Let the objective function be c₁x₁ + c₂x₂ +...+ c_nx_n. Since x¹, x², ...,  x^k all have the same objective value, z say, then, for all i,

c₁x₁ⁱ + c₂x₂ⁱ +...+ c_nx_nⁱ = z,

where xⁱ = (x₁ⁱ, x₂ⁱ,..., x_nⁱ). So (why ?),

c₁($\l$₁x₁¹ +...+ $\l$_kx₁^k) +...+ c_n($\l$₁x_n¹ +...+ $\l$_kx_n^k) = z,

which shows (why ?) that $\l$₁x¹ + $\l$₂x² +...+ $\l$_kx^k also has objective value z. Hence the result.

This solution can be written more simply by using matrix notation, letting the objective function be c^Tx.

Example 7..18   Prove (by induction on k) that, if x¹, x², ..., x^k belong to a convex set C, then any convex combination of x¹, x², ..., x^k belongs to C.

Solution Let v = $\l$₁x¹ + $\l$₂x² +...+ $\l$_kx^k be any convex combination of x¹, x², ...,  x^k. Write v = (1 - $\l$_k)u + $\l$_kx^k, where

u = $${\frac{{\l _1}}{{1-\l _k}}}$$x¹ + $${\frac{{\l _2}}{{ 1-\l _k}}}$$x² +...+ $${\frac{{\l _{k-1}}}{{ 1-\l _k}}}$$x^k-1.

By the induction hypothesis (why ?), u belongs to C and hence v belongs to C.

We now return to our main thread; that convexity gives us a handle on uniqueness. It is geometrically clear that a (strictly) convex function cannot have two different local minima, while if the same value occurs as a local minimum at different places, the graph must be flat between them, so neither minimum is isolated (and f can't be strictly convex).

Say that f is concave if - f is convex. To help remember the difference, note that x² is convex, while - x² is concave.

Taylors theorem in its general form allows us to analyse f. At the point x, we have

$$f(\mathbf{x}+ \mathbf{h}) = f(\mathbf{x}) +\mathbf{h}.\ensur... ...\mathbf{h}^TG(\mathbf{x})\mathbf{h}+ \text{higher order terms}$$

exactly as in the two variable case. We have written

G = $$\begin{pmatrix} \displaystyle \frac{\partial^{2}f}{\partial x_1^... ... }&\ldots& \displaystyle \frac{\partial^{2}f}{\partial x_n^{2}} \end{pmatrix}$$

With our usual assumptions, G(x) is symmetric and so it can be diagonalised; let $\l$₁, $\l$₂,...,$\l$_n be the eigenvalues of G(x) and write D(x) = D = diag($\l$₁,$\l$₂,...,$\l$_n). Then there is an orthogonal P (ie P^T = P^-1 such that G(x) = P^TDP, and we have

$$f(\mathbf{x}+ \mathbf{h}) = f(\mathbf{x}) +\mathbf{h}.\ensur... ...{h}^TP^TD(\mathbf{x})(P\mathbf{h}) + \text{higher order terms}$$

At a critical point, $\ensuremath{\nabla}{} f(\mathbf{x}) = 0$ and so

f (x + h) = f (x) + $${\frac{{1}}{{2}}}$$$$\left(\vphantom{\l _1u_1^2 + \l _2u_2^2 + \dots + \l _nu_n^2 }\right.$$$\l$₁u₁² + $\l$₂u₂² + ... + $\l$_nu_n²$$\left.\vphantom{\l _1u_1^2 + \l _2u_2^2 + \dots + \l _nu_n^2 }\right)$$ + higher order terms

where Ph = u. Thus f is convex iff $\l$_i$\ge$ 0 for all i; we can read the behaviour of f from the set of eigenvalues of the Hessian. This leads to:

Theorem 7..19 (Second Derivative Theorem)   Assume that f is twice differentiable on the convex set D. Then f is convex on D if its Hessian G is positive semidefinite, so x^TGx$\ge$ 0 for each x.

Note that if f is linear then it is both convex and concave. The function f (x) = x₁² + ... + x_n² is strictly convex, since

G = $$\begin{pmatrix} 2&0&\dots&0\\ 0&2&\dots&0\\ \hdotsfor[1.5]{4}\\ 0&0&\dots&2 \end{pmatrix}$$

Theorem 7..20 (Second Kuhn-Tucker)   Let f : D$\to$$\mathbb {R}$ⁿ be a convex function and suppose that each constraint c_j is concave on D. Assume that each of the functions involved is twice continuously differentiable. Then every solution of the Kuhn-Tucker conditions is a global minimum of the corresponding NLCO problem.