I've got an optimization problem that I'd love a little help with. I'm trying to model a binomial process, where the free parameters are (n_i) the number of trials (unknown), a parameter that determines success probability (p_i) when combined with other data, and the number of successes (k_i). It's actually slightly more complicated, as I have repeated/grouped measures, so I have several observations per free parameter.

I've formulated an objective function in R that looks roughly like this:

-sum(dbinom(x=successes,
            size=round(group.dummies %*% par.group),
            prob=(1-(1-par.success)^options),
            log=TRUE))

Where sucesses and options are fixed vectors, group.dummies is a fixed matrix of dummy variables, par.group is a vector of parameters, and par.success is a scalar parameter. There are about 1000 observations and 150 free parameters in my current data set. I can give reasonable bounds on the parameters; par.group are probably all between 10 and 10,000, and par.success is probably between 0.01 and 0.5.

The question is, what kind of optimizer can I/should I use to solve this? I tried a trust-region derivitive-free non-linear optimizer I found on the R optimization page (minqa), and it seems to scale on my problem well (when I was minimizing SSE instead of maximizing LL), but it doesn't deal well with parameters with radically different ranges, like I have here. I've tried rescaling, but that makes the objective function more complex, and the fact that the group parameters can be a couple of orders of magnitude different causes problems.

Are there other optimizers (available through R) that I could use that wouldn't choke on that many parameters, that don't require a derivative function (or should I think about deriving that?), and that don't need the parameters to be similarly scaled? (Or, am I drastically misunderstanding something?)

Thanks!

asked 10 Jun '11, 16:29

Harlan's gravatar image

Harlan
83116
accept rate: 0%

edited 10 Jun '11, 16:54

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
14.6k513


Separate from the question of concavity, there's apparently an R package neldermead that implements the Nelder-Mead simplex algorithm (which has nothing to do with linear programming and Dantzig's simplex algorithm, by the way). Nelder-Mead is a hill-climbing technique that requires no derivatives. I don't know if your scaling would cause it problems, but likely not. Hill-climbing methods generally don't win foot races, but I think they're fairly robust. Again, just to be explicit, if you don't have concavity, there's no guarantee how good the final answer is.

link

answered 10 Jun '11, 19:21

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
14.6k513
accept rate: 19%

The terminology confuses me a bit -- I assume that what you're calling "parameters" are actually the variables in the optimization. Have you checked whether the LL function is actually concave in the "parameters" (so that locally optimal implies globally optimal)? If not, you'll need a global solver (unless you're content with a local optimum).

link

answered 10 Jun '11, 17:03

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
14.6k513
accept rate: 19%

Yeah, I come out of a ML background, and tend to be loose with terminology. No, I haven't checked for concavity. Not totally sure how to do that. Can you suggest a reference with a walk-through of that process?

(10 Jun '11, 18:02) Harlan
1

The bit about rounding the expression for size creates a discontinuity that rules out concavity (and also probably creates headaches for any derivative-based algorithm). If you drop the rounding bit for the moment, and let "size" be non-integer, then you can try to compute the Hessian (second derivative matrix) of the log likelihood function. I think this would require using gamma functions in lieu of factorials. You need the Hessian matrix to be positive semidefinite for all values of the "parameters" within the feasible region. Good luck with the calculus.

(10 Jun '11, 19:15) Paul Rubin ♦♦
Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Tags:

×190
×46

Asked: 10 Jun '11, 16:29

Seen: 2,039 times

Last updated: 10 Jun '11, 19:21

OR-Exchange! Your site for questions, answers, and announcements about operations research.