Изпъкнало програмиране
КОНВЕКСНО ПРОГРАМИРАНЕ, раздел на математическо програмиране, в който проблемът за максимизиране на вдлъбната целева функция f (x) на векторния аргумент x = (x1,. Xn), удовлетворяващ ограниченията gi (x) ≥ 0, x Є X, i = 1, се изследва. m, където gi са вдлъбнати функции, X е изпъкнал набор. Точка x, отговаряща на тези ограничения, се нарича допустима. Основният резултат от теорията на изпъкналото програмиране е теоремата за седловината точка: за да бъде допустима точка x * на задача за изпъкнало програмиране оптимална, е необходимо (при доста широки условия) и достатъчно съществуването на вектор y * = (y * 1,. Ym *) с неотрицателни компоненти y *, така че точката (x *, y *) е седлова точка за функцията на Лагранж
изпъкнали задачи за програмиране, тоест за всеки x Є X и y с неотрицателни компоненти, неравенствата
Редица изпъкнали методи за програмиране се основават на теоремата за седловината, в която или функцията φ (y1,. Um) = maxxЄXL (x, у) е сведена до минимум за уi≥ 0, i = 1,. m, или седловината се намира директно и вместо функцията на Лагранж понякога се използват някои от нейните модификации. Друг подход за решаване на проблема с изпъкналото програмиране е свързан с търсенето на възможни посоки на движение на допустима точка x, които не са получени от множеството допустими точки и, при движение по които, целевата функция се увеличава. Този подход се прилага с помощта на последователност от итерации. При всяка итерация се изчислява възможната посока, излизаща от следващата точка, след което се прави изместване в тази посока с известно разстояние до следващата точка. Съществуват методи за решаване на изпъкнали задачи за програмиране, специално адаптирани към случая, когато целевата функция е нелинейна и ограниченията са линейни. Като правило методите на изпъкнало програмиране изискват безкраен брой повторения, за да се определи точно оптималната точка. Изключение правят проблемите на квадратното програмиране (целевата функция е сумата от вдлъбнати квадратни и линейни функции, ограниченията са линейни) и линейното програмиране (целевата функция и ограниченията са линейни), за които се използват главно крайни методи. Много изчислителни методи на изпъкнало програмиране се прилагат под формата на компютърни програми; има и софтуерни пакети, обхващащи проблеми с линейното програмиране и изпъкналото програмиране. Вижте също Operations Research.