EE5121 Optimization - Background summary

A vector \(x\) in \(n\) dimensional space, \(\mathbb{R}^n\), is represented as a column with \(n\) entries like so: \(x = \begin{bmatrix} x_1 \\ x_2 \\ \ldots \\ x_n \end{bmatrix}\). The transpose, \(x^T\) is simply a row vector with the same entries, whereas the hermitian (or conjugate transpose), \(x^H\) has the complex conjugate entries as a row vector.

Similarly, the components of a matrix \(A \in \mathbb{R}^{m\times n}\) are denoted as \(A_{ij}\). An often encountered matrix is a positive definite matrix, defined as follows: \(x^TAx > 0 \,\, \forall x \in \mathbb{R}^n\).

Inner and outer product representations of a matrix product: Say that we have three matrices such that \(C=AB\). In the usual inner product representation, we can write the element \(C_{ij} = A_i \, b_j\), where \(A_i\) is row-\(i\) of \(A\), and \(b_j\) is column-\(j\) of \(B\). Another equivalent way of expressing \(C\) is to write it in outer product form: \(C = \sum_{i=1}^p a_i B_i\), where \(a_i\) is column-\(i\) of \(A\), and \(B_i\) is row-\(j\) of \(B\) and \(p\) is the number of columns of \(A\) (or number of rows of \(B\)). This outer product role plays an important role in the SVD as we shall see further.

The p-norm of a vector \(x \in \mathbb{R}^n\) is defined as: \(\|x\|_p = \left(\sum_{i=1}^n |x_i|^p\right)^{1/p} \,\, 1\leq p \leq \infty\). The most commonly encountered norm is for \(p=2\) (also called the Euclidean norm), whereas the \(\infty\) norm is defined as \(\|x\|_{\infty} = \underset{i\in[1,n]}{\text{max}} \, |x_i|\).

Important properties of norms are:

Associated with any norm is it’s dual norm, defined as: \(\|x\|_D = \underset{\|y\|=1}{\text{max}} \, x^Ty\).

Matrix norms that are consistent with the above defined vector norms are defined as: \(\|A\| = \underset{x \neq 0}{\text{sup}} \, \frac{\|Ax\|}{\|x\||}\).

The 2-norm is often quite useful and takes the form \(\|A\|_2=\) largest eigenvalue of \((A^TA)^{1/2}\). Another useful norm (though not a consistent norm) is the Frobenius norm, defined as: \(\|A\|_F = \left(\sum_i \sum_j |A_{ij}|^2 \right)^{1/2}\).

The condition number is a very useful concept in numerical applications and for a non-singular matrix \(A\) is defined as: \(\kappa(A) = \|A\| \|A^{-1}\|,\,\,\text{for any matrix norm } \|.\|\).

The subset \(S \subset \mathbb{R}^n\) is a subspace of \(\mathbb{R}^n\) if given any two elements in it, their linear combination also lies in it.

A set of vectors \(\{s_1,s_2,\ldots,s_m\} \in \mathbb{R}^n\) is called:

Combining the above two concepts, we call the vectors \(\{s_1,s_2,\ldots,s_m\} \in \mathbb{R}^n\) a basis of \(S\) if the vectors are linearly independent and a spanning set for \(S\). In such a case, the dimension of \(S\) is the number of elements in the basis, \(m\).

There are four fundamental subspaces associated with a matrix \(A \in \mathbb{R}^{m\times n}\), best visualized like so:

Given a square matrix \(A\), we say that a non-zero vector \(x\) is its eigenvector with an eigenvalue \(\lambda\) if the following holds: \(Ax=\lambda x\).

If a matrix is symmetric, its eigenvalues are all real, and with the associated eigenvectors \(q_i\) admits the following spectral decomposition: \(A = Q\Lambda Q^T = \sum_{i=1}^n \lambda_i q_i q_i^T\), where \(Q\) is an orthogonal matrix with \(q_i\)'s as column vectors. If further, the matrix is symmetric positive definite, the eigenvalues are all positive real numbers.

All matrices have a singular value decomposition as \(A = U\Sigma V^T\), where \(U,V\) are square orthogonal matrices and \(\Sigma\) takes the form:

It is easy to express the pseudoinverse of a matrix, \(A^{+}\) using the SVD \(A^{+} = V \Sigma^{+} U^T\), where \(\Sigma^{+}\) is a diagonal matrix of the same size as \(\Sigma^T\) and entries \(\Sigma^{+}_{ii} = 1/\sigma_i\).

