Path: news.mathworks.com!not-for-mail
From: Alan Weiss <aweiss@mathworks.com>
Newsgroups: comp.soft-sys.matlab
Subject: Re: Which to use (quadprog or fmincon)?
Date: Tue, 16 Dec 2008 11:46:12 -0500
Organization: The MathWorks, Inc.
Lines: 72
Message-ID: <gi8m0k$r2d$1@fred.mathworks.com>
References: <Xns9B72911B0AAD8ejhericholtmamcom@216.168.3.30>
NNTP-Posting-Host: weissa.dhcp.mathworks.com
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
X-Trace: fred.mathworks.com 1229445972 27725 172.31.57.119 (16 Dec 2008 16:46:12 GMT)
X-Complaints-To: news@mathworks.com
NNTP-Posting-Date: Tue, 16 Dec 2008 16:46:12 +0000 (UTC)
User-Agent: Thunderbird 2.0.0.18 (Windows/20081105)
In-Reply-To: <Xns9B72911B0AAD8ejhericholtmamcom@216.168.3.30>
Xref: news.mathworks.com comp.soft-sys.matlab:507332


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