# 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$$

1. if $A$ is symmetric positive deﬁnite, then $x$ is minimizer of BQP iff x is a solution to LCP;
2. if $A$ is symmetric, then $x$ is a first order solution to BQP iff $x$ is solution to LCP;
3. if $A$ is general, then there is no convenient relationship between solutions of BQP and of LCP.
1. 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?
2. 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.

-
Thanks! (1) How about going from LCP to BQP? Note that KKT is necessary condition for BQP. (2) Will the properties of $A$ play some role? – Tim Nov 29 '11 at 16:48
KKT is sufficient if the objective function is convex. Perhaps, that tells you something about the properties that must be true for the matrix $A$? – tards Nov 29 '11 at 16:57
I see. Thanks! How shall I understand the second statement for symmetric $A$? What does "first order solution to BQP" in statement 2 mean? – Tim Nov 29 '11 at 17:03
Sorry, no idea. Perhaps, they mean that the solution meets the necessary condition for optimality but is not sufficient analogous to how $f'(x)=0$ is necessary for optimality but not sufficient. – tards Nov 29 '11 at 17:09
Thanks! I made a mistake in the original questions. In the first equation of KKT conditions of BQP, the coefficient matrix of $x$ should be $\frac{1}{2} (A^T+A)$, instead of $A$. – Tim Nov 29 '11 at 18:14