[R] Can R solve this optimization problem?
Gabor Grothendieck
ggrothendieck at gmail.com
Mon Jan 7 18:00:12 CET 2008
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.
>
More information about the R-help
mailing list