3
$\begingroup$

I have $a^\intercal M b > 0$, where $\forall a_i > 0$, $\forall b_j > 0$, and M is known. I'd like to find a tight linear constraint on $b$ which is independent of $a$ (other than the positivity constraint on $a$). That is, I'd like to find a vector $v$ such that $v^\intercal b > 0$. (It's possible, of course, that such a vector may not exist for some $M$.)

Example: For the matrix $\left[\begin{matrix}9 & -2 \\ 8 & -2\end{matrix}\right]$, $v^\intercal = [4,-1]$ is a solution, because $[4,-1] b > 0$ implies $a^\intercal M b > 0$ for all positive $a$.

This feels like it should be reducible to a constrained linear optimization problem, but for the life of me I cannot figure out how. I'm not even sure how to typify $v$ as "tight"; for the example above, $v^\intercal = [5,-1]$ is also a solution but one which is weaker than $v^\intercal = [4,-1]$. For that matter, I wonder if there are multiple tight constraints when the size of $b$ grows beyond 2.

Incidentally, I'm not sweating $> 0$ versus $\geq 0$. Whichever makes the problem easier.

$\endgroup$
0
$\begingroup$

Hmmm.... I'm not 100% certain of this, but it looks like $v^\intercal$ may just be composed of the minimum element from each column of $M$. As for "tight", that seems to mean "can't subtract a nonnegative vector from $v$ without violating the constraint". And there I was gearing up with the LCP...

$\endgroup$

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.