MATP6640/ISYE6770 Linear and Conic Optimization, Homework 1.

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?
  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.
  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.
  4. What is the dual of the following linear programming problem?
    min  3x1  -   5x2   +   8x3
s.t.   x             -    x   =     6
       1                   3
              2x2   -    x3  ≥   - 5
      x1  +    x2            ≤     6
               x2  ≤ 0,  x3  ≥    0.

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

  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.

    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