Main

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$}
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$}
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:
# {`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)
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$}
Changed lines 11-15 from:
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`}
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).
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`}

June 15, 2015, at 08:14 AM by 45.56.3.184 -
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>
April 20, 2015, at 08:20 AM by 174.148.138.9 -
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:)
March 22, 2013, at 12:13 PM by 128.187.97.24 -
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]].
March 22, 2013, at 09:33 AM by 128.187.97.24 -
Changed line 9 from:
-> Attach:kkt_contour.png
to:
[[http://apmonitor.com/online/view_pass.php?f=qp3.apm | -> Attach:kkt_contour.png]]
March 22, 2013, at 09:27 AM by 128.187.97.24 -
Added lines 8-9:

-> Attach:kkt_contour.png
March 20, 2013, at 11:50 AM by 128.187.97.24 -
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>
March 20, 2013, at 11:39 AM by 128.187.97.24 -
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>
March 20, 2013, at 10:00 AM by 128.187.97.24 -
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]]
March 20, 2013, at 05:13 AM by 69.169.188.188 -
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]]
March 18, 2013, at 03:49 AM by 69.169.188.188 -
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:
* 2 Linear equality constraints
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]]
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>
March 17, 2013, at 07:13 AM by 69.169.188.188 -
Deleted lines 3-4:

!!!! Karush-Kuhn-Tucker (KKT) Conditions
March 17, 2013, at 07:13 AM by 69.169.188.188 -
Changed line 1 from:
(:title Karush-Kuhn-Tucker (KKT) Conditions and Lagrange Multipliers:)
to:
(:title Karush-Kuhn-Tucker (KKT) Conditions:)
March 17, 2013, at 07:10 AM by 69.169.188.188 -
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
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
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:)
March 15, 2013, at 07:06 AM by 152.179.16.250 -
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:)