Path: news.mathworks.com!not-for-mail
From: <HIDDEN>
Newsgroups: comp.soft-sys.matlab
Subject: Re: Which to use (quadprog or fmincon)?
Date: Fri, 12 Dec 2008 21:10:18 +0000 (UTC)
Organization: Xoran Technologies
Lines: 67
Message-ID: <ghujvq$bh1$1@fred.mathworks.com>
References: <Xns9B72911B0AAD8ejhericholtmamcom@216.168.3.30>
Reply-To: <HIDDEN>
NNTP-Posting-Host: webapp-02-blr.mathworks.com
Content-Type: text/plain; charset="ISO-8859-1"
Content-Transfer-Encoding: 8bit
X-Trace: fred.mathworks.com 1229116218 11809 172.30.248.37 (12 Dec 2008 21:10:18 GMT)
X-Complaints-To: news@mathworks.com
NNTP-Posting-Date: Fri, 12 Dec 2008 21:10:18 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 1440443
Xref: news.mathworks.com comp.soft-sys.matlab:506642


"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.