I need to find vector \(f\) such that \((I-\rho A)f\) is an increasing vector (i.e. for \(i > j, g_i \ge g_j\) for some \(g \in R^N\). Some of the properties of the different parameters are:

  1. \(f \in R^N\)

  2. \(0 \le \rho \le1\)

  3. \(A\) is a stochastic matrix and its row add up to 1. Further, \(A\) is a totally positive matrix of order 2. That means all its second order minors are positive. This fact has following implications:

    a. For an increasing vector \(g\), \(Ag\) is an increasing vector.

    b. Given \(i>j\), \(i\)-th row of \(A\) stochastically dominates the \(j\)-th row in maximum likelihood ratio ordering, i.e., \(\cfrac{a_{i,k}}{a_{j,k}}\) is increasing with \(k\).

  4. \(I\) is the identity matrix.

I can find a \(f\) based on the power series representation of \((I-\rho A)^{-1}\). However, I am looking at some alternate methods for constructing vector \(f\). Any trivial/non trivial construction would suffice.

asked 26 Jan '14, 12:20

anon123's gravatar image

accept rate: 0%

edited 26 Jan '14, 20:19

By "increasing vector" do you mean \(i\gt j \implies f_i\ge f_j\)? Also,do you need \(f\ge 0\)?

(26 Jan '14, 16:16) Paul Rubin ♦♦

Yes I added the definition in the question too

(26 Jan '14, 20:24) anon123

Assuming that \(\rho\) and \(A\) are specified, this seems like a rather straightforward LP feasibility model. You could try the following in any LP solver: \[ \begin{array}{ccccc} \min & g_N\\ \textrm{s.t.} & \left(I-\rho A\right)f & = & g\\ & g_{i} + \epsilon & \le & g_{i+1} & \forall i\in\left\{ 1,\dots,N-1\right\}\\ & g & \ge & 0 \end{array} \]


answered 27 Jan '14, 11:59

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
accept rate: 19%

edited 28 Jan '14, 10:48

I am aware of solving an LP to check for feasibility. I was looking for some sort of theoretical construction which would illustrate that the LP always have a solution. Or perhaps show that above LP will always have a solution.

(27 Jan '14, 12:48) anon123

Is there a result in LP which says that if \(x\) is feasible for an LP then all the points in the neighborhood of \(x\) will also be feasible. For my problem \(x\) is a constant vector that is all entries of vector \(x\) are for example one.

(27 Jan '14, 13:13) anon123

I have no idea what \(x\) is in relation to your original question. Also, the term "neighborhood" implies a topology. If you mean euclidean neighborhood (all points within some distance of \(x\)), then no, not all nearby points need be feasible. The feasible region will be a polyhedron, and \(x\) could be on the boundary.

(27 Jan '14, 14:28) Paul Rubin ♦♦

My fault for being flawed and imprecise. The question that I was trying to pose concern the LP that you wrote. My question was that does there exist a feasible f and g for the given LP. f being a constant vector is always feasible as the corresponding g are all constant too (check f = [1,...,1] yields g = [1-p,..,1-p]). I was looking to construct f such that g is strictly increasing.

(27 Jan '14, 15:04) anon123

I changed the model (bounded \(g_N\) and gave it a nontrivial objective function) in order to avoid the trivial solution \(f = 0 = g\), which was feasible in the original formulation.

(27 Jan '14, 15:29) Paul Rubin ♦♦

Do you require \(f\) (and therefore \(g\)) to be nonnegative? Without that, I'm not positive my modified model is bounded, although I suspect it is. With nonnegativity, it's definitely bounded.

(27 Jan '14, 15:31) Paul Rubin ♦♦

Instead of adding an objective you could have set g_n=1 to normalize the solution. The problem is homogeneous so that should be ok.

Btw if \((I-\rho{}A)\) is nonsingular then it has a solution I think.

(28 Jan '14, 01:34) Erling_MOSEK

@Erling: You are correct about normalization, provided that we can assume \(g\ge 0\). The OP never said that, and I've been trying to avoid that assumption.

(28 Jan '14, 10:41) Paul Rubin ♦♦

I just changed the model again (sigh), since the problem description changed again. Apparently \(g\) needs to be strictly increasing. I've also constrained \(g\ge 0\), although I'm not sure that is warranted. The LP has a solution iff the original problem does, and gives a mechanism to construct a solution when one exists, but does not prove a solution exists (unless the dual is provably bounded).

(28 Jan '14, 10:47) Paul Rubin ♦♦
showing 5 of 9 show 4 more comments
Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported



Asked: 26 Jan '14, 12:20

Seen: 811 times

Last updated: 28 Jan '14, 10:48

OR-Exchange! Your site for questions, answers, and announcements about operations research.