[R] constraint optimization: solving large scale general nonlinear problems

Ravi Varadhan rvaradhan at jhmi.edu
Sun Mar 29 19:42:16 CEST 2009


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>


>  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:
>  
>  > 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>
>  > 
>  > 
>  > > The number of variables is larger that the number of functions
>  > > constraints. You are right I can rewrite my problem like this
>  > >  
>  > >  max f =h1(x11;x12;..;x1n;Y,b)+ h2(x21,x22, ... x2m;Y,b)
>  > >   x,b
>  > >  
>  > >  I know  Y  and  for  given values of  b  I can compute {x11,
>  > > x1n} as
>  > >  one  system of equations
>  > >  and {x21,x22  and x2m} as another system of equations.   The x are
>  > > functions of  Y and b.
>  > >  
>  > >  I can solve these systems and after plug x(Y,b) in  f(.)  and
>  > > find optimal b, but this will introduce discontinuity  and I cannot
>  > > find the optimal solution. I tried like this by using Rgenoud and
>  > > SANN  but both algorithms did not converge after 1 week!!!!!
>  > >  In my case the number of h functions are over 30.
>  > >  
>  > >  Florin
>  > >  
>  > >  
>  > >  On Fri, Mar 27, 2009 at 8:19 PM, Ravi Varadhan
>  > > <rvaradhan at jhmi.edu> wrote: 
>  > >  > 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>
>  > >  >
>  > >  >
>  > >  > > 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>
>  > >  > >
>  > >  > >
>  > >  > >  > 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 ( for large optimization problems.
>  > >  > >  >
>  > >  > >  >  It will be great if you can suggest me some alternatives
>  > >  > >  > solutions.
>  > >  > >  >
>  > >  > >  >
>  > >  > >  >  Thanks in advance,
>  > >  > >  >  Florin
>  > >  > >  >
>  > >  > >  >
>  > >  > >  >
>  > >  > >  >  --
>  > >  > >  >           Florin G. Maican
>  > >  > >  >  ==================================
>  > >  > >  >
>  > >  > >  >  Ph.D. candidate,
>  > >  > >  >  Department of Economics,
>  > >  > >  >  School of Business, Economics and Law,
>  > >  > >  >  Gothenburg University, Sweden
>  > >  > >  >  -----------------------------------
>  > >  > >  >      P.O. Box 640 SE-405 30,
>  > >  > >  >      Gothenburg, Sweden
>  > >  > >  >
>  > >  > >  >   Mobil:  +46 76 235 3039
>  > >  > >  >   Phone:  +46 31 786 4866
>  > >  > >  >   Fax:    +46 31 786 4154
>  > >  > >  >   Home Page:
>  > >  > >  >   E-mail: florin.maican at handels.gu.se
>  > >  > >  >  ------------------------------------
>  > >  > >  >   "Not everything that counts can be
>  > >  > >  >   counted, and not everything that can be
>  > >  > >  >   counted counts."
>  > >  > >  >                           --- Einstein ---
>  > >  > >  >
>  > >  > >  >  ______________________________________________
>  > >  > >  >  R-help at r-project.org mailing list
>  > >  > >  >
>  > >  > >  >  PLEASE do read the posting guide
>  > >  > >  >  and provide commented, minimal, self-contained,
>  > >  > >  > reproducible 
>  > > code.
>  > >  > >
>  > >  > >  ______________________________________________
>  > >  > >  R-help at r-project.org mailing list
>  > >  > >
>  > >  > >  PLEASE do read the posting guide
>  > >  > >  and provide commented, minimal, self-contained, reproducible
>  > >  > > code.
>  > >  >
>  > >  >
>  > >  
>  > >  
>  > >  -- 
>  > >  --
>  > >         Florin G. Maican
>  > >  ==================================
>  > >  
>  > >  Ph.D. candidate,
>  > >  Department of Economics,
>  > >  School of Business, Economics and Law,
>  > >  Gothenburg University, Sweden
>  > >  -----------------------------------
>  > >    P.O. Box 640 SE-405 30,
>  > >    Gothenburg, Sweden
>  > >  
>  > >  Mobil:  +46 76 235 3039
>  > >  Phone:  +46 31 786 4866
>  > >  Fax:    +46 31 786 4154
>  > >  Home Page: 
>  > >  E-mail: florin.maican at handels.gu.se
>  > >  ------------------------------------
>  > >  "Not everything that counts can be
>  > >  counted, and not everything that can be
>  > >  counted counts."
>  > >                         --- Einstein --- 
>  > 
>  
>  
>  -- 
>           Florin G. Maican            
>  ==================================
>  
>  Ph.D. candidate,                    
>  Department of Economics,
>  School of Business, Economics and Law,             
>  Gothenburg University, Sweden       
>  -----------------------------------
>      P.O. Box 640 SE-405 30,         
>      Gothenburg, Sweden              
>  
>   Mobil:  +46 76 235 3039             
>   Phone:  +46 31 786 4866             
>   Fax:    +46 31 786 4154              
>   Home Page: 
>   E-mail: florin.maican at handels.gu.se 
>  ------------------------------------
>   "Not everything that counts can be 
>   counted, and not everything that can be 
>   counted counts."
>                           --- Einstein ---




More information about the R-help mailing list