General questions

[alexvoronov]

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]

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" ;-)

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.

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. :)

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.

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.

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
#48.

[alexvoronov]

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]

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.

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
#48 (comment).

[alexvoronov]

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!