3
$\begingroup$

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 definite, 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!

1 Answers 1

2

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.

  • 0
    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$.2011-11-29