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

    x  =  x- a   for some x∈ L

   =  x- a + b- b
   =  (x - a+  b) - b
        b
   ∈  L
    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.

  3. Consider the optimization problem
                T        T
minx,w     c x  +   d w
subject to  Ax  +   Hw    ≤  b
            |xi| =     wi     ∀i
    (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
        minx+,x-   cTx+  -   cTx-  +   dTx+   +  dT x-
subject to  Ax+   -   Ax -  +   Hx+    +   Hx -  ≤   b
            x+,        x-                       ≥   0
        (2)

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

             {                            {
 +      xi if xi ≥ 0          -       0   if xi ≥ 0
xi =    0  otherwise    and  xi =    - xi otherwise

        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

        x = x+ - x- ,  w = |x|.

        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:
        minx,w     cTx  +   dTw
subject to  Ax  +   Hw    ≤  b

             xi -     wi  ≤  0  ∀i
           - xi -     wi  ≤  0  ∀i
        (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:
      minx,w ∈ℝ   - x
subject to  2x  -   w  ≤   0
           |x| =   w

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

      1. The corresponding version of (2) is
        min        - x+  +   x -
subject to 2x+   -  2x -  -  x+   -  x -  ≤  0
             +         -
            x ,      x                    ≥  0

        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
        min        - x
   x,w
subject to  2x  -   w  ≤   0
            x  -   w  ≤   0
           - x -   w  ≤   0

        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?
    min  3x1  -   5x2   +   8x3
s.t.   x1            -    x3  =     6
              2x2   -    x3  ≥   - 5
      x1  +    x2            ≤     6
               x   ≤ 0,  x   ≥    0.
                2          3

    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

    maxy ∈ℝ3   6y1  -   5y2   +   6y3
subject to  y1            +    y3  =    3
                    2y2   +    y3  ≥   - 5
           - y  -    y             ≤    8
             1        2
                     y2  ≥ 0,  y3  ≤    0

    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:

                T                                    T
maxx       0 x                      min        - eT u   T
subject to  Ax  ≤   - e    (P )      subject to A  u+ B  v  =   0    (D )
            Bx  =   0                          u ≥ 0,  v free

    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