The necessary conditions for a constrained local optimum are called the Karush Kuhn Tucker (KKT) Conditions, and these conditions play a very important role in constrained optimization theory and algorithm development. For an optimization problem:

$$\min_x f(x)$$ $$\mathrm{subject\;to}\quad g_i(x)-b_i \ge 0 \quad i=1,\ldots,k$$ $$\quad\quad\quad\quad\quad g_i(x)-b_i = 0 \quad i=k+1,\ldots,m$$

There are four KKT conditions for optimal primal `(x)` and dual `(\lambda)` variables. The asterisk (*) denotes optimal values.

$$g_i(x^*)-b_i \mathrm{\;is\;feasible}$$

$$\nabla f(x^*)-\sum_{i=1}^m \lambda_i^* \nabla g_i\left(x^*\right)=0$$

$$\lambda_i^* \left( g_i(x^*)-b_i \right) = 0$$

$$\lambda_i^* \ge 0$$

The feasibility condition (1) applies to both equality and inequality constraints and is simply a statement that the constraints must not be violated at optimal conditions. The gradient condition (2) ensures that there is no feasible direction that could potentially improve the objective function. The last two condition (3 and 4) are only required with inequality constraints and enforce a positive Lagrange multiplier when the constraint is active (=0) and a zero Lagrange multiplier when the constraint is inactive (>0).

This 5 minute introductory video reviews the 4 KKT conditions and applies them to solve a simple quadratic programming (QP) problem with:

- 1 Quadratic objective function
- 2 Linear equality constraints
- 3 Variables (x
_{1}, x_{2}, x_{3})

Download the following worksheet on KKT conditions. The video below reviews the solution to this worksheet.

This next 5 minute introductory is similar to the previous one but solves a problem with inequality constraints instead of equality constraints. The problem is a simple quadratic programming (QP) problem with:

- 1 Quadratic objective function
- 2 Linear inequality constraints
- 3 Variables (x
_{1}, x_{2}, x_{3})

Download the following worksheet on KKT conditions with inequality constraints. The video below reviews the solution to this worksheet.

This 5 minute exercise is similar to the previous ones but solves a problem with both equality and inequality constraints.

Download the following worksheet on KKT conditions with inequality and equality constraints. The video below reviews the solution to this worksheet.

This 5 minute exercise covers an application to a tank volume optimization. In this case, we specify the final Lagrange multiplier of $8/ft^{3}.

Download the following worksheet on this application of the KKT conditions. The video below reviews the solution to this worksheet.

This assignment can be completed in groups of two. Additional guidelines on individual, collaborative, and group assignments are provided under the Expectations link.

comments powered by Disqus

Retrieved from http://apmonitor.com/me575/index.php/Main/KuhnTucker

Page last modified on October 18, 2016, at 04:17 AM