Homework 6

Due: Nov. 29, 22:00:00

Linear programming

  1. Consider the following optimization problem:

    subject to: , ,

    where , , and are given. Assume that for all .

    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

  1. Let

    be a real matrix, where is a real number.

    Suppose is a quadratic function where .

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

    • Assume . We would like to use the gradient descent method with fixed step size to minimize . 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 . Compute the condition number of .

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