Re: apply simplex method to fix linear programming in spark
Dear Debasish Das, Thanks very much for your kind reply. I am very sorry that, but may you clearify a little more about the places, since I could not find them. On Thursday, November 5, 2015 5:50 AM, Debasish Das wrote: Yeah for this you can use breeze quadratic minimizer...that's integrated with spark in one of my spark pr. You have quadratic objective with equality which is primal and your proximal is positivity that we already support. I have not given an API for linear objective but that should be simple to add. You can add an issue in breeze for the enhancememt. Where is the API or link site for the breeze quadratic minimizer integrated with spark?And where is the breeze lpsolver... Alternatively you can use breeze lpsolver as well that uses simplex from apache math. Thank you,Zhiliang On Nov 4, 2015 1:05 AM, "Zhiliang Zhu" wrote: Hi Debasish Das, Firstly I must show my deep appreciation towards you kind help. Yes, my issue is some typical LP related, it is as:Objective function:f(x1, x2, ..., xn) = a1 * x1 + a2 * x2 + ... + an * xn, (n would be some number bigger than 100) There are only 4 constraint functions,x1 + x2 + ... + xn = 1, 1) b1 * x1 + b2 * x2 + ... + bn * xn = b, 2) c1 * x1 + c2 * x2 + ... + cn * xn = c, 3) x1, x2, ..., xn >= 0 . To find the solution of x which lets objective function the biggest. Since simplex method may not be supported by spark. Then I may switch to the way as, since the likely solution x must be on the boundary of 1), 2) and 3) geometry,that is to say, only three xi may be >= 0, all the others must be 0. Just look for all that kinds of solutions of 1), 2) and 3), the number would be C(n, 3) + C(n, 2) + C(n, 1), at last to select the most optimized one. Since the constraint number is not that large, I think this might be some way. Thank you,Zhiliang On Wednesday, November 4, 2015 2:25 AM, Debasish Das wrote: Spark has nnls in mllib optimization. I have refactored nnls to breeze as well but we could not move out nnls from mllib due to some runtime issues from breeze.Issue in spark or breeze nnls is that it takes dense gram matrix which does not scale if rank is high but it has been working fine for nnmf till 400 rank.I agree with Sean that you need to see if really simplex is needed. Many constraints can be formulated as proximal operator and then you can use breeze nonlinearminimizer or spark-tfocs package if it is stable.On Nov 2, 2015 10:13 AM, "Sean Owen" wrote: I might be steering this a bit off topic: does this need the simplex method? this is just an instance of nonnegative least squares. I don't think it relates to LDA either. Spark doesn't have any particular support for NNLS (right?) or simplex though. On Mon, Nov 2, 2015 at 6:03 PM, Debasish Das wrote: > Use breeze simplex which inturn uses apache maths simplex...if you want to > use interior point method you can use ecos > https://github.com/embotech/ecos-java-scala ...spark summit 2014 talk on > quadratic solver in matrix factorization will show you example integration > with spark. ecos runs as jni process in every executor. > > On Nov 1, 2015 9:52 AM, "Zhiliang Zhu" wrote: >> >> Hi Ted Yu, >> >> Thanks very much for your kind reply. >> Do you just mean that in spark there is no specific package for simplex >> method? >> >> Then I may try to fix it by myself, do not decide whether it is convenient >> to finish by spark, before finally fix it. >> >> Thank you, >> Zhiliang >> >> >> >> >> On Monday, November 2, 2015 1:43 AM, Ted Yu wrote: >> >> >> A brief search in code base shows the following: >> >> TODO: Add simplex constraints to allow alpha in (0,1). >> ./mllib/src/main/scala/org/apache/spark/mllib/clustering/LDA.scala >> >> I guess the answer to your question is no. >> >> FYI >> >> On Sun, Nov 1, 2015 at 9:37 AM, Zhiliang Zhu >> wrote: >> >> Dear All, >> >> As I am facing some typical linear programming issue, and I know simplex >> method is specific in solving LP question, >> I am very sorry that whether there is already some mature package in spark >> about simplex method... >> >> Thank you very much~ >> Best Wishes! >> Zhiliang >> >> >> >> >> >
Re: apply simplex method to fix linear programming in spark
Yeah for this you can use breeze quadratic minimizer...that's integrated with spark in one of my spark pr. You have quadratic objective with equality which is primal and your proximal is positivity that we already support. I have not given an API for linear objective but that should be simple to add. You can add an issue in breeze for the enhancememt. Alternatively you can use breeze lpsolver as well that uses simplex from apache math. On Nov 4, 2015 1:05 AM, "Zhiliang Zhu" wrote: > Hi Debasish Das, > > Firstly I must show my deep appreciation towards you kind help. > > Yes, my issue is some typical LP related, it is as: > Objective function: > f(x1, x2, ..., xn) = a1 * x1 + a2 * x2 + ... + an * xn, (n would be some > number bigger than 100) > > There are only 4 constraint functions, > x1 + x2 + ... + xn = 1, 1) > b1 * x1 + b2 * x2 + ... + bn * xn = b, 2) > c1 * x1 + c2 * x2 + ... + cn * xn = c, 3) > x1, x2, ..., xn >= 0 . > > To find the solution of x which lets objective function the biggest. > > Since simplex method may not be supported by spark. Then I may switch to > the way as, since the likely solution x must be on the boundary of 1), 2) > and 3) geometry, > that is to say, only three xi may be >= 0, all the others must be 0. > Just look for all that kinds of solutions of 1), 2) and 3), the number > would be C(n, 3) + C(n, 2) + C(n, 1), at last to select the most optimized > one. > > Since the constraint number is not that large, I think this might be some > way. > > Thank you, > Zhiliang > > > On Wednesday, November 4, 2015 2:25 AM, Debasish Das < > debasish.da...@gmail.com> wrote: > > > Spark has nnls in mllib optimization. I have refactored nnls to breeze as > well but we could not move out nnls from mllib due to some runtime issues > from breeze. > Issue in spark or breeze nnls is that it takes dense gram matrix which > does not scale if rank is high but it has been working fine for nnmf till > 400 rank. > I agree with Sean that you need to see if really simplex is needed. Many > constraints can be formulated as proximal operator and then you can use > breeze nonlinearminimizer or spark-tfocs package if it is stable. > On Nov 2, 2015 10:13 AM, "Sean Owen" wrote: > > I might be steering this a bit off topic: does this need the simplex > method? this is just an instance of nonnegative least squares. I don't > think it relates to LDA either. > > Spark doesn't have any particular support for NNLS (right?) or simplex > though. > > On Mon, Nov 2, 2015 at 6:03 PM, Debasish Das > wrote: > > Use breeze simplex which inturn uses apache maths simplex...if you want > to > > use interior point method you can use ecos > > https://github.com/embotech/ecos-java-scala ...spark summit 2014 talk on > > quadratic solver in matrix factorization will show you example > integration > > with spark. ecos runs as jni process in every executor. > > > > On Nov 1, 2015 9:52 AM, "Zhiliang Zhu" > wrote: > >> > >> Hi Ted Yu, > >> > >> Thanks very much for your kind reply. > >> Do you just mean that in spark there is no specific package for simplex > >> method? > >> > >> Then I may try to fix it by myself, do not decide whether it is > convenient > >> to finish by spark, before finally fix it. > >> > >> Thank you, > >> Zhiliang > >> > >> > >> > >> > >> On Monday, November 2, 2015 1:43 AM, Ted Yu > wrote: > >> > >> > >> A brief search in code base shows the following: > >> > >> TODO: Add simplex constraints to allow alpha in (0,1). > >> ./mllib/src/main/scala/org/apache/spark/mllib/clustering/LDA.scala > >> > >> I guess the answer to your question is no. > >> > >> FYI > >> > >> On Sun, Nov 1, 2015 at 9:37 AM, Zhiliang Zhu > > >> wrote: > >> > >> Dear All, > >> > >> As I am facing some typical linear programming issue, and I know simplex > >> method is specific in solving LP question, > >> I am very sorry that whether there is already some mature package in > spark > >> about simplex method... > >> > >> Thank you very much~ > >> Best Wishes! > >> Zhiliang > >> > >> > >> > >> > >> > > > > > >
Re: apply simplex method to fix linear programming in spark
Hi Debasish Das, I found that there are lots of much useful information for me in your kind reply.However, I am sorry that still I could not exactly catch each words you said. I just know spark mllib will use breeze as its underlying package, however, I did not practise and do not know how to directly apply breeze in spark program.What is and where is nnls in mllib optimization, and what is spark-tfocs package , I do not find them in spark official website...Where is to use breeze nonlinearminimizer... Next I will also meet with optimized function with nonlinear constraint functions. I am sorry that I do not know whether it is convenient for you to comment some more for my above issues. Thank you in advance. Zhiliang On Wednesday, November 4, 2015 2:25 AM, Debasish Das wrote: Spark has nnls in mllib optimization. I have refactored nnls to breeze as well but we could not move out nnls from mllib due to some runtime issues from breeze.Issue in spark or breeze nnls is that it takes dense gram matrix which does not scale if rank is high but it has been working fine for nnmf till 400 rank.I agree with Sean that you need to see if really simplex is needed. Many constraints can be formulated as proximal operator and then you can use breeze nonlinearminimizer or spark-tfocs package if it is stable.On Nov 2, 2015 10:13 AM, "Sean Owen" wrote: I might be steering this a bit off topic: does this need the simplex method? this is just an instance of nonnegative least squares. I don't think it relates to LDA either. Spark doesn't have any particular support for NNLS (right?) or simplex though. On Mon, Nov 2, 2015 at 6:03 PM, Debasish Das wrote: > Use breeze simplex which inturn uses apache maths simplex...if you want to > use interior point method you can use ecos > https://github.com/embotech/ecos-java-scala ...spark summit 2014 talk on > quadratic solver in matrix factorization will show you example integration > with spark. ecos runs as jni process in every executor. > > On Nov 1, 2015 9:52 AM, "Zhiliang Zhu" wrote: >> >> Hi Ted Yu, >> >> Thanks very much for your kind reply. >> Do you just mean that in spark there is no specific package for simplex >> method? >> >> Then I may try to fix it by myself, do not decide whether it is convenient >> to finish by spark, before finally fix it. >> >> Thank you, >> Zhiliang >> >> >> >> >> On Monday, November 2, 2015 1:43 AM, Ted Yu wrote: >> >> >> A brief search in code base shows the following: >> >> TODO: Add simplex constraints to allow alpha in (0,1). >> ./mllib/src/main/scala/org/apache/spark/mllib/clustering/LDA.scala >> >> I guess the answer to your question is no. >> >> FYI >> >> On Sun, Nov 1, 2015 at 9:37 AM, Zhiliang Zhu >> wrote: >> >> Dear All, >> >> As I am facing some typical linear programming issue, and I know simplex >> method is specific in solving LP question, >> I am very sorry that whether there is already some mature package in spark >> about simplex method... >> >> Thank you very much~ >> Best Wishes! >> Zhiliang >> >> >> >> >> >
Re: apply simplex method to fix linear programming in spark
Hi Debasish Das, Firstly I must show my deep appreciation towards you kind help. Yes, my issue is some typical LP related, it is as:Objective function:f(x1, x2, ..., xn) = a1 * x1 + a2 * x2 + ... + an * xn, (n would be some number bigger than 100) There are only 4 constraint functions,x1 + x2 + ... + xn = 1, 1) b1 * x1 + b2 * x2 + ... + bn * xn = b, 2) c1 * x1 + c2 * x2 + ... + cn * xn = c, 3) x1, x2, ..., xn >= 0 . To find the solution of x which lets objective function the biggest. Since simplex method may not be supported by spark. Then I may switch to the way as, since the likely solution x must be on the boundary of 1), 2) and 3) geometry,that is to say, only three xi may be >= 0, all the others must be 0. Just look for all that kinds of solutions of 1), 2) and 3), the number would be C(n, 3) + C(n, 2) + C(n, 1), at last to select the most optimized one. Since the constraint number is not that large, I think this might be some way. Thank you,Zhiliang On Wednesday, November 4, 2015 2:25 AM, Debasish Das wrote: Spark has nnls in mllib optimization. I have refactored nnls to breeze as well but we could not move out nnls from mllib due to some runtime issues from breeze.Issue in spark or breeze nnls is that it takes dense gram matrix which does not scale if rank is high but it has been working fine for nnmf till 400 rank.I agree with Sean that you need to see if really simplex is needed. Many constraints can be formulated as proximal operator and then you can use breeze nonlinearminimizer or spark-tfocs package if it is stable.On Nov 2, 2015 10:13 AM, "Sean Owen" wrote: I might be steering this a bit off topic: does this need the simplex method? this is just an instance of nonnegative least squares. I don't think it relates to LDA either. Spark doesn't have any particular support for NNLS (right?) or simplex though. On Mon, Nov 2, 2015 at 6:03 PM, Debasish Das wrote: > Use breeze simplex which inturn uses apache maths simplex...if you want to > use interior point method you can use ecos > https://github.com/embotech/ecos-java-scala ...spark summit 2014 talk on > quadratic solver in matrix factorization will show you example integration > with spark. ecos runs as jni process in every executor. > > On Nov 1, 2015 9:52 AM, "Zhiliang Zhu" wrote: >> >> Hi Ted Yu, >> >> Thanks very much for your kind reply. >> Do you just mean that in spark there is no specific package for simplex >> method? >> >> Then I may try to fix it by myself, do not decide whether it is convenient >> to finish by spark, before finally fix it. >> >> Thank you, >> Zhiliang >> >> >> >> >> On Monday, November 2, 2015 1:43 AM, Ted Yu wrote: >> >> >> A brief search in code base shows the following: >> >> TODO: Add simplex constraints to allow alpha in (0,1). >> ./mllib/src/main/scala/org/apache/spark/mllib/clustering/LDA.scala >> >> I guess the answer to your question is no. >> >> FYI >> >> On Sun, Nov 1, 2015 at 9:37 AM, Zhiliang Zhu >> wrote: >> >> Dear All, >> >> As I am facing some typical linear programming issue, and I know simplex >> method is specific in solving LP question, >> I am very sorry that whether there is already some mature package in spark >> about simplex method... >> >> Thank you very much~ >> Best Wishes! >> Zhiliang >> >> >> >> >> >
Re: apply simplex method to fix linear programming in spark
Spark has nnls in mllib optimization. I have refactored nnls to breeze as well but we could not move out nnls from mllib due to some runtime issues from breeze. Issue in spark or breeze nnls is that it takes dense gram matrix which does not scale if rank is high but it has been working fine for nnmf till 400 rank. I agree with Sean that you need to see if really simplex is needed. Many constraints can be formulated as proximal operator and then you can use breeze nonlinearminimizer or spark-tfocs package if it is stable. On Nov 2, 2015 10:13 AM, "Sean Owen" wrote: > I might be steering this a bit off topic: does this need the simplex > method? this is just an instance of nonnegative least squares. I don't > think it relates to LDA either. > > Spark doesn't have any particular support for NNLS (right?) or simplex > though. > > On Mon, Nov 2, 2015 at 6:03 PM, Debasish Das > wrote: > > Use breeze simplex which inturn uses apache maths simplex...if you want > to > > use interior point method you can use ecos > > https://github.com/embotech/ecos-java-scala ...spark summit 2014 talk on > > quadratic solver in matrix factorization will show you example > integration > > with spark. ecos runs as jni process in every executor. > > > > On Nov 1, 2015 9:52 AM, "Zhiliang Zhu" > wrote: > >> > >> Hi Ted Yu, > >> > >> Thanks very much for your kind reply. > >> Do you just mean that in spark there is no specific package for simplex > >> method? > >> > >> Then I may try to fix it by myself, do not decide whether it is > convenient > >> to finish by spark, before finally fix it. > >> > >> Thank you, > >> Zhiliang > >> > >> > >> > >> > >> On Monday, November 2, 2015 1:43 AM, Ted Yu > wrote: > >> > >> > >> A brief search in code base shows the following: > >> > >> TODO: Add simplex constraints to allow alpha in (0,1). > >> ./mllib/src/main/scala/org/apache/spark/mllib/clustering/LDA.scala > >> > >> I guess the answer to your question is no. > >> > >> FYI > >> > >> On Sun, Nov 1, 2015 at 9:37 AM, Zhiliang Zhu > > >> wrote: > >> > >> Dear All, > >> > >> As I am facing some typical linear programming issue, and I know simplex > >> method is specific in solving LP question, > >> I am very sorry that whether there is already some mature package in > spark > >> about simplex method... > >> > >> Thank you very much~ > >> Best Wishes! > >> Zhiliang > >> > >> > >> > >> > >> > > >
Re: apply simplex method to fix linear programming in spark
I might be steering this a bit off topic: does this need the simplex method? this is just an instance of nonnegative least squares. I don't think it relates to LDA either. Spark doesn't have any particular support for NNLS (right?) or simplex though. On Mon, Nov 2, 2015 at 6:03 PM, Debasish Das wrote: > Use breeze simplex which inturn uses apache maths simplex...if you want to > use interior point method you can use ecos > https://github.com/embotech/ecos-java-scala ...spark summit 2014 talk on > quadratic solver in matrix factorization will show you example integration > with spark. ecos runs as jni process in every executor. > > On Nov 1, 2015 9:52 AM, "Zhiliang Zhu" wrote: >> >> Hi Ted Yu, >> >> Thanks very much for your kind reply. >> Do you just mean that in spark there is no specific package for simplex >> method? >> >> Then I may try to fix it by myself, do not decide whether it is convenient >> to finish by spark, before finally fix it. >> >> Thank you, >> Zhiliang >> >> >> >> >> On Monday, November 2, 2015 1:43 AM, Ted Yu wrote: >> >> >> A brief search in code base shows the following: >> >> TODO: Add simplex constraints to allow alpha in (0,1). >> ./mllib/src/main/scala/org/apache/spark/mllib/clustering/LDA.scala >> >> I guess the answer to your question is no. >> >> FYI >> >> On Sun, Nov 1, 2015 at 9:37 AM, Zhiliang Zhu >> wrote: >> >> Dear All, >> >> As I am facing some typical linear programming issue, and I know simplex >> method is specific in solving LP question, >> I am very sorry that whether there is already some mature package in spark >> about simplex method... >> >> Thank you very much~ >> Best Wishes! >> Zhiliang >> >> >> >> >> > - To unsubscribe, e-mail: user-unsubscr...@spark.apache.org For additional commands, e-mail: user-h...@spark.apache.org
Re: apply simplex method to fix linear programming in spark
Use breeze simplex which inturn uses apache maths simplex...if you want to use interior point method you can use ecos https://github.com/embotech/ecos-java-scala ...spark summit 2014 talk on quadratic solver in matrix factorization will show you example integration with spark. ecos runs as jni process in every executor. On Nov 1, 2015 9:52 AM, "Zhiliang Zhu" wrote: > Hi Ted Yu, > > Thanks very much for your kind reply. > Do you just mean that in spark there is no specific package for simplex > method? > > Then I may try to fix it by myself, do not decide whether it is convenient > to finish by spark, before finally fix it. > > Thank you, > Zhiliang > > > > > On Monday, November 2, 2015 1:43 AM, Ted Yu wrote: > > > A brief search in code base shows the following: > > TODO: Add simplex constraints to allow alpha in (0,1). > ./mllib/src/main/scala/org/apache/spark/mllib/clustering/LDA.scala > > I guess the answer to your question is no. > > FYI > > On Sun, Nov 1, 2015 at 9:37 AM, Zhiliang Zhu > wrote: > > Dear All, > > As I am facing some typical linear programming issue, and I know simplex > method is specific in solving LP question, > I am very sorry that whether there is already some mature package in spark > about simplex method... > > Thank you very much~ > Best Wishes! > Zhiliang > > > > > >
Re: apply simplex method to fix linear programming in spark
Hi Ted Yu, Thanks very much for your kind reply.Do you just mean that in spark there is no specific package for simplex method? Then I may try to fix it by myself, do not decide whether it is convenient to finish by spark, before finally fix it. Thank you,Zhiliang On Monday, November 2, 2015 1:43 AM, Ted Yu wrote: A brief search in code base shows the following: TODO: Add simplex constraints to allow alpha in (0,1)../mllib/src/main/scala/org/apache/spark/mllib/clustering/LDA.scala I guess the answer to your question is no. FYI On Sun, Nov 1, 2015 at 9:37 AM, Zhiliang Zhu wrote: Dear All, As I am facing some typical linear programming issue, and I know simplex method is specific in solving LP question, I am very sorry that whether there is already some mature package in spark about simplex method... Thank you very much~Best Wishes!Zhiliang
Re: apply simplex method to fix linear programming in spark
A brief search in code base shows the following: TODO: Add simplex constraints to allow alpha in (0,1). ./mllib/src/main/scala/org/apache/spark/mllib/clustering/LDA.scala I guess the answer to your question is no. FYI On Sun, Nov 1, 2015 at 9:37 AM, Zhiliang Zhu wrote: > Dear All, > > As I am facing some typical linear programming issue, and I know simplex > method is specific in solving LP question, > I am very sorry that whether there is already some mature package in spark > about simplex method... > > Thank you very much~ > Best Wishes! > Zhiliang > > >
apply simplex method to fix linear programming in spark
Dear All, As I am facing some typical linear programming issue, and I know simplex method is specific in solving LP question, I am very sorry that whether there is already some mature package in spark about simplex method... Thank you very much~Best Wishes!Zhiliang
