Problema dinainte a fost un pretext pentru a va introduce notiunea de 'functie convexa':http://en.wikipedia.org/wiki/Convex_function. O astfel de functie are proprietatea ca pentru oricare doua puncte de pe graficul ei, graficul se afla sub segmentul determinat de cele doua functii.
*Rezolvarea pe scurt:*
Functia <tex>2 dist(M, A) + dist(M, B) + dist(M, C)</tex> e o functie convexa. Functiile convexe isi ating maximul pe marginea domeniului de definitie. Astfel e de ajuns sa evaluam functia in punctele A, B si C si gasim ca maximul este 13 si e realizat in punctul C.
Mai formal, daca f:X->R unde X e un domeniu convex (interval etc.) atunci pentru oricare doua puncte x1 si x2 din X si orice t din intervalul [0, 1] avem ca f(tx1 + (1-t)x2) <= tf(x1) + (1-t)f(x2).
*Functii convexe:*
Problema este pretext pentru a discuta notiunea de 'functie convexa':http://en.wikipedia.org/wiki/Convex_function. O astfel de functie are proprietatea ca pentru oricare doua puncte de pe graficul ei, graficul se afla sub segmentul determinat de cele puncte. Mai formal, daca <tex>f:X->R</tex> unde <tex>X</tex> e un domeniu convex (interval etc.) atunci pentru oricare doua puncte <tex>x1</tex> si <tex>x2</tex> din <tex>X</tex> si orice <tex>t</tex> din intervalul <tex>[0, 1]</tex> avem ca <tex>f(tx_{1} + (1-t)x_{2}) \le tf(x_{1}) + (1-t)f(x_{2})</tex>. <tex>X</tex> poate fi orice spatiu vectorial, R, interval in o dimensiune, poligon convex in doua si asa mai departe.
O proprietate importanta a functiilor convexe este ca au doar un minim local care este si global. Astfel problema *minimizarii valorii unei functii* este mai simplu de rezolvat pentru functii convexe.
In *machine learning* apare frecvent aceasta problema. Functiile generale nu sunt usor de minimizat. Nu au o forma care poate fi rezolvata matematic sau sunt neregulate si au multe optime locale. Pentru a putea obtine solutii bune, de multe ori functiile generale sunt aproximate sau marginite de functii convexe pentru care exista algoritmi eficienti de minimizare, cum ar fi 'cautare ternara':http://en.wikipedia.org/wiki/Ternary_search pentru cazul unidimensional sau 'gradient descent':http://en.wikipedia.org/wiki/Gradient_descent pentru cazul general.
O proprietate importanta a functiilor convexe este ca au doar un minim local care este si global. Astfel problema *minimizarii valorii unei functii multi dimensionale* este mai simplu de rezolvat pentru functii convexe. Ea apare frecvent in *machine learning*. Functiile generale nu sunt usor de minimizat. Nu au o forma care poate fi rezolvata matematic sau sunt neregulate si au multe optime locale. Pentru a putea obtine solutii bune, de multe ori functiile generale sunt aproximate de functii convexe pentru care exista algoritmi eficienti de minimizare, cum ar fi 'cautare ternara':http://en.wikipedia.org/wiki/Ternary_search pentru cazul unidimensional sau 'gradient descent':http://en.wikipedia.org/wiki/Gradient_descent pentru cazul general.
*Rezolvarea mai detaliata:*
Functia distanta euclidiana fata de un punct fix e o functie convexa.
_demonstratie:_
Vedem usor daca facem un grafic care este un con sau putem incerca sa ne uitam la derivate.
Suma a doua functii convexe este tot o functie convexa.
_demonstratie:_
<tex>f_{1}(tx_{1} + (1-t)x_{2}) \le tf_{1}(x_{1}) + (1-t)f_{1}(x_{2})</tex>
<tex>f_{2}(tx_{1} + (1-t)x_{2}) \le tf_{2}(x_{1}) + (1-t)f_{2}(x_{2})</tex>
=>
<tex>f_{1}(tx_{1} + (1-t)x_{2}) + f_{2}(tx_{1} + (1-t)x_{2}) \le t(f_{1}(x_{1}) + f_{2}(x_{1})) +</tex>
<tex>(1-t)(f_{1}(x_{2}) + f_{2}(x_{2}))</tex>
Astfel <tex>2dist(M, A) + dist(M, B) + dist(M, C)</tex> e si ea o functie convexa.
!{margin: 1px; margin-right: 10px; border: 1px solid gray;}<blog/suma-in-triunghi-rezolvare?graph.gif!
*Rezolvarea problemei:*
Maximul pentru o functie convexa e realizat pe marginea domeniului de definitie.
_demonstratie:_
Din definitie, graficul intre <tex>x1</tex> si <tex>x2</tex> se afla sub segmentul determinat de <tex>(x1, f(x1))</tex> si <tex>(x_{2}, f(x_{2}))</tex> astfel pentru <tex>x_{1}</tex> si <tex>x_{2}</tex> pe contur unul dintre cele doua puncte va fi mai sus decat toate restul din grafic.
Functia distanta euclidiana e o functie strict convexa. E simplu de demonstrat ca suma a doua functii convexe e tot o functie convexa. De aici rezulta ca 2dist(M, A) + dist(M, B) + dist(M, C) e si ea o functie convexa.
Maximul pentru o functie convexa e realizat pe marginea domeniului de definitie. Asta e usor de vazut mai ales pentru functii unidimensionale cum ar fi parabolele.
Astfel e deajuns sa ne uitam la valoarea functiei in punctele A, B si C. Obtinem ca C e punctul cautat.
Acum am demonstrat toti pasii din prima propozitie a articolului.
Am facut un grafic folosind octave unde punctele A, B si C au coordonatele (0, 0), (3, 0) respectiv (0, 4), iar culoarea graficului reprezinta suma ceruta in problema.
In graficul alaturat puteti vedea cum se comporta functia. Punctele A, B si C au coordonatele (0, 0), (3, 0) respectiv (0, 4), iar culoarea graficului reprezinta suma ceruta in problema.
Aveti aici codul cu care am generat.
Aveti aici codul in 'Octave':http://www.gnu.org/software/octave/ cu care e generat.
== code(c) |
dist = @(x, y, x1, y1) sqrt((x - x1).^2 + (y - y1).^2)
sumt = @(x, y) 2 * dist(x, y, 0, 0) + dist(x, y, 3, 0) + dist(x, y, 0, 4)
