Relation between bounded quadratic  and linear complementary problems In a paper, it says that

Given a bounded quadratic problem (BQP) $$ \min_{x \in \mathbb{R}^n}
 \frac{1}{2} x^T A x + b^T x $$ subject to $$ x \geq 0, \quad i.e. \quad x_i \geq 0, i=1,...,n$$
and a linear complementary problem (LCP) $$ x .* (Ax+b) = 0, \quad i.e. \quad x_i \times (A(i,:)x+b_i) =
 0, i=1,...,n $$ $$ Ax+b \geq 0, \quad i.e.  \quad A(i,:)x+b_i \geq 0, i=1,...,n $$ $$ x \geq 0, \quad i.e. \quad x_i \geq 0,
 i=1,...,n$$
  
  
*
  
*if $A$ is symmetric positive deﬁnite, then   $x$ is minimizer of BQP
  iff x is a solution to LCP;
  
*if $A$ is symmetric, then  $x$ is a first order solution to BQP iff
  $x$ is solution to LCP;
  
*if $A$ is general, then there is no convenient relationship between
  solutions of BQP and of LCP.
  



*

*I am trying to understand the above statements based on the KKT
conditions for the BQP, which are $$ \frac{1}{2} (A^T+A) x + b - \mu=0 $$ $$ \mu .* x =0, \quad i.e. \quad \mu_i \times
    x_i=0, i=1,...,n $$ $$ \mu \geq 0 , \quad i.e. \quad \mu_i \geq 0, i=1,...,n $$ $$ x \geq 0, \quad i.e. \quad x_i \geq 0,
    i=1,...,n,  $$ but not sure how to go from here, or I just think in the wrong direction?

*What does "first order solution to BQP" in statement 2 mean? Is it defined as a
solution to the BQP that also satisfies KKT conditions?


Thanks and regards!

You are on the right track I think. You can re-write your first condition as:
$$\mu = Ax +b$$
Substituting in the second condition it follows that:
$$x.* (Ax+b) = 0$$ 
Using the fact that $\mu \ge 0$, we have:
$$Ax+b \ge 0$$
Thus, in essence, you need to eliminate $\mu$ from the KKT conditions to get to the LCP.

In response to your edit, note the following:
(A). If $A$ is symmetric then $A^T = A$ and hence KKT reduces to the LCP as far as 1 and 2 are concerned.
(B). If $A$ is positive definite in addition to being symmetric then the objective function is convex and hence KKT is both necessary and sufficient for optimality. Hence, 1 follows from above.
(C) If $A$ is only symmetric then KKT is necessary but not sufficient which is what may be meant by 'first order solution'
(D) If $A$ is general matrix not necessarily symmetric, positive definite then the KKT conditions do not map one-to-one with the LCP and hence there may not be any relationship between your original program and LCP.
