# Semidefinite program Generalized inequalities can be defined based on propoer cones. Till now we have seen inequalities for real numbers and elementwise inequalities real vectors. The former type of inequality is defined by the propoer cone of nonnegative real numbers. The later type is defined by the proper cone of the nonnegative orthant ($\mathbb{R}^n_+$) in $\mathbb{R}^n$. One natural extension of the optimization problems we have seen so far is to define the inequalities by the proper cone of positive semidefinite matrices. For example, consider the following linear optimization problem: $$\begin{align} \text{minimize} & c^\text{T}x\nonumber\\ \text{subject to}& Fx+g\preccurlyeq_{\mathcal{S}^n_+} 0\nonumber\\ & Ax=b \end{align}$$ where $\mathcal{S}^n_+$ is the cone of positive semidefinite matrices in $\mathcal{R}^{n\times n}$. In other words, the first constraint of the above optimization problem says that $Fx+g$ is positive semidefinite. This is an extension of linear programming. A semidefinite program (SDP) is defined as: $$\begin{align} \text{minimize} & c^\text{T}x\nonumber\\ \text{subject to}& x_1F_1+x_2F_2+\cdots+x_nF_n+G \leq 0\nonumber\\ & Ax=b \end{align}$$ where $x =\left[\begin{matrix}x_1&x_2&\cdots&x_n\end{matrix}\right]^\text{T}$ is a vector in $\mathbb{R}^n$ and $F_i, i=1,\ldots,m$ and $G$ are symetric matrices in $\mathcal{R}^{m\times m}$. Note that the standard LP problem: $$\begin{align} \text{minimize}&c^\text{T}x\nonumber\\ &Ax\preccurlyeq b \end{align}$$ can be written as the following SDP problem: $$\begin{align} \text{minimize}&c^\text{T}x\nonumber\\ &\text{diag}(Ax) \leq b \end{align}$$ where $\text{diag}(v)$ for $v\in\mathbb{R}^n$ is a diagonal matrix in $\mathbb{R}^{n\times n}$ with $v$ as the main diagonal. Also the standard SOCP problem: $$\begin{align} \text{minimize}&c^\text{T}x\nonumber\\ &\|A_ix+b_i\|_2 \leq c_i^\text{T}x+d_i,\ i=1,\ldots,m \end{align}$$ can be written as the following SDP problem: $$\begin{align} \text{minimize}&c^\text{T}x\nonumber\\ & \left[\begin{matrix} (c_i^\text{T}x+d_i)I & A_ix+b_i\\ A_ix+b_i & c_i^\text{T}x+d_i\end{matrix}\right] \geq 0,\ i=1,\ldots,m \end{align}$$ *Example (eigenvalue minimization):* Consider minimizing the maximum eigenvalue of matrix $A(x)$: $$\begin{align} \text{minimize}& \lambda_\max(A(x)) \end{align}$$ where $A(x)=A_0+x_1A_1+\cdots+x_nA_n$ where $A_i$'s are symmetric matrices. This problem can be written as the following SDP problem: $$\begin{align} \text{minimize}&t\nonumber\\ & A(x)\leq tI \end{align}$$ As a numerical example, consider: $$\begin{equation} A(x) = \left[\begin{matrix} x_3 & 0 & 0 & x_1+x_2-2\\ 0 & x_3 & 0 & 2x_1+x_2-3\\0 & 0 & x_3 & 3x_1+2x_2-4\\ x_1+x_2-2 & 2x_1+x_2-3 & 3x_1+2x_2-4 & x_3 \end{matrix}\right] \end{equation}$$ We would like to minimize the largest eigenvalue of $A$ subject to $A$ being a positive semidefinite matrix. The following code solves this problem: x1 = cp.Variable() x2 = cp.Variable() x3 = cp.Variable() t = cp.Variable() X = cp.SDPVar(4) Y = cp.SDPVar(4) A0 = co.matrix([[0,0,0,-2],[0,0,0,-3],[0,0,0,-4],[-2,-3,-4,0]]) A1 = co.matrix([[0,0,0,1],[0,0,0,2],[0,0,0,3],[1,2,3,0]]) A2 = co.matrix([[0,0,0,1],[0,0,0,1],[0,0,0,2],[1,1,2,0]]) A3 = co.matrix([[1,0,0,0],[0,1,0,0],[0,0,1,0],[0,0,0,1]]) I = co.matrix(np.identity(4)) objective = cp.Minimize(t) Ax = A0+A1*x1+A2*x2+A3*x3 constraints = [ Ax == X, t*I-Ax == Y ] p = cp.Problem(objective, constraints) The optimal largest eigenvalue of $A(x)$ is equal to: result=p.solve() print(result) 1.15470050608 The optimal solution for $x$ is: print([x1.value,x2.value,x3.value]) [1.0000000000000004, 0.6666666666666659, 0.5773502530380881] The value of $A(x)$ for the optimal solution is equal to: print(Ax.value) [ 5.77e-01 0.00e+00 0.00e+00 -3.33e-01] [ 0.00e+00 5.77e-01 0.00e+00 -3.33e-01] [ 0.00e+00 0.00e+00 5.77e-01 3.33e-01] [-3.33e-01 -3.33e-01 3.33e-01 5.77e-01] In this case, eigenvalues of $A(x)$ are equal to: EigenValues = np.linalg.eig(Ax.value)[0] print(EigenValues) [ -1.61515377e-08 5.77350253e-01 1.15470052e+00 5.77350253e-01]