Duality and KKT conditions

4. Duality and KKT conditions#

In this chapter we take a few steps back to consider some of the mathematical properties of the types of problems we are looking at. Understanding these is not strictly necessary - you could just use a modelling language to formulate and let the computer solve your problem while ignoring everything in this chapter.

However, understanding duality and KKT conditions will be useful in various ways. Duality can be exploited to perform sensitivity analyses and is important when using optimisation methods to solve market problems (Section 5). An understanding of KKT conditions will become relevant particularly when we look at mixed complementarity (Section 6) and non-linear programming problems. As you will see below, duality and KKT conditions are also related. Understanding one can help you understand the other, and vice versa.

4.1. Duality#

4.1.1. Introduction to duality#

In linear programming, for every problem, which we shall call the primal problem, there exists a “mirrored” problem that we call the dual problem. What’s important is that we (or a computer) can follow a set number of rules to transform the primal problem into the dual problem, and having the dual problem available opens up some interesting possibilities. We will get into these rules and the possibilities further below.

What a dual problem is, is best illustrated with an example. Consider this LP problem (from Table 6.1 in [Hillier and Lieberman, 2021]):

(4.1)#

\begin{aligned} max & Z = 3 x_{1} + 5 x_{2} \\ s.t. & x_{1} \leq 4 \\ 2 x_{2} \leq 12 \\ 3 x_{1} + 2 x_{2} \leq 18 \\ x_{1} \geq 0 \\ x_{2} \geq 0 \end{aligned}

The corresponding dual problem is:

(4.2)#

\begin{aligned} min & W = 4 y_{1} + 12 y_{2} + 18 y_{3} \\ s.t. & y_{1} + 3 y_{3} \geq 3 \\ 2 y_{2} + 2 y_{3} \geq 5 \\ y_{1} \geq 0 \\ y_{2} \geq 0 \\ y_{3} \geq 0 \end{aligned}

The color coding in Fig. 4.1 illustrates some important points:

Green: The dual problem of a maximisation primal problem is a minimisation problem (and vice versa).
Yellow: Two primal variables lead to two dual constraints. The primal objective function coefficients (3 and 5) are the dual constraint parameters.
Purple: The “ $\geq 0$ ” bounds on the primal variables lead to “ $\geq$ ” in the dual constraints.
Blue: Three primal constraints lead to three dual variables. The primal constraint parameters (4, 12, and 18) are the dual objective function coefficients.
Cyan: The “ $\leq$ ” in the primal constraints leads to “ $\geq 0$ ” bounds on the dual variables.
Red: The coefficients of the dual constraints are a “rotation” of the primal constraint coefficients.

../_images/duality_introduction.jpg — Fig. 4.1 Relationship between primal and dual problem. Adapted from Table 6.1 in [Hillier and Lieberman, 2021].#

If we look at the solutions to the primal and dual problems, we see another important property of duality in linear problems: the optimal solution to the primal problem is the same value as the optimal solution to the dual problem. Furthermore, the shadow prices of the primal problem are the optimal variable values of the dual problem, and vice versa. The shadow prices of the primal problem in Fig. 4.1 are $(0, 1.5, 1)$ . The value of the variables in the optimal solution to the dual problem are also $(0, 1.5, 1)$ .

Strong and weak duality

Weak duality means that the solution to any primal minimisation problem is always greater than or equal to the solution of the corresponding dual (maximisation) problem. Under certain conditions - and this includes the condition that we are dealing with linear optimisation - we also see strong duality, which means that the solution of the primal problem is equal to the solution of the dual problem. We only deal with the linear case here, where strong duality always applies. Thus we will not consider this distinction further, but it is something you will find discussed in detail elsewhere.

4.1.2. Economic dispatch example#

We will now revisit the economic dispatch problem from Section 2.1 and formulate the corresponding dual problem. Recall our economic dispatch problem:

(4.3)#

\begin{aligned} Min. & J = 3 P_{1} + 4 P_{2} \\ s.t. & 50 \leq P_{1} \leq 300 \\ 100 \leq P_{2} \leq 400 \\ P_{1} + P_{2} = 500 \end{aligned}

We also have the variable bounds: $P_{1} \geq 0$ and $P_{2} \geq 0$ (this comes from the physical nature of our system: power plants produce electricity; their power production has to be a positive value).

Now, to make our life easier, we will rewrite this problem into the standard form that we introduced in Section 2.8.1. We separate out the upper and lower limits on generation which are technically separate constraints, and give all the constraints the same sign.

