Main
~~# ~~{~~`g~~_i(x*)-b_~~i`~~} ~~(Feasible constraints)~~

#{~~`~~\grad f(x*)-\sum_{i=1}^m \lambda_i^* \grad g_i\left(x*\right)=~~0`~~} ~~(No direction improves objective and is feasible~~)

~~# {`~~\~~lambda_i* \left( g_i(x*)-b_i \right) = 0`~~} ~~(Complementary slackness)~~

#{~~`~~\lambda_i* \ge ~~0`~~}~~ (Positive Lagrange multipliers)~~
~~The~~ four KKT conditions for optimality ~~are~~

#{~~`g_i(x)-b_i`~~} ~~is feasible~~

#{`\~~grad f~~(x~~^~~*)-~~\sum~~_~~{i=1~~}~~^m \lambda_i^* \grad g_i~~\~~left~~(x~~^~~*~~\right~~)=~~0`~~}

(:html:)

<iframe width="560" height="315" src="https://www.youtube.com/embed/ws38Jon_-_E?rel=0" frameborder="0" allowfullscreen></iframe>(:htmlend:)

----

Attach:group50.png This assignment can be completed in groups of two. Additional guidelines on individual, collaborative, and group assignments are provided under the [[Main/CourseStandards | Expectations link]].
~~-> Attach~~:~~kkt_contour~~.~~png~~

(:html:)

<iframe width="560" height="315" src="http://www.youtube.com/embed/JTTiELgMyuM?rel=0" frameborder="0" allowfullscreen></iframe>

(:htmlend:)

----

!!!! Part 3: 5 Minute KKT Exercise with both Inequality and Equality Constraints

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.

* [[Attach:kkt_example3.pdf|KKT Conditions Worksheet 3]]

* [[Attach:kkt_example3_solution.pdf|KKT Conditions Worksheet 3 Solution]]

(:html:)

<iframe width="560" height="315" src="http://www.youtube.com/embed/JTTiELgMyuM?rel=0" frameborder="0" allowfullscreen></iframe>

(:htmlend:)

----

!!!! Part 4: 5 Minute Application Exercise for the Optimal Volume of a Tank

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.

* [[Attach:kkt_example4.pdf|KKT Conditions Worksheet 4]]

* [[Attach:kkt_example4_solution.pdf|KKT Conditions Worksheet 4 Solution]]
~~* 2 Linear equality constraints~~

----

!!!! Tutorial on the KKT Conditions

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

* 3 Variables (x'_1_', x'_2_', x'_3_')

* 2 Linear equality constraints

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

* [[Attach:kkt_example1.pdf|Worksheet 1 on the KKT Conditions]]

(:html:)

<iframe width="560" height="315" src="http://www.youtube.com/embed/eaKPzb11qFw?rel=0" frameborder="0" allowfullscreen></iframe>

(:htmlend:)

## Karush-Kuhn-Tucker (KKT) Conditions

## Main.KuhnTucker History

Hide minor edits - Show changes to output

Changed line 11 from:

There are four KKT conditions for ~~optimality with the primal ~~{~~`x*~~`} ~~variable ~~and dual {`\lambda~~*~~`} ~~variable optimal~~ values.

to:

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

Changed lines 9-10 from:

{$\quad\quad\quad g_i(x)-b_i = 0 \quad i=k+1,\ldots,m$}

to:

{$\quad\quad\quad\quad\quad g_i(x)-b_i = 0 \quad i=k+1,\ldots,m$}

Changed line 14 from:

{$g_i(x^*)-b_i$}

to:

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

Changed lines 8-10 from:

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

{$\quad\quad g_i(x)-b_i = 0 \quad i=k+1,\ldots,m$}

{$\quad\quad g_i(x)-b_i = 0 \quad i=k+1,\ldots,m$}

to:

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

{$\quad\quad\quad g_i(x)-b_i = 0 \quad i=k+1,\ldots,m$}

{$\quad\quad\quad g_i(x)-b_i = 0 \quad i=k+1,\ldots,m$}

Changed line 20 from:

{$~~`~~\lambda_i^* \left( g_i(x^*)-b_i \right) = 0$}

to:

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

Changed line 17 from:

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

to:

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

Changed lines 14-15 from:

{$g_i(x*)-b_i$}

to:

{$g_i(x^*)-b_i$}

Changed line 17 from:

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

to:

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

Changed lines 20-21 from:

{$`\lambda_i* \left( g_i(x*)-b_i \right) = 0$}

