Optimization inconsistencies

classic Classic list List threaded Threaded
7 messages Options
Reply | Threaded
Open this post in threaded view
|

Optimization inconsistencies

Nathan Stephens
I have a very simple maximization problem where I'm solving for the vector
x:

objective function:
w'x = value to maximize

box constraints (for all elements of w):
low < x < high

equality constraint:
sum(x) = 1

But I get inconsistent results depending on what starting values I. I've
tried various packages but none seem to bee the very solver in Excel. Any
recommendations on what packages or functions I should try?

--Nathan

        [[alternative HTML version deleted]]

______________________________________________
[hidden email] 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.
Reply | Threaded
Open this post in threaded view
|

Re: Optimization inconsistencies

Peter Dalgaard-2

On May 18, 2012, at 00:14 , Nathan Stephens wrote:

> I have a very simple maximization problem where I'm solving for the vector
> x:
>
> objective function:
> w'x = value to maximize
>
> box constraints (for all elements of w):
> low < x < high
>
> equality constraint:
> sum(x) = 1
>
> But I get inconsistent results depending on what starting values I. I've
> tried various packages but none seem to bee the very solver in Excel. Any
> recommendations on what packages or functions I should try?

Sounds like a linear programming problem, so perhaps one of the packages that are specialized for that? lpSolve looks like it should do it.

(As a general matter: There's nothing simple about constrained maximization problems, and generic optimizers aren't really geared towards dealing with large sets of constraints.)

>
> --Nathan
>
> [[alternative HTML version deleted]]
>
> ______________________________________________
> [hidden email] 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.

--
Peter Dalgaard, Professor,
Center for Statistics, Copenhagen Business School
Solbjerg Plads 3, 2000 Frederiksberg, Denmark
Phone: (+45)38153501
Email: [hidden email]  Priv: [hidden email]

______________________________________________
[hidden email] 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.
Reply | Threaded
Open this post in threaded view
|

Re: Optimization inconsistencies

Hans W Borchers
peter dalgaard <pdalgd <at> gmail.com> writes:

>
> On May 18, 2012, at 00:14 , Nathan Stephens wrote:
>
> > I have a very simple maximization problem where I'm solving for the vector
> > x:
> >
> > objective function:
> > w'x = value to maximize
> >
> > box constraints (for all elements of w):
> > low < x < high
> >
> > equality constraint:
> > sum(x) = 1
> >
> > But I get inconsistent results depending on what starting values I. I've
> > tried various packages but none seem to bee the very solver in Excel. Any
> > recommendations on what packages or functions I should try?

Use the equality constraint to reduce the dimension of the problem by one.
Then formulate the inequality constraints and apply, e.g., constrOptim().
You can immediately write down and use the gradient, so method "L-BFGS-B" is
appropriate.

Because the problem is linear, there is only one maximum and no dependency
on starting values.

If you had supplied some data and code (which packages did you try, and how?),
a more concrete answer would have been possible. My own test example worked
out of the box.

Hans Werner


> Sounds like a linear programming problem, so perhaps one of the packages
> that are specialized for that? lpSolve looks like it should do it.
>
> (As a general matter: There's nothing simple about constrained maximization
> problems, and generic optimizers aren't really geared towards dealing with
> large sets of constraints.)
>
> >
> > --Nathan

______________________________________________
[hidden email] 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.
Reply | Threaded
Open this post in threaded view
|

Re: Optimization inconsistencies

Marc Girondot-2
In reply to this post by Nathan Stephens
Le 18/05/12 00:14, Nathan Stephens a écrit :

> I have a very simple maximization problem where I'm solving for the vector
> x:
>
> objective function:
> w'x = value to maximize
>
> box constraints (for all elements of w):
> low<  x<  high
>
> equality constraint:
> sum(x) = 1
>
> But I get inconsistent results depending on what starting values I. I've
> tried various packages but none seem to bee the very solver in Excel. Any
> recommendations on what packages or functions I should try?
>
>
I had similar problem to solve (x were frequencies) and optimization
stops before to reach the global maximum. As [hidden email]
indicates, I fitted {x}-1 values because the last one is known by the
equality constraint.
For the vector constraints, I used w <- -Inf when x goes out of the limits.

Finally I used Bayesian mcmc to get the convergence and it works much
better.

I don't know why in this case the optim does not converge.

Hope it hepls,

Marc

--
__________________________________________________________
Marc Girondot, Pr

Laboratoire Ecologie, Systématique et Evolution
Equipe de Conservation des Populations et des Communautés
CNRS, AgroParisTech et Université Paris-Sud 11 , UMR 8079
Bâtiment 362
91405 Orsay Cedex, France

Tel:  33 1 (0)1.69.15.72.30   Fax: 33 1 (0)1.69.15.73.53
e-mail: [hidden email]
Web: http://www.ese.u-psud.fr/epc/conservation/Marc.html
Skype: girondot

