Thread Subject: Which to use (quadprog or fmincon)?

OK, here's a re-formulation of a question I asked earlier
today:

What's the best way to solve this problem:

Minimize: c1 x1 + q1*x1*x1 + c2 x2 + q2*x2*x2 . . .

(I have about 3,000 x variables)

Subject to:
many constraints like

x1 <= 40;
x1 + x2 = 7;

all x >=0;

Now, I know a few things about this problem:

1) It's quadratic.
2) The Hessian is sparse, and well structured (only entries
on the diagonal
3) all variables are >= 0.


I'd like to use quadprog, but it seems like that's not
feasible, as if I use the problem as stated, it will use
the medium scale, which uses a dense Hessian, which will
kill performance.

If I want to use the large-scale, I can re-write my
constraints:

x1 <= 40; becomes x1 + slack1 = 40, etc, etc. But
the docs for the large scale say that I if I use the
Aeq and beq entries, I can't pass bounds. So how do
I limit my xs and slacks to be >=0?

Also, the large-scale docs imply that I cannot have more
constraints than variables, which means that if every
x has an absolute upper bound (i.e. x1 <= 40), that
blows all my rows, and I don't have enough left to do
the linear combinations.

It seems like I must be mis-understanding something about
quadprog, because it seems like my problem is perfect
for a structured approach (I can compute Hx quickly, etc,
etc).

If I want to stick with MATLAB (and not NAG, or TOMLAB),
am I reduced to using fmincon, which seems like overkill,
even though it does have the advantage that I can pass
in arbitrary numbers of constraints, and gradients and
such, since I know all that information?




Thanks for any clues,


Eric

"Eric J. Holtman" <ejh@ericholtman.com> wrote in message <Xns9B72911B0AAD8ejhericholtmamcom@216.168.3.30>...
>
> OK, here's a re-formulation of a question I asked earlier
> today:
>
> What's the best way to solve this problem:
>
> Minimize: c1 x1 + q1*x1*x1 + c2 x2 + q2*x2*x2 . . .
>
> (I have about 3,000 x variables)
>
> Subject to:
> many constraints like
>
> x1 <= 40;
> x1 + x2 = 7;
>
> all x >=0;
>
> Now, I know a few things about this problem:
>
> 1) It's quadratic.
> 2) The Hessian is sparse, and well structured (only entries
> on the diagonal
> 3) all variables are >= 0.
>
>
> I'd like to use quadprog, but it seems like that's not
> feasible, as if I use the problem as stated, it will use
> the medium scale, which uses a dense Hessian, which will
> kill performance.
>
> If I want to use the large-scale, I can re-write my
> constraints:
>
> x1 <= 40; becomes x1 + slack1 = 40, etc, etc. But
> the docs for the large scale say that I if I use the
> Aeq and beq entries, I can't pass bounds. So how do
> I limit my xs and slacks to be >=0?
>
> Also, the large-scale docs imply that I cannot have more
> constraints than variables, which means that if every
> x has an absolute upper bound (i.e. x1 <= 40), that
> blows all my rows, and I don't have enough left to do
> the linear combinations.
>
> It seems like I must be mis-understanding something about
> quadprog, because it seems like my problem is perfect
> for a structured approach (I can compute Hx quickly, etc,
> etc).
>
> If I want to stick with MATLAB (and not NAG, or TOMLAB),
> am I reduced to using fmincon, which seems like overkill,
> even though it does have the advantage that I can pass
> in arbitrary numbers of constraints, and gradients and
> such, since I know all that information?

A couple of questions,

(1) Are all the q_i>0? If so, you can forget about your Hessian. You can make a change of variables y_i= sqrt(q_i)*x_i and then the problem in the variables y_i has a Hessian which is the identity matrix.

Effectively, this means the problem reduces to one of finding the minimum Euclidean distance of a point to a polyhedral set. I think there are a gazillion papers out there on how to do that.


(2) How many equality constraints do you have? If there aren't too many, it looks like the dual quadratic program may be fairly easy to handle.

>
> OK, here's a re-formulation of a question I asked
> earlier
> today:
>
> What's the best way to solve this problem:
>
> Minimize: c1 x1 + q1*x1*x1 + c2 x2 + q2*x2*x2 . . .
>
> (I have about 3,000 x variables)
>
> Subject to:
> many constraints like
>
> x1 <= 40;
> x1 + x2 = 7;
>
> all x >=0;
>
> Now, I know a few things about this problem:
>
> 1) It's quadratic.
> 2) The Hessian is sparse, and well structured (only
> entries
> on the diagonal
> 3) all variables are >= 0.
>
>
> I'd like to use quadprog, but it seems like that's
> not
> feasible, as if I use the problem as stated, it will
> use
> the medium scale, which uses a dense Hessian, which
> will
> kill performance.
>
> If I want to use the large-scale, I can re-write my
> constraints:
>
> x1 <= 40; becomes x1 + slack1 = 40, etc, etc. But
> the docs for the large scale say that I if I use the
> Aeq and beq entries, I can't pass bounds. So how do
> I limit my xs and slacks to be >=0?
>
> Also, the large-scale docs imply that I cannot have
> more
> constraints than variables, which means that if every
> x has an absolute upper bound (i.e. x1 <= 40), that
> blows all my rows, and I don't have enough left to do
>
> the linear combinations.
>
> It seems like I must be mis-understanding something
> about
> quadprog, because it seems like my problem is perfect
> for a structured approach (I can compute Hx quickly,
> etc,
> etc).
>
> If I want to stick with MATLAB (and not NAG, or
> TOMLAB),
> am I reduced to using fmincon, which seems like
> overkill,
> even though it does have the advantage that I can
> pass
> in arbitrary numbers of constraints, and gradients
> and
> such, since I know all that information?
>
>
>
>
> Thanks for any clues,
>
>
> Eric


