Appunti del Corso di Controlli II – Teoria dell’ottimizzazionewpage.unina.it/framato/materiale...

Francesco Amato

Appunti del Corso di “Sistemi di Controllo Multivariabile”

Elementi di Teoria dell’ottimizzazione

A.A. 2010-11 – Università degli Studi di Napoli Federico II

Versione 1.2 Novembre 2011

1 Introduzione ................................................................................................................................. 2

2 Formulazione di alcuni problemi decisionali in termini di problemi di programmazione

matematica ........................................................................................................................................... 6

2.1 Ottimizzazione della portanza di una superficie mobile ...................................................... 6

2.2 Gestione ottimale di centrali elettriche interconnesse .......................................................... 6

2.3 Soluzione di un sistema di equazioni lineari ........................................................................ 7

3 Definizioni preliminari ................................................................................................................. 8

4 Programmazione non lineare: metodi analitici .......................................................................... 13

4.1 Condizioni necessarie di minimo locale ............................................................................ 14

4.2 Condizioni necessarie e condizioni sufficienti di minimo locale per un problema non

vincolato ......................................................................................................................................... 15

4.3 Problemi con vincoli di uguaglianza .................................................................................. 17

4.4 Un primo problema con vincoli di uguaglianza: Funzione obiettivo di tipo quadratico e

funzioni di vincolo di tipo lineare. Pseudoinversa minima a destra .............................................. 22

4.4.1 Una applicazione della pseudoinversa minima a destra ad un problema di

raggiungibilità ............................................................................................................................ 24

4.5 Un secondo problema con vincoli di uguaglianza: Funzione obiettivo di tipo quadratico

dipendente implicitamente dalla variabile di ottimizzazione e funzioni di vincolo di tipo lineare.

Pseudoinversa minima a sinistra .................................................................................................... 25

4.5.1 Una applicazione della pseudoinversa minima a sinistra: stima parametrica a minimi

quadrati 28

4.5.2 Identificazione della risposta armonica ...................................................................... 29




Versione 1.2 Novembre 2011 – Francesco Amato

1

4.6 Problemi con vincoli di uguaglianza e disuguaglianza ...................................................... 31

5 Appendice A .............................................................................................................................. 35





2

1 Introduzione

Le tecniche di controllo basate sulla retroazione di stato, laddove questo sia interamente misurabile,

o di uscita, mediante l’uso di osservatori, se da un lato permettono di allocare in posizione

opportuna i poli del sistema a ciclo chiuso e quindi di agire sulla velocità di risposta e sulla

sovraelongazione, dall’altro, non essendo agevole la traduzione di alcune specifiche, quali la

moderazione delle grandezze in gioco (variabili di controllo e di stato), nel dominio del tempo, non

consentono di portare in conto all’atto della sintesi tali specifiche.

Per ovviare a tali inconvenienti è necessario portare in conto tutte le specifiche richieste attraverso

la definizione di una funzione obiettivo e/o di opportuni vincoli; il progetto della legge di controllo

va dunque effettuato in modo che essa ottimizzi tale indice e contemporaneamente soddisfi, se

presenti, preassegnati vincoli sulle variabili di interesse.

A questo proposito, si consideri un processo fisico descritto dalle equazioni

],[)()(),,( 00 fn ttttRtt 0xxxuxfx

Eq. (1.1)

Il problema del controllo ottimo si può porre in questi termini: trovare la legge di controllo

ftt ,0u per il sistema descritto dalle Eq. (1.1) che

a) porti lo stato terminale del sistema in una assegnata regione dello spazio di stato,

individuata dall’equazione s(x)0;

b) soddisfi un indice di qualità scalare del tipo ftJ ,,, fxux , dove xf=x(tf);

c) soddisfi determinati vincoli sulle variabili di ingresso u e/o di stato x, individuati da

equazioni e disequazioni del tipo g(x(t),u(t))=0 e h(x(t),u(t))0.

Successivamente si mostrerà che, sotto opportune ipotesi, la legge di controllo ottimale si può

realizzare utilizzando una retroazione di stato, pervenendo dunque allo schema di Figura 1.1.





3

Figura 1.1: Retroazione di stato

Laddove lo stato non fosse disponibile per la retroazione si può far ricorso ad una retroazione

dell’uscita tramite osservatore. Dunque il punto chiave sarà quello di esprimere la legge di controllo

ottimo attraverso una retroazione di stato.

Per il momento focalizzeremo la discussione sul problema dell’ottimizzazione. In virtù di quanto

affermato sopra esso si può formalizzare come segue.

Problema 1.1

0uxh

0uxg

0xs

xxuxfx

xux

f

0

fu

))(),((

)(),(

],[)(),,(

.

,),(),(min

00

],[ 0

tt

tt

ttttt

as

tJ

f

ftt f

Il Problema 1.1 è un classico problema di ottimizzazione dinamica che si può risolvere utilizzando i

principi del calcolo variazionale.

Processo

x

Controllore w u





4

La teoria dell’ottimizzazione dinamica è abbastanza complicata e non verrà affrontata in queste

note. Ciò è giustificato dal fatto che, in molte situazioni, è possibile fare una serie di ipotesi

semplificative che permettono di trasformare il Problema 1.1 in un problema di tipo statico. Tali

ipotesi possono riassumersi come segue:

a) il sistema considerato è stazionario, cioè ),(),,( uxfuxf t ;

b) siamo interessati al comportamento del sistema a regime. Dunque l’indice di costo non

dipenderà più dallo stato e dall’istante terminale, in quanto tf=+ , ed inoltre non dipenderà

