MATP6640/ISYE6770 Linear and Conic Optimization, Homework 1.

Due: 11.59pm on Friday, January 21, 2022 on LMS.

10% penalty for each day late.

- Let a,b ∈ L, where L is an affine space in ℝ
^{n}. Let L^{a}:= {x ∈ ℝ^{n}: x = - a for some ∈ L}. Define L^{b}similarly. Let x be a point in L^{a}. Show that x is also in L^{b}. How are L^{a}and L^{b}related? - 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. - 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.- 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.
- Provide a counterexample with n = 1 where your LP and (1) are not equivalent when H contains negative entries.

- 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.

- 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: A^{T }u + B^{T }v = 0 for some u ∈ ℝ^{p}, v ∈ ℝ^{q}, with u ≥ 0 and u≠0.

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 |