Can one efficiently optimize over the inverse of matrix? 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!
 A: 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$.
