Пусть дана система неравенств вида
ji(x1, x2,..., xn) £ bi, i=1,2,...,m (1)
x1, x2,...,xn ³ 0,
и функция Z=f(x1, x2,..., xn), (2)
причем все функции ji(Х) являются выпуклыми на некотором выпуклом множестве М, а функция Z либо выпукла на множестве М, либо вогнута.
Задача выпуклого программирования (ВП) состоит в отыскании такого решения системы ограничений (1), при котором целевая функция Z достигает минимального значения, или вогнутая функция Z достигает максимального значения.
Напомним, что множество точек называется выпуклым, если оно вместе с любыми своими двумя точками содержит и весь отрезок, соединяющий эти точки. Если [a,b] – отрезок на числовой прямой и хÎ[a,b], то х=aa+(1-a)b, 0£a£1 или
х=a1a+a2b, a1+a2=1, a1³0, a2³0. (*)
Нетрудно видеть и обратное: если выполняется (*), то хÎ[a,b].
Исходя из равенства (*) видно, что если М – выпуклое пространство, то 
для любых точек X1,…,Xr ÎM и любых действительных чисел ti ³0, удовлетворяющих условию 
.
Функция F(X)=F(x1, x2,..., xn), определенная на выпуклом множестве М n-мерного пространства, называется выпуклой на этом множестве, если
F(aX1 +(1-a)X2)£ aF(X1)+(1-a)F(X2 ),
вогнутой на этом множестве, если F(aX1 +(1-a)X2)£ aF(X1)+(1-a)F(X2 ),
строго выпуклой на этом множестве, если F(aX1 +(1-a)X2)> aF(X1)+(1-a)F(X2 )
строго вогнутой на этом множестве, если F(aX1 +(1-a)X2)< aF(X1)+(1-a)F(X2 ),
для любых точек Х1, Х2 ÎМ и любого числа aÎ[0,1].
Алгебраические и аналитические свойства выпуклых функций:
- если функция F(X) выпукла, то функция - F(X) вогнута.
- функция F(X)=С и линейная функция F(X)= aХ+b являются всюду выпуклыми и всюду вогнутыми.
- если функции Fi(X), I=1,2,…,m выпуклы, то при любых действительных числах aI³0 функция
также выпукла. - если функция F(X) выпукла, то для любого числа a область решений неравенства F(X)<a является выпуклым множеством, либо пустым.
- если функции jI(X) выпуклые при всех неотрицательных значениях переменных, то область решений системы неравенств jI(X)£bi, I=1,…,m является выпуклым множеством (если она не пуста).
- выпуклая (вогнутая) функция, определенная на выпуклом множестве М, непрерывна в каждой внутренней точке этого множества.
- всякая дифференцируемая строго выпуклая (вогнутая) функция имеет не более одной стационарной точки (т.е. точки, в которой равны 0 все частные производные). При этом для выпуклой (вогнутой) функции стационарная точка всегда является точкой локального и глобального минимума (максимума).
- дважды дифференцируемая функция F(X)= F(x1, x2,...,xn) является выпуклой в том и только в том случае, когда
для любых Х ÎМ и Dxi, Dxj, не обращающихся в 0 одновременно.
Ввиду свойства 3 всякая ЗЛП является частным случаем задачи ВП. В общем случае задачи ВП являются ЗНП.
Выделение задач ВП в специальный класс объясняется экстремальными свойствами выпуклых функций:
- всякий локальный минимум выпуклой функции (локальный максимум вогнутой функции) является одновременно и глобальным;
- ввиду свойства 2 выпуклая (вогнутая) функция, заданная на замкнутом ограниченном множестве, достигает на этом множестве глобального максимума и глобального минимума.
Отсюда вытекает, что если целевая функция является строго выпуклой (строго вогнутой) и если область решений системы ограничений не пуста и ограничена, то ЗВП всегда имеет единственное решение. В этом случае минимум выпуклой (максимум вогнутой) функции достигается внутри области решений, если там имеется стационарная точка, или на границе этой области, если внутри нет стационарной точки.
