# Non-linear optimization problem with more constraints than variables

• Sep 21st 2009, 12:21 AM
kmg
Non-linear optimization problem with more constraints than variables
Hello all,

For the proof of a game-theoretic proposition I need to solve a non-convex non-linear optimization problem. The problem has both equality and inequality constraints (but can be turned into a problem with all inequality constraints). I wanted to solve this problem using the Lagrange / KKT approach, but ran into the following difficulty.

The original problem has 3*n variables and 4*n + 1 constraints. Therefore, when I use the Lagrange / KKT approach I end up with a system of 3*n + 4*n + 1 variables and 3*n equations.

Although I can eliminate some Lagrangian multipliers, I still have a system with more variables than equations - and hence, a system which I cannot solve.

Any ideas on how to tackle this problem?

Thanks for your consideration.

Kris
• Jan 21st 2010, 06:10 AM
Rebesques
Quote:

a system with more variables than equations - and hence, a system which I cannot solve.

I think you cannot solve it because it has more than one solutions. (Thinking)
• Jan 21st 2010, 09:32 AM
CaptainBlack
Quote:

Originally Posted by kmg
Hello all,

For the proof of a game-theoretic proposition I need to solve a non-convex non-linear optimization problem. The problem has both equality and inequality constraints (but can be turned into a problem with all inequality constraints). I wanted to solve this problem using the Lagrange / KKT approach, but ran into the following difficulty.

The original problem has 3*n variables and 4*n + 1 constraints. Therefore, when I use the Lagrange / KKT approach I end up with a system of 3*n + 4*n + 1 variables and 3*n equations.

Although I can eliminate some Lagrangian multipliers, I still have a system with more variables than equations - and hence, a system which I cannot solve.

Any ideas on how to tackle this problem?

Thanks for your consideration.

Kris

There is one equation for the partial derivative of the Lagrangian with respect to each variable usually.

CB
• Jan 21st 2010, 11:45 AM
kmg
Solved
Thanks. You are right, I did not count the original constraints. I got it solved now.