Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.