For symmetric positive definite matrix \(A\) with singular values \({\sigma_i}\), the additional property holds: \(\|A\|_2 = \sigma_1(A)\), and \(\|A^{-1}\| = 1/\sigma_n(A)\). This implies that the condition number of a matrix can be expressed in terms of the minimum and maximum singular values: \(\kappa = \sigma_1/\sigma_n\).

For a square matrix \(A\), the following important properties hold:

The LU decomposition of a square matrix, \(A\), is given as \(PA = L U\) where \(L\) is lower triangular and \(U\) is upper triangular. When solving a matrix equation of the form \(Ax = b\), performing a one-time factorization of \(A\) allows for multiple solves for different right hand sides \(b\).

When \(A\) is symmetric positive definite, the Cholesky factorization leads to \(A=LL^T\), where \(L\) is lower triangular with real and positive diagonal entries.

For rectangular matrices, the QR decomposition gives \(AP = QR\), where \(Q\) is orthogonal and \(R\) is upper triangular.

The sequence is said to converge to some point \(x\) (expressed as \(\lim_{k\rightarrow\infty} x_k = x\)) if for any \(\epsilon>0\), there is an index \(K\) such that \(\|x_k - x\|\leq \epsilon\) for all \(k\geq K\).

Given an index set \(\mathcal{S}\subset\{1,2,3,\ldots\}\), a subsequence of \(\{x_k\}\) is denoted by \(\{x_k\}_{k\in\mathcal{S}}\). For this subsequence, \(\hat{x}\) is called an accumulation or limit point if there is an infinite set of indices \(k_1,k_2,\ldots\) such that the subsequences \(\{x_{k_i}\}_{i=1,2,\ldots}\) converges to \(\hat{x}\). A sequence converges iff it has exactly one limit point.

A sequence is said to be a Cauchy sequence if for any \(\epsilon>0\) there exists and integer \(K\) such that \(\|x_k-x_l\|\leq \epsilon\) for all indices \(k\geq K\) and \(l \geq K\). A sequence converges iff it is a Cauchy sequence.

A sequence is bounded above if there is a scalar \(u\) s.t. \(t_k \leq u \, \forall k\) (and an analogous definition for being bounded below follows).

A nondecreasing sequence is one where \(t_{k+1} \geq t_k \, \forall k\). If a sequence is nondecreasing and bounded below, it converges, i.e. \(\lim_{k\rightarrow \infty} t_k = t\). An analogous definition for being nonincreasing and bounded below follows.

The supremum of a sequence \(\{t_k\}\) is the smallest number \(u\) such that \(t_k \leq u\), denoted as sup \(\{t_k\}\). Similarly, the infimum of the sequence is the largest number \(v\) such that \(t_k \geq v\), denoted as inf \(\{t_k\}\).

It is bounded if for some real number \(M\), we have \(\|x\|\leq M\) for all \(x\in\mathcal{F}\).

It is open if for every \(x\in\mathcal{F}\), we can find an \(\epsilon > 0\) such that a ball containing \(x\) lies within itself, i.e. \(\{y | \|y-x\| \leq \epsilon\} \subset \mathcal{F}\).

It is closed if for all possible sequences \(\{x_k\} \in \mathcal{F}\), all limit points are elements of \(\mathcal{F}\).

The interior, denoted by int \(\mathcal{F}\), is the largest open set contained in \(\mathcal{F}\). Similarly, the closure, denoted by cl \(\mathcal{F}\), is the smallest closed set containing \(\mathcal{F}\). Obviously, if \(\mathcal{F}\) is open, then int \(\mathcal{F}\) = \(\mathcal{F}\), whereas if it is closed, then cl \(\mathcal{F}\) = \(\mathcal{F}\). Additionally, the union of finitely many closed sets is closed, while the intersection of closed sets is closed. The intersection of finitely many open sets is open, while and union of open sets is open.

It is compact if every sequence \(\{x_k\}\) in \(\mathcal{F}\) has at least one limit point, and all such limit points are in \(\mathcal{F}\). An important result in topology states — \(\mathcal{F}\in\mathbb{R}^n\) is closed and bounded \(\implies\) \(\mathcal{F}\) is compact.

The neighbourhood of a point \(x\) is an open set containing it. For example, the open ball of radius \(\epsilon\) around \(x\) is — \(\mathbb{B}(x,\epsilon) = \{y | \, \|y-x\|< \epsilon\}\).

Given two points \(x_1,x_2\in\mathbb{R}^n\) and \(\theta \in \mathbb{R}\), points of the form \(y = \theta x_1 + (1-\theta) x_2\) form a line passing through \(x_1,x_2\).

A set \(\mathcal{S}\subseteq \mathbb{R}^n\) is affine if the line through any two distinct points in C lies in C. Generalizing to more than 2 points, we say that the point given by \(\sum_i \theta_i x_i\) where \(\sum_i \theta_i =1\) is an affine combination of the points \(\{x_i\}\).

