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! (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?2011-11-29
  • 0
    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$?2011-11-29
  • 0
    I see. Thanks! How shall I understand the second statement for symmetric $A$? What does "first order solution to BQP" in statement 2 mean?2011-11-29
  • 0
    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.2011-11-29
  • 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