uni
Questo è un metodo di risoluzione del Problema di Programmazione Non Lineare (PNL).

Teorema della Proiezione

La matrice $H$ è la matrice di Proiezione, e $Hy$ è la proiezione di $y$ su $M$ .

Algoritmo per MAX

trovo la matrice $M$ , ovvero la matrice formata dalle righe dei vincoli attivi di $A$ (dominio di forma $A x \leq b$ ) in $x^{k}$ .
Calcolo la matrice $H$

H = {I se x^{k} n o n ha v in co l i a tt i v i I - M^{T} (M M^{T})^{- 1} M

calcolo la direzione

d^{k} = H \cdot \nabla f (x^{k})

se $d^{k} = 0$ vai al punto 3ª
4. calcolo il passo massimo

\hat{t}_{k} = {max t A (x^{k} + t \cdot d^{k}) \leq b

calcolo il passo effettivo

t_{k} \in a r g ma x_{t \in [0; \hat{t}_{k}]} ϕ (t)

con $ϕ (t) = f (x^{k} + t \cdot d^{k})$
6. calcolo il nuovo punto

x^{k + 1} = x^{k} + t_{k} \cdot d^{k}

3ª. se $d^{k} = 0$ :
1. calcolo

λ = - (M M^{T})^{- 1} M \cdot \nabla f (x^{k})

2. se $\lambda≤0$ allora $x^k$ risolve $LKKT$ 
3. altrimenti sia $j:\lambda_j=\max_{i\in[0;k]} \lambda_i$ , sappiamo che è $>0$ 
4. elimino la riga $j$ da $M$ e ritorno al passo ___2___.

Algoritmo per MIN

oppure applico l’algoritmo per il massimo a $- f$ .

trovo la matrice $M$ , ovvero la matrice formata dalle righe dei vincoli attivi di $A$ (dominio di forma $A x \leq b$ ) in $x^{k}$ .
Calcolo la matrice $H$

H = {I se x^{k} n o n ha v in co l i a tt i v i I - M^{T} (M M^{T})^{- 1} M

calcolo la direzione

d^{k} = H \cdot (- \nabla f (x^{k}))

se $d^{k} = 0$ vai al punto 3ª
4. calcolo il passo massimo

\hat{t}_{k} = {max t A (x^{k} + t \cdot d^{k}) \leq b

calcolo il passo effettivo

t_{k} \in a r g mi n_{t \in [0; \hat{t}_{k}]} ϕ (t)

con $ϕ (t) = f (x^{k} + t \cdot d^{k})$
6. calcolo il nuovo punto

x^{k + 1} = x^{k} + t_{k} \cdot d^{k}

3ª. se $d^{k} = 0$ :
1. calcolo

λ = - (M M^{T})^{- 1} M \cdot \nabla f (x^{k})

2. se $\lambda≥0$ allora $x^k$ risolve $LKKT$ 
3. altrimenti sia $j:\lambda_j=\min_{i\in[0;k]} \lambda_i$ 
4. elimino la riga $j$ da $M$ e ritorno al passo ___2___.