../_images/duality_economic_dispatch_standardform.jpg — Fig. 4.2 Modifying our economic dispatch example into a standard form.#

So our problem now looks like this:

(4.4)#

\begin{aligned} Min. & J = 3 P_{1} + 4 P_{2} \\ s.t. & P_{1} \leq 300 \\ P_{2} \leq 400 \\ - P_{1} \leq - 50 \\ - P_{2} \leq - 100 \\ P_{1} + P_{2} = 500 \end{aligned}

It is up to us to pick the naming for the new variables in the dual problem. Often we write down the variable name we’ll use in the dual problem next to the corresponding constraint in the primal problem, which in the above example would look like this:

(4.5)#

\begin{aligned} Min. & J = 3 P_{1} + 4 P_{2} \\ s.t. & P_{1} \leq 300 & (X_{1}) \\ P_{2} \leq 400 & (X_{2}) \\ - P_{1} \leq - 50 & (X_{3}) \\ - P_{2} \leq - 100 & (X_{4}) \\ P_{1} + P_{2} = 500 & (X_{5}) \end{aligned}

Now, we can use the rules in Table 4.1:

Table 4.1 Conversion from a standard-form minimisation primal problem to its dual problem.#
Primal	Dual
Minimise	Maximise
Variables	Constraints
$\geq 0$	$\leq$
Constraints	Variables
$=$	Unconstrained
$\leq$	$\leq 0$

The dual problem becomes a maximisation problem. There are two primal variables of the form “ $\geq 0$ ” so there are two dual constraints of the form “ $\leq$ ”. The primal constraints of “ $\leq$ ” form become dual variables with bounds “ $\leq 0$ ”, while the primal constraint of “ $=$ ” form corresponds to a dual variable that is unconstrained or unbounded. We have five primal constraints, which means there are five dual variables.

This is the resulting conversion:

../_images/duality_economic_dispatch_conversion.jpg — Fig. 4.3 Converting our standard form economic dispatch example into its dual (maximisation) problem.#

We end up with this dual problem:

(4.6)#

\begin{aligned} Max. & Z = 300 X_{1} + 400 X_{2} - 50 X_{3} - 100 X_{4} + 500 X_{5} \\ s.t. & X_{1} - X_{3} + X_{5} \leq 3 \\ X_{2} - X_{4} + X_{5} \leq 4 \end{aligned}

Our new variables are $X_{1} \leq 0, X_{2} \leq 0, X_{3} \leq 0, X_{4} \leq 0$ , and $X_{5}$ unconstrained. Notice that the objective function coefficients 3 and 4 are the parameters in the dual constraints. Likewise, the primal constraint parameters 300, 400, -50, -100, and 500 are the coefficients in the dual objective function.

Elaboration on constraints (red box in Fig. 4.3)

The left-hand side of the primal and dual constraints can be understood as a rotation of each other. In the context of the economic dispatch example:

$P_{1}$ in the first primal constraint leads to $X_{1}$ in the first dual constraint
$P_{2}$ in the second primal constraint leads to $X_{2}$ in the second dual constraint
$- P_{1}$ in the third primal constraint leads to $- X_{3}$ in the first dual constraint
$- P_{2}$ in the fourth primal constraint leads to $- X_{4}$ in the second dual constraint
$P_{1}$ in the fifth primal constraint leads to $X_{5}$ in the first dual constraint
$P_{2}$ in the fifth primal constraint leads to $X_{5}$ in the second dual constraint

Notice that when there is a factor of $P_{1}$ in a primal constraint, this leads to a term in the first dual constraint. When there is a factor of $P_{2}$ , it leads to a term in the second dual constraint. The first primal constraint leads to a factor of $X_{1}$ in the dual constraint, the second primal constraint leads to a factor of $X_{2}$ in the dual constraint, the third primal constraint leads to a factor of $X_{3}$ in the dual constraint, and so on.

We can solve the dual problem to obtain the optimal solution ( $X_{1} = - 1, X_{2} = 0, X_{3} = 0, X_{4} = 0, X_{5} = 4$ ). Recall that this solution to the dual problem gives the shadow prices of the primal problem. Looking at the shadow prices also reveals something about the primal constraints. When the shadow price is zero, that means the constraint is non-binding. In our example, only the first constraint ( $P_{1} \leq 300$ , capacity limit on unit 1) and last constraint ( $P_{1} + P_{2} = 500$ , demand constraint) are active. If the right-hand side of the demand constraint is changed marginally (by one unit) then the optimal value of the objective function will change by $X_{5} = 4$ . The objective function value is 1700 in both the primal and dual solution. The optimal value of the objective function in the primal problem is always equal to the optimal value of the dual objective function.

