Optimization Models
Home
Software
Links
Index
Contact
1. Introduction
1.1. Overview
1.2. Optimization Models
2. Linear Algebra
2.1. Vectors
2.2. Matrices
2.3. Linear Equations
2.4.  Least-Squares
2.5. Eigenvalues
2.6  Singular Values
3. Convex Models
3.1. Convexity
3.2. LP and QP
3.3. SOCP
3.4. Robust LP
3.5. GP
3.6. SDP
3.7. Non-Convex Models
4. Duality
4.1. Weak Duality
4.2. Strong Duality
4.3.  Applications
5. Case Studies
5.1. Senate Voting
5.2. Antenna Arrays
5.3. Localization
5.4. Circuit Design

Exercises

Matrices > Exercises

Matrix products

  1. Let f : mathbf{R}^m rightarrow mathbf{R}^k and g : mathbf{R}^n rightarrow mathbf{R}^m be two maps. Let h : mathbf{R}^n rightarrow mathbf{R}^k be the composite map h = f circ g, with values h(x) = f(g(x)) for x in mathbf{R}^n. Show that the derivatives of h can be expressed via a matrix-matrix product, as J_h(x) = J_f(g(x)) cdot J_g(x), where the Jacobian matrix of h at x is defined as the matrix J_h(x) with (i,j) element partial h_i/partial x_j(x).

Special matrices

  1. A matrix P in mathbf{R}^{n times n} is a permutation matrix if it is a permutation of the columns of the n times n identity matrix.

    1. For a n times n matrix A, we consider the products PA and AP. Describe in simple terms what these matrices look like with respect to the original matrix A.

    2. Show that P is orthogonal.

    3. Show that P^2 = I.

Linear maps, dynamical systems

  1. Let f : mathbf{R}^n rightarrow mathbf{R}^m be a linear map. Show how to compute the (unique) matrix A such that f(x) = Ax for every x in mathbf{R}^n, in terms of the values of f at appropriate vectors, which you will determine.

  2. Consider a discrete-time linear dynamical system (for background, see here) with state x in mathbf{R}^n, input vector u in mathbf{R}^p, and output vector y in mathbf{R}^k, that is described by the linear equations

x(t+1) = Ax(t) + Bu(t), ;; y(t) = Cx(t),

with A in mathbf{R}^{n times n}, B in mathbf{R}^{n times p}, and C in mathbf{R}^{k times n} given matrices.

    1. Assuming that the system has initial condition x(0) = 0, express the output vector at time T as a linear function of u(0),ldots,u(T); that is, determine a matrix H such that y(T) = H bar{u}(T), where bar{u}(T) := (u(0),ldots,u(T-1)) is a vector containing all the inputs up to and including at time T-1.

    2. What is the interpretation of the range of H?

Matrix inverses, norms

  1. Show that a square matrix is invertible if and only if its determinant is non-zero. You can use the fact that the determinant of a product is a product of the determinant, together with the QR decomposition of the matrix A.

  2. Let A in mathbf{R}^{m times n}, B in mathbf{R}^{n times p}, and let C := AB in mathbf{R}^{m times p}. Show that |C| le |A| cdot |B| where | cdot | denotes the largest singular value norm of its matrix argument.