FE501 – NLP Summary

Convex and Concave Functions

Single variable case

\begin{matrix} (1) & \begin{matrix} \forall x \in S, f^{″} (x) \geq 0 \Rightarrow f (x) is convex \\ \forall x \in S, f^{″} (x) \leq 0 \Rightarrow f (x) is concave \end{matrix} \end{matrix}

Multiple variable case

\begin{matrix} (2) & \begin{matrix} H = [\begin{matrix} a & d \\ c & b \end{matrix}] \\ P M_{1}^{(1)} = a, \\ P M_{1}^{(2)} = b, \\ P M_{2} = a \times b - c \times d \end{matrix} \end{matrix}

\begin{matrix} (3) & \begin{matrix} \forall (x_{1}, \dots, x_{n}) \in S, P M_{k} \geq 0 \Rightarrow f (x_{1}, \dots, x_{n}) is convex \\ \forall (x_{1}, \dots, x_{n}) \in S, (- 1)^{k} \cdot P M_{k} \geq 0 \Rightarrow f (x_{1}, \dots, x_{n}) is concave \end{matrix} \end{matrix}

Solving NLP with one variables

\begin{matrix} (4) & \begin{matrix} max (min) f (x) \\ s . t . x \in [a, b] \end{matrix} \end{matrix}

Step 1 : find all stationary points.
Find other points where f’(x) dose not exist.
$\infin$ )

\begin{matrix} (5) & \begin{matrix} if f^{'} (x_{0}) = 0, f^{″} (x_{0}) < 0, a < x_{0} < b \Rightarrow x_{0} is local max \\ if f^{'} (x_{0}) = 0, f^{″} (x_{0}) > 0, a < x_{0} < b \Rightarrow x_{0} is local min \end{matrix} \end{matrix}

Unconstrained NLPs with multiple variables

\begin{matrix} (6) & \begin{matrix} max (o r min) f (x_{1}, \dots, x_{n}) \\ s . t . (x_{1}, \dots, x_{n}) \in R \end{matrix} \end{matrix}

$\bar x$ ) :

\begin{matrix} (7) & \begin{matrix} let f^{'} = 0 to get \bar{x} \\ if H_{k} (\bar{x}) > 0 \Rightarrow \bar{x} is a local min \\ if (- 1)^{k} \cdot H_{k} (\bar{x}) > 0 \Rightarrow \bar{x} is a local max \end{matrix} \end{matrix}

Constrained NLPs with multiple variables

Equality (Lagrangian)

\begin{matrix} (8) & \begin{matrix} max (o r min) f (x_{1}, \dots, x_{n}) \\ s . t . h_{1} (x_{1}, \dots, x_{n}) = b_{1} \\ h_{2} (x_{1}, \dots, x_{n}) = b_{2} \\ \dots \\ h_{m} (x_{1}, \dots, x_{n}) = b_{m} \end{matrix} \end{matrix}

Write Lagrangian function

\begin{matrix} (9) & \begin{matrix} min L = f + \sum_{i = 1}^{m} λ_{i} (h_{i} - b_{i}) \\ max L = f + \sum_{i = 1}^{m} λ_{i} (b_{i} - h_{i}) \end{matrix} \end{matrix}

Solve

\begin{matrix} (10) & \begin{matrix} \frac{\partial L}{\partial x_{i}} = 0 \\ \frac{\partial L}{\partial λ} = 0 \end{matrix} \end{matrix}

Inequality (KKT)

\begin{matrix} (11) & \begin{matrix} max (o r min) f (x_{1}, \dots, x_{n}) \\ s . t . g_{1} (x_{1}, \dots, x_{n}) = b_{1} \\ g_{2} (x_{1}, \dots, x_{n}) \leq= b_{2} \\ \dots \\ g_{m} (x_{1}, \dots, x_{n}) \leq b_{m} \end{matrix} \end{matrix}

Then write Lagrangian function

\begin{matrix} (12) & \begin{matrix} min L = f + \sum_{i = 1}^{m} μ_{i} (g_{i} - b_{i}) \\ max L = f + \sum_{i = 1}^{m} μ_{i} (b_{i} - g_{i}) \end{matrix} \end{matrix}

Then write KKT conditions and solve:

$\part f / \part x_i = 0$
$g_i \le b_i$
$\mu (g_i - b_i) = 0 \ \text{(min)}$
$\mu \ge 0$

Important Notice from Hocam:

In contrained NLPs you cannot check the type of the candidate point by evaluating the Hessian matrix as we do in unconstrained optimization. We determined the local maximality of the point by evaluating some neighboring points. There is a method called restricted Lagrangean, but beyond the material we cover in this class