search

cvxgrp / qcml

A Python parser for generating Python/C/Matlab solver interfaces
Other
42 stars 9 forks source link

General questions #48

Closed alexvoronov closed 10 years ago

alexvoronov commented 10 years ago

Hi Eric,

I have a few general question, and here I bundled them into one "issue" ;-)

  1. The first question is about the frontend for QCML-application: why do you use a QCML-language, and not, for example, just reuse an AST from CVXPY? (Or, conversely, integrate the codegenerator into CVXPY?)
  2. In your thesis, you mention a pre-solver to eliminate new variables introduced when converting affine atoms to Smith form. Do you have a link to such pre-solver?
  3. You also mention that "if many problems from the same family are to be solved, [...] setup routines and tasks such as determining the elimination order in ECOS or allocating memory can be done beforehand, and only once." But as far as I could find, the data generated from QCML have to be passed to ECOS_setup, where the whole initialization process is performed, and there is no way to produce/update pwork directly from QCML?
  4. If QCML(-application) could generate ECOS_setup, it maybe could also generate code to statically pre-allocate arrays for ECOS (for problems with fixed dimensions), to run ECOS on systems without malloc()?
  5. Also in your thesis, you mention GPU-based solvers, do you know if there are any open-source available?

/Alex

echu commented 10 years ago

Wow, great questions! I've interspersed my answers with your questions below (also, sorry for the formatting--hard to get it right on a cell phone).

On Thursday, July 10, 2014, alexvoronov notifications@github.com wrote:

Hi Eric,

I have a few general question, and here I bundled them into one "issue" ;-)

1.

The first question is about the frontend for QCML-application: why do you use a QCML-language, and not, for example, just reuse an AST from CVXPY? (Or, conversely, integrate the codegenerator into CVXPY?)

This is a great question, and I've asked myself this many times. The main reason is that I wrote QCML before CVXPY came into existence. Steven (@SteveDiamond) and I have talked about combining them but we haven't come up with a good way of doing this yet, because CVXPY targets problems that QCML doesn't.

Also, having my own syntax means I only need to worry about keywords, etc that I introduce for myself, whereas CVXPY lets you mix python code with your CVXPY code, which can cause some ambiguity at codegen.

If you're wondering why I chose to implement QCML as a separate language instead of embedded in python, the main reason is that I had a bad experience with CVXMOD (an earlier incarnation of CVXPY). :)

Ultimately, I would love to have the two projects combined, and I think it can be done, but I don't have time (yet) to do this. I have some crazy ideas and am hoping to get around to them soon.

1.

In your thesis, you mention a pre-solver to eliminate new variables introduced when converting affine atoms to Smith form. Do you have a link to such pre-solver?

Ah, there's a bunch of these for LP solvers. Don't have the links immediately on me (on my cell phone at the moment), but I think if you google LPs and presolvers, something will show up. I never did find anything "stand alone" though.

QCML does this "on the fly." It keeps track of expressions it's introduced new variables for and tries to reuse them. It also tries not to introduce new variables unless it absolutely needs to. I don't guarantee that it always works, though. :)

1.

You also mention that "if many problems from the same family are to be solved, [...] setup routines and tasks such as determining the elimination order in ECOS or allocating memory can be done beforehand, and only once." But as far as I could find, the data generated from QCML have to be passed to ECOS_setup, where the whole initialization process is performed, and there is no way to produce/update pwork directly from QCML?

You're right. This isn't part of QCML yet. Alex (@adomahidi) and I have played around with this idea, since ECOS setup just creates a permuted KKT system, and I can do this work ahead of time.

The only thing stopping me from doing this is that QCML would be tightly integrated with ECOS. I originally thought we could call other C solvers, but I don't think "solvers" are a very popular piece of software to write. So it may not be a bad thing to integrate tightly with ECOS.

1.

If QCML(-application) could generate ECOS_setup, it maybe could also generate code to statically pre-allocate arrays for ECOS (for problems with fixed dimensions), to run ECOS on systems without malloc()?

Yes! In fact, the original design for QCML was to be a front end for ECOS. I may revisit that idea again.

1.

Also in your thesis, you mention GPU-based solvers, do you know if there are any open-source available?

There are ones specifically for the lasso (l1-regularized least squares), but none for cone problems in general. I think the main issue is that nobody has tried to write one (that and lack of double precision arithmetic).

By the way, http://stanford.edu/class/ee364b/projects2014.html has a list of recent projects out of my advisor's class. The ADMM project could probably be adapted to solve cone programs (Neal's block splitting paper gives an example), although that particular code is for Spark and not GPUs. I can put you in touch with one of the TAs, who--I think--mentioned a GPU-based cone solver (but I don't see it on the page right now).

