Karush Kuhn Tucker problem (minimizing a function subject to a constraint)

In summary, using Karush Kuhn Tucker's theorem, you can find the minimum of f(x,y)= 3x2+y2 subject to the constraint 1<=xy by setting the derivatives equal to 0 and using Lagrange multipliers. The only possible extrema will be on the set 1=xy, and the minimum can be found by taking the positive root of 6x = -λy and 2y = -λx and using the constraint xy = 1. There are two optimal solutions in (x,y) space for this problem.
  • #1
porroadventum
34
0

Homework Statement


Find the minimum of f(x,y)= 3x2+y2, subject to the constraints 1<=xy.


Homework Equations


I thought I would use Karush Kuhn Tucker's theorem to solve this.
∇f=(6x, 2y) and ∇h=(-y,-x)
The general equation according to KKT is ∇f=λ∇h.

First case: h<0. According to KKT theorem when h is inactive (<0) then λ=0.
So the equation becomes 6x=0, therefore x=0 and 2y=0 therefore y=0 which cannot happen due to the constraint 1<=xy (since 1 is not <=0). Therefore this is not a solution.

Second case: h=0
The equation is 6x=-y and 2y=-x. These seem like inconsistent equations to me?
I also got 1-xy=0.

What is the next step or am I right in thinking there are again no solutions and there is no minimum or maximum? I'm pretty sure the set is not compact so the min/max may not even exist.

Some help would be greatly appreciated. Thank you.
 
Physics news on Phys.org
  • #2
porroadventum said:

Homework Statement


Find the minimum of f(x,y)= 3x2+y2, subject to the constraints 1<=xy.


Homework Equations


I thought I would use Karush Kuhn Tucker's theorem to solve this.
∇f=(6x, 2y) and ∇h=(-y,-x)
The general equation according to KKT is ∇f=λ∇h.

First case: h<0. According to KKT theorem when h is inactive (<0) then λ=0.
So the equation becomes 6x=0, therefore x=0 and 2y=0 therefore y=0 which cannot happen due to the constraint 1<=xy (since 1 is not <=0). Therefore this is not a solution.

Second case: h=0
The equation is 6x=-y and 2y=-x. These seem like inconsistent equations to me?
I also got 1-xy=0.

What is the next step or am I right in thinking there are again no solutions and there is no minimum or maximum? I'm pretty sure the set is not compact so the min/max may not even exist.

Some help would be greatly appreciated. Thank you.

I'd just reason using ordinary Lagrange multipliers. 1<xy is an open set. So setting the derivatives equal to 0 gives the only critical point at (0,0) as you showed, which doesn't satisfy the constraint. So the only possible extrema will be on 1=xy. You should be able to find them using a Lagrange multiplier. No, there obviously won't be a max but you'll certainly be able to find a min.
 
  • #3
I'm getting the minimum at a value of 2√3, is this correct?
 
  • #4
porroadventum said:
I'm getting the minimum at a value of 2√3, is this correct?

Be best if you showed your work, but yes, that sounds right.
 
Last edited:
  • #5
porroadventum said:

Homework Statement


Find the minimum of f(x,y)= 3x2+y2, subject to the constraints 1<=xy.


Homework Equations


I thought I would use Karush Kuhn Tucker's theorem to solve this.
∇f=(6x, 2y) and ∇h=(-y,-x)
The general equation according to KKT is ∇f=λ∇h.

First case: h<0. According to KKT theorem when h is inactive (<0) then λ=0.
So the equation becomes 6x=0, therefore x=0 and 2y=0 therefore y=0 which cannot happen due to the constraint 1<=xy (since 1 is not <=0). Therefore this is not a solution.

Second case: h=0
The equation is 6x=-y and 2y=-x. These seem like inconsistent equations to me?
I also got 1-xy=0.

What is the next step or am I right in thinking there are again no solutions and there is no minimum or maximum? I'm pretty sure the set is not compact so the min/max may not even exist.

Some help would be greatly appreciated. Thank you.

Your "inconsistent" equations are not correct, so their being inconsistent is not important.

You should have 6x = -λy and 2y = -λx, so λ can be found. You should take the positive root (why?) Then, putting the value of λ into one of those equations and using the other equation xy = 1, you get the complete solution. There are two optimal solutions in (x,y) space; do you see why?
 

1. What is the Karush Kuhn Tucker (KKT) problem?

The Karush Kuhn Tucker (KKT) problem is a mathematical optimization problem that involves minimizing a function subject to a constraint. It is a generalization of the Lagrange multiplier method and is used to find the optimal solution for constrained optimization problems.

2. What is the purpose of the KKT conditions?

The KKT conditions are necessary conditions for a point to be the optimal solution of a constrained optimization problem. They help to identify the optimal solution by checking if certain conditions are satisfied at the point.

3. What are the KKT conditions?

The KKT conditions consist of three parts: the gradient of the objective function must be equal to a linear combination of the gradients of the constraints, the constraints must be satisfied at the optimal point, and the Lagrange multiplier for each constraint must be non-negative. In addition, the constraints must be either active or inactive at the optimal point.

4. How are the KKT conditions used to solve a constrained optimization problem?

To solve a constrained optimization problem using the KKT conditions, first, the Lagrangian function is constructed by combining the objective function and the constraints. Then, the KKT conditions are checked at different points until the optimal solution is found. The optimal solution must satisfy all three parts of the KKT conditions.

5. What are some real-world applications of the KKT problem?

The KKT problem has many applications in various fields, including economics, engineering, and physics. For example, it can be used to optimize production and allocation in economics, design optimal structures in engineering, and find the optimal conditions for physical systems in physics. It is also used in machine learning and data analysis to find the best model parameters that satisfy certain constraints.

Similar threads

  • Calculus and Beyond Homework Help
Replies
2
Views
480
  • Calculus and Beyond Homework Help
Replies
1
Views
417
  • Calculus and Beyond Homework Help
Replies
6
Views
794
  • Calculus and Beyond Homework Help
Replies
8
Views
348
  • Calculus and Beyond Homework Help
Replies
18
Views
1K
  • Calculus and Beyond Homework Help
Replies
4
Views
798
  • Calculus and Beyond Homework Help
Replies
5
Views
1K
  • Calculus and Beyond Homework Help
Replies
3
Views
515
  • Calculus and Beyond Homework Help
Replies
1
Views
664
  • Calculus and Beyond Homework Help
Replies
5
Views
1K
Back
Top