Homework 2
Assigned Mon Feb 1, due Fri Feb 19 (at midnight)

To submit by email: send a single pdf file to Azam Asl (aa2821@nyu.edu)
To submit by hard copy: give to Azam or me in person or leave under her door (WWH 411) (not in her mailbox)

Ground rules for homework: you can get help from any source (friends, classmates, books, the web) but you must acknowledge the source in your submission. Collaborative work by at most two students is OK if both students work together on all problems and make the statement on the submission that equal work was done by both students. Penalty for not reporting your sources : grade of zero for the homework. Penalty for late homework: 20%. Homework will not be accepted more than one week late.

I will be out of town Feb 8-12 but I will be reading email in case you have any questions. Also, you may send questions to the class mailing list, and suggestions for trouble-shooting (but not homework solutions!) may be posted there too.

  1. Ex 3.16
  2. Ex 3.36 (a) and (b)
  3. Ex 3.37
  4. If you are not familar with MATLAB start familiarizing yourself with it. There are many free tutorials on the web.
  5. Download and install CVX and, in MATLAB, run the example program on the CVX home page. Make sure you understand the purpose and syntax of the code before proceeding. Here are two more simple examples of the use of CVX: lsqsol.m and simpleLP.m
  6. Go to the Chebyshev center of a polyhedron example (see Section 4.3.1 of the text). Run this code, including the figure generation. To understand why the problem that is set up, which is an LP, solves the "Chebyshev center" problem, you need to read Section 4.3.1, particularly equations (4.30)-(4.31).
  7. Modify the code as follows:
    1. Write a MATLAB function with input arguments A and b (type "help function" at the prompt for more information), where A is a matrix with 2 rows and the same number of columns as the number of rows in the column vector b. This function should generalize the code on the web page by allowing an arbitrary number of inequalities. Note: A(:, k) is the kth column of the matrix A. Include a modified version of the plotting commands inside the function and return x_c and r as output arguments. Setting A and b appropriately, rerun the example on the web page, checking that you get the right answer, and generate one additional example with more inequalities (submit a printed copy of the function listing as well as the printed plot).
    2. What happens if you choose A and b so there is no point inside the polyhedron?
    3. Let's change the problem so that, given p defining a p-norm (see p.635-637), we want to find the largest "scaled unit ball" in the p-norm that lies inside the specified polyhedron. How do equations (4.30)-(4.31) change? Is the optimization problem still an LP? Add a third input argument, p, to your MATLAB function, and change the code appropriately, including the code that plots the largest scaled "unit ball" appropriately. Note that norm(x,p) computes the p-norm of x. Submit the function listing as well as printed plots for the following choices of p: p = 0.5, p = 1, p = 1.5 and p = ∞. (In MATLAB, inf is a valid floating point number which is, for example, equal to 1/0.) Which of these unit balls is convex? For which p are the optimization problems convex? Does CVX indeed solve the right problem for all these choices of p, and if not, what is the difficulty?
  8. Read about another example in Chapter 4 for which there is CVX code on the example page, in sufficient detail that you can explain the code to someone else. Write the name of the example on your homework submission.
Note: I do not expect you to understand how CVX is solving these problems. This is nontrivial and will be discussed, at a high level, later in the semester!