1
$\begingroup$

Hello,

I have the following problem:

Find a non-negative matrix $L$ (i.e. $L_{i,j} \geq 0$ for all $i,j$), $L \neq I$ so that $A(I-L)^{-1}y \geq 0$ (the inequality must hold for each component), where $A$ is a given matrix and $y$ is a known vector. Also, I would like the rows of $L$ to sum to one, but perhaps that condition can be dropped.

Is there a known way of approaching this problem, or is it NP-complete? Basically the issue is that I need both $L$ and $L^{-1}$ to satisfy a certain property. Surprisingly, I haven't found any results on optimization problems that involve a matrix and its inverse.

Thanks a lot!

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ If each row of $L$ sums to $1$, $I - L$ can't be invertible (the column vector of all $1$'s is in its null space). $\endgroup$
    – Robert Israel
    Commented Dec 22, 2011 at 8:14
  • $\begingroup$ Thank you, I should have seen that. Let's assume for now that there is no restriction on what the columns sum to. $\endgroup$
    – Woland
    Commented Dec 22, 2011 at 10:38
  • $\begingroup$ Although your question has already been answered, let me comment that you can impose constraints on a matrix and its inverse by semidefinite programming. See my answer in mathoverflow.net/questions/162100/… for an example. Or even better, have a look at the chapter 4 of the Ben-Tal & Nemirovski book (Lectures on Modern Convex Optimization). $\endgroup$
    – Cristóbal Guzmán
    Commented Apr 9, 2014 at 14:05
  • $\begingroup$ I forgot to say in my comment above that this only works in the case your matrix variable is positive semidefinite. The tool you use is the Lemma on Schur complements, so you need your block diagonal parts to be psd. $\endgroup$
    – Cristóbal Guzmán
    Commented Apr 9, 2014 at 14:57

1 Answer 1

Reset to default
1
$\begingroup$

Leaving out for the moment the requirement that $I-L$ is invertible, write your inequality as $A u \ge 0$ where $Lu = u - y$.

Case 1: Suppose we can find a vector $u$ such that $A u \ge 0$ and $u$ has both positive and negative components: if possible, this can be done efficiently by linear programming. Then we can easily get $L u = u - y$ with $L \ge 0$, looking at each row of $L$ separately.

Case 2: Suppose case 1 does not hold, but there is a vector $u \ge 0$ with $A u \ge 0$ and $u_j > 0$ for those $j$ where $y_j > 0$. Again this can be found efficiently with linear programming. Multiplying be a suitable positive scalar, we can assume $u > y$. Then again we can easily get $L$ so $L u = u - y$.

Case 3: Suppose every vector $u$ with $A u \ge 0$ has $u \ge 0$, but case 2 does not hold: then there is a component $j$ such that $y_j > 0$ and every $u$ with $A u \ge 0$ has $u_j = 0$. Then $u_j - (L u)_j = y_j$ is impossible.

Similarly we can deal with the case where every vector $u$ with $A u \ge 0$ has $u \le 0$.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you very much, that indeed solves the problem. Unfortunately I was a bit tired yesterday and I didn't state my question correctly. What I really have are $m$ matrices $A_j$ $1 \leq j \leq m$ and I am looking for a single positive matrix $L$ and vectors $u_j$ so that $\sum_j A_j u_j \geq 0$ and $Lu_j = u_j - y_j$, where $y_j$ is given. I'm not sure if I should post a new question or edit the one above. $\endgroup$
    – Woland
    Commented Dec 22, 2011 at 22:30

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .