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.
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!
- Ex 3.16
- Ex 3.36 (a) and (b)
- Ex 3.37
- 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.
- 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.
- 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).
- Modify the code as follows:
- 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).
- What happens if you choose A and b so there is no point inside
- 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?
- 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.