'Functiile convexe':http://en.wikipedia.org/wiki/Convex_function sunt functiile pentru care graficul lor 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).

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

E simplu de demonstrat ca suma a doua functii convexe e tot o functie convexa. O proprietate utila pentru problema noastra este ca ca maximul pentru o functie convexa e realizat pe marginea domeniului de definitie.