Optimisation
Suppose f, g_1, g_2, …, g_m are differentiable.
$$ \max_{x_1, x_2,…, x_n} f(x_1, x_2, …, x_n) $$
$$s.t. g_1(x_1, x_2, …, x_n)\geq 0 $$
$$\quad g_2(x_1, x_2, …, x_n)\geq 0 $$
$$\quad ……$$
$$\quad g_m(x_1, x_2, …, x_n)\geq 0 $$
There are m constraints g_i, i \in (1,m), and one object function f to maximum. n variables.
KKT Conditions
Suppose the constraint qualification is satisfied. A local maximiser of the above problem \bar{x} = (\bar{x_1}, \bar{x_2},… \bar{x_n}) together with some \bar{lambda_1}, \bar{lambda_2}, …, \bar{lambda_m} \geq 0 satisfies the following:
$$ \frac{\partial f}{\partial x_i}(\bar{x}) + \lambda_1 \frac{\partial g_1}{\partial x_i}(\bar{x})+ \lambda_2 \frac{\partial g_2}{\partial x_i}(\bar{x}) +…+ \lambda_{m} \frac{\partial g_m}{\partial x_i}(\bar{x}) = 0$$
for i=1,2,…,n, and
$$\bar{\lambda_k} g_k(\bar{x})=0$$
for k=1,2,…,m
- We have state “Suppose the constraint qualification is satisfied” in the beginning. What is the qualification?
See step 4 in the next section.
Solve the Maximisation Problem
- Step 1. Step up the Lagrangian
- Step 2. Write down the KKT conditions and constraints.
- Step 3. Solve the equation set. (P.S. Discuss the complementary slackness, and confirm the possible solutions)
- Step 4. Check constraint qualification.
- Step 4.
Constraint Set, C=\{ (x_1, x_2, …, x_n)\in \mathbb{R}^n | g_k(x_1, x_2, …, x_m) \geq 0 \} for k=1,2,…,m.
The constraint qualification is satisfied at \bar{x} in C, if the constraints that hold at \bar{x} with equality are independent. That is, if the m vectors
$$ \nabla g_k(\bar{x})=\bigg( \frac{\partial g_k}{\partial x_1}(\bar{x}), \frac{\partial g_k}{\partial x_2}(\bar{x}),…,\frac{\partial g_k}{\partial x_n}(\bar{x}) \bigg)’ $$
for k=1,2,…,m are independent.