Skip to content

Optimization inconsistencies

7 messages · Nathan Stephens, Peter Dalgaard, Hans W Borchers +2 more

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

            

      
      
      
    

        
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.)

            

      
      
      
    

        

      
      
    

        

  
    

      
      
    

  


  


      

    

    

      
      

        


  

        

      Hans W Borchers
    

    

      
      #
    

  


  

      
peter dalgaard <pdalgd <at> gmail.com> writes:

            

      
      
      
    

        
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

            

      
      
      
    

  
  


  


      

    

    

      
      

        


  

        

      Marc Girondot
    

    

      
      #
    

  


  

      
Le 18/05/12 00:14, Nathan Stephens a ?crit :

            

      
      
      
    

        
I had similar problem to solve (x were frequencies) and optimization 
stops before to reach the global maximum. As hwborchers at googlemail.com 
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

  
    

      
      
    

  


  


      

    

    

      
      

        


  

        

      Peter Dalgaard
    

    

      
      #
    

  


  

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

        

            

      
      
      
    

        
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?

            

      
      
      
    

        
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.

            

      
      
      
    

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

            

      
      
      
    

        

      
      
    

        

  
    

      
      
    

  


  


      

    

    

      
      

        


  

        

      Hans W Borchers
    

    

      
      #
    

  


  

      
Marc Girondot <marc_grt <at> yahoo.fr> writes:

            

      
      
      
    

        
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

            

      
      
      
    

  
  


  


      

    

    

      
      

        


  

        

      Petr Savicky
    

    

      
      #
    

  


  

      
On Thu, May 17, 2012 at 06:14:37PM -0400, Nathan Stephens wrote:

            

      
      
      
    

        
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.