Homework 6

Due: Nov. 29, 22:00:00

Linear programming

1. Consider the following optimization problem:

   $\max \ \sum_{i=1}^n c_i \cdot |x_i - d_i |$

   subject to: $Ax=b$, $x≥ \mathbf{0}$,

   where $A \in \mathbb{R}^{m\times n}$, $b \in \mathbb{R}^m$, and $c, d \in \mathbb{R}^n$ are given. Assume that $c_i \geq 0$ for all $i$.

   This is not a linear program since the objective function involves absolute values.

   Is it possible to formulate it equivalently as a linear program?

Gradient descent

2. Let

   $$Q = \begin{pmatrix} 2 & 0\\ a & 2 \end{pmatrix}$$

   be a $2\times 2$ real matrix, where $a$ is a real number.

   Suppose $f: \mathbb{R}^2 \to \mathbb{R}$ is a quadratic function where $f(x)=x^{\mathsf{T}} Qx$.

   • Determine the range of $a$ such that $f$ has a global minimum value.

   • Assume $a=2$. We would like to use the gradient descent method with fixed step size to minimize $f$. Determine the range of the step size so that the algorithm will converge no matter which initial point we choose, and give the reason.

   • Suppose $0< a < 4$. Compute the condition number of $\nabla^2 f$.

     If $a$ goes to $4$, what happens to the condition number? Does the result given by the gradient descent with fixed step size converge if $a = 4$?