This is more of a conceptual question. Don't expect a highly mathematical question. Nonetheless, the questions I pose here often arise in my field (not mathematics).
Usually Semidefinite Programs (SDP) arise from applying the Schur complement to the objective function or constraints. For example, a problem of interest to me is \begin{equation} \min_{\operatorname{trace}\mathbf{X}\leq1} \sum_{k=1}^K f_k(\mathbf{X}) \end{equation} where \begin{equation} f_k(\mathbf{X}) = \frac{1}{\mathbf{a}_k^\mathrm{T}\mathbf{X}\mathbf{a}_k-\frac{\left|\mathbf{a}_k^\mathrm{T}\mathbf{X}\mathbf{b}_k\right|^2}{\mathbf{b}_k^\mathrm{T}\mathbf{X}\mathbf{b}_k}}. \end{equation} By making use of the Schur complement, this problem can be transformed into the following SDP: \begin{align} \min_{\mathbf{X}}\quad& & &\sum_{k=1}^K p_k \\ & & &\begin{pmatrix} p_k & 1 \\ 1 & q_k \end{pmatrix}\geq 0 \quad k=1,\ldots,K \\ & & &\begin{pmatrix} \mathbf{a}_k^\mathrm{T}\mathbf{X}\mathbf{a}_k-q_k & \mathbf{a}_k^\mathrm{T}\mathbf{X}\mathbf{b}_k \\ \mathbf{a}_k^\mathrm{T}\mathbf{X}\mathbf{b}_k & \mathbf{b}_k^\mathrm{T}\mathbf{X}\mathbf{b}_k \end{pmatrix}\geq 0 \quad k=1,\ldots,K \\ & & &\operatorname{trace}\mathbf{X}\leq 1 \end{align} where $\geq 0$ denotes a positive semidefinite matrix. Here, I applied the relaxation $p_k\geq \frac{1}{q_k}$ to convert it to an SDP.
Questions:
- In your opinion, is the SDP formulation the only way to convexify the original problem?
- Whether or not the original problem is convex, in cases where the SDP formulation (convex by definition) and the original problem are convex. What stops us from applying the Newton method or Interior Point algorithms to the original problem which does not involve positive semidefinite constraints? Why convert it into an SDP by applying the Schur complement?
- Are SDPs objective and constraints smooth? Why solving SDPs with moderate amount of constraints so computationally intensive?
Thank you.
