# Lecture 8, Optimality conditions

We are still studying the full problem
$$
\begin{align} \
\min \quad &f(x)\\
\text{s.t.} \quad & g_j(x) \geq 0\text{ for all }j=1,\ldots,J\\
& h_k(x) = 0\text{ for all }k=1,\ldots,K\\
&x\in \mathbb R^n.
\end{align}
$$

In order to identify which points are optimal, we want to define similar conditions as there are for unconstrained problems through the gradient:

>If $x$ is a  local optimum to function $f$, then $\nabla f(x)=0$.

## KKT conditions



**Theorem (First order Karush-Kuhn-Tucker (KKT) Necessary Conditions)** Let $x^**$ be a local minimum for problem
$$
$$
\begin{align} \
\min \quad &f(x)\\
\text{s.t.} \quad & g_j(x) \geq 0\text{ for all }j=1,\ldots,J\\
& h_k(x) = 0\text{ for all }k=1,\ldots,K\\
&x\in \mathbb R^n.
\end{align}
$$
$$

and assume that $x^*$ satisfies some regularity conditions (see e.g., https://en.wikipedia.org/wiki/Karush%E2%80%93Kuhn%E2%80%93Tucker_conditions#Regularity_conditions_.28or_constraint_qualifications.29). Then there exists unique Lagrance multiplier vectors $\lambda^* = (\lambda^*_1,\ldots,\lambda_J^*)$ and $\mu^*=(\mu_1^*,\ldots,\mu_K^*)$ such that
$$
\begin{align}
&\nabla_xL(x,\lambda,\mu) = 0\\
&\mu_j^*\geq0,\text{ for all }j=1,\ldots,J\\
&\mu_j^*g_j(x)=0,\text{for all }j=1,\ldots,J,
\end{align}
$$
where $$L(x,\lambda,\mu) = f(x)- \sum_{k=1}^K\mu_kg_k(x) -\sum_{j=1}^J\lambda_jh_j(x)$$ and $A(x^*)$ is the set of active constraints at $x^*$.

The coefficients $\lambda$ and $\mu$ are called the KKT multipliers.

The first equality $\nabla_xL(x,\lambda,\mu) = 0$ is called stationary rule and the requirement $\mu_j^*g_j(x)=0,\text{for all }j=1,\ldots,J$ is called the complementary rule.

## Example

Consider the optimization problem
$$
\begin{align}
\min &\qquad (x_1^2+x^2_2+x^2_3)\\
\text{s.t}&\qquad -3+x_1+x_2+x_3\geq 0.
\end{align}
$$
Let us verify the KKT necessary conditions for the local optimum $x^*=(1,1,1)$.

We can see that
$$
L(x,\lambda,\mu) = (x_1^2+x_2^2+x_3^3)+\mu_1(3-x_1-x_2-x_3)
$$
and thus
$$
\nabla_x L(x,\lambda,\mu) = (2x_1-\mu_1,2x_2-\mu_1,2x_3-\mu_1)
$$
and if $\nabla_x L((1,1,1),\lambda,\mu)=0$, then 
$$
2-\mu_1=0 $$
which holds when $$
\mu_1=2.
$$
In addition to this, we can see that $-3+x^*_1+x^*_2+x^*_3= 0$. Thus, the completementary rule holds even though $\mu_1\neq 0$.

## Example 2

Let us check the KKT for a solution that is not a local optimum. Let us have $x^*=(0,1,1)$.

We can easily see that in this case, the conditions are 

$$\left\{
\begin{array}{c}
-\mu_1 = 0\\
2-\mu_1=0
\end{array}
\right.
$$
Clearly, there does not exist a $\mu_1\in \mathbb R$ such that these equalities would hold.

## Example 3

Let us check the KKT for another solution that is not a local optimum. Let us have $x^*=(2,2,2)$.

We can easily see that in this case, the conditions is
$$
4-\mu_1 = 0
$$
Now, $\mu_1=4$ satisfies this equation. However, now
$$
\mu_1(-3+x^*_1+x^*_2+x^*_3)=4(-3+6) = 12 \neq 0.
$$
Thus, the completementary rule fails and the KKT conditions are not true.

## Geometric interpretation of the KKT conditions

## Stationary rule

The stationary rule can be written as, there exist $\lambda',\mu$ so that
$$
-\nabla f(x) = -\sum_{j=1}^K\mu_j\nabla g_j(x) + \sum_{k=1}^K\lambda'_k\nabla h_k(x).
$$
Notice that we have slightly different $\lambda'$.

Now, remember that the $-\nabla v(x)$ gives us the direction of reduction of the function $v$ for all functions.

Thus, the above equation means that the direction of reduction of the function $-\nabla f(x)$ is countered by the direction of the reduction of the inequality constraints $-\nabla g_j(x)$ and the directions of either growth (or reduction, since $\lambda'$ can be negative) of the equality constraints $\nabla h_k(x)$.

**This means that the function cannot get reduced without reducing the inequality constraints (making the solution infeasible, if already at the bound), or increasing or decreasing the equality constraints (making, thus, the solution again infeasible).**



#### With just one inequality constraint this means that the negative gradients of $f$ and $g$ must point to the same direction.



#### With equality constraints this means that the negative of the function and the gradiemt of the equality constraint must either to the same or opposite directions



## Complementary conditions
Another way of saying complementary condition
$$
\mu_jg_j(x) = 0 \text{ for all } j=1,\ldots,J
$$
is to say that both $\mu_j$ and $g_j(x)$ cannot be positive at the same time. Especially, if $\mu_j>0$, then $g_j(x)=0$.

**This means that if we want to use the gradient of a constraint for countering the reduction of the function, then the constraint must be at the border.**

3e7c47f20495799bc1dd7765ff1bbcb45c0212d6
ipynb
Jupyter Notebook
Lecture 8, optimality conditions.ipynb
maeehart/TIES483
cce5c779aeb0ade5f959a2ed5cca982be5cf2316
CC-BY-3.0
2019-04-26T12:46:14.000Z
2021-11-23T03:38:59.000Z
Lecture 8, optimality conditions.ipynb
maeehart/TIES483
cce5c779aeb0ade5f959a2ed5cca982be5cf2316
CC-BY-3.0
Lecture 8, optimality conditions.ipynb
maeehart/TIES483
cce5c779aeb0ade5f959a2ed5cca982be5cf2316
CC-BY-3.0
2016-01-08T16:28:11.000Z
2021-04-10T05:18:10.000Z
Qwen/Qwen-72B
1. YES
2. YES