1
$\begingroup$

I am interested in bounding the computational complexity of the interior points method for solving a generic conic problem of the form \begin{equation} \min_x \left\{ c^T x : \mathcal{A}x-B\in\mathbf{K} \right\}, \end{equation} associated to cone \begin{equation} \mathbf{K} = \mathbf{S}_+^{k_1} \times \ldots \times \mathbf{S}_+^{k_p} \times \mathbf{L}_+^{k_{p+1}} \times \ldots \times \mathbf{L}_+^{k_{p+m}}. \end{equation} This exact formulation appears in this book, $\mathbf{S}_+^{k}$ is the cone of $k\times k$ symmetric positive-semidefinite matrices, and $\mathbf{L}_+^{k}$ is the Lorentz or second order cone with $k$ variables.

This book in fact provides insights on how many steps are required by this kind of problem in page 278 as it states,

The canonical barrier K for the cone K given by (Cone), by definition, is the direct sum of the canonical barriers of the factors.

However, the analysis on the computational complexity for computing each step is only given for particular instances: linear programs (LP), second-order cone programs (SOCP) and semidefinite programs (SDP).

Is the computational complexity of a conic problem including linear constraints, second-order cones and semidefinite cones, known?

$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.