Homework 2
Assigned Wed Feb 11, due Thu Feb 26 (any time)

Please do not submit homework by email. Submit a hard copy to me in person or leave it under my office door later, but not in my mailbox.

Ground rules for homework: you can get help from any source (friends, relatives, books, the web) but you must acknowledge the source in your submission.

Generally, homework will not be accepted late unless there is a good reason!

I will be out of town Feb 12-22 but I will be reading email if 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. MATLAB should be available on any CIMS-supported workstation, and can be purchased from The Mathworks for your own computer at a special student price (up until recently this has been $99). There are many MATLAB tutorials available on the web. There are also free clones, such as Octave, on the web.
  5. Download and install CVX and, in MATLAB (or a clone if you can get it work), run the example program at the top of the web page. Make sure you understand the purpose and syntax of the code before proceeding.
  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 understand how it works. 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 later in the semester!