Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
add comment

4 Answers

up vote 2 down vote accepted

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)

share|improve this answer
add comment

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

share|improve this answer
add comment

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

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.