Consider solving the following standard-form primal LP by Affine Scaling Algorithm 7A starting from solution x = 12, 3, 2, 3, 1>32.

(a) Verify that the given solution is an appropriate point at which to start Algorithm 7A.

(b) Derive the scaled standard form in terms of variables y that comes from the given starting x. Also explain why it might be more convenient to work with this form than the original standard form.

(c) Write an expression for the move direction x in x-space to be followed on the first solution update of the algorithm. You need not explicitly do projections, just denote them symbolically. For example, to show that you want to project direction d = 11, 22 on matrix A = c 3 4 5 6 7 8 d , just write x = proj c 3 4 5 6 7 8 d a 1 2 b.
Also, briefly justify the elements of this expression, that is, (i) what does it start with, (ii) how does it utilize results, and (iii) why is the final form what it is?

Transcribed Image Text:

min e s.t. 2520 X2 X3 x4 x5 4 3 2 16 0 1 0 6 1 1 2 3 12 182 b