to:

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

Changed line 23 from:

{$\lambda_i* \ge 0$}

to:

{$\lambda_i^* \ge 0$}

Changed lines 13-16 from:

#

#

to:

!!!!! 1. Feasible Constraints

{$g_i(x*)-b_i$}

!!!!! 2. No Feasible Descent

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

!!!!! 3. Complementary Slackness

{$`\lambda_i* \left( g_i(x*)-b_i \right) = 0$}

!!!!! 4. Positive Lagrange Multipliers

{$\lambda_i* \ge 0$}

{$g_i(x*)-b_i$}

!!!!! 2. No Feasible Descent

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

!!!!! 3. Complementary Slackness

{$`\lambda_i* \left( g_i(x*)-b_i \right) = 0$}

!!!!! 4. Positive Lagrange Multipliers

{$\lambda_i* \ge 0$}

Changed lines 11-15 from:

#

#

to:

There are four KKT conditions for optimality with the primal {`x*`} variable and dual {`\lambda*`} variable optimal values.

# {`g_i(x*)-b_i`} (Feasible constraints)

# {`\grad f(x*)-\sum_{i=1}^m \lambda_i^* \grad g_i\left(x*\right)=0`} (No direction improves objective and is feasible)

# {`\lambda_i* \left( g_i(x*)-b_i \right) = 0`} (Complementary slackness)

# {`\lambda_i* \ge 0`} (Positive Lagrange multipliers)

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).

# {`g_i(x*)-b_i`} (Feasible constraints)

# {`\grad f(x*)-\sum_{i=1}^m \lambda_i^* \grad g_i\left(x*\right)=0`} (No direction improves objective and is feasible)

# {`\lambda_i* \left( g_i(x*)-b_i \right) = 0`} (Complementary slackness)

# {`\lambda_i* \ge 0`} (Positive Lagrange multipliers)

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).

Changed lines 5-15 from:

The necessary conditions for a constrained local optimum are called the Kuhn~~-Tucker Conditions, and these conditions play a very important role in constrained optimization theory and algorithm~~ development.

to:

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}\;g_i(x)-b_i \ge 0 \quad i=1,\ldots,k$}

{$\quad\quad g_i(x)-b_i = 0 \quad i=k+1,\ldots,m$}

The four KKT conditions for optimality are

# {`g_i(x)-b_i`} is feasible

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

{$\min_x f(x)$}

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

{$\quad\quad g_i(x)-b_i = 0 \quad i=k+1,\ldots,m$}

The four KKT conditions for optimality are

# {`g_i(x)-b_i`} is feasible

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

Added lines 80-87:

(:htmlend:)

----

!!!! Part 5: KKT Conditions for Dynamic Optimization

(:html:)

<iframe width="560" height="315" src="https://www.youtube.com/embed/n4OzENKziR4" frameborder="0" allowfullscreen></iframe>

----

!!!! Part 5: KKT Conditions for Dynamic Optimization

(:html:)

<iframe width="560" height="315" src="https://www.youtube.com/embed/n4OzENKziR4" frameborder="0" allowfullscreen></iframe>

Added lines 29-31:

(:html:)

<iframe width="560" height="315" src="https://www.youtube.com/embed/ws38Jon_-_E?rel=0" frameborder="0" allowfullscreen></iframe>(:htmlend:)

Added lines 78-81:

----

Attach:group50.png This assignment can be completed in groups of two. Additional guidelines on individual, collaborative, and group assignments are provided under the [[Main/CourseStandards | Expectations link]].

Changed line 9 from:

to:

