Thread: question about stochastic optimization

  1. #1
    Registered User
    Join Date
    Apr 2010
    Posts
    79

    question about stochastic optimization

    Dear All.

    Maybe this is a little bit irrelative question for this forum but maybe someone has experience on this. I would like to minimize a function of the form (A*x-b)^2 ( A matrix x vector b vector) where x the parameters are a lot. So far I am using genetic algorithm which works but gives a lot of local minima. Do you have to suggest a stochastic method which could work better in finding global minima.

    Many thanks,
    Chris

  2. #2
    3735928559
    Join Date
    Mar 2008
    Location
    RTP
    Posts
    838

  3. #3
    Registered User
    Join Date
    Jun 2005
    Posts
    6,815
    If, by (A*x-b)^2, you mean the square of the length of Ax-b, then you might try some basic geometry/algebra. That allows you to evaluate the solution exactly, without any searching.
    Right 98% of the time, and don't care about the other 3%.

    If I seem grumpy or unhelpful in reply to you, or tell you you need to demonstrate more effort before you can expect help, it is likely you deserve it. Suck it up, Buttercup, and read this, this, and this before posting again.

  4. #4
    3735928559
    Join Date
    Mar 2008
    Location
    RTP
    Posts
    838
    he's doing a least squares problem.

  5. #5
    Registered User
    Join Date
    Jun 2005
    Posts
    6,815
    Quote Originally Posted by m37h0d View Post
    he's doing a least squares problem.
    That is my point.
    Right 98% of the time, and don't care about the other 3%.

    If I seem grumpy or unhelpful in reply to you, or tell you you need to demonstrate more effort before you can expect help, it is likely you deserve it. Suck it up, Buttercup, and read this, this, and this before posting again.

  6. #6
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Quote Originally Posted by grumpy View Post
    That is my point.
    I think you're assuming that A is square and non-singular. If A is nonsquare or singular, then there is no "analytic" answer, hence the need to do minimization. (EDIT: I suppose I should add that still in some of these situations there is still an analytic solution to the least-squares problem, although I don't believe it's all.)

    For the OP: I've never worked with genetic algorithms here, so I've not got direct advice for you, unfortunately. My hand-wavy suggestion is that, if you are often getting stuck in a "rut", I would guess that either you've got some very good local minima (is the geometry very steep around these points, making it difficult to get out?) or that something weird is going on with mutations, that aren't allowing them to get "far enough" away.
    Last edited by tabstop; 06-25-2011 at 08:09 AM.

  7. #7
    Registered User
    Join Date
    Jun 2005
    Posts
    6,815
    Look up pseudo-inverse, specifically the Moore-Penrose pseudo-inverse (which is a particular pseudo-inverse that is unique for any matrix A). Techniques to compute it include QR decomposition, singular value decomposition, etc.

    One of the most common applications of the pseudo-inverse is computing a "best" (least-squares) fit for exactly this problem.
    Right 98% of the time, and don't care about the other 3%.

    If I seem grumpy or unhelpful in reply to you, or tell you you need to demonstrate more effort before you can expect help, it is likely you deserve it. Suck it up, Buttercup, and read this, this, and this before posting again.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Optimization question
    By Noise in forum C++ Programming
    Replies: 25
    Last Post: 02-14-2009, 01:40 PM
  2. optimization question
    By ole111 in forum C Programming
    Replies: 3
    Last Post: 09-10-2005, 03:42 PM
  3. Optimization Question
    By saxman in forum C Programming
    Replies: 7
    Last Post: 06-30-2004, 10:49 PM
  4. optimization
    By krithi in forum C Programming
    Replies: 9
    Last Post: 01-19-2003, 10:52 AM
  5. question on optimization
    By ygfperson in forum C++ Programming
    Replies: 4
    Last Post: 06-09-2002, 11:07 PM