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