Is there an analytic solution to the following problem: Given A x = b where A is m*n matrix (m<n), and x, b are vectors of lengths n and m correspondingly, find x that minimizes cost function C|x| where C is a positive vector (of lenghts n).I'd really appreciate if someone could refer me to any literature where this type of problem is addressed.Thanks,Olya.

this sort of problems has an incredible range of solutions. There are approximate and exact ones, depending on the structure of your matrix. Check Daniel J Duffy´s "Instrument Pricing in C++" he devotes a single chapter on LU decomposition, which is a numeric exact method to solve your problem.

This is a standard linear programming problem. The simplest solution is the Simplex algorithm, although interior point methods can also be used. There are numerous freeware and comercial solvers available. In terms of literature, Chvatal wrote a good book on the subject, but you'll find plenty of online material if you do a search.

you can even solve this with ms excel (featuring the simplex algo)

i guess http://math.fullerton.edu/mathews/n2003 ... adMod.html could helpful 2 u...redards.

QuoteOriginally posted by: OlyaIs there an analytic solution to the following problem: Given A x = b where A is m*n matrix (m<n), and x, b are vectors of lengths n and m correspondingly, find x that minimizes cost function C|x| where C is a positive vector (of lenghts n).The problem does not have analytic solutions (unless considerable additional structure is imposed on the problem). Algorithms for LU decomposition does not apply to this problem (although such algorithms may be employed by linear programming solvers).Chvatal's book was spectacular in the sense that it was the first textbook on linear programming void of simplex tableau's. This makes for a very compact and readable style. Bazaraa, Jarvis and Sherali has written a textbook utilized in many OR courses as introduction to LP - the sheer number of pages may scare you off, though. George Dantzig recently wrote a two-volume textbook together with co-writer (ghost-writer ?) Mukund Thapa, which is very readable. Lex Schrijver wrote a reference on linear (and integer) programming dealing mainly with the theoretical issues in linear optimization. Stephen J. Wright has written a small book on interior point solvers, but you may be able to find newer accounts.For online resources, try INFORMS OR/MS Resource collection

Thanks so much for your replies! QuoteOriginally posted by: caroeThe problem does not have analytic solutions (unless considerable additional structure is imposed on the problem). Algorithms for LU decomposition does not apply to this problem (although such algorithms may be employed by linear programming solvers).This is what I thought I've already tried to use LP for this problem (Excel solver and LpSolve in R) but the first one is very slow and the second one does not always find solution which I guess should always exist. To do online search, I can't think of words to look for - I don't want to end up with all the LP links or all matrix equations whatever... How to narrow it down to what I need?Thanks again,Olya.

This is a basic problem and your question is pretty broad - your LP can have an unbounded solution, one solution or none. It all depends on the matrix A and b. Numerical methods and algorithms for this problem are so well developed that no one even thinks about analytical solutions. Excel is limited to 200 vars. How big is the matrix? What are m, n? If it is too slow, you probably want to try free code or free software on the net. Try thesehttp://www-fp.mcs.anl.gov/otc/Guide/SoftwareGuide/Categories/linearprog.htmlhttp://www.netlib.org/http://plato.la.asu.edu/ ... eE.html#LP