DOC PREVIEW
MIT 6 079 - Homework 10

This preview shows page 1 out of 4 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 4 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 4 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

6.079/6.975, Fall 2009-10 S. Boyd & P. Parrilo (Part of) Homework 10: Standard form LP barrier method In the following three exercises, you will implement a barrier method for solving the standard form LP minimize cT x subject to Ax = b, x � 0, with variable x ∈ Rn, where A ∈ Rm×n, with m < n. Throughout this exercise we will assume that A is full rank, and the sublevel sets {x | Ax = b, x � 0, cT x ≤ γ} are all bounded. (If this is not the case, the centering problem is unbounded below.) 1. Centering step. Implement Newton’s method for solving the centering problem minimize cT x −�in =1 log xi subject to Ax = b, with varia ble x, given a strictly feasible starting point x0. Your code should accept A, b, c, and x0, and return x ⋆, the primal optimal point, ν⋆ , a dual optimal point, and the number o f Newton steps executed. Use t he block elimination method to compute the Newton step. (You can also compute the Newton step via the KKT system, and compare the result to the Newton step computed via block elimination. The two steps should be close, but if any xi is very small, you might get a warning a bout the condition number of the KKT matrix.) Plot λ2/2 versus iteration k, f or various problem data and initial points, to verify that your implementa t io n gives asymptotic quadratic convergence. As stopping criterion, you can use λ2/2 ≤ 10−6 . Experiment with varying the algorithm parameters α and β, observing the effect on the total number of Newton steps required, for a fixed problem instance. Check that your computed x ⋆ and ν⋆ (nearly) satisfy the KKT conditions. To generate some random problem data (i.e., A, b, c, x0), we recommend the f ollowing approach. First, generate A randomly. (You might want to check that it has full rank.) Then generate a random po sitive vector x0, and t ake b = Ax0. (This ensures that x0 is strictly feasible.) The parameter c can be chosen randomly. To be sure the sublevel sets are bounded, you can add a r ow t o A with all positive elements. If you want to be able to repeat a run with the same pro blem data, be sure to set the state for the uniform and normal r andom number generators. Here are some hints that may be useful. • We recommend computing λ2 using the f ormula λ2 = −ΔxntT ∇f(x). You don’t really need λ for anything; you can work with λ2 instead. (This is impor tant for reasons described below.) 1• There can be small numerical errors in the Newton step Δxnt that you compute. When x is nearly optimal, the computed value of λ2 , i.e., λ2 = −ΔxntT ∇f(x), can actually be (slightly) negative. If you take the squareroot to get λ, you’ll get a complex number, and you’ll never recover. Moreover, your line search will never exit. However, this only happens when x is nearly optimal. So if you exit on the condition λ2/2 ≤ 10−6, everything will be fine, even when the computed value of λ2 is negative. • For the line search, you must first multiply the step size t by β until x + tΔxnt is feasible (i.e., strictly positive). If you don’t, when you evaluate f you’ll be taking the logarithm of negative numbers, and you’ll never recover. 2. LP solver with strictly feasible starting point. Using the centering code from part (1), implement a barrier method to solve the standard form LP minimize cT x subject to Ax = b, x � 0 , with variable x ∈ Rn, given a strictly f easible starting point x0. Your LP solver should take as argument A, b, c, and x0, and return x ⋆ . You can terminate your barrier method when the duality g ap, as measured by n/t, is smaller than 10−3 . (If you make the tolerance much smaller, you might run into some numerical trouble.) Check your LP solver against the solution found by cvx, for several problem instances. The comments in part (1) on how to generate random data hold here too. Experiment with the parameter µ to see the effect on the number of Newton steps p er centering step, and the total number of Newton steps required to solve the problem. Plot the progress of the algorithm, for a problem instance with n = 500 and m = 100, showing duality gap (on a log scale) on the vertical axis, versus the cumulative total number of Newton steps (on a linear scale) on the horizontal axis. Your algor ithm should return a 2 × k matrix history, (where k is the total number of centering steps), whose first row contains the number of Newton steps required for each centering step, and whose second row shows the duality gap at the end of each centering step. In order to get a plot that looks like the ones in the book (e.g., figure 11.4, page 572 ) , you should use the following code: [xx, yy] = stairs(cumsum(history(1,:)),history(2,:)); semilogy(xx,yy); 3. LP solver. Using the code from part (2), implement a general standard form LP solver, that takes arguments A, b, c, determines (strict) feasibility, and returns an optimal point if the problem is (strictly) feasible. 2You will need to implement a phase I method, that determines whether the problem is strictly feasible, and if so, finds a strictly feasible point, which can then be fed to the code from part (2). In fact, you can use the code from part (2) to implement the phase I method. To find a strictly feasible initial point x0, we solve the phase I problem minimize t subject to Ax = b x � (1 − t)1, t ≥ 0, with variables x and t. If we can find a feasible (x, t), with t < 1, then x is strictly feasible for the original problem. The converse is also true, so the original LP is strictly feasible if and only if t ⋆ < 1, where t ⋆ is the optimal value of the phase I problem. We can initialize x and t for the phase I problem with any x0 satisfying Ax0 = b, and t0 = 2−mini xi 0 .


View Full Document

MIT 6 079 - Homework 10

Download Homework 10
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Homework 10 and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Homework 10 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?