\[
\begin{array}{lc}
\mbox{min} & x_1^2 \\
\mbox{st} & x_1 \geq 0
\end{array}
\]
because the problem does not have s strict complementarity solution. This fact leads interior-point methods to converge slowly.
In interesting observation is that it can be formulated as the following conic quadratic optimization problem:
\[
\begin{array}{lc}
\mbox{min} & x_2 \\
\mbox{st} & x_2 \geq ||x_1|| \\
& x_1 \geq 0
\end{array}
\]
An optimal primal solution is \(x_1 = 0\) and \(x_2=0\). Observe Vanderbei study the same problem in his working paper Section 2.2) on solving SOCPs with LOQO.
If I solve the problem with MOSEK I obtain
ITE PFEAS DFEAS GFEAS PRSTATUS POBJ DOBJ MU TIME 0 1.0e+000 1.0e+000 2.0e+000 0.00e+000 1.000000000e+000 0.000000000e+000 1.0e+000 0.00 1 1.6e-001 1.6e-001 3.2e-001 1.00e+000 2.404340377e-001 0.000000000e+000 1.6e-001 0.00 2 8.2e-003 8.2e-003 1.6e-002 1.12e+000 1.181687831e-002 0.000000000e+000 8.2e-003 0.00 3 4.1e-004 4.1e-004 8.2e-004 1.01e+000 5.891864452e-004 0.000000000e+000 4.1e-004 0.00 4 2.1e-005 2.1e-005 4.1e-005 1.00e+000 2.945495827e-005 0.000000000e+000 2.1e-005 0.00 5 2.6e-010 2.6e-010 5.2e-010 1.00e+000 4.144019664e-010 0.000000000e+000 2.6e-010 0.00
As can be seen from mu column (average complementarity gap) MOSEK converges quickly. In fact there is quadratic convergence in the last iteration. Now the dual problem is
\[
\begin{array}{lc}
\mbox{max} & 0 \\
\mbox{st} & s_3 = 1 \\
& s_2 \geq ||s_1|| \\
& s_1 \geq 0
\end{array}
\]
and an optimal dual solution is \(s_1=0.0\), \(s_2=1.0\) and \(s_3=1\). In this case the dual solution is in the interior and hence the solutions are stricly complementarity. This is also indicated by the interior-point optimizer in MOSEK which also converge quickly.
An equivalent conic quadratic problem using a rotated quadratic cone can be stated as follows
\[
\begin{array}{lc}
\mbox{min} & x_2 \\
\mbox{st} & 2 x_3 x_2 \geq ||x_1||^2 \\
& x_3 =1 \\
& x_1 \geq 0
\end{array}
\]
Now solving that problem with MOSEK produces
ITE PFEAS DFEAS GFEAS PRSTATUS POBJ DOBJ MU TIME 0 1.0e+000 1.0e+000 1.7e+000 0.00e+000 7.071067812e-001 0.000000000e+000 1.0e+000 0.00 1 1.4e-001 1.4e-001 2.4e-001 6.09e-001 1.517397994e-001 -4.749764644e-002 1.4e-001 0.00 2 2.2e-002 2.2e-002 3.7e-002 1.21e+000 2.120093451e-002 -6.971441263e-003 2.2e-002 0.00 3 5.3e-003 5.3e-003 9.0e-003 1.14e+000 4.674957163e-003 -1.445168902e-003 5.3e-003 0.00 4 1.5e-003 1.5e-003 2.6e-003 1.07e+000 1.234899144e-003 -3.403939914e-004 1.5e-003 0.00 5 4.4e-004 4.4e-004 7.4e-004 1.04e+000 3.331026029e-004 -7.962820209e-005 4.4e-004 0.00 6 1.2e-004 1.2e-004 2.1e-004 1.02e+000 8.925963682e-005 -1.860468131e-005 1.2e-004 0.00 7 3.4e-005 3.4e-005 5.8e-005 1.01e+000 2.373850359e-005 -4.389268847e-006 3.4e-005 0.00 8 9.2e-006 9.2e-006 1.6e-005 1.01e+000 6.273175074e-006 -1.049389687e-006 9.2e-006 0.00 9 2.4e-006 2.4e-006 4.2e-006 1.00e+000 1.649538759e-006 -2.545236451e-007 2.4e-006 0.00 10 6.5e-007 6.5e-007 1.1e-006 1.00e+000 4.321347177e-007 -6.259486109e-008 6.5e-007 0.00 11 1.7e-007 1.7e-007 2.9e-007 1.00e+000 1.128991865e-007 -1.558439042e-008 1.7e-007 0.00 12 4.5e-008 4.5e-008 7.7e-008 1.00e+000 2.943872208e-008 -3.919657806e-009 4.5e-008 0.00 13 1.2e-008 1.2e-008 2.0e-008 1.00e+000 7.665414689e-009 -9.952574739e-010 1.2e-008 0.00
It is seen that interior-point optimizer now converge at a much slower rate and takes many more iterations. It is easy to verify that there is no strictly complementarity solution in this case.
This give rise to some comments. There might be several ways of representing a set and they not all equally effective. Secondly maybe we should think about improving the code for problems without a stricly complementarity solution as Gould et al. is suggesting.
