I am working on developing my own solver(for implementation on hardware), based on IPM for following problem: \begin{equation} \begin{split} \min_{X} \; \frac{1}{2}&\|X\|_F^2 + trace(CX)\\ \text{s.t. } & trace(AX)\leq b\\ & X\succeq 0\\ \end{split} \end{equation} As a reference I already know how to obtain KKT equations for \begin{equation} \begin{split} \min_{X} \; \frac{1}{2}&\|X\|_F^2 + trace(CX)\\ \text{s.t. } & trace(AX) = b\\ & X\succeq 0\\ \end{split} \end{equation} Dual of this problem will be \begin{equation} \begin{split} \max_{X,y,S}\;& -\frac{1}{2}\|X\|_F^2+by+\beta\log\det(S)\\ \text{s.t. }\;& A^Ty-X+S=C,\; S\succeq 0 \end{split} \end{equation} KKT system will be \begin{equation} \begin{array}{ccccccc} -X & + & A^Ty & + & S & = C, & S\succeq 0\\ trace(AX) & & & & & = b, & X\succeq 0\\ & & XS & & & = 0, &\\ \end{array} \end{equation} Later I sove it with Newton-Rhapson method, have no problems there. My question, therefore, be, how to obtain KKT system, when $trace(AX) \leq b$?

All responses or references are appreciated.

  • $\begingroup$ That's a set of linear inequality constraints that you can either solve using an interior penalty method, or an active set method. Have you looked into one of these? $\endgroup$ Jan 16, 2018 at 2:57
  • $\begingroup$ Yes I did. Commercial solvers like cvxopt, sdpt3 that have developed efficient conic solvers introduce additional nonnegative slack variable and solve it as combination of two cones(sdp and nonnegative orphant). Hence, my question also can be rephrased as how to put combination of two cones in one set of KKT equations. I also agree that active set is an option, but I want to develop something more practical(as when number of constraints grows, active set method becomes less efficient). $\endgroup$ Jan 17, 2018 at 7:43


Your Answer

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