Convex Optimization - Fritz-John Conditions

Advertisements

Previous Page
Next Page  

Necessary Conditions

Theorem

Consider the problem − $min f\left ( x \right )$ such that $x \in X$ where X is an open set in $\mathbb{R}^n$ and let $g_i \left ( x \right ) \leq 0, \forall i =1,2,....m$.

Let $f:X \rightarrow \mathbb{R}$ and $g_i:X \rightarrow \mathbb{R}$

Let $\hat{x}$ be a feasible solution and let f and $g_i, i \in I$ are differentiable at $\hat{x}$ and $g_i, i \in J$ are continuous at $\hat{x}$.

If $\hat{x}$ solves the above problem locally, then there exists $u_0, u_i \in \mathbb{R}, i \in I$ such that $u_0 \bigtriangledown f\left ( \hat{x} \right )+\displaystyle\sum\limits_{i\in I} u_i \bigtriangledown g_i \left ( \hat{x} \right )$=0

where $u_0,u_i \geq 0,i \in I$ and $\left ( u_0, u_I \right ) \neq \left ( 0,0 \right )$

Furthermore, if $g_i,i \in J$ are also differentiable at $\hat{x}$, then above conditions can be written as −

$u_0 \bigtriangledown f\left ( \hat{x}\right )+\displaystyle\sum\limits_{i=1}^m u_i \bigtriangledown g_i\left ( \hat{x} \right )=0$

$u_ig_i\left (\hat{x} \right )$=0

$u_0,u_i \geq 0, \forall i=1,2,....,m$

$\left (u_0,u \right ) \neq \left ( 0,0 \right ), u=\left ( u_1,u_2,s,u_m \right ) \in \mathbb{R}^m$

Remarks

  • $u_i$ are called Lagrangian multipliers.

  • The condition that $\hat{x}$ be feasible to the given problem is called primal feasible condition.

  • The requirement $u_0 \bigtriangledown f\left (\hat{x} \right )+\displaystyle\sum\limits_{i=1}^m u-i \bigtriangledown g_i\left ( x \right )=0$ is called dual feasibility condition.

  • The condition $u_ig_i\left ( \hat{x} \right )=0, i=1, 2, ...m$ is called complimentary slackness condition. This condition requires $u_i=0, i \in J$

  • Together the primal feasible condition, dual feasibility condition and complimentary slackness are called Fritz-John Conditions.

Sufficient Conditions

Theorem

If there exists an $\varepsilon$-neighbourhood of $\hat{x}N_\varepsilon \left ( \hat{x} \right ),\varepsilon >0$ such that f is pseudoconvex over $N_\varepsilon \left ( \hat{x} \right )\cap S$ and $g_i,i \in I$ are strictly pseudoconvex over $N_\varepsilon \left ( \hat{x}\right )\cap S$, then $\hat{x}$ is local optimal solution to problem described above. If f is pseudoconvex at $\hat{x}$ and if $g_i, i \in I$ are both strictly pseudoconvex and quasiconvex function at $\hat{x},\hat{x}$ is global optimal solution to the problem described above.

Example

  • $min \:f\left ( x_1,x_2 \right )=\left ( x_1-3 \right )^2+\left ( x_2-2 \right )^2$

    such that $x_{1}^{2}+x_{2}^{2} \leq 5, x_1+2x_2 \leq 4, x_1,x_2 \geq 0$ And $\hat{x}=\left ( 2,1 \right )$

    Let $g_1\left (x_1,x_2 \right )=x_{1}^{2}+x_{2}^{2} -5,$

    $g_2\left (x_1,x_2 \right )=x_1+2x_2-4,$

    $g_3\left (x_1,x_2 \right )=-x_1$ and $g_4\left ( x_1, x_2 \right )= -x_2$.

    Thus the above constraints can be written as −

    $g_1\left (x_1,x_2 \right )\leq 0,$

    $g_2\left (x_1,x_2 \right )\leq 0,$

    $g_3\left (x_1,x_2 \right )\leq 0$ and

    $g_4\left (x_1,x_2 \right )\leq 0$ Thus, $I = \left \{1,2 \right \}$ therefore, $u_3=0,u_4=0$

    $\bigtriangledown f \left (\hat{x} \right )=\left (2,-2 \right ),\bigtriangledown g_1\left (\hat{x} \right )=\left (4,2 \right )$ and $\bigtriangledown g_2\left (\hat{x} \right )=\left (1,2 \right )$

    Thus putting these values in the first condition of Fritz-John conditions, we get −

    $u_0=\frac{3}{2} u_2, \:\:u_1= \frac{1}{2}u_2,$ and let $u_2=1$, therefore $u_0= \frac{3}{2},\:\:u_1= \frac{1}{2}$

    Thus Fritz John conditions are satisfied.

  • $min f\left (x_1,x_2\right )=-x_1$.

    such that $x_2-\left (1-x_1\right )^3 \leq 0$,

    $-x_2 \leq 0$ and $\hat{x}=\left (1,0\right )$

    Let $g_1\left (x_1,x_2 \right )=x_2-\left (1-x_1\right )^3$,

    $g_2\left (x_1,x_2 \right )=-x_2$

    Thus the above constraints can be wriiten as −

    $g_1\left (x_1,x_2 \right )\leq 0,$

    $g_2\left (x_1,x_2 \right )\leq 0,$

    Thus, $I=\left \{1,2 \right \}$

    $\bigtriangledown f\left (\hat{x} \right )=\left (-1,0\right )$

    $\bigtriangledown g_1 \left (\hat{x} \right )=\left (0,1\right )$ and $g_2 \left (\hat{x} \right )=\left (0, -1 \right )$

    Thus putting these values in the first condition of Fritz-John conditions, we get −

    $u_0=0,\:\: u_1=u_2=a>0$

    Thus Fritz John conditions are satisfied.

Advertisements