MATP6640/ISYE6770 Linear and Conic Optimization, Homework 1.

Solutions

Due: 11.59pm on Friday, January 21, 2022 on LMS.
10% penalty for each day late.

1. Let a,b L, where L is an affine space in n. Let La := {x n : x = x - a for some x L}. Define Lb similarly. Let x be a point in La. Show that x is also in Lb. How are La and Lb related?

Solution: Assume x La. It follows that

since x, a, and b are all in L and so x - a + b L since it is an affine combination of points in L.

It follows similarly that if x Lb then x La. Thus La = Lb.

2. Let Q be a convex polyhedron in n and let F be a nonempty face of Q. Let x be a point on the face F. Show that x is an extreme point of Q if and only if it is an extreme point of F.

Solution: We prove both directions by contradiction.

• Assume x F is not an extreme point of F, show it is not an extreme point of Q:

By assumption, there exist points y,z F, yz, and scalar λ with 0 < λ < 1 satisfying x = λy+(1-λ)z. Since F Q, we see immediately that x is not an extreme point of Q.

• Assume x F is not an extreme point of Q, show it is not an extreme point of F:

Since F is a face of Q, there exists a vector a n and a scalar α such that (i) F = Q H with H = {x n : aT x = α} and (ii) aT x α for all x Q. By assumption, there exist points y,z Q, yz, and scalar λ with 0 < λ < 1 satisfying x = λy + (1 - λ)z. Now, aT x = α, aT y α, aT z α. If aT y > α or aT z > α then aT x = λaT y + (1 - λ)aT z > α, a contradiction. Thus, we must have aT y = aT z = α, so y,z F, so x is not an extreme point of F.

3. Consider the optimization problem
 (1)

where x,w n, b m, and all other vectors and matrices are dimensioned appropriately. Note that the components of x are not restricted in sign.

1. Assume all entries in d and H are nonnegative. Show that (1) can be formulated as an equivalent linear program, in the sense that the LP and (1) have the same optimal value if they are feasible, and each is infeasible if the other is infeasible.
2. Provide a counterexample with n = 1 where your LP and (1) are not equivalent when H contains negative entries.

Solution:

1. LP formulations can be constructed in (at least) two ways: either split x into positive and negative components, or set wi to be at least as large as both xi and -xi. Both formulations relax the constraint |xi| = wi to |xi|≤ wi.
1. Split x into positive and negative components: We introduce nonnegative variables xi+ and xi- for each i, replace the absolute value of x by x+ + x-, and then construct the LP
 (2)

If (x,w) is feasible in (1) then we can construct a feasible solution to (2) with the same value by setting:

for i = 1,,n. Hence (2) is feasible if (1) is feasible, with optimal value that is at least as good. This observation does not exploit the sign of H or d.

If (x+,x-) is feasible in (2) then we can construct a feasible solution to (1) with the same or better value by setting

The feasibility of this solution in (1) follows from the nonnegativity of the entries in H. Similarly, dT w dT (x+ + x-) because of the nonnegativity of d.

2. Impose two linear constraints on w:
 (3)

If (x,w) is feasible in (1) then it is feasible in (3), with the same value.

If (x,w) is feasible in (3) then we can construct a feasible solution in (1) by decreasing each component of w to |xi| (if necessary). Feasibility of this modified solution follows from the nonnegativity of H, and the objective value is no worse because of the nonnegativity of d.

2. We use the same example in both formulations, with m = 1:

The constraints imply x 0, so the optimal value is 0, achieved by x = w = 0.

1. The corresponding version of (2) is

For any t 0, we can set x+ = 3t, and x- = t, which has value -2t. Thus, this LP has unbounded optimal value.

2. The corresponding version of (3) is

For any t 0, we can set x = t and then any w 2t is feasible, with value -t. Thus, the LP has unbounded optimal value.

4. What is the dual of the following linear programming problem?

Use complementary slackness to show that x = (6,0,0) is optimal for this problem. Find two different dual optimal solutions.

Solution: The dual is

The slack in the second primal constraint is positive at the given solution, so by complementary slackness we need y2 = 0. Two dual feasible solutions that satisfy complementary slackness are y = (3,0,0) and y = (8,0,-5) (and any convex combination of them). Since primal and dual feasibility and complementary slackness are satisfied, the given solutions are optimal, with optimal value 18.

5. Let A be a p × n matrix and B be a q × n matrix. Show that exactly one of the following systems has a solution:

System 1: Ax < 0, Bx = 0 for some x n.
System 2: AT u + BT v = 0 for some u p, v q, with u 0 and u0.

Solution:

Consider the primal-dual pair of LPs:

where e is the vector of ones.

If (P) is feasible then System (I) is consistent, and vice versa (rescaling x if necessary).

Note that (D) is always feasible: take u = 0 and v = 0. So either (D) has optimal value 0 or it is unbounded, since any solution with nonzero objective function value can be rescaled.

If System (1) is consistent then (P) is feasible with optimal value 0. So (D) has optimal value 0 by strong duality. Thus, System (2) is inconsistent.

If System (1) is inconsistent then (P) is infeasible. So (D) must be unbounded by strong duality. Thus, System (2) is consistent.

 John Mitchell Amos Eaton 325 x6915. mitchj at rpi dot edu Office hours: Tuesday, Friday 12noon-2pm on webex https://rensselaer.webex.com/meet/mitchj