Prove that if \(a,b\geq 0\) and \(X,Y\succeq0\text{,}\) then \(aX+bY\succeq0\text{.}\)
A principal submatrix of an \(n\times n\) matrix \(A\) is obtained by taking a set \(D\subseteq \{1,\dots,n\}\) and deleting the \(i\)th row and column of \(A\) for every \(i\in D\text{.}\) Prove that if \(A\) is positive semidefinite, then every principal submatrix of \(A\) is positive semidefinite.
Show that any linear program in Standard Equality Form (as described in Section 2.2) can be expressed as a semidefinite program.
Show that a symmetric \(2\times 2\) real matrix is positive semidefinite if and only if the diagonal entries are non-negative and the determinant is non-negative. Hint: The determinant of a matrix is equal to the product of its eigenvalues.
Prove that, if \(X\) and \(Z\) are positive semidefinite matrices, then \(\langle X,Z\rangle\geq0\text{.}\)
Prove the Weak Duality Theorem for semidefinite programming (Theorem 7.1.3). You may use the result of Exercise 5 without proof.
Our goal is to show that strong duality does not hold for semidefinite programs. Consider the following optimization problem where the variables form a \(3\times 3\) matrix \(X\text{:}\)
Prove that any feasible matrix \(X\) for the above SDP satisfies \(x_{i,2}=x_{2,i}=0\) for all \(1\leq i\leq 3\) and use this to show that the value of the SDP is \(1\text{.}\) Here, and throughout all parts of this exercise, you can use Exercise 2 without proof.
Find the dual of this SDP and show that its value is \(0\text{.}\) Conclude that strong duality does not hold in general for semi-definite programs.
Show that neither the above SDP nor its dual are strictly feasible.
Prove that, for every \(\varepsilon>0\) there exists a feasible matrix \(X\) with \(x_{1,1}\leq \varepsilon\text{,}\) but that there does not exist a feasible matrix \(X\) such that \(x_{1,1}=0\) (and therefore, when we talk about finding the “minimum/maximum” of an SDP, what we are technically talking about is finding a “infimum/supremum”).
A nice feature of linear programs is that any linear program in which the objective function and all of the constraits only involve rational numbers, then the value of the LP is rational. Prove that this is not true for SDPs. That is, find a simple example of an SDP whose objective function and constraints are described in terms of integers where the value of the SDP is not rational.
Prove that every graph \(G\) satisfies \(\maxcut(G)\geq\frac{1}{2}|E(G)|\text{.}\) (This does not require semi-definite programming)
Improve the bound from the previous part of the question to \(\frac{n^2}{4\binom{n}{2}}|E(G)|\text{.}\) (This does not require semi-definite programming either).
for all \(1\leq i\leq n\text{.}\) Prove that \(A\succeq 0\text{.}\)Hint: Show \(x^TAx\geq0\) for all \(x\in\mathbb{R}^n\text{.}\) You may want to use the inequality \(2|ab|\leq a^2+b^2\) somewhere in the proof.
Prove that, for any symmetric \(n\times n\) matrix \(A\text{,}\) there exists \(t\in\mathbb{R}\) such that \(A+tI_n\) is positive semi-definite.
Let \(x\in \mathbb{R}^n\text{.}\) Prove that \(\|x\|_2\leq 1\) if and only if \(X:=\begin{bmatrix}1 \amp x^T \\ x \amp I_n\end{bmatrix}\succeq 0\text{.}\)Hint: Recall that \(X\succeq0\) if and only if \(z^TXz\geq0\) for every \(z=(z_0,\dots,z_n)\in\mathbb{R}^{n+1}\text{.}\) The inequality \(\sum_{i=1}^n|x_iz_i|\leq \left(\sum_{i=1}^nx_i^2\right)^{1/2}\left(\sum_{i=1}^nz_i^2\right)^{1/2}\) may come in handy; you can use it without proof.
Let \(c\in\mathbb{R}\text{.}\) Show that the problem of minimizing \(c^Tx\) over all \(x\) such that \(\|x\|_2\leq1\) can be written as a semi-definite program and take its dual. Is the primal strictly feasible? Is the dual strictly feasible?
