R help - Mar 2010 - Advice wanted on using optim with both continuous and discrete par arguments...

Dear R users,

I have a problem for which my objective function depends on both discrete and
continuous arguments.

The problem is that the number of combinations for the (multivariate) discrete
arguments can become overwhelming (when it is univariate this is not an issue)
hence search over the continuous arguments for each possible combination of the
discrete arguments may not be feasible. Guided search over the discrete and
continuous arguments would be infinitely preferable. That is, exhaustive search
over all possible combinations works perfectly, but for large problems
exhaustive search simply is not in the feasible set.

Both the discrete and continuous arguments are bounded (the discrete lie in
[0,K] and the continuous in [0,1]) and I am using L-BFGS-B with lower and upper
vectors defining these bounds.

The issue is that when I feed optim my objective function and par (whose first
`k' elements must necessarily be rounded by my objective function while the
remaining `l' arguments are continuous), the default settings naturally do
not perform well at all. Typically if the initial values for the discrete
variables are, say, par[1:3]= c(2,3,4) while those for the continuous are, say,
par[4:6] = c(.17, .35, .85), then optim finds the minimum for only the
continuous variables and dumps back the initial values for the discrete
variables. I presume that the numerical approximation to the gradients/hessian
is thrown off by the `flat spots' or step-like-nature of the objective
function with respect to the discrete variables.

I have played with ndeps, parscale etc. but nothing really works. I realize this
is a mixed combinatorial optimization/continuous optimization problem and
ideally would love pointers to any related literature or ideally an R package
that implements such a beast.

However, if anyone has attempted to use optimization routines native to R with
any success in similar settings, I would love to get your feedback.

Many thanks in advance for your advice.

-- Jeff



Professor J. S. Racine         Phone:  (905) 525 9140 x 23825
Department of Economics        FAX:    (905) 521-8232
McMaster University            e-mail: racinej at mcmaster.ca
1280 Main St. W.,Hamilton,     URL: http://www.economics.mcmaster.ca/racine/
Ontario, Canada. L8S 4M4

`The generation of random numbers is too important to be left to chance'

On 01.03.2010 16:34, Jeffrey Racine wrote:
> Dear R users,
>
> I have a problem for which my objective function depends on both discrete
and continuous arguments.
>
> The problem is that the number of combinations for the (multivariate)
discrete arguments can become overwhelming (when it is univariate this is not an
issue) hence search over the continuous arguments for each possible combination
of the discrete arguments may not be feasible. Guided search over the discrete
and continuous arguments would be infinitely preferable. That is, exhaustive
search over all possible combinations works perfectly, but for large problems
exhaustive search simply is not in the feasible set.
>
> Both the discrete and continuous arguments are bounded (the discrete lie in
[0,K] and the continuous in [0,1]) and I am using L-BFGS-B with lower and upper
vectors defining these bounds.
>
> The issue is that when I feed optim my objective function and par (whose
first `k' elements must necessarily be rounded by my objective function
while the remaining `l' arguments are continuous), the default settings
naturally do not perform well at all. Typically if the initial values for the
discrete variables are, say, par[1:3]= c(2,3,4) while those for the continuous
are, say, par[4:6] = c(.17, .35, .85), then optim finds the minimum for only the
continuous variables and dumps back the initial values for the discrete
variables. I presume that the numerical approximation to the gradients/hessian
is thrown off by the `flat spots' or step-like-nature of the objective
function with respect to the discrete variables.
>
> I have played with ndeps, parscale etc. but nothing really works. I realize
this is a mixed combinatorial optimization/continuous optimization problem and
ideally would love pointers to any related literature or ideally an R package
that implements such a beast.
>
> However, if anyone has attempted to use optimization routines native to R
with any success in similar settings, I would love to get your feedback.

If your 3 first discrete variables have a rather limited number of 
possible values (sounds like that is the case), you may want to apply 
optim() on the other variables on a complete grid of the first 3 
variables and select the best result. Even with this complete evaluation 
of the whole grid with say 20 possible values in each dimension the 
results should be there within minutes without a need for more 
specialized optimization procedures. ...

Best wishes,
Uwe Ligges


> Many thanks in advance for your advice.
>
> -- Jeff
>
>
>
> Professor J. S. Racine         Phone:  (905) 525 9140 x 23825
> Department of Economics        FAX:    (905) 521-8232
> McMaster University            e-mail: racinej at mcmaster.ca
> 1280 Main St. W.,Hamilton,     URL:
http://www.economics.mcmaster.ca/racine/
> Ontario, Canada. L8S 4M4
>
> `The generation of random numbers is too important to be left to
chance'
>
> ______________________________________________
> R-help at r-project.org mailing list
> https://stat.ethz.ch/mailman/listinfo/r-help
> PLEASE do read the posting guide
http://www.R-project.org/posting-guide.html
> and provide commented, minimal, self-contained, reproducible code.

On 01.03.2010 18:34, Jeffrey Racine wrote:
> Thanks Uwe.
>
> I appreciate your feedback.. in the paragraph in my email beginning
"The problem..."
Whoops, apologies, I was too quickly reading your message, apparently.
CCing R-help to add:

There is the Optimization Task View on CRAN:
http://cran.r-project.org/web/views/Optimization.html

See particularly the hints related to Mixed integer programming and its 
variants

Best wishes,
uwe









 > I point out that yes, I indeed do what you suggest for small 
problems, but encounter problems where this is not feasible (e.g., 10 
variables with integer ranging from 0-20 for each variable for
instance).
>
> Thanks again!
>
> -- Jeff
>
> On 2010-03-01, at 12:28 PM, Uwe Ligges wrote:
>
>>
>>
>> On 01.03.2010 16:34, Jeffrey Racine wrote:
>>> Dear R users,
>>>
>>> I have a problem for which my objective function depends on both
discrete and continuous arguments.
>>>
>>> The problem is that the number of combinations for the
(multivariate) discrete arguments can become overwhelming (when it is univariate
this is not an issue) hence search over the continuous arguments for each
possible combination of the discrete arguments may not be feasible. Guided
search over the discrete and continuous arguments would be infinitely
preferable. That is, exhaustive search over all possible combinations works
perfectly, but for large problems exhaustive search simply is not in the
feasible set.
>>>
>>> Both the discrete and continuous arguments are bounded (the
discrete lie in [0,K] and the continuous in [0,1]) and I am using L-BFGS-B with
lower and upper vectors defining these bounds.
>>>
>>> The issue is that when I feed optim my objective function and par
(whose first `k' elements must necessarily be rounded by my objective
function while the remaining `l' arguments are continuous), the default
settings naturally do not perform well at all. Typically if the initial values
for the discrete variables are, say, par[1:3]= c(2,3,4) while those for the
continuous are, say, par[4:6] = c(.17, .35, .85), then optim finds the minimum
for only the continuous variables and dumps back the initial values for the
discrete variables. I presume that the numerical approximation to the
gradients/hessian is thrown off by the `flat spots' or step-like-nature of
the objective function with respect to the discrete variables.
>>>
>>> I have played with ndeps, parscale etc. but nothing really works. I
realize this is a mixed combinatorial optimization/continuous optimization
problem and ideally would love pointers to any related literature or ideally an
R package that implements such a beast.
>>>
>>> However, if anyone has attempted to use optimization routines
native to R with any success in similar settings, I would love to get your
feedback.
>>
>>
>> If your 3 first discrete variables have a rather limited number of
possible values (sounds like that is the case), you may want to apply optim() on
the other variables on a complete grid of the first 3 variables and select the
best result. Even with this complete evaluation of the whole grid with say 20
possible values in each dimension the results should be there within minutes
without a need for more specialized optimization procedures. ...
>>
>> Best wishes,
>> Uwe Ligges
>>
>>
>>
>>> Many thanks in advance for your advice.
>>>
>>> -- Jeff
>>>
>>>
>>>
>>> Professor J. S. Racine         Phone:  (905) 525 9140 x 23825
>>> Department of Economics        FAX:    (905) 521-8232
>>> McMaster University            e-mail: racinej at mcmaster.ca
>>> 1280 Main St. W.,Hamilton,     URL:
http://www.economics.mcmaster.ca/racine/
>>> Ontario, Canada. L8S 4M4
>>>
>>> `The generation of random numbers is too important to be left to
chance'
>>>
>>> ______________________________________________
>>> R-help at r-project.org mailing list
>>> https://stat.ethz.ch/mailman/listinfo/r-help
>>> PLEASE do read the posting guide
http://www.R-project.org/posting-guide.html
>>> and provide commented, minimal, self-contained, reproducible code.
>
> Professor J. S. Racine         Phone:  (905) 525 9140 x 23825
> Department of Economics        FAX:    (905) 521-8232
> McMaster University            e-mail: racinej at mcmaster.ca
> 1280 Main St. W.,Hamilton,     URL:
http://www.economics.mcmaster.ca/racine/
> Ontario, Canada. L8S 4M4
>
> `The generation of random numbers is too important to be left to
chance'
>
>
>
>