4.1.3. Strategies to convert a primal into its dual problem#

The easiest approach to convert a primal problem to its dual problem, and the one we use above, is:

Rewrite the primal problem to standard form
Follow the (standard, always same) steps to convert the standard-form problem to its dual

Summary of the recommended approach

Duality: conversion summary in the appendix contains a summary of this recommended approach with a generic example.

You do not have to rewrite to standard form first, however. There is a method called “SOB” which gives you a “map” on how to translate a primal problem into the corresponding dual problem, no matter what exact form it is in. In principle this also always works, but it can be a bit trickier to get your head around and it is easier to make mistakes.

The table in Fig. 4.4 shows you how what the rules in the SOB method are.

../_images/duality_conversion.jpg — Fig. 4.4 How to convert a primal problem into a dual problem From the “SOB method”: Benjamin (1995), SIAM Review 37(1): 85-87 as summarised in [Hillier and Lieberman, 2021], Table 6.14**#

4.1.4. Additional examples#

In the appendix chapter “Duality: additional examples” you can find additional examples of duality, including an example of how duality allows you to see the same problem from two perspectives (the buyer and the seller of ingredients for a lunch).

4.2. Karush-Kuhn-Tucker (KKT) conditions#

In this section, we introduce the Karush-Kuhn-Tucker (KKT) conditions for convex optimisation problems with equality and inequality constraints. For such convex problems, these conditions form a set of conditions that describe all optimal solutions to the problem at hand. They form the basis for many numerical methods to solve optimisation problems and in simple cases allow determining the solution analytically. They also combine primal and dual variables, which offers additional insight in the solution (e.g., which constraints are active, or what is the electricity price in this system?).

We start from unconstrained optimisation and gradually introduce equality and inequality constraints. We will use an economic dispatch example to illustrate our approach.

4.2.1. Unconstrained optimisation#

Let’s go back to basic optimisation (high school mathematics). Whenever you had to optimise (minimise or maximise) a function, you were doing unconstrained optimisation. To determine the maximum or minimum of a certain function, we should take the derivative of that function with respect to (w.r.t.) the decision variable $x$ and equate it to zero (necessary condition for optimality). Then we take the second order derivative to see if it is a minimum or maximum (sufficient condition). If there are multiple variables, we take partial derivatives.

(4.7)#

\begin{aligned} min f (x) & \to & \frac{\partial f (x)}{\partial x} = 0 (necessary condition) \\ \frac{\partial^{2} f (x)}{\partial x^{2}} > 0 (sufficient condition) \\ max f (x) & \to & \frac{\partial f (x)}{\partial x} = 0 (necessary condition) \\ \frac{\partial^{2} f (x)}{\partial x^{2}} < 0 (sufficient condition) \end{aligned}

A point that satisfies the necessary condition for optimality ( $\frac{\partial f (x)}{\partial x} = 0$ ) is called a stationary point. For convex optimisation problems, we never use the sufficient condition because any stationary point will be a minimum.

4.2.2. Equality constrained optimisation#

In energy systems, unfortunately we do not deal with many unconstrained optimisation problems—usually there are at least a few constraints. Consider the example of economic dispatch from Section 2.1. We will again use an economic dispatch example, and build up the complexity of the problem throughout this chapter to illustrate how we can use KKT conditions and duality to solve such problems and interpret their solutions.

Consider two generators $G_{1}$ and $G_{2}$ with cost structures $C_{1} (g_{1}) = a_{1} + b_{1} \cdot g_{1}^{2}$ and $C_{2} (g_{2}) = a_{2} + b_{2} \cdot g_{2}^{2}$ . Note that the cost functions here are quadratic, not linear. This is quite typical in power systems.

Unlike before, we now have a quadratic programming (QP) problem. This is still a convex optimisation problem. Therefore, the techniques we use here also apply to linear programming problems.

Reminder: convex optimisation

Convex optimisation means that we are dealing with convex functions over convex regions. Both linear and quadratic optimisation problems are convex. In general, however, many kinds of non-linear optimisation problems are non-convex, and we cannot apply the techniques we discuss here to them.

We need to dispatch the generators to meet a load $L$ at minimal cost. We will ignore the capacity constraints of the generators for now. Thus, we have the following optimisation problem:

