Minimization under non-linear constraints - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T13:58:04Z http://mathoverflow.net/feeds/question/29215 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/29215/minimization-under-non-linear-constraints Minimization under non-linear constraints Chaya 2010-06-23T10:48:57Z 2010-07-23T19:32:40Z <p>There is a linear function of two variables that I am trying to minimize under an equality constraint. But, the constraint is non linear in the variables. Is there any technique to solve this? or can I use approximations and linearize the constraint?</p> http://mathoverflow.net/questions/29215/minimization-under-non-linear-constraints/29217#29217 Answer by Charles Matthews for Minimization under non-linear constraints Charles Matthews 2010-06-23T10:56:56Z 2010-06-23T10:56:56Z <p>You need Lagrange multipliers (http://en.wikipedia.org/wiki/Lagrange_multipliers).</p> http://mathoverflow.net/questions/29215/minimization-under-non-linear-constraints/29242#29242 Answer by Jan for Minimization under non-linear constraints Jan 2010-06-23T14:40:32Z 2010-06-23T14:40:32Z <p>In addition to the tip about using Lagrange multipliers, take a look at <a href="http://en.wikipedia.org/wiki/Nonlinear_programming" rel="nofollow">http://en.wikipedia.org/wiki/Nonlinear_programming</a> which has a small paragraph about methods for solving nonlinear optimization problems.</p> <p>If you can know (or can show) that the problem is convex and you want to learn techniques for convex nonlinear optimization, take a look at the following textbook <a href="http://www.stanford.edu/~boyd/cvxbook/" rel="nofollow">http://www.stanford.edu/~boyd/cvxbook/</a> (pdf available)</p> http://mathoverflow.net/questions/29215/minimization-under-non-linear-constraints/29378#29378 Answer by Chaya for Minimization under non-linear constraints Chaya 2010-06-24T13:53:55Z 2010-06-24T13:53:55Z <p>To be precise, the constraint equality is exponential in the two variables. Will Lagrange multipliers help here?</p> http://mathoverflow.net/questions/29215/minimization-under-non-linear-constraints/33130#33130 Answer by Gilead for Minimization under non-linear constraints Gilead 2010-07-23T19:32:40Z 2010-07-23T19:32:40Z <p>As I understand, your problem looks like this:</p> <p>$\min_{x,y} \Phi=a_{1} x + a_{2}y$</p> <p>s.t. $f(x,y) = 0$</p> <p>where $f(x,y)$ looks something like this: $f(x,y) = a_{3} \exp{(a_{4}x)} + a_{5} \exp{(a_{6}y)}$</p> <p>This looks like a nonconvex NLP can be trivially solved using any NLP solver.</p> <p>Or are you looking for a closed form solution? </p> <p>Normally, the first thing I would try is to see if I can substitute constraints into the objective to transform the problem into an unconstrained one, but it looks like it's not possible here.</p> <p>As mentioned above, you can write the first order optimality conditions for the above system and solve the resulting nonlinear system of equations.</p> <p>$\nabla L(x,y,\lambda) = \nabla\Phi + \lambda \nabla f(x,y) = 0$</p> <p>In your case, it would be:</p> <p>$a_{1} + \lambda a_{3} a_{4} \exp{(a_{4}x)} = 0$</p> <p>$a_{2} + \lambda a_{5} a_{6} \exp{(a_{6}x)} = 0$</p> <p>$a_{3} \exp{(a_{4}x)} + a_{5} \exp{(a_{6}y)} = 0$</p> <p>Solve the above system for $x,y,\lambda$. And bam! You're done.</p>