Assigned Mon Feb 1, due Fri Feb 19 (at midnight)
To submit by email: send a single pdf file to Azam Asl (firstname.lastname@example.org)
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.
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!
- Ex 3.16
- Ex 3.36 (a) and (b)
- Ex 3.37
- If you are not familar with MATLAB start familiarizing yourself with it.
There are many free tutorials on the web.
- 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
- 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 can explain the code to someone else.
Write the name of the example on your homework submission.