(4.8)#

\begin{aligned} min. a_{1} + b_{1} \cdot g_{1}^{2} + a_{2} + b_{2} \cdot g_{2}^{2} \\ s.t. g_{1} + g_{2} = L \end{aligned}

If we do not consider the equality constraint $g_{1} + g_{2} = L$ then the optimal solution to this problem (what minimises operating cost of the system) is $g_{1}^{*} = 0$ , $g_{2}^{*} = 0$ , i.e. not run the generators at all. You can easily confirm this with the necessary condition for optimality: take the derivative of the objective function w.r.t. $g_{1}$ and $g_{2}$ , equate those expressions to zero, and solve for $g_{1}$ and $g_{2}$ . This is the unconstrained optimisation previously discussed.

To deal with the constraint in our optimisation problem, we introduce the Lagrangian. The Lagrangian elevates the constraint to the objective function.

(4.9)#

L = (a_{1} + b_{1} \cdot g_{1}^{2} + a_{2} + b_{2} \cdot g_{2}^{2}) + λ \cdot (L - g_{1} - g_{2})

The first part of the Lagrangian is the original objective function. Then we add the constraint multiplied by a Lagrange multiplier $λ$ . We want to find an optimal value of $λ$ that coordinates the decision of $g_{1}$ and $g_{2}$ to ensure that the constraint $L = g_{1}^{*} + g_{2}^{*}$ is met at minimum cost.

To do this, we draw on our knowledge of unconstrained optimisation, since now we have a single function, the Lagrangian, to minimise. Thus, we take the first derivative of the Lagrangian w.r.t. $g_{1}$ and $g_{2}$ and $λ$ :

(4.10)#

\begin{aligned} \frac{\partial L}{\partial g_{1}} = 2 \cdot b_{1} \cdot g_{1} - λ = 0 \\ \frac{\partial L}{\partial g_{2}} = 2 \cdot b_{2} \cdot g_{2} - λ = 0 \\ \frac{\partial L}{\partial λ} = L - g_{1} - g_{2} = 0 \end{aligned}

Notice that now we have three equations and three unknowns. So, we can solve for $g_{1}$ , $g_{2}$ , and $λ$ , which gives the optimal solution to the original optimisation problem. Note that the last equation is identical to our original constraint. A solution to the system of equations above will hence be as such that $g_{1}$ and $g_{2}$ jointly meet the load $L$ .

Now we will generalise the Lagrangian to any equality constrained optimisation problem. Consider the following minimisation problem with equality constraints $h_{i} (x)$ :

(4.11)#

\begin{aligned} min. & f (x) \\ s.t. & h_{i} (x) = 0 (λ_{i}) \forall i \in {1, 2, . . ., m} \end{aligned}

The equality constraints are written in standard form (as introduced in Section 2.8.1), so we have “= 0” on the right-hand side. There are $m$ equality constraints. We associate a Lagrange multiplier $λ_{i}$ to each constraint.

The Lagrangian is then:

(4.12)#

L = f (x) + \sum_{i = 1}^{m} λ_{i} \cdot h_{i} (x)

We can find the optimal solution ( $x^{*}, λ_{i}^{*}$ ) to the original optimisation problem by taking the derivative of the Lagrangian w.r.t. the decision variables $x$ and w.r.t. the Lagrange multipliers $λ_{i}$ . Notice that taking $\frac{\partial L}{\partial λ_{i}} = 0$ recovers the equality constraints $h_{i} (x) = 0$ .

(4.13)#

\begin{aligned} \frac{\partial L}{\partial x} = 0 \\ \frac{\partial L}{\partial λ_{i}} = h_{i} (x) = 0 \forall i \in {1, 2, . . ., m} \end{aligned}

Notation and standard form

You will notice that in this section, we write all constraints in a standard form with zeros on the right-hand side (i.e., $= 0$ or $\leq 0$ for equality constraints below). This ensures that you don’t make mistakes when you’re constructing the Lagrangian. In Section 4.1 above we used a different standard form that makes it easier to construct the dual problem. This highlights that there is no generally “correct” approach to write a standard form. It makes sense to go with an approach that works best for what you are doing.

The equality constrained optmisation problem also has a graphical interpretation. Fig. 4.5 shows the graphical interpretation of our economic dispatch example.

../_images/KKT_eqconst_graphical.png — Fig. 4.5 Graphical representation of the equality constrained economic dispatch problem#

