0
$\begingroup$

I have quadratically constrained linear program where one objective is of the form $x_1.x_2 \leq x_1k_1 + k_2$, $k_1, k_2$ are constants. I know that QCLP is NP-Hard in general but can be solved in PTIME if the matrix for the quadratic constraint is positive semidefinite. For my problem, the matrix is $\begin{bmatrix} 0 & 1/2 \\ 1/2 & 0 \end{bmatrix}$. By the design of my problem, $x, y > 0$. Is positive semidefinite condition $x^T M x \geq 0$ satisfied for all $x$ or only over the the constraints that vector $x > 0$ (in which case, the matrix is positive semidefinite)?

$\endgroup$
1
$\begingroup$

According to Matrix theory (Horn and Johnson), if the diagonals of a matrix are all 0, the matrix can only be indefinite. You may also check with diagonally dominant condition, which (in my impression) is a sufficient condition for positive definiteness.

In your case, the matrix [0, 1/2;1/2 0] has eigenvalues -1/2 and 1/2. So it is indefinite.

$\endgroup$
  • $\begingroup$ I thought so. Thank you for confirming! $\endgroup$ – karmanaut Sep 15 '17 at 1:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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