Rezolvare pentru "suma in triunghi" si functii convexe

Cosmin Negruseri
21 decembrie 2011

Pe scurt:

Functia 2 dist(M, A) + dist(M, B) + dist(M, C) e o functie convexa. Functiile convexe isi ating maximul pe marginea domeniului de definitie. Astfel e de ajuns sa ne uitam la valoarea functiei in punctele A, B si C si gasim ca maximul este 13 realizat in punctul C.

Problema este pretext pentru a va introduce notiunea de functie convexa. 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.

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).

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

Rezolvarea mai detaliata:

Functia distanta euclidiana e o functie convexa.
demonstratie:
Vedem usor din grafic, sau putem incerca sa ne uitam la derivate.

Suma a doua functii convexe este tot o functie convexa.

demonstratie:
f1(tx1 + (1-t)x2) <= tf1(x1) + (1-t)f1(x2)
f2(tx1 + (1-t)x2) <= tf2(x1) + (1-t)f2(x2)
=>
f1(tx1 + (1-t)x2) + f1(tx1 + (1-t)x2) <= t(f1(x1) + f2(x1)) + (1-t)(f1(x2) + f2(x2))
Astfel 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.
demonstratie:
Din definitie, graficul intre x1 si x2 se afla sub segmentul determinat de (x1, f(x1)) si (x2, f(x2)) astfel pentru x1 si x2 pe contur unul dintre cele doua puncte va fi mai sus decat toate restul din grafic.

Acum am demonstrat toti pasii din prima propozitie a articolului.

Am mai 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))

Adapost2 se poate rezolva folosind idei din acest post.
Sper ca v-am deschis apetitul pentru functii convexe :).