$g_{1}$ and $g_{2}$ are on the axes. The red contour lines are constant values of the objective function (total operating cost). The total operating cost increases as $g_{1}$ and $g_{2}$ increase. The blue line is the equality constraint. The green dot is the optimal solution. At this point, the gradient of the objective function $\nabla f (x)$ (red arrow) is (1) perpendicular to the constraint and (2) parallel to the gradient of the constraint $\nabla h (x)$ (blue arrow). This can be expressed as:

(4.14)#

\nabla f (x) + λ \cdot \nabla h (x) = 0

4.2.3. Inequality and equality constrained optimisation#

In energy systems, we not only have equality constraints, but also inequality constraints. For example, returning to the economic dispatch example, the generators have maximum generation capacity constraints $\overset{―}{G_{1}}$ and $\overset{―}{G_{2}}$ and cannot run at negative output (lower bound of zero). The optimisation problem becomes:

(4.15)#

\begin{aligned} min. & a_{1} + b_{1} \cdot g_{1}^{2} + a_{2} + b_{2} \cdot g_{2}^{2} \\ s.t. & g_{1} + g_{2} = L \\ 0 \leq g_{1} \leq \overset{―}{G_{1}} \\ 0 \leq g_{2} \leq \overset{―}{G_{2}} \end{aligned}

To solve the problem with equality and inequality constraints, we extend our graphical interpretation. The grey area in Fig. 4.6 is the feasible region because it represents the feasible range of output of $g_{1}$ and $g_{2}$ . The set of feasible solutions—the values of $g_{1}$ and $g_{2}$ that satisfy both the equality and inequality constraints—lie on the blue line within the grey area. This is exactly what we already did in Section 2.1, just with different notation for our generation and demand constraints - and as will become clear in FIGURE, a key difference in where the optimal solution lies, since we are dealing with a quadratic rather than a linear problem.

../_images/KKT_eqconst_ineqconst_graphical.png — Fig. 4.6 Graphical representation of the equality and inequality constrained economic dispatch problem#

The optimal solution needs to be part of the feasible solution set. In this case, we see that the optimal solution (green dot) is indeed in the feasible area. Thus the inequality constraints $0 \leq g_{1} \leq \overset{―}{G_{1}}$ and $0 \leq g_{2} \leq \overset{―}{G_{2}}$ actually do not play a role in this particular example.

From linear to quadratic problems

Recall that in Section 2.1, we were able to say that an optimal solution (if it exists) would always lie at one of the corners of the feasible region. Here, however, we now have a solution in the interior of the feasible region. You can see why when you look at the contour lines: they are no longer linear. We are dealing with a quadratic problem here.

However, it will not always be the case that none of the inequality constraints play a role. What if the capacity limits on $g_{1}$ and $g_{2}$ do play a role? Then we want to figure out which inequality constraints are active. If we can identify the active constraints, we can replace these constraints with equality constraints (e.g., $g_{1} \leq \overset{―}{G_{1}}$ becomes $g_{1} = \overset{―}{G_{1}}$ ) and ignore all inactive constraints (because they don’t influence the solution). Then we are left with an equality constrained optimisation problem which we know how to solve.

For most problems, we do not know which constraints will be active/binding. Luckily, we can use a set of optimality conditions called Karush-Kuhn-Tucker (KKT) conditions to reflect the fact that in some cases inequality constraints are binding and in some cases they are not.

Consider the general inequality and equality constrained optimisation problem written in standard form:

(4.16)#

\begin{aligned} min. & f (x) \\ s.t. & h_{i} (x) = 0 (λ_{i}) \forall i \in {1, 2, . . ., m} \\ g_{j} (x) \leq 0 (μ_{j}) \forall j \in {1, 2, . . ., n} \end{aligned}

There are $m$ equality constraints associated with Lagrange multipliers $λ_{i}$ and $n$ inequality constraints associated with Lagrange multipliers $μ_{j}$ .

The Lagrangian is:

(4.17)#

L = f (x) + \sum_{i = 1}^{m} λ_{i} \cdot h_{i} (x) + \sum_{j = 1}^{n} μ_{j} \cdot g_{j} (x)

To formulate the Lagrangian, we followed the same logic as before: elevate the equality and inequality constraints to the Lagrangian. The Lagrangian has three components: the original objective function, the equality constraints multiplied by their Lagrange multipliers, and the inequality constraints multiplied by their Lagrange multipliers.

Then, with the help of the Lagrangian, we derive the following set of equations that characterises the optimal solution. These are the KKT conditions.

