MATP6640/DSES6770 Linear Programming, Homework 6.
Solutions

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

  1. Consider the following linear program with variables η and vs,s 1,,S:
                     ∑
minv,η      η + α1 spsvs
subject to  η   +   vs  ≥   Q(x,ξs)  ∀s
            η  free, vs  ≥   0  ∀s

    Note that x and ξs,s 1,,S are parameters. Assume the values of Q(xs),s 1,,S, ps > 0,s 1,,S, and α > 0 are given. Also assume α < 1 and s=1Sps = 1.

    1. What is the dual linear program?
    2. Assume Q(x1) Q(x2) Q(xS). Use complementary slackness to solve the primal and dual problems.

    Solution:

    1. Dual problem is
                 ∑
max π        sQ (x,∑ξs)πs
subject to           sπs  =   1
                     πs  ≤   pαs  ∀s
                     πs  ≥   0  ∀s

    2. From the assumptions on α and ps, there must exist an index ŝ such that:
      ˆs- 1                   ˆs
∑  p <  α    and     ∑  p  ≥ α,    with     1 ≤ ˆs ≤ S.
s=1  s                s=1 s

      For each s, complementary slackness requires

                                           (       )
πs(η + vs - Q(x,ξs)) = 0   and     vs ps - πs  =  0.
                                       α

      We claim one optimal primal-dual solution is to take

      1. dual solution for s = 1,,S:
              (
      ||{       pαs       for s = 1,...,ˆs- 1
            1-∑ ˆs-1
πs =  || 1 - α   s=1ps  for s = ˆs
      (       0        for s = ˆs+ 1,...,S

      2. primal solution:
         η  =   Q(x,ξˆs)
        {       s         ˆs
v   =     Q (x,ξ )- Q (x,ξ ) for s = 1,...,ˆs- 1
 s                0          for s = ˆs,...,S

      Primal feasibility follows from the ordering assumption on Q(xs). It is straightforward to check that the given solution satisfies dual feasibility and complementary slackness. Hence it is optimal.

      If πŝ = pŝ∕α then alternative primal optimal solutions exist for any η with Q(xŝ+1) η Q(xŝ).

  2. Let (Δx,Δy,Δs) solve
    ⌊      T     ⌋ ⌊     ⌋   ⌊      ⌋
  0  A    I      Δx          0
⌈ A  0    0  ⌉ ⌈ Δy  ⌉ = ⌈ - rb ⌉.
  S  0    X      Δs          0

    Assume rb0, S and X are positive definite diagonal matrices, and A is m×n with rank m. Show that ΔxT Δs0.

    Solution:

    Note that AΔx = -rb, so Δx0. Also,

              -1
Δs  = - X   S Δx.

    Let D = X-1S, a diagonal matrix with every diagonal entry strictly positive. Thus, D is positive definite, so

    ΔxT Δs  = - ΔxT X - 1SΔx =  - ΔxT D Δx  < 0.

  3. Let K be a cone. A function f : int(K) is logarithmically homogeneous if there exists a constant Θ such that f(tx) = f(x) - Θln(t) for all x int(K) and t > 0. (Here, int(K) denotes the interior of K.) Show the barrier function for the semidefinite cone, namely f(X) = -lndet(X), is logarithmically homogeneous. What is the value of Θ?

    Solution:

    For the semidefinite cone and with X n×n, we have

    f(tX ) =   - ln det(tX )
                 n
       =   - ln (t det(X ))   from  properties of det
       =   - ln det(X )- n ln(t)
    so the barrier function is logarithmically homogeneous, with barrier parameter n.
  4. Let
         ⌊          ⌋         ⌊           ⌋          ⌊         ⌋
        0  0  0             1    0  0              0  0  1          [   ]
C  := ⌈  0  0  0 ⌉,  A1 := ⌈ 0  - 1  0 ⌉ ,  A2 :=  ⌈ 0  0  1 ⌉ ,  b :=  1
        0  0  2             0    0  0              1  1  1            3

    The primal and dual semidefinite programs are

                                                          T
min  trace(CX )                           max   ∑2   b  y
s.t.  trace(AiX )  =   bi  i = 1,2    (P )    s.t.     i=1 Aiyi  +  S  =   C     (D )
             X   ≽   0                                        S  ≽   0

    Show that both (P) and (D) are feasible, but that the optimal value of (P) is not achieved.

    Solution:

    One strictly feasible primal solution is X = 3I. The primal objective requires minimizing X33. For any ϵ > 0, ϵ 6, with β max{1,9-
4ϵ}, the following matrix is primal feasible with objective function value 2ϵ:

           ⌊                          ⌋
             β       0    12(3- ϵ)
       |                          |
X (ϵ) := ⌈     0     β - 1     0    ⌉
          12(3- ϵ)    0       ϵ

    since its determinant is

                (     1       )           (     9   ϵ       )
Δ  = (β - 1) βϵ - -(3 - ϵ)2   = (β - 1) β ϵ- --+ --(6 - ϵ)  ≥ 0
                  4                         4   4

    for ϵ and β satisfying the stated conditions.

    There is no primal feasible solution with X33 = 0: if X33 = 0 then positive semidefiniteness requires X13 = X23 = X31 = X32 = 0, which then violates A2 X = b2. Thus, the optimal value of (P) is zero, but this value is not attained.

    One dual feasible solution is y = (0,0), S = C. Note that S11 = -y1 and S22 = y1, so any dual feasible solution must have y1 = 0. Positive semidefiniteness of S then requires S12 = S13 = S21 = S23 = S31 = S32 = 0. Since S13 = -y2, we must also have y2 = 0. So the only feasible solution is y = (0,0), S = C, which is therefore optimal.

  5. Let
         [      ]         [       ]          [      ]       [    ]
C :=    0  0  ,  A1 :=   1   0   ,  A2 :=   0  1  ,  b :=    3
       0  9             0  - 1             1  2            6

    The primal and dual semidefinite programs are

    min   trace(CX  )                              max  ∑     bTy
s.t.  trace(AiX  ) =   bi i = 1,...,2    (P )    s.t.     2i=1 Aiyi +   S  =   C    (D )
             X   ≽   0                                            S  ≽   0

    Show that (P) has an optimal value of 9. Is (D) strictly feasible? Show that y = (-1,2) is optimal for (D). Show that the optimal X and S matrices are simultaneously diagonalizable.

    Solution: The primal linear constraints imply

    X11 = X22 + 3,  X12 = X21 = 3 - X22.

    We then get

    det(X ) = (X22 + 3)X22 - (3 - X22)2 = 9X22 - 9.

    Thus, feasibility requires X22 1. The objective is to minimize X22, so the unique optimal solution is

         [      ]   [ -2-  -1-] [      ][  2-- -1-]
X* =   4  2   =   √ 5  √5     5  0     √5  √ 5
       2  1       √15-  √25-    0  0     -√15- √25-

    with optimal value 9.

    The dual linear constraints give

        [                   ]
S =   - y1      - y2
      - y2  9+ y1 - 2y2

    The dual is strictly feasible. For example, we can take y1 = -1, y2 = 0 to give a positive definite dual slack matrix S.

    We have

    det(S) = (- y1)(9+ y1 - 2y2)- y22 = - y22 + 2y1y2 - y1(9 + y1).

    Nonnegativity of det(S) requires

    y2- 2y y  + y (9+ y ) ≤ 0,
 2    1 2    1     1

    which holds provided

    y  - 3√--y- ≤ y ≤  y + 3√ - y-
 1        1    2    1       1

    We also require y2 12(9 + y1) to ensure S22 0. Given y1, the dual objective requires maximizing y2. Note that we need y1 0. So we can parametrize as:

               {                     }
y2  =  min  y1 + 3√ - y1, 1-(9 + y1)
                        2
       {  y1 + 3√ - y1 if - 9 ≤ y1 ≤ 0
    =       1(9 + y ) if y ≤ - 9
            2      1     1
    The dual objective function then requires max{3y1 + 6y2}, which can then be stated as
                      √----
max {max {9y1 + 18 - y1 : - 9 ≤ y1 ≤ 0}, max {27 + 6y1 : y1 ≤ - 9}}
    = max {9, - 27} = 9

    where the first inner max is achieved by y1 = -1 and the second by y1 = -9. Thus, the optimal dual solution is y = (-1,2) with value 9. The corresponding optimal dual slack matrix is

         [         ]   [  2√-- -√-1 ][      ] [ √2-  1√--]
S * =    1  - 2  =    15- -25    0  0     -51-  25-
       - 2   4        √5  √5-    0  5     √5   √5

    It can be seen that X* and S* are simultaneously diagonalizable.

    1. Formulate the primal problem in Question 5 as an equivalent second order cone program, and solve it using CPLEX. Hint: in AMPL, you should be able to enter a constraint of the following form when x, y, z are variables, with y,z 0:
      subject to soc: x**2 <= y*z ;

    2. Formulate the dual problem in Question 5 as an equivalent second order cone program, and solve it using CPLEX.

    Solution:

    1. Here are the primal model, data, and output, files.
    2. Here are the dual model, data, and output, files.
    1. Construct and solve a second order cone relaxation of the primal SDP in Question 4, by requiring all the principal 1 × 1 and 2 × 2 subdeterminants of X be nonnegative.
    2. Construct and solve a second order cone relaxation of the dual SDP in Question 4, by requiring all the principal 1 × 1 and 2 × 2 subdeterminants of S be nonnegative.

    Solution:

    1. Here are the primal model, data, and output, files. As can be seen, the SOCP formulation also doesn’t achieve an optimal solution.
    2. Here are the dual model, data, and output, files.
  6. Most semidefinite relaxations of combinatorial optimization problems result in a linear constraint on the trace of the primal matrix X. For example, in the relaxation of MaxCut, the diagonal entries are all required to equal one, so the trace must equal the number of nodes. The relaxation of the combinatorial optimization problem gives a primal SDP; assume this primal SDP and its dual are feasible. Show that if the linear constraints of the primal problem imply that any feasible solution must satisfy trace(X) = a for some positive constant a then the feasible region for the dual is unbounded, and strictly feasible dual solutions exist.

    Solution:

    The primal linear constraints can be written

    Ai ∙X  = bi,  i = 1,...,m.

    The (implied) trace constraint is written

    I ∙X  = a.

    For the trace constraint to be implied by the other constraints, it must be a linear combination of the other constraints, so we must have

     m
∑   yA  = I
     i i
i=1

    for some vector y m. We are given that the dual problem is feasible, so let (ŷ,Ŝ) be a feasible dual solution satisfying

    m
∑  ˆy A + Sˆ=  C,  ˆS ≽ 0.
    i i
i=1

    Consider the choice of

    y(α) = ˆy - α y, α ≥ 0.

    The corresponding dual slack matrix is

                m                m                   m          m
           ∑                ∑                   ∑          ∑         ˆ
S(α) = C -    yi(α)Ai = C -    (ˆy - αy)Ai = C -     ˆyAi + α   yAi =  S + αI,
           i=1              i=1                 i=1        i=1

    which is positive definite for any α > 0. Hence the dual feasible region is unbounded and strictly dual feasible solutions exist.

  7. The project: Project presentations will be on Wednesday, May 4, from 3-6pm in Low 3039. Your presentation should be no more than 15 minutes long. Please bring your presentation on a memory stick, or something with a usb port. In order to encourage questions, your grade will not be lowered if you are unable to answer questions from other students, but it may be raised. Moreover, I may give some bonus points for asking a particularly good question.

    Handouts: Please prepare 10 copies of your slides, to be handed out before your talk.

    Reports: Your writeup is due by Tuesday May 3, on LMS. It can go to the same place as this homework. It should describe the problem you worked on, what you did to solve the problem, and the significance of what you did. You should also cite relevant references and state what was novel about your approach. In addition, upload a copy of your slides.

    For group projects, each group member should upload a description of his or her individual contribution. (Plain text or pdf is fine.)

    John Mitchell
    Amos Eaton 325
    x6915.
    mitchj at rpi dot edu
    Office hours: Thursday 11am–1pm., on webex https://rensselaer.webex.com/meet/mitchj