MATP6640/DSES6770 Linear Programming, Homework 6.
Solutions
Due: 11.59pm on Friday, April 22, 2022 on LMS.
10% penalty for each day late.
Note that ξ^{s},s ∈ 1,…,S are parameters. Assume the values of Q(,ξ^{s}),s ∈ 1,…,S, p_{s} > 0,s ∈ 1,…,S, and α > 0 are given. Also assume α < 1 and ∑ _{s=1}^{S}p_{s} = 1.
andSolution:
For each s, complementary slackness requires
We claim one optimal primal-dual solution is to take
Primal feasibility follows from the ordering assumption on Q(,ξ^{s}). 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(,ξ^{ŝ+1}) ≤ η ≤ Q(,ξ^{ŝ}).
Assume r_{b}≠0, S and X are positive definite diagonal matrices, and A is m×n with rank m. Show that Δx^{T }Δs≠0.
Solution:
Note that AΔx = -r_{b}, so Δx≠0. Also,
Let D = X^{-1}S, a diagonal matrix with every diagonal entry strictly positive. Thus, D is positive definite, so
Solution:
For the semidefinite cone and with X ∈ ℝ^{n×n}, we have
The primal and dual semidefinite programs are
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 X_{33}. For any ϵ > 0, ϵ ≤ 6, with β ≥ max{1,}, the following matrix is primal feasible with objective function value 2ϵ:
since its determinant is
for ϵ and β satisfying the stated conditions.
There is no primal feasible solution with X_{33} = 0: if X_{33} = 0 then positive semidefiniteness requires X_{13} = X_{23} = X_{31} = X_{32} = 0, which then violates A_{2} ∙ X = b_{2}. 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 S_{11} = -y_{1} and S_{22} = y_{1}, so any dual feasible solution must have y_{1} = 0. Positive semidefiniteness of S then requires S_{12} = S_{13} = S_{21} = S_{23} = S_{31} = S_{32} = 0. Since S_{13} = -y_{2}, we must also have y_{2} = 0. So the only feasible solution is y = (0,0), S = C, which is therefore optimal.
The primal and dual semidefinite programs are
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
We then get
Thus, feasibility requires X_{22} ≥ 1. The objective is to minimize X_{22}, so the unique optimal solution is
with optimal value 9.
The dual linear constraints give
The dual is strictly feasible. For example, we can take y_{1} = -1, y_{2} = 0 to give a positive definite dual slack matrix S.
We have
Nonnegativity of det(S) requires
which holds provided
We also require y_{2} ≤(9 + y_{1}) to ensure S_{22} ≥ 0. Given y_{1}, the dual objective requires maximizing y_{2}. Note that we need y_{1} ≤ 0. So we can parametrize as:
where the first inner max is achieved by y_{1} = -1 and the second by y_{1} = -9. Thus, the optimal dual solution is y = (-1,2) with value 9. The corresponding optimal dual slack matrix is
It can be seen that X^{*} and S^{*} are simultaneously diagonalizable.
Solution:
Solution:
Solution:
The primal linear constraints can be written
The (implied) trace constraint is written
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
for some vector ∈ ℝ^{m}. We are given that the dual problem is feasible, so let (ŷ,Ŝ) be a feasible dual solution satisfying
Consider the choice of
The corresponding dual slack matrix is
which is positive definite for any α > 0. Hence the dual feasible region is unbounded and strictly dual feasible solutions exist.
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 |