più dai valori assunti istante per istante dall’ingresso e dallo stato, ma solo dai valori che

questi assumono a regime; dunque uxxux f ,,),(),( JtJ f . Inoltre a regime

l’equazione differenziale che descrive il modello del processo viene sostituita da una

equazione statica, in quanto lo stato raggiungerà il suo valore di equilibrio; in altri termini

l’equazione del modello diventa f(x,u)=0. Allo stesso modo i vincoli non dipenderanno più

dal tempo, potendosi scrivere

0uxh

0uxg

),(

, .

Il problema di ottimizzazione, sotto le ipotesi semplificative a) e b) può dunque riscriversi nel modo

seguente.

Problema 1.2

0uxh

0uxg

uxu

),(

,

.

,min

as

J

avendo inglobato nella condizione 0uxg ),( anche la condizione 0uxf ),( .





5

E’ evidente che una volta che è stata trovata la legge di controllo ottimo a regime, bisogna

comunque assicurarsi che tale legge di controllo esibisca buone prestazioni durante il transitorio.

In definitiva un problema di controllo ottimo di tipo generale può riportarsi, sotto le condizioni a) e

b) e inglobando per semplicità di notazione u nel vettore x, ad un problema del tipo seguente.

Problema 1.3

nRX

as

x

xfx

.

min

