Scribd
Upload
233 views3 pages

KKT

The document introduces the Karush-Kuhn-Tucker (KKT) conditions for solving constrained optimization problems. The KKT conditions are necessary conditions that must be satisfied at an optimal solution. They involve the gradient of the Lagrangian function and complementary slackness conditions. The document provides the general form of the KKT conditions and gives an example of applying them to minimize power consumption in an electrical circuit. It also outlines the KKT conditions for a quadratic program and provides exercises for verifying the KKT conditions and comparing them to Wolfe's method.

Uploaded by

Wen-temi Apeaning
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
233 views3 pages

KKT

The document introduces the Karush-Kuhn-Tucker (KKT) conditions for solving constrained optimization problems. The KKT conditions are necessary conditions that must be satisfied at an optimal solution. They involve the gradient of the Lagrangian function and complementary slackness conditions. The document provides the general form of the KKT conditions and gives an example of applying them to minimize power consumption in an electrical circuit. It also outlines the KKT conditions for a quadratic program and provides exercises for verifying the KKT conditions and comparing them to Wolfe's method.

Uploaded by

Wen-temi Apeaning
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 3

KKT.

nb 1

Lagrange Multiplier Method & Karush-Kuhn-Tucker (KKT) Conditions


Part II

KKT Conditions
General Non-Linear Constrained Minimum:
Min: f[x]
Constrained by: h[x] = 0 (m constraints)
g[x] ≤ 0 (k constraints)

Introduce slack variables si for the inequality contraints: gi [x] + si 2 == 0


and the monster Lagrangian:

L[x,l,m] = f[x] + l h[x] + ∑ mi (gi [x] + si 2 )

Recall the geometry of the Lagrange multiplier conditions: The gradient of the objective function must be orthogonal to the
tangent plane of the (active) constraints. That is the projection of the gradient of f onto the space of directions tangent to the
constraint "surface" is zero.

The KT conditions are the following:


1) Gradient of the Lagrangian = 0
2) Constraints (given above)
3) Complementary Slackness ( for the si variables) m.s == 0
4) Feasibility:
5) Sign condition on the multiplier: m ≥ 0

At a feasible point for the constraints, the active constraints are those components of g with gi [x] = 0 ( if the value is < 0,
that constraint is said to be inactive.

Active & Inactive Constraints Diagram

Two variants: Saddle Point & Lagrangian

Example: Chong Zak Example 20.2


Consider a circuit with a 20V battery and two resistances in series: R and 10 ohm

Min: Power absorbed by R= i2 R = - 400 R/(10+R)^2 subject to -R ≤ 0

Find the value of R such that maximal power is delivered to the 10 ohm resistor, i.e:

Min: - Ç\frac{4000}{(10+R)^2}Ç subject to -R ≤ 0


KKT.nb 2

-4000
H10 + RL2
In[51]:= DA ÅÅÅÅÅÅÅÅÅÅÅÅÅÅÅÅÅÅÅÅÅÅÅ , RE

H10 + RL3
8000
Out[51]= ÅÅÅÅÅÅÅÅÅÅÅÅÅÅÅÅÅÅÅÅÅÅ
Å

Necessary Conditions for Quad. Program

ü Review: Quadratic Programs

ü KKT conditions for a Quadratic Program

ü Lagrangian

Given: x.Q.x/2 + p.x subject to the linear constraints:


A.x == b, x ≥ 0,

the associated Lagrangian is:

L[x,l] = x.Q.x/2 + p.x + l (A.x - b) + m.x

The KKT conditions yield:


Q.x + p - Transpose[A].l + m == 0
Transpose[l].(A.x - b) ==0
Transpose[m].x == 0
A.x == b, x ≥ 0,

Exercises
I. Write down the KKT conditions for the problem:
Min f[x] = - x1 3 + x2 2 - 2 x1 x3 2 subject to the constraints:
2 x1 + x2 2 + x3 - 5 == 0
5 x1 2 - x2 2 - x3 ≥ 2
xi ≥ 0 for i = 1,2,3.

Verify that the KKT conditions are satisfied at (1,0,3).

II. Write down the KKT conditions for the problem:


Min f[x] = x1 2 + x2 2 + x3 2 subject to the constraints:
-x1 +x2 - x3 ≥ -10
x1 +x2 +4 x3 ≥ 20
Find all the solution.

III. Here's an exercise from Grieg p. 142):


Minimize: f[x] = (x1 -1)^2 + (x2 -2)^2+ (x3 -3)^2+ (x4 -4)^2

subject to: - x1 - x2 - x3 - x4 + 5 ≥ 0
- 3 x1 - 3 x2 - 2 x3 - x4 + 10 ≥ 0
x≥0
Verify the KT conditions and then expand f to obtains a Quadratic Program and compare the KT conditions with Wolfe's.
KKT.nb 3

III. Here's an exercise from Grieg p. 142):


Minimize: f[x] = (x1 -1)^2 + (x2 -2)^2+ (x3 -3)^2+ (x4 -4)^2

subject to: - x1 - x2 - x3 - x4 + 5 ≥ 0
- 3 x1 - 3 x2 - 2 x3 - x4 + 10 ≥ 0
x≥0
Verify the KT conditions and then expand f to obtains a Quadratic Program and compare the KT conditions with Wolfe's.

Solve the problem using Wolfe's method .

Bonus: Solve the problem using a projected gradient methods (mimic affine scaling) and a projected Newton's method.
Compare the results.

You might also like