# need help with the construction of a feasible solution

 0 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: $$f \in R^N$$ $$0 \le \rho \le1$$ $$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$$. $$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 33●1●6 accept rate: 0% 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

One Answer:
 2 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 Rubin ♦♦ 14.6k●5●13 accept rate: 19% 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 community wiki

### Follow this question

By Email:

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

By RSS:

Answers

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

Tags:

Asked: 26 Jan '14, 12:20

Seen: 811 times

Last updated: 28 Jan '14, 10:48

### Related questions

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