dove 0xh0xgx )(,)(,nRX .

L’insieme delle metodologie orientate alla soluzione dei problemi statici del tipo Problema 1.3 va

sotto il nome di Programmazione Matematica (PM).

I problemi di programmazione matematica possono suddividersi in lineari e non lineari.

Definizione 1.1

Un problema di programmazione matematica si dice lineare se le funzioni hgf ,, sono lineari.

Altrimenti si dice non lineare.

Nel seguito tratteremo alcune tecniche per la soluzione dei problemi di programmazione non

lineare, dato che la maggior parte dei problemi di controllo ricade in questa categoria. Tali tecniche

si dividono in analitiche e numeriche. Le prime si utilizzano quando si è in presenza di poche

variabili di ottimizzazione e avendo a disposizione l’espressione analitica delle funzioni coinvolte;

le seconde entrano in gioco per problemi di grosse dimensioni e/o quando la funzione obiettivo o i

vincoli non sono esprimibili in forma chiusa.





6

2 Formulazione di alcuni problemi decisionali in termini di problemi di

programmazione matematica

2.1 Ottimizzazione della portanza di una superficie mobile

Si consideri una superficie di sezione S che si muova in un fluido di tipo Newtoniano con velocità

costante v ; indichiamo con l’angolo formato dalla superficie S con il vettore v (si veda la Figura

2.1). La superficie S sarà sottoposta ad una forza che si oppone al movimento e diretta in direzione

opposta al vettore v (resistenza) e in una forza diretta verso l’alto ortogonalmente a v (portanza L).

Figura 2.1:Portanza di una superficie mobile

Si intuisce che L sarà nulla tanto per =0 che per =/2. In effetti, sotto opportune ipotesi

semplificative si può dimostrare che risulta

cossin2kL

dove k è una costante che dipende da S, |v| e dal tipo di fluido in cui è immersa la superficie. Il

problema è allora quello di trovare il valore di che massimizzi il modulo di L. La soluzione di

questo problema è mostrata in Appendice A, Problema 5.3.

2.2 Gestione ottimale di centrali elettriche interconnesse

Il fabbisogno di potenza elettrica di un utente può porsi nella forma

)(tPPP pr

S

v

L





7

dove Pr è detta potenza di base e può ritenersi pressoché costante durante il giorno, mentre Pp(t),

detta potenza di picco, dipende dalla richiesta dell’utente all’istante t e quindi è di natura stocastica

e tempo-variante.

Supponiamo che per generare la potenza di base Pr si ricorra al contributo di n centrali elettriche

interconnesse. La centrale i-esima eroga una potenza pi e ha un costo di gestione ci(pi). In genere le

funzioni ci(pi) si possono approssimare come segue

iiiii bpapc 2 .

Si vuole minimizzare la spesa complessiva delle n centrali, soddisfacendo la richiesta dell’utenza.

Denotando con Tnppp 21p il problema può formularsi in questo modo

iMi

n

iri

n

iii

pp

Pp

as

pc

0

.

)(min

1

1p

Si veda il Problema 5.4 per una applicazione numerica.

2.3 Soluzione di un sistema di equazioni lineari

Si supponga di dover risolvere il seguente sistema di equazioni lineari

0,

0,

212

211

xxf

xxf.

Si osservi che tutte le soluzioni della prima equazione sono anche soluzioni dell’equazione

0, 212

1 xxf

Eq. (2.1)





8

Ovviamente una soluzione Txx 21* x della Eq. (2.1) è anche minimo globale di 212

1 , xxf .

Pertanto il problema di trovare le soluzioni del sistema di equazioni è equivalente al seguente

problema di ottimizzazione

0),(

.

),(min

212

212

1

xxf

as

xxfx

o, in maniera equivalente

0),(

.

),(min

211

212

2

xxf

as

xxfx

.

3 Definizioni preliminari

Definizione 3.1 [Minimo locale]

Data la funzione RRXf n x: , si dice che un punto X*x è di minimo locale per f se

esiste un intorno *xI del punto *x tale che )(*)( xx ff per ogni *xx I .

Definizione 3.2 [Minimo globale]

Data la funzione RRXf n x: , si dice che un punto X*x è di minimo globale per f se

)(*)( xx ff per ogni Xx .

Definizione 3.3 [Gradiente]

Data la funzione RRXf n x: , si chiama gradiente di f il vettore colonna

T

nx

f

x

f

x

ffgrad

21x .

Definizione 3.4 [Matrice Hessiana]





9

Data la funzione RRXf n x: , si chiama matrice Hessiana di f la seguente matrice

quadrata

2

2

2

2

1

2

2

2

22

2

12

21

2

21

2

21

2

nnn

n

n

f

x

f

xx

f

xx

f

xx

f

x

f

xx

f

xx

f

xx

f

x

f

H

La matrice Hessiana risulta essere simmetrica quando sono soddisfatte le ipotesi del Teorema di

Schwartz.

Definizione 3.5 [Jacobiano]

Data la funzione vettoriale mn RRX xg : , si chiama Jacobiano di g la seguente matrice

Tmx

Tx

Tx

n

mmm

n

n

ggrad

ggrad

ggrad

x

g

x

g

x

g

x

g

x

g

x

g

x

g

x

g

x

g

2

1

21

2

2

2

1

2

1

2

1

1

1

x

g

Si consideri ora una funzione mn RR xg : ; l’insieme dei punti 0: xgxnRS

definisce una iper - superficie in Rn. Si dà la seguente definizione.

Definizione 3.6 [Piano tangente]

Si assuma che la funzione mn RR xg : sia derivabile in x; si definisce piano tangente in x alla

iper - superficie S l’insieme dei punti

0: yx

x

gy

nRM .





10

In altri termini il piano tangente è composto da tutti i vettori yRn che sono ortogonali ai gradienti

delle funzioni gi(x), i=1,…,m, che definiscono la iper – superficie S .

Definizione 3.7 [Matrice semidefinita e definita positiva]

Una matrice quadrata e simmetrica nnR Q si dice essere semidefinita positiva (negativa), e si

scrive Q0 (Q0) quando

nR xQxxT 0)( ;

si dice essere definita positiva (negativa), e si scrive Q>0 (Q<0), quando

0xQxxT nR0)( .

Nel seguito sono formulate alcune condizioni affinché una matrice sia definita (semidefinita)

positiva. Ricordiamo, a questo proposito, che gli autovalori di una matrice simmetrica sono tutti

reali.

Teorema 3.1 [CNES affinché una matrice sia definita positiva]

Una matrice nnR Q risulta essere definita (semidefinita) positiva se e solo se tutti gli autovalori

sono maggiori (maggiori o uguali) di zero.

Dimostrazione.

Data una matrice simmetrica Q esiste sempre una matrice ortogonale1

nnR n21 uuuT , TTT 1 tale che

ΛQTT T

Eq. (3.1)

dove ),,,( 21 ndiag Λ , Ri è l’i-esimo autovalore di Q e ui è il corrispondente

autovettore. Inoltre T, essendo ortonormale, gode della proprietà che 0jTi uu se ji e

12 ii

Ti uuu .

1 Una matrice

nnR T si dice ortogonale se risulta ITTT .





11

Dalla Eq. (3.1) segue che

n

i

T

iii

T

n

T

T

n

n

T

1

2

1

2

1

21

00

00

00

uu

u

u

u

uuu

TΛQT

da cui si ha

n

iii

n

i

T

iii

n

i

Tiii

1

2

1

1

ux

uxux

xuuxQxx

T

TT

TT

Eq. (3.2)

Dall’ultima uguaglianza si ricava che se i>0, i=1,…,n, evidentemente xTQx>0 per ogni x0;

infatti sicuramente xT ui0 per qualche i, essendo x0 e i vettori ui linearmente indipendenti.

D’altro canto se per qualche i risultasse i<0 ponendo x=ui si avrebbe dalla Eq. (3.2) che

0

2

i

i

iT

uQxx

che contraddirebbe il fatto che xTQx è definita positiva.

Teorema 3.2 [Test di Sylvester –Matrici definite]

Una matrice nnR Q risulta essere definita positiva se e solo se tutti i suoi minori principali sono

maggiori di zero, cioè

011 q





12

02212

1211

qq

qq

0

21

22212

11211

nnnn

n

n

qqq

qqq

qqq

Teorema 3.3 [Test di Sylvester – Matrici semidefinite]

Una matrice nnR Q risulta essere semidefinita positiva se e solo se tutti i suoi minori i cui

elementi diagonali sono anche elementi diagonali di Q sono maggiori o uguali a zero; ad esempio

una matrice 33RQ risulta essere semidefinita positiva se e solo se

0,, 332211 qqq

0,,3323

2322

3313

1311

2212

1211

qq

qq

qq

qq

qq

qq

0

332313

232212

131211

qqq

qqq

qqq

Si noti che se Q è definita positiva esiste uno scalare >0 tale che

nR xxQxx2T ;

in particolare si ha

nR xxQQxx2T

min

dove Qmin denota il più piccolo autovalore di Q.

Definizione 3.8 [Direzione ammissibile]





13

Dato un insieme nRX e un punto Xx , di dice che il vettore nRd individua una direzione

ammissibile in x se esiste uno scalare 0 tale che X dx per ogni ,0 . Come si può

notare dalla figura Figura 3.1 d individua un segmento orientato che parte dal punto x e si svolge

parallelamente a d.

Figura 3.1: Direzione ammissibile

Facciamo alcune considerazioni sulle direzioni ammissibili:

- Se nRX ogni vettore nRd individua una direzione ammissibile.

- Se nRX e x è un punto interno a X allora ogni vettore nRd individua una direzione

ammissibile in x.

Il concetto di direzione ammissibile è molto utile nel calcolo del minimo di una funzione. Infatti per

dimostrare che un punto x è di minimo locale basta far vedere che muovendosi lungo una qualsiasi

direzione ammissibile in x la funzione obiettivo f(x) è non decrescente. Ciò ci consente di studiare il

comportamento della funzione f(x) come se essa dipendesse di volta in volta da una sola variabile.

4 Programmazione non lineare: metodi analitici

x1

x2

x d

x +d

d





14

4.1 Condizioni necessarie di minimo locale

Teorema 4.1 [Condizione necessaria del I ordine]

Data una funzione RRXf n x: derivabile in X, condizione necessaria affinché x* sia un

minimo locale di f è che per ogni direzione d ammissibile

0)*( dxT

x fgrad .

Dimostrazione.

Se x* è un punto di minimo locale per f comunque si consideri una direzione d ammissibile si ha

per 0 sufficientemente piccolo

**** xdxxdx ffgradffT

x ,

da cui segue

0* dT

x xfgrad

Commento. La condizione non è anche sufficiente perché per quelle direzioni d lungo le quali

0)*( dxT

x fgrad

non si può concludere che

** xdx ff .

In questi casi bisogna esaminare il termine quadratico. Ciò viene fatto nel prossimo teorema.

Teorema 4.2 [Condizione necessaria del II ordine]

Data una funzione RRXf n x: due volte derivabile in X, condizione necessaria affinché

x* sia un minimo locale di f è che

a) per ogni direzione d ammissibile si abbia

