Загальна задача математичного програмування формулюється так. У деякому просторі задано тим чи іншим способом множину G і функцію f елементів множини G, яка кожному елементу G ставить у відповідність деяке дійсне число. Потрібно знайти найменше (найбільше) значення функції f, заданої на множині G, а також елементи G, на яких таке значення досягається.

Розглянемо дійсний n-вимірний простір Rn, нехай x=(x1; x2; ...; xn) є елементом (точкою) з Rn. Множину G можна визначити, наприклад, як множину елементів з Rn, таких, що задовольняють умови:

ji(x) £ 0 (i=1, 2, ..., m),

де ji(x) - деякі функції елементів з Rn, що мають значення в Ri.

Якщо при цьому функції ji(x) і f(x) опуклі, то задача називається задачею опуклого програмування. Нагадаємо, що функція g(x) називається опуклою, якщо для будь-яких точок x1 та x2 справджується нерівність:

g(ax(1) + (1-a)x(2)) £ ag(x(1))+ (1-a)g(x(2)), (0£ a £ >1).

З геометричного погряду це означає, що графік функції g(x) над прямою що з'єднує точки x(1) та x (2), лежить нижче від хорди, що сполучає точки (x (1); g(x(1))) і (x(2); g(x(2))) (мал. 1). Для опуклих функцій ji(x) кожна нерівність ji(x) £ 0 визначає деяку опуклу множину Gi. Нагадаємо, що множина називається опуклою, якщо разом з будь-якими двома точками x(1) та x(2) їй належать також усі точки відрізка x(1) + a(x(2) - x(1)), (0£ a £ 1), який сполучає точки x(1) і x(2) (мал. 2). Перерізом опуклих множин Gi є опукла множина G, . Отже, задача опуклого програмування полягає в тому, щоб знайти найменше значення опуклої функції f(x) на опуклій множині G (мал. 3). Як бачимо на мал. 4, точки, в яких j 1(x) = 0, визначають межу множини G1 (лінія нульового рівня функції j1 (x)), а у внутрішніх точках G1 виконується нерівність j1(x) < 0. Аналогічно в точках множини G2 справджується нерівність j2(x) £ 0, причому на межі G2 (лінія нульового рівня функції j2(x)) j2(x) = 0. У точках x Î G1 Ç G2 виконується обидві нерівності j1(x) £ 0 і j2(x) £ 0. На мал. 3 показано точку x*, у якій досягається найменше значення функції f(x) на множині G.

Задача опклого програмування має таку важливу особливість: будь-який локальний мінімум опуклої функції f(x) на опуклій множині є водночас і глобальним мінімумом.