Re: [ojAlgo-user] solving a linear optimization problem with ojAlgo ?

[Andreas A. <and...@go...>]

Hi,

there can be a feasible solution, if a vector v can be expressed as a conve=
x
combination of the vectors v1,...,vn

like this: v =3D c1*v1+c2*v2+...+cn*vn

My problem is actually: given the vectors v1,,.,vn and given the vector v, =
I
need to find the coefficients c1,,.,cn which are valid.
A valid solution exists if v is inside the convex set, which is spanned by
the vectors v1,..,vn.

If the vector v can not be expressed as a convex combination of v1,,.,vn,
that there is no possible solution to this problem.


I have already a solution in maple for this, using a Linear
ProgrammingSolver:
LPSolve(NoUserValue, [NoUserValue, NoUserValue, A, v], assume =3D
nonnegative)[2]

where A is a Matrix containing the vectors v1,..,vn. Where every vector is =
a
column in the matrix.
v is a vector (the actual v vector of the description above)


However, I hope to find a java library which is capable of the same ;)

regards,
Andreas


On Jan 5, 2008 1:39 AM, Anders Peterson <an...@op...> wrote:

> If you you have 50 variables and several hundred equations there
> typically is no feasible solution.
>
> You can get a "best fit" solution using the QR or SVD decompositions
> but those cannot handle the constraints/inequalities that the
> variables must be non-negative. You'll have to invent something to
> handle that.
>
> /Anders
>
> On 4 jan 2008, at 16.51, Andreas Andreakis wrote:
>
> > hi,
> >
> > I want to find a solution to the following problem:
> >
> > (explained by example)
> > 1 *c1 + 4 * c2 + 4* c3 + 4 * c4 =3D 2.5
> > 1 *c1 + 4 * c2 + 1* c3 + 4 * c4 =3D 3.0
> >
> > here the constraints:
> > 1) c1+c2+c3+c4 =3D 1 (of course this could be expressed as an
> > additional equation: c1 + c2 + c3 + c4 =3D 1.0)
> > 2) c1,c2,c3 and c4 are all positive
> >
> > Important is that I need only one and feasible solution, thus the
> > computation should be as fast as possible. So there is no need to
> > search for every possible result.
> > And it needs to work with doubles (not only integers, because some
> > libraries work only with integers)
> >
> > Actually the solution needs to scale for several dozens c=B4s ( there
> > will not be only 4 like c1,c2,c3,c4), but more like 50 c1,
> > c2,...,c49, c50
> > And there will not be only two equations (like in the example) but
> > several hundred.
> >
> >
> > So the questions are:
> > 1) can I find a solution using ojAlgo ?
> > 2) how will the performance be ?
> > 3) could you give me a code snipped which is able to compute the
> > given example ? (I will generalize it then myself)
> >
> > kind regards,
> > Andreas
> > ----------------------------------------------------------------------
> > ---
> > This SF.net email is sponsored by: Microsoft
> > Defy all challenges. Microsoft(R) Visual Studio 2005.
> > http://clk.atdmt.com/MRT/go/vse0120000070mrt/direct/01/
> > _______________________________________________
> > ojAlgo-user mailing list
> > ojA...@li...
> > https://lists.sourceforge.net/lists/listinfo/ojalgo-user
>
>
> -------------------------------------------------------------------------
> This SF.net email is sponsored by: Microsoft
> Defy all challenges. Microsoft(R) Visual Studio 2005.
> http://clk.atdmt.com/MRT/go/vse0120000070mrt/direct/01/
> _______________________________________________
> ojAlgo-user mailing list
> ojA...@li...
> https://lists.sourceforge.net/lists/listinfo/ojalgo-user
>