6. Phase I and Phase I-II methods

Phase I : find a strictly feasible starting point.

6.1 Gig-M method

6.1.1 Case 1

Case 1 : A strictly feasible x is known, but no strictly feasible Z.

Take a large enough M , to forme an additional constraint to the primal problem (without loss of generality):

\[\begin{split}\begin{align} minimize \quad & c^{T}x \\ subject\ to \quad & F(x) \ge 0, \ Tr(F(x)) \le M. \end{align}\end{split}\]

The duality of this modified problem is :

\[\begin{split}\begin{align*} maximize\quad &-Tr(F_{0}(Z-\tau I))-M\tau \\ subject\ to \quad &Tr(F_{i}(Z-\tau I)) = c_{i}, i=1,...m, \\ & Z \ge 0, \ \tau \ge 0, \ Z^{T} = Z \in \mathbb{R}^{n\times n} \end{align*}\end{split}\]

We can easily find a strictly feasible point for this problem. By firstly found any \(U=U^{T}\) such that \(Tr(F_{i}U)=c_{i}\) (which does not require U to be positive semidefine) . Then we define \(\tau^{(0)} > - \min \{\lambda_{min}(U), 0 \}\), along with \(Z^{(0)} = U + \tau^{(0)}I\). Which will assure Z to be positive-definite. With this method we could easily get a starting point for x and Z.

The difficulty is the choice of M. We need to check if the constraint of M is activated at the solution of the modified problem. Then choose to modify M.

6.1.2 Case 2

Case 2 : A strictly feasible Z is known, but no strictly feasible x.

Adding the big-M term to the primal objective :

\[\begin{split}\begin{align} minimize \quad & c^{T}x + Mt\\ subject\ to \quad & F(x)+tI \ge 0, \ t\ge 0. \end{align}\end{split}\]

Then choose any \(x^{(0)}\), and take :

\[t^{(0)} > - \min\{\lambda_{min}(F(x^{(0)})), 0 \}\]

The dual problem of it is :

\[\begin{split}\begin{align*} maximize\quad &-Tr(F_{0}Z) \\ subject\ to \quad &Tr(F_{i}Z) = c_{i}, i=1,...m, \\ & Tr(Z) + \tau = M \\ & Z\ge 0, \ \tau \ge 0, \end{align*}\end{split}\]

Eliminate the slack variable \(\tau\) :

\[\begin{split}\begin{align*} maximize\quad &-Tr(F_{0}Z) \\ subject\ to \quad &Tr(F_{i}Z) = c_{i}, i=1,...m, \\ & Tr(Z) \le M \end{align*}\end{split}\]

Which is the modified SDP dual problem by adding an upper bound on the trace of Z.

6.1.3 Case 3

Case 3 : Neither a strictly feasible x nor a strictly feasible Z is known.

We will combine the two upper cases, to forme the modified primal problem as :

\[\begin{split}\begin{align} minimize \quad & c^{T}x + M_{1}t\\ subject\ to \quad & F(x)+tI \ge 0, \ t\ge 0,\\ & Tr(F(x)) \le M_{2} \end{align}\end{split}\]

And the dual become :

\[\begin{split}\begin{align*} maximize\quad &-Tr(F_{0}(Z-\tau I))-M_{2}\tau \\ subject\ to \quad &Tr(F_{i}(Z-\tau I)) = c_{i}, i=1,...m, \\ & Z \ge 0, \ \tau \ge 0, \\ & Tr(Z) \le M_{1}. \end{align*}\end{split}\]

6.2 Others

Other methods can start from a infeasible points and do not require big-M terms.