0* dxT

xfgrad ;

b) per ogni vettore d per cui la a) è soddisfatta con il segno di uguaglianza risulti

0dxHd fT *

Dimostrazione.

La a) segue dal Teorema 4.1. Inoltre per ogni vettore d per cui nella a) vale il segno di uguaglianza,

se x* è un punto di minimo locale per f , deve risultare





15

* *2

*

*2

***

2

2

xdxHdx

dxHddxxdx

f

T

f

T

ff

fgradffT

x

da cui segue l’asserto.

Commento. La condizione non è anche sufficiente perché per quelle direzioni d lungo le quali

0*

0*

dxHd

dx

f

T

T

x fgrad

non si può concludere che

** xdx ff .

In questi casi bisognerebbe esaminare il termine cubico.

4.2 Condizioni necessarie e condizioni sufficienti di minimo locale per un problema non

vincolato

Le condizioni necessarie enunciate nel paragrafo precedente valgono sia nel caso di problemi

vincolati che di problemi non vincolati. In quest’ultimo caso è possibile dare una versione delle

condizioni necessarie più semplice; ciò è dovuto al fatto che ogni direzione è ammissibile.

Teorema 4.3 [Condizione necessaria del I ordine problema non vincolato]

Data una funzione RRf n x: derivabile in Rn, condizione necessaria affinché x* sia un

minimo locale di f è che risulti

0* xfgradx .

Dimostrazione.

Per il Teorema 4.1 deve risultare per un dato vettore dRn

0* dxT

x fgrad .

D’altro canto, poiché anche -dRn

, deve essere pure

0* dxT

x fgrad .

Da cui segue che





16

0* dxT

x fgrad .

Poiché l’ultima uguaglianza deve valere per ogni dRn segue l’asserto.

Teorema 4.4 [Condizione necessaria del II ordine problema non vincolato]

Data una funzione RRf n x: due volte derivabile in Rn, condizione necessaria affinché x* sia

un minimo locale di f è che risulti

a) 0*)( xfgradx

b) *xH f semidefinita positiva.

Dimostrazione.

La prima condizione discende banalmente dal Teorema 4.3. Per quanto riguarda la seconda

condizione, dalla b) del Teorema 4.2 discende immediatamente che deve risultare per ogni dRn

0dxHd fT *

da cui segue l’asserto.

Teorema 4.5 [Condizione sufficiente di minimo locale problema non vincolato]

Data una funzione RRf n x: due volte derivabile in Rn, condizione sufficiente affinché x* sia

un minimo locale di f è che risulti

a) 0* xfgradx

b) *xH f definita positiva.

Dimostrazione.

Poiché *xH f è definita positiva si ha per qualche >0 e per ogni dRn

2* ddxHd f T

Ora per un >0 sufficientemente piccolo si ha





17

2

*

* perchè *2

*

*2

***

2

2

2

2

f

T

f

T

dx

0xdxHdx

dxHddxxdx

f

fgradf

fgradff

x

T

x

Da cui segue

02

**2

2

dxdx

ff

e quindi l’asserto.

In definitiva per risolvere un problema non vincolato si trovano prima tutti i punti che soddisfano la

condizione necessaria del I ordine. Quindi si studia la matrice Hessiana della funzione f valutata in

tali punti. Se, in un dato punto, l’Hessiana risulta definita positiva siamo in presenza di un minimo

locale; se risulta semidefinita positiva non si può concludere nulla; negli altri casi il punto non è di

minimo locale.

Ovviamente il minimo globale risulta essere il più piccolo tra tutti i minimi locali.

Esempio.

Le condizioni esaminate nel caso non vincolato sono valide anche nel caso vincolato laddove si

considerino punti interni all’insieme X.

4.3 Problemi vincolati: vincoli di uguaglianza

Consideriamo il seguente problema con vincoli di uguaglianza.

Problema 4.1

xx fmin

s. a

