Re: [R] Can R solve this optimization problem?

From: Paul Smith <phhs80_at_gmail.com>
Date: Tue, 8 Jan 2008 01:09:51 +0000

Thanks again, Gabor. Apparently, something is missing in your approach, as I tried to apply it to the original problem (without sin) and the result seems not being correct::

f <- function(z) {
  a <- sum(-(999:1)*z)
  return(a)
}

result <- optim(rep(0,999), f,
NULL,lower=rep(-1/1000,999),upper=rep(1/1000,999),method="L-BFGS-B") b <- result$par

x <- 0

for (i in 1:999) {
  x[i+1] <- b[i] + x[i]
}

The vector x contains the solution, but it does not correspond to the analytical solution. The analytical solution is

x(t) = t, if t <= 1/2 and

x(t) = 1 - t, if t >= 1/2.

Am I missing something?

Paul

On Jan 7, 2008 5:00 PM, Gabor Grothendieck <ggrothendieck_at_gmail.com> wrote:
> Just looking at this again what I meant was that unless you can linearize it
> you can't use linear programming. You still could use general nonlinear
> optimization subject to constraints.
>
> Define new variables z[i] = x[i] - x[i-1]
>
> Then x[i] = z[0] + ... + z[i]
>
> so maximize (we dropped the first and last
> terms since they are constant and f corresonds
> to sin in your example):
>
> f(z[1]) + f(z[1]+z[2]) + ... + f(z[1] + ... + z[n-1])
>
> subject to
>
> -1/n <= z[1] <= 1/n
> -1/n <= z[2] <= 1/n
> ...
> -1/n <= z[n-1] <= 1/n
>
> using optim.
>
>
> On Jan 6, 2008 9:22 PM, Gabor Grothendieck <ggrothendieck_at_gmail.com> wrote:
> >
> > On Jan 6, 2008 8:43 PM, Paul Smith <phhs80_at_gmail.com> wrote:
> > >
> > > On Jan 7, 2008 1:32 AM, Gabor Grothendieck <ggrothendieck_at_gmail.com> wrote:
> > > > This can be discretized to a linear programming problem
> > > > so you can solve it with the lpSolve package. Suppose
> > > > we have x0, x1, x2, ..., xn. Our objective (up to a
> > > > multiple which does not matter) is:
> > > >
> > > > Maximize: x1 + ... + xn
> > > >
> > > > which is subject to the constraints:
> > > >
> > > > -1/n <= x1 - x0 <= 1/n
> > > > -1/n <= x2 - x1 <= 1/n
> > > > ...
> > > > -1/n <= xn - x[n-1] <= 1/n
> > > > and
> > > > x0 = xn = 0
> > > >
> > > >
> > > > On Jan 6, 2008 7:05 PM, Paul Smith <phhs80_at_gmail.com> wrote:
> > > > > Dear All,
> > > > >
> > > > > I am trying to solve the following maximization problem with R:
> > > > >
> > > > > find x(t) (continuous) that maximizes the
> > > > >
> > > > > integral of x(t) with t from 0 to 1,
> > > > >
> > > > > subject to the constraints
> > > > >
> > > > > dx/dt = u,
> > > > >
> > > > > |u| <= 1,
> > > > >
> > > > > x(0) = x(1) = 0.
> > > > >
> > > > > The analytical solution can be obtained easily, but I am trying to
> > > > > understand whether R is able to solve numerically problems like this
> > > > > one. I have tried to find an approximate solution through
> > > > > discretization of the objective function but with no success so far.
> > >
> > > Thats is clever, Gabor! But suppose that the objective function is
> > >
> > > integral of sin( x( t ) ) with t from 0 to 1
> > >
> > > and consider the same constraints. Can your method be adapted to get
> > > the solution?
> >
> > If a linear approx is sufficient then yes; otherwise, no. For
> > example, if x can
> > be constrained to be small then its roughly true that sin(x) = x and you are
> > back to the original problem.
> >
>



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. Received on Tue 08 Jan 2008 - 01:16:06 GMT

Archive maintained by Robert King, hosted by the discipline of statistics at the University of Newcastle, Australia.
Archive generated by hypermail 2.2.0, at Tue 08 Jan 2008 - 03:30:05 GMT.

Mailing list information is available at https://stat.ethz.ch/mailman/listinfo/r-help. Please read the posting guide before posting to the list.

list of date sections of archive