______________________________________________
[hidden email] 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.
Reply | Threaded
Open this post in threaded view
|

Re: Optimization inconsistencies

Peter Dalgaard-2
In reply to this post by Hans W Borchers

On May 18, 2012, at 09:10 , Hans W Borchers wrote:

> peter dalgaard <pdalgd <at> gmail.com> writes:
>>
>> On May 18, 2012, at 00:14 , Nathan Stephens wrote:
>>
>>> I have a very simple maximization problem where I'm solving for the vector
>>> x:
>>>
>>> objective function:
>>> w'x = value to maximize
>>>
>>> box constraints (for all elements of w):
>>> low < x < high
>>>
>>> equality constraint:
>>> sum(x) = 1
>>>
>>> But I get inconsistent results depending on what starting values I. I've
>>> tried various packages but none seem to bee the very solver in Excel. Any
>>> recommendations on what packages or functions I should try?
>
> Use the equality constraint to reduce the dimension of the problem by one.
> Then formulate the inequality constraints and apply, e.g., constrOptim().
> You can immediately write down and use the gradient, so method "L-BFGS-B" is
> appropriate.

I considered making a similar remark, then realized that lpSolve actually allows equality constraints, so why not just use the tool that is designed for the job?


> Because the problem is linear, there is only one maximum and no dependency
> on starting values.

However, with a linear objective function, the Hessian is 0 and the maximum is attained at a corner point, which is likely to confuse algorithms that expect a locally quadratic function.

> If you had supplied some data and code (which packages did you try, and how?),
> a more concrete answer would have been possible. My own test example worked
> out of the box.
>

Yes, also from the development perspective. We need to see more of these hard examples.


> Hans Werner
>
>
>> Sounds like a linear programming problem, so perhaps one of the packages
>> that are specialized for that? lpSolve looks like it should do it.
>>
>> (As a general matter: There's nothing simple about constrained maximization
>> problems, and generic optimizers aren't really geared towards dealing with
>> large sets of constraints.)
>>
>>>
>>> --Nathan
>
> ______________________________________________
> [hidden email] 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.

--
Peter Dalgaard, Professor,
Center for Statistics, Copenhagen Business School
Solbjerg Plads 3, 2000 Frederiksberg, Denmark
Phone: (+45)38153501
Email: [hidden email]  Priv: [hidden email]

______________________________________________
[hidden email] 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.
Reply | Threaded
Open this post in threaded view
|

Re: Optimization inconsistencies

Hans W Borchers
In reply to this post by Marc Girondot-2
Marc Girondot <marc_grt <at> yahoo.fr> writes:
>
> Le 18/05/12 00:14, Nathan Stephens a écrit :
> > I have a very simple maximization problem where I'm solving for the vector
> > But I get inconsistent results depending on what starting values I. I've
> > tried various packages but none seem to bee the very solver in Excel. Any
> > recommendations on what packages or functions I should try?
> > [...]

> I had similar problem to solve (x were frequencies) and optimization
> stops before to reach the global maximum. As [...] indicate[d], I fitted
>  {x}-1 values because the last one is known by the equality constraint.
>
> For the vector constraints, I used w <- -Inf when x goes out of the limits.

Same as before:
Would you *please* post data and code, as the posting guide requests!

The variable that is left out still has some (linear) inequalities to fullfil.
I didn't understand how you worked that out with optim() as it only allows to
include box constraints.

Hans Werner

> Finally I used Bayesian mcmc to get the convergence and it works much
> better.
>
> I don't know why in this case the optim does not converge.
>
> Hope it hepls,
>
> Marc

______________________________________________
[hidden email] 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.
Reply | Threaded
Open this post in threaded view
|

Re: Optimization inconsistencies

Petr Savicky
In reply to this post by Nathan Stephens
On Thu, May 17, 2012 at 06:14:37PM -0400, Nathan Stephens wrote:

> I have a very simple maximization problem where I'm solving for the vector
> x:
>
> objective function:
> w'x = value to maximize
>
> box constraints (for all elements of w):
> low < x < high
>
> equality constraint:
> sum(x) = 1

Hi.

As Peter Dalgaard suggested, lpSolve may be used. If "low" may contain
negative values, then it is important to note that lpSolve assumes
all variables nonnegative. So, a transformation is needed, for example
x = low + y and solve for y. The following is one approach.

  library(lpSolve)
 
  n <- 8
  w <- 1:n
  low <- rep(-1, times=n)
  high <- rep(1, times=n)
 
  crit <- w
  mat <- rbind(diag(n), 1)
  rhs <- c(high - low, 1 - sum(low))
  dir <- c(rep("<=", times=n), "==")
 
  out <- lp("max", objective.in=crit, const.mat=mat, const.dir=dir, const.rhs=rhs)
  x <- low + out$solution

  round(x, digits=15)

  [1] -1 -1 -1  0  1  1  1  1

Hope this helps.

Petr Savicky.

______________________________________________
[hidden email] 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.