Skip to content

constraint optimization: solving large scale general nonlinear problems

7 messages · Ravi Varadhan, Florin Maican

Florin Maican
# 
Hi

I need advice regarding constraint optimization with large number of
variables. 

I need to solve the following problem

   max      f(x1,...,xn)
  x1,..xn
  
    x1=g1(x1,...,xn)
    .
    .
    xn=gn(x1,...,xn) 

I am using Rdonlp2  package which works well until 40 variables in my
case. I need to solve this problem with over 300 variables. In this case
Rdonlp2 is very  very slowly. I know that in Matlab exists  Knitro
(http://www.ziena.com/knitro.htm.) for large optimization problems.

It will be great if you can suggest me some alternatives solutions.


Thanks in advance,
Florin
Ravi Varadhan
# 
Can you tell us more about your obj function, f, and the equality constraints g_k?  

Do you really have as many equality constraints as the number of variables?  Are these all non-linear?  Can't you find the roots of this system of equations?  If yes, you could find all the roots (with multiple starts or some other search technique) and choose the one that maximizes f(x).

Ravi.
____________________________________________________________________

Ravi Varadhan, Ph.D.
Assistant Professor,
Division of Geriatric Medicine and Gerontology
School of Medicine
Johns Hopkins University

Ph. (410) 502-2619
email: rvaradhan at jhmi.edu


----- Original Message -----
From: Florin Maican <florin.maican at handels.gu.se>
Date: Friday, March 27, 2009 2:01 pm
Subject: [R] constraint optimization: solving large scale general nonlinear problems
To: r-help <r-help at r-project.org>
Ravi Varadhan
# 
Hi,

Looking at your problem, it seems like you can simply transform it to an unconstrained problem:

Maximize h(x1, x2, ..., xn)

where h(x1, x2, ..., xn) = f(g1(x), g2(x), ..., gn(x)).

Am I missing something or haven't you provided all the information?

Ravi.

____________________________________________________________________

Ravi Varadhan, Ph.D.
Assistant Professor,
Division of Geriatric Medicine and Gerontology
School of Medicine
Johns Hopkins University

Ph. (410) 502-2619
email: rvaradhan at jhmi.edu


----- Original Message -----
From: Ravi Varadhan <rvaradhan at jhmi.edu>
Date: Friday, March 27, 2009 2:42 pm
Subject: Re: [R] constraint optimization: solving large scale general nonlinear problems
To: Florin Maican <florin.maican at handels.gu.se>
Cc: r-help <r-help at r-project.org>
Ravi Varadhan
# 
Florin,

How do you obtain x from (Y, b), i.e. x = g(Y,b)? 

I don't follow how a "discontinuity" is introduced, when you plug in x(Y, b) into f.  If f(.) is smooth and all the g(.) are smooth, then the composition f(g(.)) will also be smooth.  If this is not the case, what type of discontinuity do you have (e.g. f(.) is continuous, but its gradient is not, or f(.) itself has jump discontinuites)? 

Ravi.

____________________________________________________________________

Ravi Varadhan, Ph.D.
Assistant Professor,
Division of Geriatric Medicine and Gerontology
School of Medicine
Johns Hopkins University

Ph. (410) 502-2619
email: rvaradhan at jhmi.edu


----- Original Message -----
From: Florin Maican <florin.maican at handels.gu.se>
Date: Friday, March 27, 2009 3:48 pm
Subject: Re: [R] constraint optimization: solving large scale general	nonlinear problems
To: Ravi Varadhan <rvaradhan at jhmi.edu>
Cc: r-help <r-help at r-project.org>
1 day later
Florin Maican
# 
Ravi, 

I solve for the fixed-point  x=g(x;b,Y). The variable Y is given - i
can omitted here to not introduce confusion. 

   max_{x,b}  f(x,b)
     
    constr    x=g(x;b)

Let b1 the  initial values for b.  Having b1 I
can compute the solution x1 of the system x=g(x,b1) - x1 fixed-point.
So,

   b2= max_{b} f(x1,b)=f( g(x1,b),b), since x1=g(x1,b)

I repeat this until || b_{n}-b_{n-1}||< eps   then I have  b optim.

Why I introduce discontinuity in f?
It is hard in this way to control the error from solving the
fixed-point. In addition, the x=g(x,b) may have multiple solutions.
For those reasons, I  want to solve a constraint optimization
problem. 

Best regards,
Florin


On Fri, 27 Mar 2009 18:03:02 -0400
Ravi Varadhan <rvaradhan at jhmi.edu> wrote:

            

      
      
      
    

        

      
      
    

        

  
    

      
      
    

  


  


      

    

    

      
      

        


  

        

      Ravi Varadhan
    

    

      
      #
    

  


  

      
You don't need to find the fixed points.  This is a kind of "profiling" approach.  As I had said before, a better approach would be to jointly maximize over x and b:

max_{x, b}  h(x, b) = f(g(x,b), b).

You can use any unconstrained optimization tools (assuming there are no box-constraints on x and/or b) including optim() or spg() in the "BB" package.

Ravi.

____________________________________________________________________

Ravi Varadhan, Ph.D.
Assistant Professor,
Division of Geriatric Medicine and Gerontology
School of Medicine
Johns Hopkins University

Ph. (410) 502-2619
email: rvaradhan at jhmi.edu


----- Original Message -----
From: Florin Maican <florin.maican at handels.gu.se>
Date: Sunday, March 29, 2009 12:02 pm
Subject: Re: [R] constraint optimization: solving large scale general nonlinear problems
To: Ravi Varadhan <rvaradhan at jhmi.edu>
Cc: r-help <r-help at r-project.org>