# [R] Advice wanted on using optim with both continuous and discrete par arguments...

Mon Mar 1 20:32:27 CET 2010

I know that Matlab can solve this problem, but I didn't mention it in my previous email since OP had asked for "native to R" solutions.

Ravi.
____________________________________________________________________

Assistant Professor,
Division of Geriatric Medicine and Gerontology
School of Medicine
Johns Hopkins University

Ph. (410) 502-2619

----- Original Message -----
Date: Monday, March 1, 2010 2:27 pm
Subject: Re: [R] Advice wanted on using optim with both continuous and discrete par arguments...
To: Uwe Ligges <ligges at statistik.tu-dortmund.de>
Cc: "r-help at r-project.org" <r-help at r-project.org>, Jeffrey Racine <racinej at mcmaster.ca>

> Hi Uwe & Jeff,
>
>  It seems to me that Jeff's problem falls under the class of
> "mixed-integer nonlinear programming" (MINLP) problem.  I would
> classify this as a "damn tough optimization problem" (DTOP!).  I am
> not sure if there is any R package that can handle this or there is
> any R link to a commercial package that can handle this (e.g. Rcplex).
> (mixed-integer linear and quadratic programming).
>
>  Being totally ignorant of the state-of-art methods for MINLP, I would
> like to suggest a "novel" approach for solving this:
>
>  Let f(X,Y) be the objective function where X and Y be the continuous
> and categorical variables.  You already have constraints g(X) on X.
> Now, let us treat Y as continuous.  Let us define some artificial
> constraints on Y.  For example, if we have only one variable y, let us
> define a constraint function that penalizes y as it gets away from
> integer values I = {0, 1, ..., K}, call this h(y; I, \sigma).  This
> function is defined such that it is zero on the integer set I, but
> increases monotonically as a function of the distance away from the
> integer points.  The parameter \sigma is like a scaling parameter.  It
> should be relatively easy to come up with a smooth penalty function
> (may be some kind of a K-sum of reciprocal of Gaussian densities).
> You can then solve the resulting nonlinear programming problem for a
> sequence of \sigma values starting with a large dispersion and then
> decreasing it towards zero.  You could use extrapolation to
> extrapolate to the limit as \sigma goes
>  to zero.  Of course, you will then round-off the solution at the end.
>  Does this make sense?
>
>  Ravi.
>
>  ____________________________________________________________________
>
>  Assistant Professor,
>  Division of Geriatric Medicine and Gerontology
>  School of Medicine
>  Johns Hopkins University
>
>  Ph. (410) 502-2619
>
>
>  ----- Original Message -----
>  From: Uwe Ligges <ligges at statistik.tu-dortmund.de>
>  Date: Monday, March 1, 2010 12:59 pm
>  Subject: Re: [R] Advice wanted on using optim with both continuous
> and discrete par arguments...
>  To: Jeffrey Racine <racinej at mcmaster.ca>
>  Cc: "r-help at r-project.org" <r-help at r-project.org>
>
>
>  >
>  >  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:
>  >
>  >
>  >  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
>  >  >>
>  >  >>
>  >  >> 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
>  >  >>
>  >  >>
>  >  >>
>  >  >>>
>  >  >>> -- 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:
>  >  >>> 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
>  >  >>>
>  >  >>> 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:
>  >  > 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
>  >
`