Verified SemiDefinite-quadratic-linear Programming

The functions `vsdplow`

and `vsdpup`

prove strict feasibility and compute
rigorous error bounds. For the verification of infeasibility the function
`vsdpinfeas`

can be applied. In this section we show how to use this
function.

We consider a slightly modified second order cone problem ([BenTal2001], Example 2.4.2)

with its dual problem

Both, the primal and the dual problem, are infeasible. We can easily prove this fact by assuming that there exists a primal feasible point $x$. This point has to satisfy $x_{3} = -2x_{1}$, and therefore $x_{1} \geq \sqrt{x_{2}^{2} + (-2x_{1})^{2}}$. From the second equality constraint we get $x_{2} = 1$ yielding the contradiction $x_{1} \geq \sqrt{1 + 4x_{1}^{2}}$. Thus, the primal problem has no feasible solution. A certificateof infeasibility of the primal problem is given by the dual unbounded ray $y = \alpha (-2,1)^{T}$.

The input data are

Using the approximate solver SDPT3 we obtain a rigorous certificate of
infeasibility with the routine `vsdpinfeas`

:

Apart from the problem data parameters `(A,b,c,K)`

and the approximations
`(xt,yt,zt)`

an additional parameter is required, namely

`'p'`

if primal infeasibility should be verified, or`'d'`

if dual infeasibility should be verified.

The function `vsdpinfeas`

tries to verify the existence of an improving
ray using the approximations that are computed by the approximate solver.
If the return value `isinfeas`

is equal to one then `vsdpinfeas`

has
verified primal infeasibility. The return value is equal to negative one
if dual infeasibility could be proved. In the case that no certificate of
infeasibility could be found `vsdpinfeas`

returns zero.

For the considered example `vsdpinfeas`

returns

Hence, primal infeasibility is verified. The return parameter `y`

provides
a rigorous dual improving ray. The return parameter `x`

must be `NaN`

, since
we did not check dual infeasibility.

Now we try to solve the problem \eqref{SDPexample} for $?? = -10^{4} < 0$. We know that in this case the problem is primal and dual infeasible.

SeDuMi terminates the computation with the termination code `info = 1`

and
gives the warnings

If we apply the routines `vsdplow`

and `vsdpup`

then the bounds $fL$, $fU$ are infinite, as expected. By applying
`vsdpinfeas`

we obtain

Since `isinfeas = 0`

, primal infeasibility could not be verified, and
therefore the certificates `x`

, `y`

are set to `NaN`

. The reason is that
all dual improving rays `y`

must satisfy

This is only possible for $y_{1} = y_{3} = y_{4} = 0$. Hence, for each improving ray the matrix \eqref{exmImpvRay} has a zero eigenvalue. In VSDP we verify positive semidefiniteness by computing enclosures of the eigenvalues. If all enclosures are non-negative positive semidefiniteness is proved. If one eigenvalue is zero then, except in special cases, the corresponding enclosure has a negative component implying that positive semidefinitness cannot be proved and primal infeasibility is not verified.

Now we try to verify dual infeasibility by using `vsdpinfeas`

with the
parameter `'d'`

.

Also dual infeasibility cannot be proved. An easy calculation shows that the primal improving ray must satisfy

and with the same argument as above positive semidefiniteness cannot be verified.

Published with GNU Octave 4.4.1