I have a concern about a result given by Murty in [1] and also written by Floudas and Visweswaran in [2]
They consider a QP:
\begin{array}{ll}{\min _{x} Q(x)} & {=c^{T} x+\frac{1}{2} x^{T} D x} \\ {\text {s.t.} \quad A x} & {\geq b} \\ {x} & {\geq 0}\end{array}
with no particular assumption on $D$ (appart from symmetric). Murty argues that if $x_{*}$ is a solution of the QP it is also solution of the following LP:
\begin{array}{cl}{\min _{x}} & {\left(c+x_{*}^{T} D\right) x} \\ {\text {s.t.}} & {A x \geq b} \\ {x} & {\geq 0}\end{array}
The proof of Murty is the following:
Let $\hat{x}$ be any feasible solution of the LP and $x_{\lambda}=\lambda \hat{x}+(1-\lambda) x_{*}$ for $\lambda \in ]0,1[$. It is also feasible since the set of feasible solutions is a convex polyhedron. Then by optimality of $x_{*}, Q\left(x_{\lambda}\right)-Q(x_{*}) \geq 0$ which implies:
$$\lambda\left(c+x_{*}^{T} D\right)(\hat{x}-x_{*})+(1 / 2)\lambda^{2}(\hat{x}-x_{*})^{T} D(\hat{x}-x_{*}) \geq 0 $$
And so dividing by $\lambda$ leads to:
$$\left(c+x_{*}^{T} D\right)(\hat{x}-x_{*}) \geq(-\lambda / 2)(\hat{x}-x_{*})^{T} D(\hat{x}-x_{*})$$
At this part Murty argues that it "obviously implies":
$$\left(c+x_{*}^{T} D\right)(\hat{x}-x_{*}) \geq 0 $$
and hence $\hat{x}$ must be an optimum feasible solution of the LP.
It seems to be false at first sight except when the QP is concave (and D neg definite) so that the rightmost term of the inequality is negative. Am I missing something ?
Ref:
[1] Linear Complementarity, Linear and non Linear Programming, 1988
[2] Quadratic Optimization by Floudas and Visweswaran, 1995
