home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / comp / ai / genetic / 195 < prev    next >
Encoding:
Internet Message Format  |  1993-01-28  |  1.7 KB
  1. Path: sparky!uunet!ukma!gatech!pitt.edu!genetic
  2. From: genetic+@pitt.edu (David M. Tate)
  3. Newsgroups: comp.ai.genetic
  4. Subject: Re: Penalty functions
  5. Keywords: Penalty Optimization Minimization
  6. Message-ID: <2716@blue.cis.pitt.edu>
  7. Date: 28 Jan 93 16:23:13 GMT
  8. References: <C1F8H9.8nw@world.std.com> <1853@airgun.wg.waii.com>
  9. Sender: news+@pitt.edu
  10. Organization: Department of Industrial Engineering
  11. Lines: 24
  12.  
  13. hart@de01.denver.waii.com said:
  14. >
  15. >Multiplier methods, for constrained optimization problems, generally
  16. >exceed the performance of penalty function methods.  The reference:
  17. >R.A. Tapia, "Diagonalized Multiplier Methods and Quasi-Newton Methods for
  18. >Constrainded Optimization", Journal of Optimization Theory and Applications,
  19. >Vol. 22., No.2, June 1977, p. 135-194., is where I got started with these
  20. >methods.  Two papers on Penalty Function methods are in the reference section
  21. >of this paper.  They should point you to some examples of penalty functions.
  22.  
  23.  
  24. Multiplier methods are fine for *continuous* optimization, but not readily
  25. applicable for many combinatorial problems, unless a convenient continuous
  26. relaxation exists.  Multiplier methods also require that you have an explicit
  27. representation of the constraint set in a particular form.  For example, in
  28. a Travelling Salesman problem the logically simply constraint "Each tour must
  29. pass through each city exactly once" translates into an exponential number of
  30. linear inequalities in the linear/integer programming formulation.
  31.  
  32. -- 
  33.        David Tate        |"Something there is that doesn't love a wall,
  34.  dtate@unix.cis.pitt.edu | That sends the screaming liner over it 
  35.  Prof. of Story Problems | And spills the bleacher-dwellers from their seats."
  36.  Member ORSA, TIMS, SABR |      "Fenway Wall", Robert Frost          
  37.