/Alex

— Reply to this email directly or view it on GitHub https://github.com/cvxgrp/qcml/issues/48.

alexvoronov commented 10 years ago

I probably should have splitted the questions :) Anyway, I tried my best with the formatting.

1.

Alex:

The first question is about the frontend for QCML-application: why do you use a QCML-language, and not, for example, just reuse an AST from CVXPY? (Or, conversely, integrate the codegenerator into CVXPY?)

Eric:

This is a great question, and I've asked myself this many times. The main reason is that I wrote QCML before CVXPY came into existence. Steven (@SteveDiamond) and I have talked about combining them but we haven't come up with a good way of doing this yet, because CVXPY targets problems that QCML doesn't.

Also, having my own syntax means I only need to worry about keywords, etc that I introduce for myself, whereas CVXPY lets you mix python code with your CVXPY code, which can cause some ambiguity at codegen.

If you're wondering why I chose to implement QCML as a separate language instead of embedded in python, the main reason is that I had a bad experience with CVXMOD (an earlier incarnation of CVXPY). :)

Ultimately, I would love to have the two projects combined, and I think it can be done, but I don't have time (yet) to do this. I have some crazy ideas and am hoping to get around to them soon.

Aha, now I know :) I'm looking forward to seeing your ideas come to life!

2.

Alex:

In your thesis, you mention a pre-solver to eliminate new variables introduced when converting affine atoms to Smith form. Do you have a link to such pre-solver?

Eric:

Ah, there's a bunch of these for LP solvers. Don't have the links immediately on me (on my cell phone at the moment), but I think if you google LPs and presolvers, something will show up. I never did find anything "stand alone" though.

QCML does this "on the fly." It keeps track of expressions it's introduced new variables for and tries to reuse them. It also tries not to introduce new variables unless it absolutely needs to. I don't guarantee that it always works, though. :)

So QCML does not introduce redundant variables, so presolver would not have much to do?

3 & 4.

Alex:

You also mention that "if many problems from the same family are to be solved, [...] setup routines and tasks such as determining the elimination order in ECOS or allocating memory can be done beforehand, and only once."But as far as I could find, the data generated from QCML have to be passed to ECOS_setup, where the whole initialization process is performed, and there is no way to produce/update pwork directly from QCML?

If QCML(-application) could generate ECOS_setup, it maybe could also generate code to statically pre-allocate arrays for ECOS (for problems with fixed dimensions), to run ECOS on systems without malloc()?

Eric:

You're right. This isn't part of QCML yet. Alex (@adomahidi) and I have played around with this idea, since ECOS setup just creates a permuted KKT system, and I can do this work ahead of time.

The only thing stopping me from doing this is that QCML would be tightly integrated with ECOS. I originally thought we could call other C solvers, but I don't think "solvers" are a very popular piece of software to write. So it may not be a bad thing to integrate tightly with ECOS.

Yes! In fact, the original design for QCML was to be a front end for ECOS. I may revisit that idea again.

Would it be possible to generate solver-independent code (prob2socp), and then generate two solver-specific pieces of code, one for data-independent (but problem-specific) initialization code, and one for moving solver-independent socp data into solver datastructures? Then QCML would be both general enough for any socp solver, and will have a backend for one specific solver (ECOS) with possibility to implement other backends.

5.

Alex:

Also in your thesis, you mention GPU-based solvers, do you know if there are any open-source available?

Eric:

There are ones specifically for the lasso (l1-regularized least squares), but none for cone problems in general. I think the main issue is that nobody has tried to write one (that and lack of double precision arithmetic).

By the way, http://stanford.edu/class/ee364b/projects2014.html has a list of recent projects out of my advisor's class. The ADMM project could probably be adapted to solve cone programs (Neal's block splitting paper gives an example), although that particular code is for Spark and not GPUs. I can put you in touch with one of the TAs, who--I think--mentioned a GPU-based cone solver (but I don't see it on the page right now).

Sure, I'm curious if there's anything available (but I'm unlikely to work myself on the implementation anytime soon...). I looked at the code for ADMM-on-Spark project, it is written in Scala, do you know if it is somehow related to OptiCVX?

echu commented 10 years ago

See below.

On Fri, Jul 11, 2014 at 5:12 AM, alexvoronov notifications@github.com wrote:

I probably should have splitted the questions :) Anyway, I tried my best with the formatting. 1.

Alex:

The first question is about the frontend for QCML-application: why do you use a QCML-language, and not, for example, just reuse an AST from CVXPY? (Or, conversely, integrate the codegenerator into CVXPY?)