0xg )(





18

dove nRx e Tmggg )()()()( 21 xxxxg con m<n.

Prima di risolvere il Problema 4.1 osserviamo che in un problema con vincoli di uguaglianza tutti i

punti che soddisfano la condizione di vincolo sono di frontiera, e quindi i risultati del Paragrafo 4.2

non si possono applicare.

La strada da seguire consiste nel partizionare il vettore x in due vettori come segue

w

yx ,

dove yRn-m

e wRm

, e successivamente esprimere il vettore w in funzione del vettore y.

A questo punto enunciamo un lemma che ci sarà utile nel seguito; esso generalizza il Teorema 4.3

sostituendo le direzioni ammissibili con quelle del piano tangente. Sia S la superficie individuata

dall’equazione vincolare g(x)=0.

Lemma 4.1

Condizione necessaria affinché un punto x* sia un minimo locale di f soggetto ai vincoli g(x)=0 è

che a) g(x*)=0 e b) per ogni variazione infinitesima dx che non violi i vincoli del problema, e

quindi tale da appartenere al piano tangente ad S in x*, cioè tale che

0xxx

g

d* ,

risulti

0* xxx dfgradT

Dal Lemma 4.1 immediatamente discende il seguente corollario.

Corollario 4.1


che risulti





19

0wxw

gyx

y

g

w

yx0wxyx

0xg

wy

ddc

d

dddfgraddfgradb

a

TT

**)

:**)

*)

Per trovare una condizione di minimo locale più agevole ricaviamo dalla c) del Corollario 4.1

l’espressione di dw

yxy

gx

w

gw dd **

1

,

e sostituiamolo nella b). Si ottiene

0yxy

gx

w

gxx

yxy

gx

w

gxyx

wy

wy

dfgradfgrad

dfgraddfgrad

TT

TT

****

****

1

1

Poiché dy è arbitrario l’ultima condizione è equivalente a richiedere

0xy

gx

w

gxx wy

****

1

TTfgradfgrad .

Quindi possiamo enunciare il seguente teorema.

Teorema 4.6 [Condizioni necessarie del primo ordine per la soluzione del Problema 4.1]


che risulti





20

0xy

gx

w

gxx wy

****

1

TTfgradfgrad

0xg *

Si può arrivare ad una formulazione equivalente a quella del Teorema 4.6 passando per un problema

fittizio non vincolato. Introduciamo a questo proposito la funzione Lagrangiana

)()(:),( xgλxλxT fl

dove Tm 21λ si chiama vettore dei moltiplicatori di Lagrange.

Facciamo vedere che il calcolo di un minimo locale per il problema non vincolato avente per

funzione obiettivo la Lagrangiana restituisce le stesse condizioni del Teorema 4.6.

Ricordiamo che la condizione necessaria del primo ordine per un problema non vincolato richiede

che il gradiente della funzione obiettivo sia nullo nel punto di minimo. Nel nostro caso, ricordando

che x=[yT w

T]T si ha

0*)(**,

0*****,

0*****,

xgλx

λxw

gxλx

λxy

gxλx

ww

yy

lgrad

fgradlgrad

fgradlgrad

T

T

Eq.(4.1)

Ricavando dalla seconda equazione * si ha

*** xxw

gλ w fgrad

T

e sostituendo nella prima

0xxw

gx

y

gx wy

**** fgradfgrad

TT





21

che restituisce la condizione del Teorema 4.6. In definitiva il nostro problema con vincoli di

uguaglianza si può ricondurre ad un problema non vincolato avente come funzione obiettivo la

Lagrangiana. Ciò è riassunto nel prossimo teorema.

Teorema 4.7 [Condizioni necessarie del primo ordine utilizzando la Lagrangiana]


che

a) g(x*)=0

b) Esista un vettore mR*λ tale che 0λxx

gxλx x

*****,

T

x fgradlgrad

La determinazione delle soluzioni della equazione b) del Teorema 4.7 richiede la valutazione dei

moltiplicatori di Lagrange. Si può quindi concludere che il relativo aggravio di complessità dal

punto di vista computazionale è il prezzo da pagare per aver sostituito un problema di

ottimizzazione vincolata con uno di ottimizzazione non vincolata.

Al solito, introducendo gli Hessiani delle funzioni coinvolte, si possono dimostrare i teoremi

seguenti che contengono condizioni necessarie del secondo ordine e condizioni sufficienti.

Teorema 4.8 [Condizione necessaria del secondo ordine per la soluzione del Problema 4.1]


che

a) g(x*)=0


gxx

***

T

fgrad

c) ***1

xHxHigf

m

ii sia semidefinita positiva sul piano tangente in x* alla iper –

superficie definita dai vincoli.





22

Si noti che la condizione c) del Teorema 4.8 è equivalente alla seguente

0yxx

gyyyxHxHy

igfT *::0***

1

nm

ii RS .

Se nel Teorema 4.8 nella condizione c) si richiede la definitezza positiva in luogo della

semidefinitezza, si ottiene una condizione sufficiente di minimo locale.

Teorema 4.9 [Condizione sufficiente per la soluzione del Problema 4.1]

Condizione sufficiente affinché un punto x* sia un minimo locale di f soggetto ai vincoli g(x)=0 è

che

a) g(x*)=0


gxx

***

T

fgrad

c) ***1

xHxHigf

m

ii sia definita positiva sul piano tangente in x* alla iper – superficie

definita dai vincoli.

Esempio.

In generale, le n+m equazioni che si ottengono scrivendo le condizioni necessarie del primo ordine

sono non lineari. Ciò limita fortemente l’utilizzo di tali condizioni analitiche.

4.4 Un primo problema con vincoli di uguaglianza: Funzione obiettivo di tipo quadratico e

funzioni di vincolo di tipo lineare. Pseudoinversa minima a destra

Di particolare importanza nell’ambito dei problemi di controllo sono i problemi di PM in cui la

funzione obiettivo è di tipo quadratico e le funzioni di vincolo sono lineari. Tale problema può

formalizzarsi come segue:

