Course Page for Math 309 Fall 2008 - Adam Oberman Math

Course Page for Math 309 Fall 2008

Contents

Homework 4, due October 23rd (due date extended to Friday)

  • Plot and minimize the following functions
    • f(x) = max( | x | , | 2x − 3 | )
    • f(x) = | x | + | 2x − 3 |
  • Consider the matrices and the vector

M_1 =\left(\begin{array}{cc}1 & 0 \\0 & 1 \\1 & 1\end{array}\right) \quad M_2 = \left(\begin{array}{cc}5 & 0 \\0 & 1 \\2 & 1\end{array}\right)
b = \left(\begin{array}{c}0 \\0 \\4\end{array}\right) .

    • Do a surface plot the functions \| M_1 x - b \|_p for p = 1,2,\infty using matlab.

For each of the matrices, do the following.

    • minimize the residual \| Mx - b \|_2
    • minimize the residual \| Mx - b \|_1
    • minimize the residual \| Mx - b \|_\infty


Homework 5, due October 30th

  • verify your solutions from the previous HW by reformulating the problems as a Linear Program, and solving the LP numerically, using CVX in Matlab. (You may also use another language if you prefer).
  • Consider the norm minimization problem

\min \| x\|_p subject to Mx = b for p = 1,2,\infty

    • Consider the two dimensional problem with the single linear constraint y = 5 − 7x. Draw a diagram of the problem and solve analytically (by hand) for each p = 1,2,\infty
    • Reformulate the problem for p =\infty as a Linear Program
    • Now consider the three dimensional problem, with the single linear constraint 3x + 4y − 5z = 7 Draw a diagram of the problem and solve analytically (by hand) for each p = 1,2,\infty
    • verify your solutions for p = 1, \infty reformulating the problems as a Linear Program and solving the LP numerically, using CVX in Matlab. (or another language)
    • verify your solutions for p = 2 by reformulating the problem as a linear equation and solving the linear equation (either by hand or numerically).

Homework 6, due November 6th

(Hint: base your proof on the simpler version from the class notes).

  • Maximize the volume of a cylindrical can of fixed cost C cents if the cost of the top and bottom is C1 cents per square centimeter, and the cost of the side of the can is C2 cents per square centimeter.
    • Show that regardless of the values of C1 and C2, the optimal dimensions of the can will assign 1/3 of the total cost to the top and bottom and 2/3 of the total cost to the sides.
  • Solve the following classical calculus problems by means of the AMGM inequality. Find the largest circular cylinder that can be inscribed in a sphere of given radius.
  • Find the minimum over the positive quadrant of the following two functions (Hint: one will use AMGM, the other by inspection).
    • (a) minimize ~ f(x,y) = x + 2 \tfrac x y + 3 y {x^{-2}}
    • (b) minimize ~f(x,y) = x + 2 \tfrac x y + 2 {x^2} y^{-1}
  • Use the Arithmetic Geometric Mean Inequality to solve the following optimization problem over the positive octant
    • minimize x2 + y + z subject to xyz = 1
    • maximize xyz subject to 3x + 4y + 12z = 1
    • minimize x3 + y2 + z subject to xy2z3 = 39

Homework 7, due November 20th (extended to Monday)

  • Prove that convexity of the norm unit ball is equivalent to the triangle inequality for the norm.
  • Write out the unit balls for the L1 and maximum norm, and show they are dual norms
  • Show that the Lp norm is dual to the Lq norm, if 1/p + 1/q = 1.
  • Write out the octagonal norm, and it's dual, the rotated octagonal norm. (Hint: find the vectors which are the vertices, and write is as a maximum over the vertices OR just write out the planes directly. Take advantage of the symmetry).
  • Shrinkage: find the minimizer of the function

f(x) = \delta |x| + \frac 1 2 (x - u)^2 + b x (Hint: complete the square, and use shrinkage).

  • Show that the vector shrinkage problem which is to minimize

f(x) = \delta \|x\|_1 + \frac 1 2 \|x - b\|_2^2 is simply shrinkage in each component. Find the minimizer when δ = 1 / 4,b = (.1,5, − .2, − 9)

  • Let b be a random vector, with 100 components chosen uniformly from [-1,1]. What is the probability that after shrinkage with shrink factor δ = 1 / 4, a particular component is zero?
  • Generate a such a vector in Matlab (using rand) and plot it, and the result of shrinking it with factor 1/4. How many components are nonzero? (use nnz)

Homework 8, due Nov 27th

Problems from Boyd

  • 5.1
  • 5.3
  • 5.6 (Hint for part (b): use the fact that the norm of AT(ATA) − 1A is less than one. You don't need to compare, beyond remarking that one of the estimates doesn't depend on the size of the system)
  • 5.7

Also

  • Define the scaled 1-norm to be \| x \|_{(3,5)} = 3|x_1| + 5|x_2|. Draw the unit ball in the norm, and find the dual of the norm. Verify that the dual of the dual is the original norm.
  • Compute the conjugate function (see Boyd 3.3) of the following functions.
  1. f(x) = 5x2 / 2 + 7
  2. f(x) = exp(x)
  3. f(x) = − log(x),x > 0
  4. f(x) = − 3log(x / 5),x > 0 (Hint: use the transform property on page 95).
Retrieved from "http://www.divbyzero.ca/oberman/wiki/Course_Page_for_Math_309_Fall_2008"