The set of all affine combinations of points in some set \(\mathcal{S} \subseteq \mathbb{R}^n\) is called the affine hull of \(\mathcal{S}\), denoted as: aff \(\mathcal{S} = \{\sum_i \theta_i x_i \, | \, \{x_i\} \in \mathcal{S}, \, \sum_i \theta_i = 1\}\). It is the smallest affine set that contains \(\mathcal{S}\).

A set \(\mathcal{S}\) is convex if the line segment between any two points in \(\mathcal{S}\) lies in \(\mathcal{S}\), i.e. for \(x_1,x_2 \in \mathcal{S}\) and any \(0\leq \theta\leq 1\), we have \(\theta x_1 + (1-\theta) x_2 \in \mathcal{S}\). See Fig 2.2 of BV.

We say that the point given by \(\sum_i \theta_i x_i\) where \(\sum_i \theta_i =1\) and \(\theta_i \geq 0\) is a convex combination of the points \(\{x_i\}\). This leads to the definition of the convex hull of a set \(\mathcal{S}\) as the set of all convex combinations of points in the set, denoted as conv \(\mathcal{S}\).

A set \(\mathcal{S}\) is called a cone if for every \(x\in \mathcal{S}\) and \(\theta \geq 0\), we have that \(\theta x \in \mathcal{S}\).

A set \(\mathcal{S}\) is called a convex cone if it is convex and a cone, i.e. for every \(x_1, x_2 \in \mathcal{S}\) and \(\theta_1, \theta_2 \geq 0\), we have that \(\theta_1 x_1 + \theta_2 x_2 \in \mathcal{S}\). See Fig. 2.4 of BV.

A function \(f\) is continuous at \(x\in\) dom \(f\) if for all \(\epsilon>0\) there exists a \(\delta\) s.t.:

In the above definition, the constant \(\delta\) depends on \(\epsilon,x,y\) in general. In case we can find the constant \(\delta\) as purely a function of \(\epsilon\), then we term the function as uniformly continuous.

The function \(f\) is said to be Lipschitz continuous on some set \(\mathcal{N} \subset \mathcal{D}\) if there is a constant \(L\) such that

The function \(f\) is called (Frechet) differentiable at \(x\) if there exists a vector \(g\in \mathbb{R}^n\) such that

A function is differentiable on a domain if \(\nabla f(x)\) exists for all \(x\) in the domain. It is further called continuously differentiable if \(\nabla f(x)\) is a continuous function of \(x\).

When \(f\) is vector valued, for e.g. \(f:\mathbb{R}^n\to \mathbb{R}^m\), the following definitions hold:

The usual chain rule of differentiation is applicable as follows. Let \(x\) depend on \(t\), i.e. \(x = x(t)\). In this case, with \(h(t) = f(x(t))\), we get: \(\nabla h(t) = \sum_i \frac{\partial f}{\partial x_i} \frac{\partial x_i}{\partial t} = \nabla x(t) \nabla(f(x(t)))\). In the final expression, interpret \(\nabla x(t)\) as a row vector.

The directional derivative of a function in a direction \(p\) is given by the definition: \(D(f(x),p) = \lim_{\epsilon\to 0} \frac{f(x+\epsilon p) - f(x)}{\epsilon}\).

The Hessian is a matrix of second partial derivatives of \(f\) and is defined as:

Mean value theorem: In the univariate case, given a continuously differentiable function \(f : \mathbb{R} \to \mathbb{R}\), and two real numbers \(x,y\) satisfying \(x<y\), then \(f(y) = f(x) + f'(z)(y-x)\), for some \(z\in(x,y) \).

The above theorem also has an integral counterpart: From the fundamental theorem of calculus, given a continuous function \(f : \mathbb{R} \to \mathbb{R}\), defined over \( [a,b\) ], and \(F\) defined as: \(F(x) = \int_a^x f(t)dt\), then \(F\) is uniformly continuous on [a,b] and differentiable on \( (a,b) \) and \(F'(x) = f(x)\). We can conveniently write this as \(f(x) = \int_{a}^x f'(t)dt\). Invoking the MVT from the previous point, we can write \(f(y) - f(x) = \int_x^y f'(t) dt\). Performing a change of variables, \( t \rightarrow x+p(y-x)\), leads to \(f(y) - f(x) = (y-x) \int_0^1 f'(x+p(y-x)) dp\). This is referred to as the integral version of the MVT (compare with the original \( f(y) - f(x) = (y-x) f'(z)\) for some \(z\in(x,y)\)).