Eric:

This is a great question, and I've asked myself this many times. The main reason is that I wrote QCML before CVXPY came into existence. Steven ( @SteveDiamond https://github.com/SteveDiamond) and I have talked about combining them but we haven't come up with a good way of doing this yet, because CVXPY targets problems that QCML doesn't.

Also, having my own syntax means I only need to worry about keywords, etc that I introduce for myself, whereas CVXPY lets you mix python code with your CVXPY code, which can cause some ambiguity at codegen.

If you're wondering why I chose to implement QCML as a separate language instead of embedded in python, the main reason is that I had a bad experience with CVXMOD (an earlier incarnation of CVXPY). :)

Ultimately, I would love to have the two projects combined, and I think it can be done, but I don't have time (yet) to do this. I have some crazy ideas and am hoping to get around to them soon.

Aha, now I know :) I'm looking forward to seeing your ideas come to life! 2.

Alex:

In your thesis, you mention a pre-solver to eliminate new variables introduced when converting affine atoms to Smith form. Do you have a link to such pre-solver?

Eric:

Ah, there's a bunch of these for LP solvers. Don't have the links immediately on me (on my cell phone at the moment), but I think if you google LPs and presolvers, something will show up. I never did find anything "stand alone" though.

QCML does this "on the fly." It keeps track of expressions it's introduced new variables for and tries to reuse them. It also tries not to introduce new variables unless it absolutely needs to. I don't guarantee that it always works, though. :)

So QCML does not introduce redundant variables, so presolver would not have much to do?

I think the correct statement is QCML tries not to introduce redundant variables. I may do it inadvertently. :) A presolver certainly would have some value, although I haven't tried running one before calling ECOS.

3 & 4.

Alex:

You also mention that "if many problems from the same family are to be solved, [...] setup routines and tasks such as determining the elimination order in ECOS or allocating memory can be done beforehand, and only once."But as far as I could find, the data generated from QCML have to be passed to ECOS_setup, where the whole initialization process is performed, and there is no way to produce/update pwork directly from QCML?

If QCML(-application) could generate ECOS_setup, it maybe could also generate code to statically pre-allocate arrays for ECOS (for problems with fixed dimensions), to run ECOS on systems without malloc()?

Eric:

You're right. This isn't part of QCML yet. Alex (@adomahidi https://github.com/adomahidi) and I have played around with this idea, since ECOS setup just creates a permuted KKT system, and I can do this work ahead of time.

The only thing stopping me from doing this is that QCML would be tightly integrated with ECOS. I originally thought we could call other C solvers, but I don't think "solvers" are a very popular piece of software to write. So it may not be a bad thing to integrate tightly with ECOS.

Yes! In fact, the original design for QCML was to be a front end for ECOS. I may revisit that idea again.

Would it be possible to generate solver-independent code (prob2socp), and then generate two solver-specific pieces of code, one for data-independent (but problem-specific) initialization code, and one for moving solver-independent socp data into solver datastructures? Then QCML would be both general enough for any socp solver, and will have a backend for one specific solver (ECOS) with possibility to implement other backends.

Sure. This is definitely possible, but is a bit of work. It may be more worthwhile to just generate (compile) a solver--like CVXGEN.

5.

Alex:

Also in your thesis, you mention GPU-based solvers, do you know if there are any open-source available?

Eric:

There are ones specifically for the lasso (l1-regularized least squares), but none for cone problems in general. I think the main issue is that nobody has tried to write one (that and lack of double precision arithmetic).

By the way, http://stanford.edu/class/ee364b/projects2014.html has a list of recent projects out of my advisor's class. The ADMM project could probably be adapted to solve cone programs (Neal's block splitting paper gives an example), although that particular code is for Spark and not GPUs. I can put you in touch with one of the TAs, who--I think--mentioned a GPU-based cone solver (but I don't see it on the page right now).

Sure, I'm curious if there's anything available (but I'm unlikely to work myself on the implementation anytime soon...). I looked at the code for ADMM-on-Spark project, it is written in Scala, do you know if it is somehow related to OptiCVX http://stanford-ppl.github.io/Delite/opticvx/ ?

I don't think that project is related to OptiCVX, they just both use Scala. :)

— Reply to this email directly or view it on GitHub https://github.com/cvxgrp/qcml/issues/48#issuecomment-48723145.

alexvoronov commented 10 years ago

Yes, you're right, it might be better to generate the whole solver...

I got answers to all the questions I had, I'll close this "issue" to not introduce any more mess :)

Thanks a lot for all your answers!