Problema 4.2

bFx

QxxT

x

as.

min





23

con xRn , FR

mxn , m<n, Q>0 ed F di pieno rango riga.

Si noti che se nel Problema 4.2 si pone Q=I il problema diventa quello di minimizzare la norma di

x soggetta al vincolo Fx=b.

Poiché il problema in esame presenta solo vincoli di uguaglianza si può utilizzare per la sua

soluzione la teoria sviluppata nella sezione 4.3. In questo caso la Lagrangiana risulta essere definita

come segue

bFxλQxxλx TTl ),( .

Ora si ha (si vedano il Problema 5.1 e il Problema 5.2)

λFQxλxT

x 2),(lgrad

ed inoltre

bFxλxλ ),(lgrad .

Dunque, in accordo al Teorema 4.7, i punti di minimo si possono trovare imponendo le condizioni

bFx

0λFQxT

2 .

Dalla prima equazione si ricava

λFQxT1

2

1*

Eq. (4.2)

che, sostituita nella seconda porge

bλFQF T1

2

1

da cui

bFFQλ112* T .

Infine sostituendo nella Eq. (4.2) si ha

bFbFFQFQxRM

QTT :*

111 ,





24

che è quindi un possibile punto di minimo. Ora ponendo

mmb

b

b

2

1

2 , b

f

f

f

F

T

T

T1

si ha

021

QHHH

QxxxfQxxTT

m

ibi

iTi

e quindi x* è effettivamente un punto di minimo (globale essendo l’unico punto di minimo).

La matrice RMQF è detta pseudoinversa minima a destra. L’aggettivo “minima” ricorda che tale

matrice è legata al calcolo del minimo della forma quadratica xTQx; l’aggettivo “pseudoinversa a

destra” discende dal fatto che

IFFQFFQFF 111 TTRM

Q .

4.4.1 Una applicazione della pseudoinversa minima a destra ad un problema di raggiungibilità

Si consideri il sistema lineare a tempo discreto descritto dalle equazioni

mn RkRkkkk )(,)(,)0(),()()1( 0 uxxxBuAxx

che supponiamo essere raggiungibile.

Un classico problema è quello di trovare la legge di controllo che in N>n passi porti lo stato del

sistema in uno stato desiderato x minimizzando l’energia impiegata dal controllore, portata in

conto attraverso un indice di costo del tipo

1

0

N

i

T ii uQu i , Qi>0, i=0,…,N-1.

Dalla teoria della raggiungibilità per i sistemi a tempo discreto si ha che

1

1

0

21

Nu

u

u

BBABAxAxNN

0N

N

che, ponendo





25

NmR

N

u

u

u

u

FBBABA

bxAx

NN

0

N

N

1

1

0

21

,

può essere riscritta

bFu .

Dunque il problema di ottimizzazione in esame può essere formulato come

Problema 4.3

bFu

QuuT

as.

min

ove si è posto

0

1

1

0

NQ00

0Q0

00Q

Q

che ammette come soluzione

bFuRM

Q* .

Esempio.

4.5 Un secondo problema con vincoli di uguaglianza. Pseudoinversa minima a sinistra

Si consideri il seguente problema.

Problema 4.4

εbFx

Qεεx

as

T

.

min ,

con Rm, xR

n, m>n, Q>0 ed F di pieno rango colonna.





26

Questo tipo di problema si incontra nella risoluzione dei sistemi di equazioni lineari sovraspecificati

del tipo Fx=b , in cui il numero delle equazioni è superiore al numero delle incognite. In questo

caso si sceglie la soluzione x che minimizza la norma (eventualmente pesata dalla matrice Q) della

differenza =Fx-b.

Si noti che il Problema 4.4 presenta la particolarità che la funzione obiettivo dipende implicitamente

dal vettore delle variabili di ottimizzazione x.

In accordo al Teorema 4.7 una condizione necessaria affinché il punto x* sia un minimo locale è la

seguente. Sia

bεFxλQεελεxTT ),,(l

si ha

0λF

Fxλλε,x

T

Txx

gradlgrad ,

0λQε

ελQεελε,xTT

εε

2

, gradlgrad

0bεFxλε,xλ ,lgrad

Eq. (4.3)

A questo punto moltiplicando la seconda delle Eq. (4.3) per FT e utilizzando la prima delle Eq. (4.3)

si ottiene

0QεF

λFQεFλQεF

T

TTT

2

22.

Eq. (4.4)

D’altro canto dalla terza delle Eq. (4.3) si ottiene

bFxε

che, sostituita nella Eq. (4.4), restituisce

0QbFQFxFTT .





27

Pertanto un punto candidato ad essere minimo è

QbFQFFxTT 1

*

.

Eq.(4.5)

Per verificare che il punto sia effettivamente un minimo, notiamo che il Problema 4.4 può

riscriversi

bvF

vQvv

~.

~min

as

T

ove si è posto v=[xT T

]T ,

Q0

00Q~

, IFF ~

.

La condizione sufficiente di minimo richiede che la matrice

Q

HHHvQvvfvQv

~2

~

1

~*

~

Ti

Ti

T

m

ibi

sia definita positiva per ogni vettore

0~

:0

~

:

*

yFRyyv

bvFRyy mn

vv

mn .

Dunque deve essere

0yFyyQyT ~

:0~ mnR .

Eq. (4.6)

Partizionando

TT2

T1 yyy

la Eq. (4.6) può essere riscritta come

0y

yIFy

y

yQyy

2

1

2

1T2

T1

:0~ mnR

o ciò che è lo stesso





28

0yFyyQyy 212T2 :0 mnR .

L’ultima condizione può essere riscritta in modo equivalente

nR 111 0 yQFyFyTT .

L’ultima condizione è verificata poiché Q è definita positiva e F è di rango pieno colonna; quindi il

punto x* definito nella Eq.(4.5) è effettivamente un punto di minimo.

La matrice

QFQFFFTTLM

Q

1

è detta pseudoinversa minima a sinistra. Infatti si ha

IQFFQFFFFTTLM

Q 1

.

4.5.1 Una applicazione della pseudoinversa minima a sinistra: stima parametrica a minimi

quadrati

Consideriamo una relazione causa – effetto tra due grandezze x e y. Supponiamo che sia nota la

struttura della dipendenza tra x e y

)()()( 2211 xxx nn fkfkfky

Eq.(4.7)

con nTn Rkkk 21k .

Siano ,,,1,, Niyi ix i risultati di N esperimenti; poiché, ovviamente, il modello fornito dalla

Eq.(4.7) non descrive perfettamente il fenomeno in esame, si ha

Niyfkfkfky iinniii ,,1,)()()(ˆ 2211 xxx .

Il problema della stima ai minimi quadrati è quello di trovare il vettore dei parametri k che

minimizzi la norma pesata dello scarto tra gli effetti misurati yi e gli effetti calcolati dal modello

teorico iy , cioè





29

εbFk

Qεεk

as

T

.

min

ove si è posto

NNnNN

n

n

iii

N

y

y

y

xfxfxf

xfxfxf

xfxfxf

yy

2

1

21

22221

11211

2

1

,

ˆ:,

bF

ε

e dunque la soluzione è pari a

bFkLM

Q* .

Esempio numerico.

4.5.2 Identificazione della risposta armonica

Supponiamo di aver determinato sperimentalmente la risposta armonica di un sistema lineare che

esibisca un comportamento riconducibile a quello di un sistema del primo ordine:

j

GW

1.

Il problema è determinare G e in modo tale che la funzione ricavata teoricamente sia il più

possibile simile a quella ricavata sperimentalmente.

Si ha

j

GWjW

1

Dunque





30

GjWjW 1

da cui

0

WW

GWW.

Le ultime uguaglianze possono essere riscritte come segue

G

W

W

W

W

0

1

e quindi

W

W

W

WG1

0

1 .

Poiché l’inversa esiste, con una unica misura sperimentale della risposta armonica si riuscirebbero

ad ottenere i valori di G e e quindi W().

Tuttavia, poiché nella pratica la risposta armonica non è misurata con precisione assoluta, si

effettuano più misure che portano al sistema di equazioni

G

W

W

W

W

W

W

W

W

W

W

W

W

NN

NN

N

N

0

1

0

1

0

1

22

22

11

11

2

2

1

1

Questo è un sistema sovraspecificato, la cui soluzione può essere trovata con le tecniche di

pseudoinversione descritte nella Sezione 4.5.





31

4.6 Problemi con vincoli di uguaglianza e disuguaglianza

Si consideri il problema

Problema 4.5

pih

mig

as

f

i

i

,,10

,,10

.

min

x

x

xx

Definizione 4.1 [Vincolo attivo]

Un vincolo di disuguaglianza hi(x)0 è detto essere attivo in un punto nRx se risulta 0xih ;

inattivo se risulta 0xih .

Si noti che i vincoli attivi in un punto sono gli unici che limitano le direzioni di spostamento

ammissibili in quel punto. Ovviamente i vincoli di uguaglianza sono per definizione sempre attivi

qualunque sia xRn.

Teorema 4.10 [Condizione necessaria del primo ordine per la soluzione del Problema 4.5]

Condizione necessaria affinché un punto x* sia un minimo locale di f soggetta ai vincoli

0xh0xg , è che esista un vettore mR*λ e un vettore pR*μ tali che

0*0*)

