Minimization under non-linear constraints

Question

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 1

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 2

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

Answer 3

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

Answer 4

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.