[[http://apmonitor.com/online/view_pass.php?f=qp3.apm | -> Attach:kkt_contour.png]]

Changed line 74 from:

<iframe width="560" height="315" src="http://www.youtube.com/embed/~~JTTiELgMyuM~~?rel=0" frameborder="0" allowfullscreen></iframe>

to:

<iframe width="560" height="315" src="http://www.youtube.com/embed/5YKXqkwWQNA?rel=0" frameborder="0" allowfullscreen></iframe>

Changed line 59 from:

<iframe width="560" height="315" src="http://www.youtube.com/embed/~~JTTiELgMyuM~~?rel=0" frameborder="0" allowfullscreen></iframe>

to:

<iframe width="560" height="315" src="http://www.youtube.com/embed/AQWy73cHoIU?rel=0" frameborder="0" allowfullscreen></iframe>

Changed lines 11-12 from:

!!!! 5 Minute Tutorial on the KKT Conditions

to:

!!!! Part 1: 5 Minute Tutorial on the KKT Conditions

Changed lines 30-31 from:

!!!! 5 Minute Tutorial with KKT Conditions and Inequality Constraints

to:

!!!! Part 2: 5 Minute Tutorial with KKT Conditions and Inequality Constraints

Added lines 42-71:

(:html:)

<iframe width="560" height="315" src="http://www.youtube.com/embed/JTTiELgMyuM?rel=0" frameborder="0" allowfullscreen></iframe>

(:htmlend:)

----

!!!! Part 3: 5 Minute KKT Exercise with both Inequality and Equality Constraints

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.

* [[Attach:kkt_example3.pdf|KKT Conditions Worksheet 3]]

* [[Attach:kkt_example3_solution.pdf|KKT Conditions Worksheet 3 Solution]]

(:html:)

<iframe width="560" height="315" src="http://www.youtube.com/embed/JTTiELgMyuM?rel=0" frameborder="0" allowfullscreen></iframe>

(:htmlend:)

----

!!!! Part 4: 5 Minute Application Exercise for the Optimal Volume of a Tank

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.

* [[Attach:kkt_example4.pdf|KKT Conditions Worksheet 4]]

* [[Attach:kkt_example4_solution.pdf|KKT Conditions Worksheet 4 Solution]]

Changed line 7 from:

* [[Attach:kuhn_tucker_hw.pdf|Kuhn-Tucker and Lagrange Multiplier Homework]]

to:

* [[Attach:kuhn_tucker_hw.pdf|Karush-Kuhn-Tucker and Lagrange Multiplier Homework]]

Changed lines 11-12 from:

!!!! Tutorial on the KKT Conditions

to:

!!!! 5 Minute Tutorial on the KKT Conditions

Added line 16:

* 2 Linear equality constraints

Changed lines 18-19 from:

to:

Changed lines 21-22 from:

* [[Attach:kkt_example1.pdf|~~Worksheet 1 on the~~ KKT Conditions]]

to:

* [[Attach:kkt_example1.pdf|KKT Conditions Worksheet 1]]

* [[Attach:kkt_example1_solution.pdf|KKT Conditions Worksheet 1 Solution]]

* [[Attach:kkt_example1_solution.pdf|KKT Conditions Worksheet 1 Solution]]

Added lines 26-44:

(:htmlend:)

----

!!!! 5 Minute Tutorial with KKT Conditions and Inequality Constraints

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.

* [[Attach:kkt_example2.pdf|KKT Conditions Worksheet 2]]

* [[Attach:kkt_example2_solution.pdf|KKT Conditions Worksheet 2 Solution]]

(:html:)

<iframe width="560" height="315" src="http://www.youtube.com/embed/JTTiELgMyuM?rel=0" frameborder="0" allowfullscreen></iframe>

----

!!!! 5 Minute Tutorial with KKT Conditions and Inequality Constraints

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.

* [[Attach:kkt_example2.pdf|KKT Conditions Worksheet 2]]

* [[Attach:kkt_example2_solution.pdf|KKT Conditions Worksheet 2 Solution]]

(:html:)

<iframe width="560" height="315" src="http://www.youtube.com/embed/JTTiELgMyuM?rel=0" frameborder="0" allowfullscreen></iframe>

Changed line 1 from:

(:title Karush-Kuhn-Tucker (KKT) Conditions~~ and Lagrange Multipliers~~:)

to:

(:title Karush-Kuhn-Tucker (KKT) Conditions:)

Changed lines 1-6 from:

(:title Kuhn-Tucker Conditions and Lagrange Multipliers:)

(:keywords Kuhn-Tucker Conditions, Lagrange Multiplier, Optimization, Constrained:)

(:description Homework on Kuhn-Tucker conditions and Lagrange multipliers including a number of problems.:)

!!!! Kuhn-Tucker Conditions

(:keywords Kuhn-Tucker Conditions, Lagrange Multiplier, Optimization, Constrained:)

(:description Homework on Kuhn-Tucker conditions and Lagrange multipliers including a number of problems.:)

!!!! Kuhn-Tucker Conditions

to:

(:title Karush-Kuhn-Tucker (KKT) Conditions and Lagrange Multipliers:)

(:keywords Karush-Kuhn-Tucker Conditions, Lagrange Multiplier, Optimization, Constrained:)

(:description Homework on Karush-Kuhn-Tucker (KKT) conditions and Lagrange multipliers including a number of problems.:)

!!!! Karush-Kuhn-Tucker (KKT) Conditions

(:keywords Karush-Kuhn-Tucker Conditions, Lagrange Multiplier, Optimization, Constrained:)

(:description Homework on Karush-Kuhn-Tucker (KKT) conditions and Lagrange multipliers including a number of problems.:)

!!!! Karush-Kuhn-Tucker (KKT) Conditions

Added lines 10-27:

----

!!!! Tutorial on the KKT Conditions

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

* 3 Variables (x'_1_', x'_2_', x'_3_')

* 2 Linear equality constraints

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

* [[Attach:kkt_example1.pdf|Worksheet 1 on the KKT Conditions]]

(:html:)

<iframe width="560" height="315" src="http://www.youtube.com/embed/eaKPzb11qFw?rel=0" frameborder="0" allowfullscreen></iframe>

(:htmlend:)

Added lines 1-28:

(:title Kuhn-Tucker Conditions and Lagrange Multipliers:)

(:keywords Kuhn-Tucker Conditions, Lagrange Multiplier, Optimization, Constrained:)

(:description Homework on Kuhn-Tucker conditions and Lagrange multipliers including a number of problems.:)

!!!! Kuhn-Tucker Conditions

The necessary conditions for a constrained local optimum are called the Kuhn-Tucker Conditions, and these conditions play a very important role in constrained optimization theory and algorithm development.

* [[Attach:kuhn_tucker_hw.pdf|Kuhn-Tucker and Lagrange Multiplier Homework]]

----

(:html:)

<div id="disqus_thread"></div>

<script type="text/javascript">

/* * * CONFIGURATION VARIABLES: EDIT BEFORE PASTING INTO YOUR WEBPAGE * * */

var disqus_shortname = 'apmonitor'; // required: replace example with your forum shortname

/* * * DON'T EDIT BELOW THIS LINE * * */

(function() {

var dsq = document.createElement('script'); dsq.type = 'text/javascript'; dsq.async = true;

dsq.src = 'http://' + disqus_shortname + '.disqus.com/embed.js';

(document.getElementsByTagName('head')[0] || document.getElementsByTagName('body')[0]).appendChild(dsq);

})();

</script>

<noscript>Please enable JavaScript to view the <a href="http://disqus.com/?ref_noscript">comments powered by Disqus.</a></noscript>

<a href="http://disqus.com" class="dsq-brlink">comments powered by <span class="logo-disqus">Disqus</span></a>

(:htmlend:)

(:keywords Kuhn-Tucker Conditions, Lagrange Multiplier, Optimization, Constrained:)

(:description Homework on Kuhn-Tucker conditions and Lagrange multipliers including a number of problems.:)

!!!! Kuhn-Tucker Conditions

The necessary conditions for a constrained local optimum are called the Kuhn-Tucker Conditions, and these conditions play a very important role in constrained optimization theory and algorithm development.

* [[Attach:kuhn_tucker_hw.pdf|Kuhn-Tucker and Lagrange Multiplier Homework]]

----

(:html:)

<div id="disqus_thread"></div>

<script type="text/javascript">

/* * * CONFIGURATION VARIABLES: EDIT BEFORE PASTING INTO YOUR WEBPAGE * * */

var disqus_shortname = 'apmonitor'; // required: replace example with your forum shortname

/* * * DON'T EDIT BELOW THIS LINE * * */

(function() {

var dsq = document.createElement('script'); dsq.type = 'text/javascript'; dsq.async = true;

dsq.src = 'http://' + disqus_shortname + '.disqus.com/embed.js';

(document.getElementsByTagName('head')[0] || document.getElementsByTagName('body')[0]).appendChild(dsq);

})();

</script>

<noscript>Please enable JavaScript to view the <a href="http://disqus.com/?ref_noscript">comments powered by Disqus.</a></noscript>

<a href="http://disqus.com" class="dsq-brlink">comments powered by <span class="logo-disqus">Disqus</span></a>

(:htmlend:)