(4.18)#

\begin{array}{r} \begin{aligned} \frac{\partial L}{\partial x} = 0 & (Optimality conditions) \\ \frac{\partial L}{\partial λ_{i}} = h_{i} (x) = 0 \forall i \in {1, 2, . . ., m} & (Primal feasibility) \\ \frac{\partial L}{\partial μ_{j}} = g_{j} (x) \leq 0 \forall j \in {1, 2, . . ., n} & (Primal feasibility) \\ μ_{j} \cdot g_{j} (x) = 0 \forall j \in {1, 2, . . ., n} & (Complementary slackness conditions) \\ μ_{j} \geq 0 \forall j \in {1, 2, . . ., n} & (Dual feasibility) \end{aligned} \end{array}

Note on inequality signs in standard form

Note that all constraints in a standard form have zeros on the right-hand side (i.e., $= 0$ or $\leq 0$ for equality constraints below).
Inequality constraints are always of the form $g_{j} (x) \leq 0$ , not $g_{j} (x) \geq 0$ . Only if you write all inequality constraints as $g_{j} (x) \leq 0$ , the signs of the Lagrangian above are correct!

Let’s look at each of these equations in a little more detail. We have:

Derivative of Lagrangian w.r.t. decision variables $x$ equal to zero $\to$ optimality conditions
Derivative of Lagrangian w.r.t. Lagrange multipliers $λ_{i}$ (equality constraints) $\to$ primal feasibility (solution is feasible with respect to the primal constraints)
Derivative of Lagrangian w.r.t. Lagrange multipliers $μ_{j}$ (inequality constraints) $\to$ primal feasibility
The multiplication of a Lagrange multiplier with its associated inequality constraint is zero $\to$ complementary slackness conditions (indicates that in some cases the inequality constraints might not be binding)
Lagrange multipliers $μ_{j}$ need to be positive or zero $\to$ dual feasibility

Let’s look more carefully at the interpretation of the complementary slackness conditions—the last two constraints in Equation (4.18):

(4.19)#

\begin{aligned} μ_{j} \cdot g_{j} (x) = 0 \forall j \in {1, 2, . . ., n} \\ μ_{j} \geq 0 \forall j \in {1, 2, . . ., n} \end{aligned}

If a constraint is binding, we can replace the inequality sign with an equality sign, so we have $g_{j} (x) = 0$ . Then, the Lagrange multiplier $μ_{j}$ may take on any non-zero value ( $μ_{j} \geq 0$ ). Since $g_{j} (x) = 0$ in this case, the constraint $μ_{j} \cdot g_{j} (x) = 0$ will be satisfied no matter the value of $μ_{j}$ . On the other hand, if the constraint is non-binding ( $g_{j} (x) < 0$ ), the Lagrange multiplier will equal zero ( $μ_{j} = 0$ ). Otherwise the constraint $μ_{j} \cdot g_{j} (x) = 0$ would be violated. This shows that an inequality constraint can only affect the optimal solution if it is binding. Note that these constraints are non-linear.

Now we want to find a solution to the set of equations (values for $x$ , $λ_{i}$ , and $μ_{j}$ ). For most, but not all, convex problems, these conditions are sufficient and necessary conditions for optimality, so the obtained solution would be an optimal solution (note once again, that KKT conditions can only be formulated for convex problems - this includes the kinds of problems we discuss here, purely linear problems and problems with a quadratic (nonlinear) objective function).

Condensed form of KKT conditions

Note that sometimes KKT conditions are written in condensed form:

(4.20)#

\begin{aligned} \nabla f (x) + \sum_{i = 1}^{m} λ_{i} \cdot \nabla h_{i} (x) + \sum_{j = 1}^{n} μ_{j} \cdot \nabla g_{j} (x) = 0 \\ μ_{j} \cdot g_{j} (x) = 0 \forall j \in {1, 2, . . ., n} \\ μ_{j} \geq 0 \forall j \in {1, 2, . . ., n} \end{aligned}

Let’s revisit the economic dispatch example and apply KKT conditions. In the standard form we want to use here, the constraints are written separately with a zero on the right-hand sign and “=” or “ $\leq$ ” signs:

(4.21)#