The following link might be interesting for you:

http://plato.asu.edu/sub/nlores.html

Here a list of codes for the solution of quadratic
programming problems is given.
Especially notice the link to the MATLAB code called MINQ.

Best wishes
Torsten.

Torsten Hennig <Torsten.Hennig@umsicht.fhg.de> wrote in
news:9303149.1229327097884.JavaMail.jakarta@nitrogen.mathforum.org:

>
>
> The following link might be interesting for you:
>
> http://plato.asu.edu/sub/nlores.html
>
> Here a list of codes for the solution of quadratic
> programming problems is given.
> Especially notice the link to the MATLAB code called MINQ.
>
> Best wishes
> Torsten.
>


Hi Torsten... thanks for the link, I'll be checking it
over carefully to see if I can find something useful.

MINQ doesn't seem like it will work for me, since it only
allows bounds constraints. I have inequalities.

I'm still confused by a minor point (I am not, as should
be obvious by now, a mathmetician by trade).

How is it even possible to convert inequalities to equalities,
unless you know that all variables are implicitly >= 0?

It seems to me that the transform of

x1 + x2 <= 40 to x1 + x2 + __Slack1 = 40 only works
if you know __Slack1 >= 0. And that seems to me to mean that
either (a) the solver must implicitly force variables to >=0
or (b) it must allow bounds in addition to equalities.

So it seems that if I have inequalities, I can never use
the large-scale quadprog, because I can't force them to
equalities, because I can't pass bounds.

Is this really true, or am I just missing something?

> Torsten Hennig <Torsten.Hennig@umsicht.fhg.de> wrote
> in
> news:9303149.1229327097884.JavaMail.jakarta@nitrogen.m
> athforum.org:
>
> >
> >
> > The following link might be interesting for you:
> >
> > http://plato.asu.edu/sub/nlores.html
> >
> > Here a list of codes for the solution of quadratic
> > programming problems is given.
> > Especially notice the link to the MATLAB code
> called MINQ.
> >
> > Best wishes
> > Torsten.
> >
>
>
> Hi Torsten... thanks for the link, I'll be checking
> it
> over carefully to see if I can find something useful.
>
> MINQ doesn't seem like it will work for me, since it
> only
> allows bounds constraints. I have inequalities.
>
> I'm still confused by a minor point (I am not, as
> should
> be obvious by now, a mathmetician by trade).
>
> How is it even possible to convert inequalities to
> equalities,
> unless you know that all variables are implicitly >=
> 0?
>
> It seems to me that the transform of
>
> x1 + x2 <= 40 to x1 + x2 + __Slack1 = 40 only
> works
> if you know __Slack1 >= 0. And that seems to me to
> mean that
> either (a) the solver must implicitly force variables
> to >=0
> or (b) it must allow bounds in addition to
> equalities.
>
> So it seems that if I have inequalities, I can never
> use
> the large-scale quadprog, because I can't force them
> to
> equalities, because I can't pass bounds.
>
> Is this really true, or am I just missing something?
>
>
>

As far as I can tell, you are right.
Maybe the MATLAB program MINQDEF is an option for you
(follow the link to MINQ).

Best wishes
Torsten.

Eric J. Holtman wrote:
> OK, here's a re-formulation of a question I asked earlier
> today:
>
> What's the best way to solve this problem:
>
> Minimize: c1 x1 + q1*x1*x1 + c2 x2 + q2*x2*x2 . . .
>
> (I have about 3,000 x variables)
>
> Subject to:
> many constraints like
>
> x1 <= 40;
> x1 + x2 = 7;
>
> all x >=0;
>
> Now, I know a few things about this problem:
>
> 1) It's quadratic.
> 2) The Hessian is sparse, and well structured (only entries
> on the diagonal
> 3) all variables are >= 0.
>
>
> I'd like to use quadprog, but it seems like that's not
> feasible, as if I use the problem as stated, it will use
> the medium scale, which uses a dense Hessian, which will
> kill performance.
>
> If I want to use the large-scale, I can re-write my
> constraints:
>
> x1 <= 40; becomes x1 + slack1 = 40, etc, etc. But
> the docs for the large scale say that I if I use the
> Aeq and beq entries, I can't pass bounds. So how do
> I limit my xs and slacks to be >=0?
>
> Also, the large-scale docs imply that I cannot have more
> constraints than variables, which means that if every
> x has an absolute upper bound (i.e. x1 <= 40), that
> blows all my rows, and I don't have enough left to do
> the linear combinations.
>
> It seems like I must be mis-understanding something about
> quadprog, because it seems like my problem is perfect
> for a structured approach (I can compute Hx quickly, etc,
> etc).
>
> If I want to stick with MATLAB (and not NAG, or TOMLAB),
> am I reduced to using fmincon, which seems like overkill,
> even though it does have the advantage that I can pass
> in arbitrary numbers of constraints, and gradients and
> such, since I know all that information?
>
>
>
>
> Thanks for any clues,
>
>
> Eric

I think you'd be well-served by the interior-point algorithm in fmincon.
It handles large, sparse problems quite well. Yes, it's too bad that
quadprog's large-scale algorithm isn't suitable, but I don't see why you
say that fmincon is overkill, it is a well-adapted tool for solving such
problems.

Alan Weiss
MATLAB mathematical toolbox documentation