3. Задачи выпуклого векторного программирования1.

Задача выпуклого программирования заключается в отыскании минимального значения функционала (критерия) при некоторых ограничениях:

 ₀(x)  min, xXRⁿ

где  ₀(x) – выпуклая функция, X– выпуклое множестмо.

Задача выпуклого векторного (многокритериального) программирования запишем в виде

i(x)  min, i M, xXRn,

где Mтакже конечное индексное множество, если это множество одноэлементное, то получаем задачу выпуклого программирования, в противном случае задачу выпуклого векторного программирования. Для многокритериальных задач необходимо всегда определить, что понимается под оптимальным решением. В данном случае под оптимальностью мы будем понимать оптимальность по Парето и Слейтеру, определения которых будут даны ниже [Подиновский,Акоф, Моудера ]. Широко бытует мнение, что многокритериальные задачи принципиально отличаются от однокритериальных задач. Возможно, что с точки зрения процедуры принятия решения это и так, например, множества точек, оптимальных по Слейтеру (или Парето) часто представляют собой замкнутые области, а требуется выбрать только одно решение. Однако с точки зрения математического аппарата, аппарат многокритериальных задач рассматриваемого класса незначительно отличается от аппарата однокритериальных. Это подтверждают работы [Коваленко А.Г. Элементы].

Ниже рассмотрены основные понятия, используемые при решении задачи выпуклого векторного программирования.

3.1. Некоторые сведения выпуклого анализа

Выпуклые множества

Рассмотрим множество вида [x, y]={z|z=(1–)x+y, [0, 1], zRⁿ}.Это отрезок прямой, соединяющий точкиx иy, так как уравнение прямой, проходящей через эти точки, имеет вид:z()=x+(y–х)=(1–)x+y, при =0 z()=x , при=1 z()=у. Если пробегает значения между 0 и 1, тоz() пробегает значения по прямой междуx иy(см. рис. 2.1).

. Определение 2.1. МножествоХRⁿ называется выпуклым, если для любых пар точекх,уХ отрезок [х,y] Х. Если при этом (х,y)X⁰ , где X⁰– множество внутренних точек множестваХ, тоХ– строго выпуклое множество

Из этого определения следует, что у выпуклого множества для любыхх,уХ и[0,1] точкаz()=(1–)x+yХ, еслиХ– строго выпуклое множество, то при(0,1) z() является внутренней точкой множества Х.На рис. 2.2 приведен пример выпуклого множества, а на рис.2.3 пример множества, не являющегося выпуклым.

Определение 2.2.ТочкаzRⁿ называется выпуклой комбинацией точекх₁, х₂, …,х_nRⁿ, если существуют такие числа.

Для выпуклых множеств справедливы следующие теоремы:

Теорема 2.1. Пересечение любого числа выпуклых множеств выпукло.

Теорема 2.2.МножествоХ={x |a,x, xRⁿ }, гдеа– заданный вектор, – скаляр, является выпуклым множеством.

Следствие 2.2.МножествоХ={x| Ахb, xRⁿ }, гдеА– матрица размерностиm×n,bR^m выпукло.

Теорема 2.3.Выпуклое множество содержит любые выпуклые комбинации любых своих точек.

Теорема 2.4.Замыканиевыпуклого множестваХ выпукло.

Проекция точки на выпуклые множества.

Расстояние  от точкиvдо множестваХ в евклидовом пространстве определяется по формуле = inf||v – х||, xХ

Определение 2.3.ТочкарXназывается проекцией точкиv на множествоХ, если

||v – р||= inf||v – х||, xХ

Теорема 2.5.Для любого множестваХи любой точки v существует точка, являющаяся проекцией точкиv.

Теорема 2.6.Для того, чтобы точкабыла проекцией точки vRⁿ на выпуклое множествоХнеобходимо и достаточно, чтобы для любогоxХвыполнялось неравенство(x–p),( v–p) 0.

По определению скалярного произведения (x–p),(v–p)=||x–p||×||v–p||cos(), где– угол между векторами (x–p) и (v–p). Таким образом, знак скалярного произведения определяется углом между векторами (x–p) и ( v–p).

Следствие 2.6.Проекция любой точкиvRⁿ на выпуклое множествоХединственная.

Теоремы отделимости.

Гиперплоскостью в Rⁿназывают множество вида:={x|c,xc,v}, гдес0_n,где 0_n–n–мерный нуль–вектор вRⁿ.

В пространстве Rⁿгиперплоскость определяют два полупространства (подмножества):

Rⁿ⁺()= {x: c,x  c,v} и

R^n–()= {x: c,x  c,v} .

Теорема отделимости 2.7.Для любого выпуклого и замкнутого множестваХи любой точкиv, не принадлежащей множествуХ, существует такая гиперплоскость

 = {x: c,x  c,v} , чтоХ R^n–().

Теорема 2.8.В любой граничной точкер выпуклого множестваХсуществует опорная гиперплоскость.

Угловые точки выпуклого множества

Определение 2.4.Точкаz Хназывается угловой (крайней) точкой, если на множествеХона не может быть представлена в виде выпуклой комбинации каких–либо точекхиу (дляху) изХ:z()(1–)x+y

Теорема 2.9.Любая точка замкнутого выпуклого и ограниченного множестваХможет быть представлена в виде выпуклой комбинации конечного числа угловых точек этого множества.

Конус. Теорема Фаркаша – Минковского.

Определение 2.5.МножествоKRⁿ называется конусом, если из справедливостих K следует справедливостьх Kдля любого>0.

Определение 2.6.Выпуклым конусом называется конус, который одновременно является выпуклым множеством.

Определение 2.7.ПустьK– выпуклый конус, тогда множество

K ^*={y|x,y0,xK, yRⁿ} называется сопряженным конусом.

Лемма 2.1.Сопряженный конус является замкнутым выпуклым конусом.

Теорема Фаркаша–Минковского 2.10.Пусть конусK={х|хRⁿ,A^Tх0_n}, тогда сопряженный конусK ^* равен ={у|уRⁿ , у=A , 0_n}

Следствие 2.10.Пустьх,bRⁿ,uR^m ,B– матрица размерностиm×n. Еслиb,x 0 для всехх, удовлетворяющих системеBх 0_{m ,}то системаB^Tu= b разрешима приu 0_m .

Выпуклые функции.

Определение 2.8.Функцию(x) , определенную на выпуклом множествеХ, называют выпуклой, если для любыхх,yХи всех[0,1] выполняется неравенство ((1–)x+y)(1–)(x)+(y) (см. рис 2.5).

(рис. 2.5.).

Примером выпуклой функции может служить квадратичная функция с положительно (x) определенной симметрической матрицейВ.

Теорема.2.11. Выпуклая функция(x), определенная на выпуклом множествеX, непрерывна в каждой внутренней точке этого множества.

Теорема. 2.12. Выпуклая функция(x), заданная на выпуклом множествеX, в каждой внутренней точке имеет производную по любому направлениюS(||s|| =1).