\begin{aligned} min. & a_{1} + b_{1} \cdot g_{1}^{2} + a_{2} + b_{2} \cdot g_{2}^{2} \\ s.t. & g_{1} + g_{2} - L = 0 & (λ) \\ - g_{1} \leq 0 & (μ_{1}) \\ g_{1} - \overset{―}{G_{1}} \leq 0 & (μ_{2}) \\ - g_{2} \leq 0 & (μ_{3}) \\ g_{2} - \overset{―}{G_{2}} \leq 0 & (μ_{4}) \end{aligned}

This makes it easy to write the Lagrangian, following Equation (4.17):

(4.22)#

\begin{aligned} L = & a_{1} + b_{1} \cdot g_{1}^{2} + a_{2} + b_{2} \cdot g_{2}^{2} + λ \cdot (g_{1} + g_{2} - L) \\ + μ_{1} \cdot (- g_{1}) + μ_{2} \cdot (g_{1} - \overset{―}{G_{1}}) \\ + μ_{3} \cdot (- g_{2}) + μ_{4} \cdot (g_{2} - \overset{―}{G_{2}}) \end{aligned}

Then we derive the KKT conditions:

(4.23)#

\begin{aligned} \frac{\partial L}{\partial g_{1}} = 2 \cdot b_{1} \cdot g_{1} + λ - μ_{1} + μ_{2} = 0 & (Optimality conditions) \\ \frac{\partial L}{\partial g_{2}} = 2 \cdot b_{2} \cdot g_{2} + λ - μ_{3} + μ_{4} = 0 & (Optimality conditions) \\ \frac{\partial L}{\partial λ} = g_{1} + g_{2} - L = 0 & (Primal feasibility (equality constraint)) \\ - g_{1} \leq 0 & (Primal feasibility (inequality constraint) \\ g_{1} - \overset{―}{G_{1}} \leq 0 & (Primal feasibility (inequality constraint) \\ - g_{2} \leq 0 & (Primal feasibility (inequality constraint) \\ g_{2} - \overset{―}{G_{2}} & (Primal feasibility (inequality constraint) \\ μ_{1} \cdot (- g_{1}) = 0 & (Complementary slackness conditions) \\ μ_{2} \cdot (g_{1} - \overset{―}{G_{1}}) = 0 & (Complementary slackness conditions) \\ μ_{3} \cdot (- g_{2}) = 0 & (Complementary slackness conditions) \\ μ_{4} \cdot (g_{2} - \overset{―}{G_{2}}) = 0 & (Complementary slackness conditions) \\ μ_{1}, μ_{2}, μ_{3}, μ_{4} \geq 0 & (Dual feasibility) \end{aligned}

Clearly, this is a large set of equations. This problem is not trivial to solve because the complementary slackness constraints are non-linear. For simple cases addressed in this course, we can solve the problem by using trial-and-error: “What if a certain constraint $g_{j} (x)$ is binding? Does that lead to a feasible solution? Is the solution optimal?” In this example, there are four inequality constraints so in theory there are 16 ( $= 2^{4}$ ) possible combinations. However, some combinations are not possible, for example if $g_{1} = 0$ , then $g_{1} \neq \overset{―}{G_{1}}$ . By trying different combinations of constraints, we come up with candidate solutions, then assess whether they are optimal or not.

Let’s look at the problem graphically (see Fig. 4.7). We assume that the feasible range of values for $g_{2}$ reduces so the original optimal solution (green dot) is no longer in the feasible set. By looking at the graph and reasoning, we can suppose that the upper capacity limit of $g_{2}$ will be binding. So, we will test the solution in which $g_{1}$ is producing somewhere in its operating range $0 < g_{1} < \overset{―}{G_{1}}$ (the inequality constraints are non-binding) and $g_{2}$ is operating at maximum capacity $g_{2} = \overset{―}{G_{2}}$ . The solution still needs to satisfy the equality constraint (be on the blue line).

../_images/KKT_g2const_graphical.png — Fig. 4.7 Graphical representation of the economic dispatch problem with reduced feasible range for $g_{2}$ #

Given this test solution, we know that $μ_{1}$ , $μ_{2}$ , $μ_{3}$ $= 0$ and $μ_{4} \neq 0$ . This simplifies the set of KKT conditions to:

(4.24)#

\begin{aligned} \frac{\partial L}{\partial g_{1}} = 2 \cdot b_{1} \cdot g_{1} + λ = 0 \\ \frac{\partial L}{\partial g_{2}} = 2 \cdot b_{2} \cdot g_{2} + λ + μ_{4} = 0 \\ \frac{\partial L}{\partial λ} = g_{1} + g_{2} - L = 0 \\ - g_{1} < 0 \\ g_{1} - \overset{―}{G_{1}} < 0 \\ g_{2} = \overset{―}{G_{2}} \\ μ_{1}, μ_{2}, μ_{3} = 0 \\ μ_{4} \geq 0 \end{aligned}

The only unknown variables are $g_{1}$ , $λ$ , and $μ_{4}$ , which we can solve for. If we can find a solution, it is optimal. We can also ask ourselves “Does the solution make sense? Is there an alternative set of binding inequality constraints that would yield a better solution?” to check that indeed we have found the optimal solution. The new solution—orange dot in Fig. 4.7—satisfies the constraints but comes at a higher total operating cost than before.

Ok, you might ask: what is this all good for? KKT conditions can help us find the optimal solutions to nonlinear problems (we don’t need them for linear problems), and we will apply them when looking at mixed complementarity problems in Section 6. But they also give us a different view on duality, and this is what we want to turn our attention to last.

4.3. The connection between duality and KKT conditions#

We know that for every primal problem, there exists a dual problem, but how do we formulate the dual problem?

Recall the general formulation of a primal problem:

(4.25)#

\begin{aligned} min. & f (x) \\ s.t. & h_{i} (x) = 0 (λ_{i}) \forall i \in {1, 2, . . ., m} \\ g_{j} (x) \leq 0 (μ_{j}) \forall j \in {1, 2, . . ., n} \end{aligned}

The Lagrangian is:

(4.26)#

L (x, λ, μ) = f (x) + \sum_{i = 1}^{m} λ_{i} \cdot h_{i} (x) + \sum_{j = 1}^{n} μ_{j} \cdot g_{j} (x)

The Lagrangian dual function, or dual function, is the minimum of the Lagrangian:

(4.27)#

D (λ, μ) = {inf}_{x} {L (x, λ, μ)} = {inf}_{x} {f (x) + \sum_{i = 1}^{m} λ_{i} \cdot h_{i} (x) + \sum_{j = 1}^{n} μ_{j} \cdot g_{j} (x)}

with “inf” a generalisation of the “min” operator.

The dual function defines a lower bound on the optimal value $p^{*}$ of the primal problem: $D (λ, μ) \leq p^{*}$ for any $μ \geq 0$ and any $λ$ . We want to find the best possible lower bound of the primal problem, which means maximising the lower bound:

(4.28)#

\begin{array}{r} \begin{aligned} max. & D (λ, μ) \\ s.t. & μ_{j} \geq 0 \forall j \in {1, 2, . . ., n} \end{aligned} \end{array}

This is the dual problem. We denote the optimal value of this problem as $d^{*}$ .

As mentioned at the beginning, strong duality is when the optimal value of the primal equals the optimal value of the dual. In our new terminology, this is written as $d^{*} = p^{*}$ . Strong duality can be used to show that a solution that satisfies the KKT conditions must be an optimal solution to the primal and dual problems. In other words, the KKT conditions are necessary and sufficient conditions for optimality.

Weak duality is when $d^{*} \leq p^{*}$ . This holds even for non-convex problems. In such problems, $p^{*} - d^{*}$ is referred to as the duality gap.

In practice, we do not need to start from the general expression in Equation (4.28) to derive the dual problem. Instead, we can simply follow the steps introduced above (Section 4.1.3): write the primal problem in standard form and then mechanistically translate it into its dual counterpart.

4.4. Further reading#

For more background on duality and to dive deeper into the mathematics, we suggest reading Chapter 5 of Boyd and Vandenberghe [2004] which is freely available online.

For alternative introductions to duality and KKT conditions based on a vector/matrix formulation, see Appendix B in Morales et al. [2014] (possibly available for free as an ebook if you are connected to a university network).

4.5. References#

[BV04]

Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, Cambridge, UK ; New York, 1st edition edition, March 2004. ISBN 978-0-521-83378-3.

[HL21] (1,2,3)

Frederick S. Hillier and Gerald J. Lieberman. Introduction to Operations Research. McGraw-Hill Education, New York, NY, 11th edition, 2021. ISBN 9781259872990.

[MCM+14]

Juan M. Morales, Antonio J. Conejo, Henrik Madsen, Pierre Pinson, and Marco Zugno. Integrating Renewables in Electricity Markets: Operational Problems. Volume 205 of International Series in Operations Research & Management Science. Springer US, Boston, MA, 2014. ISBN 978-1-4614-9410-2 978-1-4614-9411-9. doi:10.1007/978-1-4614-9411-9.