,,10)

,,10*)

*****)

xx

x

0μxx

hλx

x

gxx

hgiv

pjiii

pjhii

fgradi

j

jj

TT

Dimostrazione. Cominciamo con il far vedere che esiste un vettore mR*λ e un vettore pR*μ

tale che la condizione i) risulta valida. A questo proposito denotiamo con J l’insieme degli indici

dei vincoli attivi in x*, in altri termini

Jjh j 0*x .





32

Ora consideriamo il problema fittizio

Jjh

mig

as

f

j

i

0

,,10

.

min

x

x

xx

Il punto x* è ovviamente soluzione di questo problema con soli vincoli di uguaglianza. La

condizione necessaria di minimo dunque richiede che esista un vettore mR*λ e scalari reali j* ,

Jj , tali che

0xμλxx

gx x

Jjjj

T

x hgradfgrad *****

A questo punto basta scegliere j=0, Jj .

La condizione ii) è dimostrata automaticamente. Infatti per un dato j o risulta hj(x*)=0 oppure j=0.

Per quanto riguarda la condizione iii), per come è stato costruito il vettore * risulta j=0 per

Jj . Resta da far vedere che per i vincoli attivi, e cioè per Jj risulta j0. Supponiamo per

assurdo che esista un kJ tale che k<0.

Sia ora dx un vettore infinitesimo che individua una direzione ammissibile in x* e tale che

movendosi lungo dx tutti i vincoli attivi continuano a rimanere tali, eccezion fatta per il k-esimo che

diventa inattivo. Si consideri la trasposta della condizione a) del Teorema (già dimostrata)

0xx

hμx

x

gλxx

***** TTT

fgrad

Si moltiplichino ambo i membri di tale uguaglianza per dx. Si ottiene

0xxx

hμxx

x

gλxxx

dddfgrad TTT

*****

