Minimization under non-linear constraints - MathOverflow

Minimization under non-linear constraints

2010-06-23T10:48:57Z

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?

Answer by Charles Matthews for Minimization under non-linear constraints

2010-06-23T10:56:56Z

You need Lagrange multipliers (http://en.wikipedia.org/wiki/Lagrange_multipliers).

Answer by Jan for Minimization under non-linear constraints

2010-06-23T14:40:32Z

In addition to the tip about using Lagrange multipliers, take a look at http://en.wikipedia.org/wiki/Nonlinear_programming which has a small paragraph about methods for solving nonlinear optimization problems.

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 http://www.stanford.edu/~boyd/cvxbook/ (pdf available)

Answer by Chaya for Minimization under non-linear constraints

2010-06-24T13:53:55Z

To be precise, the constraint equality is exponential in the two variables. Will Lagrange multipliers help here?

Answer by Gilead for Minimization under non-linear constraints

2010-07-23T19:32:40Z

As I understand, your problem looks like this:

$\min_{x,y} \Phi=a_{1} x + a_{2}y$

s.t. $f(x,y) = 0$

where $f(x,y)$ looks something like this: $f(x,y) = a_{3} \exp{(a_{4}x)} + a_{5} \exp{(a_{6}y)}$

This looks like a nonconvex NLP can be trivially solved using any NLP solver.

Or are you looking for a closed form solution?

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.

As mentioned above, you can write the first order optimality conditions for the above system and solve the resulting nonlinear system of equations.

$\nabla L(x,y,\lambda) = \nabla\Phi + \lambda \nabla f(x,y) = 0$

In your case, it would be:

$a_{1} + \lambda a_{3} a_{4} \exp{(a_{4}x)} = 0$

$a_{2} + \lambda a_{5} a_{6} \exp{(a_{6}x)} = 0$

$a_{3} \exp{(a_{4}x)} + a_{5} \exp{(a_{6}y)} = 0$

Solve the above system for $x,y,\lambda$. And bam! You're done.