Rezolvare pentru "suma in triunghi" si functii convexe

Cosmin Negruseri
21 decembrie 2011

Problema dinainte a fost un pretext pentru a va introduce notiunea de functie convexa .O astfel de functie are propretatea ca graficul ei se afla sub orice segment de dreapta ce uneste doua puncte ale graficului. Mai formal, avem ca 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).

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 pentru cazul uni dimensional sau gradient descent pentru cazul general.

Sa revenim la problema noastra:

E simplu de demonstrat ca suma a doua functii convexe e tot 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.

Functia distanta euclidiana e o functie strict convexa si o combinatia din problema 2dist(M, A) + dist(M, B) + dist(M, C) este si ea o functie convexa. Si cum maximul pentru functii de genul asta e realizat in capete, ne e deajuns sa ne uitam la valoarea functiei in punctele A, B si C. Astfel vedem ca C e punctul cautat.

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.

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)
x=linspace(0, 3, 50)
y=linspace(0, 4, 50)
[xx,yy]=meshgrid(x,y)
contourf(xx,yy,sumt(xx,yy))

Sper ca v-am deschis apetitul pentru functii convexe :).