Eq. (4.8)

Ora xxx

gd*

rappresenta l’incremento subito dalla funzione g spostandosi da x* a x*+dx . Tale

incremento deve essere nullo per non violare i vincoli di uguaglianza g(x)=0 . Allo stesso modo





33

xxx

hd*

rappresenta l’incremento subito dalla funzione h spostandosi da x* a x*+dx; a questo

proposito si ha che

vincolideiattivitàperkJjsedgrad

perchèJjsedgradT

jj

j

T

jj

0*

00*

xxh

xxh

x

x

Dunque la Eq. (4.8) si riduce a

0xxhμxx xx dgraddfgradT

kkT

***

o ciò che è lo stesso

xxhμxx xx dgraddfgradT

kkT

***

Ora si ha

inattivo diventa che vincolodel incrementol' è perchè 0*

assurda ipotesil'per 0

xxhx dgradT

k

k

Dunque si otterrebbe

0* xxx dfgradT

che è assurdo poiché xxx dfgradT

* è l’incremento di f in un intorno di x* che per ipotesi è

punto di minimo. Dunque resta dimostrato che deve essere k>0 .

Il vettore μ si chiama vettore dei moltiplicatori di Kuhn-Tucker.

Esempio numerico.

Al solito si possono enunciare condizioni necessarie e condizioni sufficienti del secondo ordine

utilizzando le matrici Hessiane.





34

Teorema 4.11 [Condizione necessaria del secondo ordine per la soluzione del Problema 4.5]

Condizione necessaria affinché un punto x* sia un minimo locale di f soggetta ai vincoli


*in attivi vincoliai tangentepiano sul

positiva tasemidefini è *****)

0*0*)

,,10)

,,10*)

****)

11

x

xxxH

xx

x

0μx

hλx

x

gx

f

p

i

ih

m

i

ig

j

jj

TT

x

iiHHiv

hgiv

pjiii

pjhii

fgradi

Teorema 4.12 [Condizione sufficiente per la soluzione del Problema 4.5]

Condizione sufficiente affinché un punto x* sia un minimo locale di f soggetta ai vincoli


*in attivi vincoliai tangentepiano sul

positiva definita è *****)

0*0*)

,,10)

,,10*)

****)

11

x

xxxH

xx

x

0μx

hλx

x

gx

f

p

i

ih

m

i

ig

j

jj

TT

x

iiHHiv

hgiv

pjiii

pjhii

fgradi

Esempio.





35

5 Appendice A

Problema 5.1: Mostrare che, assegnata una matrice simmetrica QRnxn

, risulta

QxQxxx 2Tgrad .

Soluzione. Si ha

nnnn

n

Tnnnnnn

T

nnnnnn

nn

Tn

i

n

jjiij

n

n

i

n

jjiij

n

i

n

jjiij

T

x

x

qq

qq

xqxqxqxqxq

xqxxqx

xxqxqx

xxqx

xxqx

xxqgradgrad

1

1

111

111212111

21111

2111

1

1 11 11

1 1

2

22222

22

xx Qxx

Problema 5.2: Mostrare che, assegnati i vettori Rm, xR

n e una matrice FR

nxm, risulta

λFFxλT

x Tgrad

Soluzione. Si ha

mmnn

m

Tmnmnmm

Tm

i

n

jjiji

n

m

i

n

jjiji

m

i

n

jjiji

T

ff

ff

ffff

xfx

xfx

xfgradgrad

1

1

111

111111

1 11 11

1 1xx Fxλ





36

Problema 5.3: Mostrare che, per un assegnato k>0 , il problema di ottimizzazione

0

.

cossinmax 2

as

k

ammette come soluzione

3

2arcsin* .

Soluzione. Il problema può essere messo in forma standard come segue

0

0

.

cossinmin 2

as

k

Si noti che il problema presenta vincoli di disuguaglianza stretti; essi sono dunque sempre inattivi;

inoltre non ci sono vincoli di uguaglianza. Di conseguenza i moltiplicatori di Lagrange non ci sono

e i due moltiplicatori di Kuhn-Tucker sono nulli, e la Lagrangiana coincide con la funzione

obiettivo. Utilizzando la condizione necessaria affinché si abbia un punto di minimo (Teorema

4.10) si ha

0

0

0cossin2

kd

d

Eq. (5.1)

Derivando la prima delle Eq. (5.1) si ottiene

2sin3sin

cos2sinsin

sincossin2cossin

2

22

322

k

k

kkkd

d

che ammette come soluzione ,0 che scartiamo per incompatibilità dei vincoli e





37

3

2arcsin*

3

2arcsin*

2

1

che sono entrambi possibili punti di minimo, soddisfacendo i vincoli di disuguaglianza.

Ora per applicare la condizione sufficiente dobbiamo valutare

22

22

22

2

2

sin62sin3cos

cossin62sin3cos

2sin3sincossin

k

kk

kd

dk

d

d

Ora nei punti candidati si ha 02sin3 2 ; dunque in tali punti

22

2

2

sincos6cossin kkd

d

che risulta positivo per *1 e negativo per *2 .

Problema 5.4: risolvere il problema delle n centrali elettriche interconnesse descritto nel Paragrafo

2.2 con i seguenti valori dei parametri

2n

22

1

1

2222

2111

ppc

ppc

15totP

10

10

2

1

M

M

p

p





38

Soluzione: T105* p .

Appunti del Corso di Controlli II – Teoria dell’ottimizzazionewpage.unina.it/framato/materiale...

Documents

Transcript of Appunti del Corso di Controlli II – Teoria dell’ottimizzazionewpage.unina.it/framato/materiale...