On Sat, 21 Dec 2002, Shuangge Ma wrote:
> Dear Sir/Madam:
> this is shuangge Ma, graduate student in UW-Madison statistics department.
> I have a computational question.
> I have a function f(x,y). I want to find the y(x) that maximize f(x,y)
> under the constraint y(x) is a non-decreasing step function.
> Is there any R package or algorithm I can use for this purpose?
> thanks a lot for your time and help,
>
Often for a problem like this a finite set of possible locations for the
steps are known (for a not-necessarily-unique solution) -- eg the observed
values of x. In that case the answer can be parametrised by the step
heights at each of these x values, with the constraint that these are
non-negative. The L-BFGS-B method of optim() will probably work.
If you don't know where the steps are, it's likely to be much harder.
One important special case that's worth mentioning is the isotonic
regression problem. If you have data (x_i,y_i) and are trying to fit an
increasing function by least squares or maximum likelihood the (or at
least a) solution is usually the isotonic regression, given by the
Pool-Adjacent-Violators Algorithm.
-thomas