Журнал вычислительной математики и математической физики, 2020, T. 60, № 3, стр. 534-546

ВВЕДЕНИЕ

В работе [1] была развита методология решения задач многокритериальной оптимизации в рамках универсальной вычислительной процедуры, позволяющей использовать существующие численные методы скалярной оптимизации для аппроксимации множества Парето. Без предъявления дополнительных требований к вектору частных критериев эффективности и множеству допустимых решений, универсальная процедура используется в настоящей работе как инструмент разработки численных методов построения множества Парето.

1. ПОСТАНОВКА ЗАДАЧИ

Пусть в $\,s$-мерном евклидовом пространстве ${{\mathbb{R}}^{s}}$ определена $\,m$-мерная непрерывная вектор-функция

образующая вектор частных критериев эффективности, принимающий на непустом компактном множестве допустимых решений (допустимом множестве) положительные значения, $w\left( x \right) > 0$, так что справедливы соотношения и, следовательно, множество достижимых векторных оценок $w\left( X \right)$ из (3) принадлежит внутренности $\operatorname{int} \mathbb{R}_{ + }^{m}$ неотрицательного ортанта $\mathbb{R}_{ + }^{m}$. Без ограничения общности будем полагать, что каждый частный критерий эффективности из набора желательно увеличивать на множестве допустимых решений $X \subset {{\mathbb{R}}^{s}}$.

Определение 1. Векторная оценка $w \in w\left( X \right)$ эффективна (слабо эффективна), если для всякой векторной оценки $u \in w\left( X \right)$ система неравенств $u \geqslant w$ несовместна при условии, что хотя бы одно неравенство строгое (все неравенства строгие).

Векторная оценка $w \in w\left( X \right)$ доминируема или определенно неэффективна, если существует векторная оценка $u \in w\left( X \right)$, $u > w$.

Всякое допустимое решение $x \in X$, доставляющее эффективное (слабо эффективное, доминируемое) значение вектора $w\left( x \right)$, называется эффективным (слабо эффективным, доминируемым) решением.

В согласии с определением 1, эффективная векторная оценка слабо эффективна, достижимая векторная оценка $w \in w\left( X \right)$ либо слабо эффективна, либо доминируема, множества эффективных (${{X}_{e}}$), слабо эффективных (${{X}_{0}}$) и доминируемых (${{X}_{\partial }}$) решений из множества допустимых решений (X) подчиняются соотношениям

а множества $w\left( {{{X}_{e}}} \right)$, $w\left( {{{X}_{0}}} \right)$, $w\left( {{{X}_{\partial }}} \right)$, $w\left( X \right)$ – эффективных, слабо эффективных, доминируемых и достижимых векторных оценок удовлетворяют соотношениям где $\emptyset $ – пустое множество, $ \cup $ ($ \cap $) – символ объединения (пересечения) множеств.

В качестве решения задачи многокритериальной оптимизации будем рассматривать множество Парето (множество эффективных векторных оценок $w\left( {{{X}_{e}}} \right)$), причем методы аппроксимации множества $w\left( {{{X}_{e}}} \right)$ разрабатываются на базе универсальной вычислительной процедуры [1].

В дальнейшем потребуются следующие определения.

Определение 2. Если $\left\| v \right\|$ – норма вектора $v \in {{\mathbb{R}}^{m}}$, то величина

называется отклонением множества $W$ от множества $U$, а величина называется расстоянием по Хаусдорфу между множествами $W$ и $U$.

Определение 3. Величина

называется расстоянием по Чебышёву между точками $w,u \in {{\mathbb{R}}^{m}}$.

Определение 4. Заданная на выпуклом множестве $A \subset {{\mathbb{R}}^{s}}$ функция $f$ называется:

вогнутой на $A$, если для любых $x,y \in A$, $\rho \in \left( {0,1} \right)$ выполняется неравенство

квазивогнутой на $A$, если для любых $x,y \in A$, $\rho \in \left( {0,1} \right)$ выполняется неравенство

Дифференцируемая на выпуклом множестве $A \subset {{\mathbb{R}}^{s}}$ функция $f$ называется псевдовогнутой на $A$, если для любых $x,y \in A$ неравенство

влечет неравенство $f\left( x \right) \geqslant f\left( y \right)$, где $\nabla f$ – градиент функции $f$, $\left\langle {a,b} \right\rangle $ – скалярное произведение векторов $a,b \in {{\mathbb{R}}^{s}}$.

Определение 5. Заданная на выпуклом множестве $A \subset {{\mathbb{R}}^{s}}$ функция $f$ называется $\omega $-вогнутой на $A$, если для любых фиксированных $x,y \in A$ при условии $f\left( y \right) \geqslant f\left( x \right)$ можно указать величину $\omega = \omega \left( {x,y} \right) \in \left( {0,1} \right]$ такую, что для любого $\rho \in \left( {0,1} \right)$ выполняется неравенство

Функция $f$ называется выпуклой (квазивыпуклой, псевдовыпуклой, $\omega $-выпуклой) на выпуклом множестве $A \subset {{\mathbb{R}}^{s}}$, если функция $ - f$ вогнута (квазивогнута, псевдовогнута, $\omega $-вогнута) на $A$.

В согласии с [2] определения 1–4 являются стандартными. Определение 5 при $\omega \equiv 1$ совпадает с определением вогнутой функции, а в предельном случае $\omega \equiv 0\,$– с определением квазивогнутой функции; каждая вогнутая, псевдовогнутая, $\omega $-вогнутая функция квазивогнута. Отметим, что операции суммирования и взятия минимума (максимума) сохраняет свойство $\omega $-вогнутости (выпуклости) функций. Следующая лемма устанавливает связь меду $\omega $-вогнутыми и псевдовогнутыми функциями.

Лемма 1. 1. Если функция $f$ дифференцируема и $\omega $-вогнута на выпуклом множестве $A \subset {{\mathbb{R}}^{s}}$, то она псевдовогнута на $A$.

2. Если функция $f$ псевдовогнута на выпуклом множестве $A \subset {{\mathbb{R}}^{s}}$, то она $\omega $-вогнута на $A$.

Доказательство. 1. Предположим от противного, что для некоторой пары точек $x,y \in A$, $x \ne y$ выполняется соотношение

Тогда для любой точки

справедливо утверждение и для достаточно малых $\rho = \frac{{\left\| {z - x} \right\|}}{{\left\| {y - x} \right\|}} > 0$ из-за соотношения $\mathop {\lim }\limits_{\rho \to 0} \frac{{o\left( \rho \right)}}{\rho } = 0$ выполняется неравенство что невозможно для $\omega $-вогнутой функции $f$, поскольку согласно определению 5 заданная выше точка $z$ удовлетворяет неравенству что и доказывает первое утверждение леммы.

2. Предположим от противного, что для некоторой пары точек $x,y \in A$, $f\left( y \right) \geqslant f\left( x \right)$ при любом $\omega \in \left( {0,1} \right]$ можно указать точку ${{z}^{\omega }} \in \left[ {x,y} \right]$, удовлетворяющую неравенству

Если выполняется хотя бы одно из равенств

то из неравенства (6) следует утверждение тогда как ввиду квазивогнутости псевдовогнутой функции $f$ при любых $y \in {{A}_{0}}\left( x \right)$, ${{z}^{\omega }} \in \left[ {x,y} \right]$ выполняется противоположное соотношение

Тем самым с необходимостью из утверждения (1) вытекает утверждение

где первое неравенство вытекает из (6), поскольку выполняются соотношения

Ввиду компактности отрезка $\left[ {x,y} \right]$ из произвольной сходящейся последовательности величин

можно выбрать такую бесконечную подпоследовательность что последовательность векторов ${{\left\{ {{{z}^{{\omega \left( t \right)}}}} \right\}}_{{t \in T}}} \subset \left( {x,y} \right]$ сходится к точке отрезка $\left[ {x,y} \right]$:

Если $z* \ne x$, то переходя в последнем неравенстве следствия к пределу по $\omega = \omega \left( t \right)$, $t \in T$, с учетом последних двух предельных соотношений можно утверждать

что опять-таки противоречит квазивогнутости псевдовогнутой функции $f$, так что с необходимостью $z* = x$. Но тогда утверждение (7) влечет соотношения переходя в последних неравенствах к пределу по $t \in T$, с учетом двух последних предельных соотношений можно утверждать, что выполняется неравенство $\left\langle {\nabla f\left( x \right),y - x} \right\rangle \leqslant 0$. Это, в согласии с определением псевдовогнутой функции, влечет неравенство $f\left( x \right) \geqslant f\left( y \right)$, тогда как согласно (7) из неравенства (1) следует противоположное утверждение $f\left( y \right) > f\left( x \right)$. Из противоречия следует второе утверждение леммы. Лемма доказана.

Напомним несколько полезных свойств квазивогнутых (и, следовательно, $\omega $-вогнутых) функций.

Лемма 2. 1. Если заданная на непустом выпуклом множестве $A \subset {{\mathbb{R}}^{s}}$ функция $f$ является квазивогнутой на $A$, то каждое из ее множеств Лебега

либо пусто, либо выпукло.

2. Если функция $f$ непрерывна на непустом компакте $A$, то каждое из множеств Лебега $L\left( {f,\beta } \right)$ либо пусто, либо компактно.

Доказательство. 1. Пусть множество $L\left( {f,\beta } \right) \ne \emptyset $. Тогда для любой пары точек $x,y \in L\left( {f,\beta } \right)$, $x \ne y$ и любой точки $z \in \left( {x,y} \right)$ с учетом определения 4 выполняется:

так что $z \in L\left( {f,\beta } \right)$, что и доказывает первое утверждение леммы.

2. Компактность множеств Лебега функции $f$ непосредственно следует из непрерывности $f$ на компакте $A$. Лемма доказана.

2. УНИВЕРСАЛЬНАЯ ПРОЦЕДУРА

Универсальная вычислительная процедура в работе [1] опирается на ряд неформальных соображений. Для построения множества векторных оценок $w\left( {{{X}_{e}}} \right)$, эффективных по критерию $w\left( x \right)$, недостаточно стремиться к увеличению каждого частного критерия из набора (4), поскольку в этом случае достигаются лишь «рекордные» на допустимом множестве $X$ значения каждого из частных критериев, а не множество эффективных векторных оценок в целом. Необходимо, вообще говоря, добиваться увеличения значений частных критериев в каждом подмножестве критериев из набора (4), с той лишь оговоркой, что добившись улучшения значений критериев для фиксированного подмножества ${{\left\{ {{{w}_{k}}\left( x \right)} \right\}}_{{k \in M}}}$, где $\emptyset \ne M \subset I$, можно не беспокоиться о значениях критериев в любом вложенном подмножестве ${{\left\{ {{{w}_{k}}\left( x \right)} \right\}}_{{k \in K}}}$, $K \subset M$.

Дадим в согласии с [1] строгое описание универсальной процедуры аппроксимации множества эффективных векторных оценок.

На множестве допустимых решений $X \subset {{\mathbb{R}}^{s}}$ строится последовательность множеств $\left\{ {{{X}_{t}}} \right\}_{{t = 1}}^{\infty } \subset X$, где по-прежнему $X$ – непустое компактное множество. Если ${{X}_{1}} \subset X$ – произвольное начальное приближение (например, оно может включать единственное допустимое решение ${{x}^{1}} \in X$, так что ${{X}_{1}} = \left\{ {{{x}_{1}}} \right\}$), и известно множество ${{X}_{t}}$, $t \geqslant 1$, то следующее за ним множество ${{X}_{{t + 1}}}$ подчиняется соотношениям

где $A + B$ – векторная сумма множеств $A,B \subset {{\mathbb{R}}^{s}}$.

В согласии с соотношениями (8) всякая опорная точка $x \in {{X}_{t}}$ порождает на следующем t + 1-м уровне непустую векторную сумму множеств ${{X}_{{t + 1}}}\left( x \right)$, причем направление $h\left( {x,J} \right)$ перехода из опорной точки $x \in {{X}_{t}}$ в следующую точку $y = x + h\left( {x,J} \right) \in {{X}_{{t + 1}}}\left( x \right)$, $J \in {{\mathcal{M}}_{t}}\left( x \right)$ удовлетворяет условиям

где ненулевые направления $h\left( {x,J} \right) \ne 0$ подчиняются соотношениям

Последовательность множеств (8) в каждой опорной точке $x \in {{X}_{t}}$ ветвится, причем степень ее ветвления $\left| {{{\mathcal{M}}_{t}}\left( x \right)} \right|$ определяет множество не вложенных друг в друга подмножеств ${{\mathcal{M}}_{t}}\left( x \right) \subset {{2}^{I}}$, заданное соотношениями

Наибольшая степень ветвления последовательности (8) совпадает с наибольшим числом не вложенных друг в друга подмножеств множества номеров частных критериев эффективности $I = \left\{ {k\,\left| {\,1 \leqslant k \leqslant m} \right.} \right\}$, так что

где $\left| A \right|$ – количество элементов в конечном множестве $A$, $\left\lfloor z \right\rfloor $ – целая часть числа $z{\kern 1pt} $.

Соотношения (10), (11) включают величину $\varepsilon = {{\varepsilon }_{t}}\left( x \right) \in \left( {0,1} \right)$ – параметр возмущения, который в начальной точке ${{x}^{1}}$ и в любых соседних точках ${{x}^{t}} \in {{X}_{t}}$, ${{x}^{{t + 1}}} \in {{X}_{{t + 1}}}({{x}^{t}})$ последовательности (8) таких, что

удовлетворяет условиям где величина $\kappa $ определяет степень дробления параметра возмущения. Эта величина может быть выбрана любой на интервале $\left( {0,1} \right){\kern 1pt} $, но является фиксированной на протяжении всей вычислительной процедуры.

Замечание 1. Прокомментируем процедуру (8)–(13).

В согласии с соотношениями (9), (10) последовательность (8) определена таким образом, что переход из опорной точки $x \in {{X}_{t}}$ по ненулевому направлению $h\left( {x,J} \right)$, $J \in {{\mathcal{M}}_{t}}\left( x \right)$ в новую опорную точку $y = x + h\left( {x,J} \right) \in X \cap {{Y}_{J}}\left( {x,\varepsilon } \right) \cap Y\left( {x,\varepsilon } \right)$ обеспечивает следующие результаты:

благодаря включению $y \in {{Y}_{J}}\left( {x,\varepsilon } \right)$ достигается относительное (порядка ${{\varepsilon }^{2}}$) увеличение значений критериев из множества ${{\left\{ {{{w}_{k}}} \right\}}_{{k \in J}}}$ за счет возможного относительного уменьшения (на величину порядка $\varepsilon $) значений остальных критериев ${{\left\{ {{{w}_{k}}} \right\}}_{{k \in I\backslash J}}}$;

включение $y \in Y\left( {x,\varepsilon } \right)$ препятствует слишком резкому росту значений критериев из выделенного множества (18), что является существенным на поздних этапах вычислительной процедуры, не позволяя переходить от одной эффективной векторной оценки к другой и возвращаться обратно, через все множество достижимых векторных оценок;

соотношения (11) позволяют ограничиться теми ненулевыми направлениями $h\left( {x,J} \right)$, $J \in {{\mathcal{M}}_{t}}\left( x \right)$, для которых соответствующие множества улучшаемых на величину порядка ${{\varepsilon }^{2}}$ частных критериев ${{\left\{ {{{w}_{k}}} \right\}}_{{k \in J}}}$ невозможно пополнить, что также существенно на поздних этапах вычислительной процедуры, поскольку препятствует слишком резкому увеличению числа опорных точек $\left| {{{X}_{t}}} \right|$;

соотношения (12), (13) обеспечивают дробление параметра возмущения $\varepsilon $, если невозможно относительное увеличение (на величину порядка ${{\varepsilon }^{2}}$) хотя бы одного из улучшаемых на предыдущих этапах частных критериев. Поскольку непрерывные критерии на компакте $X \subset {{\mathbb{R}}^{s}}$ ограничены, для всякой последовательности решений

соответствующие значения параметра возмущения ${{\varepsilon }_{t}}({{x}^{t}})$ с ростом $t$ стремятся к нулю.

В согласии с [1] можно утверждать, что последовательность множеств $\left\{ {w\left( {{{X}_{t}}} \right)} \right\}_{{t = 1}}^{\infty }$, заданная соотношениями (8)–(13), аппроксимирует множество эффективных векторных оценок в следующем смысле.

Теорема 1. Если вектор-функция $w\left( x \right) \in {{\mathbb{R}}^{m}}$ положительно определена, удовлетворяет условию Липшица и $\omega $-вогнута на непустом выпуклом компакте $X$, то отклонение множества эффективных векторных оценок $w\left( {{{X}_{e}}} \right)$ от аппроксимирующего множества $w\left( {{{X}_{t}}} \right)$ и отклонение множества $w\left( {{{X}_{t}}} \right)$ от множества слабо эффективных векторных оценок $w\left( {{{X}_{0}}} \right)$ стремятся к нулю с ростом номера аппроксимаций $t$:

Следствие 1. Если множества эффективных и слабо эффективных векторных оценок совпадают, $w\left( {{{X}_{e}}} \right) = w\left( {{{X}_{0}}} \right)$, то в согласии с определением 2 последовательность аппроксимаций $\left\{ {w\left( {{{X}_{t}}} \right)} \right\}_{{t = 1}}^{\infty }$ сходится к множеству $w\left( {{{X}_{e}}} \right)$ в метрике Хаусдорфа.

3. ПОСТРОЕНИЕ МЕТОДА

Универсальная процедура (8)–(13) не содержит точного рецепта построения аппроксимирующей последовательности $\left\{ {w\left( {{{X}_{t}}} \right)} \right\}_{{t = 1}}^{\infty }$, поскольку для каждого непустого подмножества $J \in {{\mathcal{M}}_{t}}\left( x \right)$ не дает прямого указания, в какую именно “подходящую” опорную точку $y = x + h\left( {x,J} \right) \in X \cap {{Y}_{J}}\left( {x,\varepsilon } \right) \cap Y\left( {x,\varepsilon } \right)$ следует переходить из исходной опорной точки $x \in {{X}_{t}}$.

Процедура (8)–(13) становится реальной вычислительной процедурой (численным методом), если она дополнена правилом выбора

а) начальной точки ${{x}^{1}} \in X$ (либо множества начальных точек ${{X}_{1}} \subset X$, $\left| {{{X}_{1}}} \right| > 1$, если в работе численного метода предусмотрен мультистарт);

б) каждой последующей опорной точки $y \in X \cap {{Y}_{J}}\left( {x,\varepsilon } \right) \cap Y\left( {x,\varepsilon } \right)$.

Подчеркнем, что сходимость вычислительной процедуры (8)–(13) сохраняется, если правило выбора меняется от этапа к этапу процедуры.

Нашей целью является правило выбора, не требующее выдвижения дополнительных (по сравнению с формулировкой теоремы 1) предположений о характере вектор-функции $w\left( x \right)$ и множества допустимых решений $X$.

В согласии с утверждением теоремы 1, сходимость численных методов на основе универсальной процедуры обеспечена при старте из любых точек допустимого множества $X\,$. Вместе с тем эффективность численного метода может зависеть от состава начального множества ${{X}_{1}} \subset X$, причем для конкретизации подобного множества приходится учитывать неформальные соображения.

Как было указано в замечании 1, при выборе новой опорной точки не все требования не являются существенными на начальном этапе вычислительной процедуры. Тем самым для формирования начального приближения ${{X}_{1}}$ можно использовать упрощенный вариант процедуры (8)–(13), где вместо требований (10) предъявляются требования

чем отменяются ограничения сверху на приращения частных критериев ${{\left\{ {{{w}_{k}}} \right\}}_{{k \in J}}}$, тогда как множество подмножеств в (11) приобретает вид и содержит все такие непустые подмножества $J$ множества $I = \left\{ {k\,\left| {\,1 \leqslant k \leqslant m} \right.} \right\}$, что каждый из частных критериев ${{\left\{ {{{w}_{k}}} \right\}}_{{k \in J}}}$ допускает относительное (порядка ${{\varepsilon }^{2}}$) увеличение значения. Сформулируем следующее

Правило выбора начального приближения.

Чтобы с помощью упрощенной процедуры (8), (9), (10а), (11а), (12), (13) генерировать начальное приближение ${{X}_{1}}$, нужно уметь в соотношениях (10а) указать следующую за опорной точкой $x \in X$ опорную точку $y \in X \cap {{Y}_{J}}\left( {x,\varepsilon } \right)$. Для этого достаточно отыскать экстремум вспомогательной функции

где ${{\varphi }_{0}}$ – евклидово расстояние между фиксированным опорным решением $x \in X$ и произвольным допустимым решением $z \in X$.

В самом деле, в предположениях теоремы 1 вместе с функциями ${{w}_{k}}\left( y \right)$ каждая из функций ${{\left[ {{{w}_{k}}\left( x \right)} \right]}^{{ - 1}}}{{w}_{k}}\left( y \right)$ является положительной, непрерывной и $\omega $-вогнутой по переменным y на выпуклом компакте $X\,$, так что в согласии с леммой 2 заданные соотношениями (10), (10а) множества

замкнуты и выпуклы, а согласно (11а) каждое пересечение множеств является непустым выпуклым компактом. В согласии с (10), (10а) опорная точка $x \notin {{Y}_{J}}\left( {x,\varepsilon } \right)$, так что проекция внешней опорной точки $x \in X$ на выпуклый компакт $X \cap {{Y}_{J}}\left( {x,\varepsilon } \right) \ne \emptyset $ существует, единственна и удовлетворяет условиям $y \in X \cap {{Y}_{J}}\left( {x,\varepsilon } \right)$, $y \ne x$, так что ее можно использовать в соотношениях (10а) в качестве следующей опорной точки.

Задача отыскания следующей опорной точки $y$ согласно (15) сводится к задаче выпуклого программирования: отысканию минимума выпуклой квадратичной функции на непустом выпуклом компакте,

Если возможна линейная аппроксимация выпуклого компакта “изнутри”, когда в него вписан непустой выпуклый многогранник $Z \subset X \cap {{Y}_{J}}\left( {x,\varepsilon } \right)$, следующей опорной точкой в соотношениях (10а) может быть выбрана проекция

опорной точки $x \in X$ на выпуклый многогранник $Z$, так что поиск следующей опорной точки сводится к решению задачи квадратичного программирования, которое может быть получено (см. [3]) за конечное число арифметических действий.

По упрощенной процедуре через несколько шагов (количество которых определяется спецификой решаемой многокритериальной задачи) будет построено начальное приближение ${{X}_{1}}$. В согласии с соотношениями (10а), (11а) его образ в пространстве критериев ${{\mathbb{R}}^{m}}$ – множество $w\left( {{{X}_{1}}} \right)$ – может представлять собой грубую аппроксимацию множества Парето по всему “фронту”, если упрощенная процедура стартует при достаточно малом $\kappa \in \left( {0,1} \right)$ из доминируемой точки ${{x}^{1}} \in X{\backslash }{{X}_{0}}$, $w({{x}^{1}}) \in \operatorname{int} w\left( X \right)$.

Предположим, что вычислительная процедура (8)–(13) стартовала из конкретной опорной точки начального множества ${{X}_{1}}$. В согласии с соотношениями (10) на каждом шаге процедуры с номером $t \geqslant 1$ необходимо определить следующую за опорной точкой $x \in {{X}_{t}}$ новую опорную точку $y \in X \cap {{Y}_{J}}\left( {x,\varepsilon } \right) \cap Y\left( {x,\varepsilon } \right)$, где каждое из множеств

компактно, поскольку является пересечением выпуклого компакта $X \cap {{Y}_{J}}\left( {x,\varepsilon } \right)$ c замкнутым множеством $Y\left( {x,\varepsilon } \right)$, но не выпукло, поскольку $Y\left( {x,\varepsilon } \right)$, вообще говоря, не является выпуклым; более того, пересечение множеств (16) в общем случае не является связным множеством.

Таким образом, если допустимое множество $X \subset {{\mathbb{R}}^{s}}$ задано функциональными ограничениями, поиск подходящей опорной точки $y \in X \cap {{Y}_{J}}\left( {x,\varepsilon } \right) \cap Y\left( {x,\varepsilon } \right)$ может быть сведен к решению системы нелинейных неравенств общего вида.

Другой подход к выбору опорной точки из множества (16) связан с поиском экстремума некоторой вспомогательной функции.

Если выбрана функция (14), то согласно (11) при условии $J \in {{\mathcal{M}}_{t}}\left( x \right)$ пересечение множеств (16) не пусто, проекция

внешней опорной точки $x \in X$ на непустой компакт $X \cap {{Y}_{J}}\left( {x,\varepsilon } \right) \cap Y\left( {x,\varepsilon } \right)$ существует, удовлетворяет условиям и ее можно использовать в соотношениях (10) в качестве следующей опорной точки. Однако проекция (17) может быть не единственна, и ее определение является более трудной задачей, чем задача (15) – проектирование внешней точки на выпуклый компакт.

Прежде чем перейти к рассмотрению вспомогательных функций, отличных от (14), заметим, что образ множества (16) в пространстве критериев ${{\mathbb{R}}^{m}}$ существенно упрощается, если к заданному в (1) векторному критерию $w \in {{\mathbb{R}}^{m}}$ применить следующее линейное преобразование:

где опорная точка $x \in X$ и непустое подмножество $J \subset I = \left\{ {k\,\left| {\,1 \leqslant k \leqslant m} \right.} \right\}$ фиксированы. В согласии с преобразованием (18) каждая из функций ${{u}_{k}}\left( y \right)$ непрерывна и $\omega \,$-вогнута вместе с функциями ${{w}_{k}}\left( y \right)$.

В согласии с определениями (10), (18) задающие пересечение (16) множества приобретают вид

Тем самым преобразование (18) переводит заданные соотношениями (10) многогранные множества

в неотрицательный ортант и многогранное множество соответственно, а их пересечение, $m$-мерный параллелепипед в единичный $m$-мерный куб

В рамках процедуры (8)–(13) для отыскания последующей опорной точки можно сформулировать следующие правила выбора.

Правило 1. В согласии с определением 3 и соотношениями (18)–(21) выберем в качестве вспомогательной неотрицательную непрерывную функцию

т.е. расстояние по Чебышёву между началом координат $0 \in {{U}_{m}}$ и произвольной векторной оценкой $u\left( z \right) \in u\left( X \right) \cap \mathbb{R}_{ + }^{m}$, где последнее включение следует из включения $z \in X \cap {{Y}_{J}}\left( {x,\varepsilon } \right)$ согласно утверждению (20).

Задача вычисления чебышевского расстояния между началом координат и пересечением $u\left( X \right) \cap \mathbb{R}_{ + }^{m}$ сводится к отысканию минимума непрерывной функции (22) на выпуклом компакте,

что позволяет определить на множестве (16) искомую опорную точку $y \in X \cap {{Y}_{J}}\left( {x,\varepsilon } \right) \cap Y\left( {x,\varepsilon } \right)$. Об этом свидетельствует

Теорема 2. Пусть при непустом фиксированном подмножестве $J \subset \left\{ {k\,\left| {\,1 \leqslant k \leqslant m} \right.} \right\}$ в опорной точке $x \in X$ определено преобразование (18), выпуклый компакт $X$, выпуклое замкнутое множество ${{Y}_{J}}\left( {x,\varepsilon } \right)$ и замкнутое множество $Y\left( {x,\varepsilon } \right)$ заданы соотношениями (2), (10), (19), выпуклый компакт (единичный куб) ${{U}_{m}}$ определен в (21).

Если неотрицательная величина

то ее доставляет решение $y$, удовлетворяющее соотношениям

В противном случае выполняется строгое неравенство

и пересечение множеств (16) пусто,

Доказательство. Поскольку минимум непрерывной функции $\mathop {\max }\limits_{1 \leqslant k \leqslant m} {{u}_{k}}\left( z \right)$ на выпуклом компакте $X \cap {{Y}_{J}}\left( {x,\varepsilon } \right)$ достигается, решение

Согласно определению куба ${{U}_{m}} \subset \mathbb{R}_{ + }^{m}$ в (21) и расстояния по Чебышёву, для любых векторов $u \in \mathbb{R}_{ + }^{m}$ справедливы соотношения

так что в согласии с (20), (21) из условия (24) с необходимостью следуют включения что с учетом включения $y \in X$, доказывает утверждение (25). Если же утверждение (24) не выполняется, то согласно последнему неравенству в (26) с необходимостью выполняются соотношения что и доказывает последнее утверждение теоремы. Теорема доказана.

Правило 2. Определим вспомогательную функцию

т.е. расстояние по Чебышёву между барицентром единичного куба (21), вектором $\frac{1}{2}\sum\nolimits_{k = 1}^m {{{e}^{k}}} \in {{U}_{m}}$, и произвольной векторной оценкой $u\left( z \right) \in u\left( X \right)$. Тогда в качестве новой опорной точки можно выбрать решение, доставляющее минимум неотрицательной непрерывной функции (27) на выпуклом компакте – множестве допустимых решений $X$,

Сформулируем этот результат в качестве следствия из доказательства теоремы 2.

Следствие 2. Пусть при некотором непустом фиксированном подмножестве $J \subset \left\{ {k\,\left| {\,1 \leqslant k \leqslant m} \right.} \right\}$ в опорной точке $x \in X$ определено преобразование (18), выпуклые компакты $X$, ${{Y}_{J}}\left( {x,\varepsilon } \right)$ и компакт $Y\left( {x,\varepsilon } \right)$ заданы соотношениями (2), (10), выпуклый компакт (единичный куб) ${{U}_{m}}$ определен в (21). Тогда при условии

доставляющее минимум непрерывной функции (27) решение $y \in X$ удовлетворяет включению

В противном случае выполняется строгое неравенство

а пересечение множеств (16) пусто,

Замечание 2. По сравнению с задачей (23) при решении экстремальной задачи (28) не приходится учитывать $m$ функциональных ограничений, определяющих в согласии с (10) множество ${{Y}_{J}}\left( {x,\varepsilon } \right)$. Вместе с тем минимизируемая функция в (23) несколько проще, чем соответствующая функция в (28).

Следует отметить, что множество достижимых векторных оценок $w\left( X \right)$ – образ выпуклого допустимого множества $X$ – не обязательно является выпуклым, даже если в качестве частных критериев эффективности используются вогнутые функции (см. [4]). Согласно преобразованию (18) множество $u\left( X \right)$ также не выпукло. Вместе с тем всякой векторной оценке $u\left( x \right)$ опорного решения $x \in X$ можно сопоставить подмножество

т.е. совокупность точек множества $u\left( X \right)$ таких, что их “видно” из точки $u\left( x \right)$.

Лемма 3. Если для некоторого непустого фиксированного подмножества $J \subset I = \left\{ {k\,\left| {\,1 \leqslant k \leqslant m} \right.} \right\}$ пересечение множеств (16) содержит решение

где векторная оценка $u\left( \cdot \right)$ и подмножество $V\left( \cdot \right)$ заданы соотношениями (18), (29), то не пусто пересечение отрезка $\left[ {u\left( x \right),u\left( y \right)} \right] \subset u\left( X \right)$ с одной из граней ${{U}_{{mk}}}$, $k \in J$ единичного куба ${{U}_{m}}$,

Доказательство. Из определений (18), (29) и условия (30) следует, что векторные оценки $u\left( x \right)$ и $u\left( y \right)$ удовлетворяют соотношениям

Следовательно, можно указать точку отрезка $v \in \left[ {u\left( x \right),u\left( y \right)} \right]$, удовлетворяющую соотношениям

что и доказывает утверждение (31). Лемма доказана.

Согласно лемме 3, если пересечение множеств (16) содержит хотя бы одно подходящее решение $y$, образ которого $u\left( y \right)$ “виден” из точки $u\left( x \right)$, то существует подходящее решение ${{y}^{J}}$ из пересечения (16), образ которого $u({{y}^{J}})$ расположен на одной из содержащих 0 граней ${{U}_{{mk}}}$, $k \in J,$ единичного куба ${{U}_{m}}$.

Правило 3. Введем вспомогательную функцию

Следующая теорема свидетельствует о том, что в условиях леммы 3 в качестве новой опорной точки можно выбрать решение, доставляющее минимум неотрицательной непрерывной $\omega $-вогнутой функции (32) на выпуклом компакте,

Теорема 3. Пусть при непустом фиксированном подмножестве $J \subset \left\{ {k\,\left| {\,1 \leqslant k \leqslant m} \right.} \right\}$ в опорной точке $x \in X$ определено преобразование (18), выпуклый компакт $X$, замкнутое множество $Y\left( {x,\varepsilon } \right)$ и выпуклые замкнутые множества ${{Y}_{J}}\left( {x,\varepsilon } \right)$, ${{U}_{m}}$ заданы соотношениями (2), (10), (19), (21), условие (30) леммы 3 выполнено.

Тогда справедливо утверждение

так что существует решение

Доказательство. В условиях теоремы выполняется неравенство

поскольку непрерывная функция (32) принимает на компакте $X \cap {{Y}_{J}}\left( {x,\varepsilon } \right)$ неотрицательные значения. Но в согласии с леммой 3 можно указать номер $i \in J$, грань ${{U}_{{mi}}} = \left\{ {u \in {{U}_{m}}\,\left| {\,{{u}_{i}} = 0} \right.} \right\}$ и вектор ${{v}^{J}} \in u\left( X \right) \cap {{U}_{{mi}}}$, так что в условиях теоремы прообраз векторной оценки ${{v}^{J}}$ решение ${{y}^{J}}$ удовлетворяет соотношениям

Следовательно, справедливо утверждение

что в согласии с первым включением (35) влечет утверждение (34). Теорема доказана.

Замечание 3. Рассмотрим важный частный случай, когда компоненты вектор-функций $w$, $u$ вогнуты. Но тогда функция (32) вогнута, и ее на выпуклом компакте $X \cap {{Y}_{J}}\left( {x,\varepsilon } \right)$ можно аппроксимировать кусочно-линейной функцией

Если возможна линейная аппроксимация выпуклого компакта “изнутри”, когда в него вписан непустой выпуклый многогранник $Z \subset X \cap {{Y}_{J}}\left( {x,\varepsilon } \right)$, то ввиду перестановочности минимумов задача поиска новой опорной точки (33) приближенно сводится к решению конечного числа $Q$ задач линейного программирования:

ВЫВОДЫ

В настоящей работе проанализированы возможности синтеза численных методов аппроксимации множества Парето на основе предложенной в [1] универсальной вычислительной процедуры. Рассматривался наиболее трудный случай, когда к вектору частных критериев эффективности и множеству допустимых решений не предъявляется никаких дополнительных требований (в частности, не требуется дифференцируемости критериальных функций и функциональных ограничений). Предполагается, что множество допустимых решений является выпуклым компактом, а компоненты вектора частных критериев эффективности – непрерывные $\omega $-вогнутые функции, удовлетворяющие условию Липшица. Лемма 1 определяет место $\omega $-вогнутых функций в качестве одного из обобщений понятия вогнутой функции.

Численный метод на основе универсальной процедуры характеризуется:

конкретным правилом выбора начального приближения;

конкретным правилом выбора каждого последующего опорного решения.

Построение начального приближения согласно предложенному правилу сводится к решению нескольких задач проектирования внешней точки на выпуклый компакт (к решению нескольких задач квадратичного программирования в линейном приближении).

В качестве правила перехода от текущего опорного решения к последующему предлагаются следующие 3 варианта.

Согласно правилам 1 и 2 требуется минимизировать расстояние по Чебышёву в пространстве критериев, преобразованных в соответствии с соотношением (18). Для этого в обоих случаях следует отыскать минимум непрерывной функции на выпуклом компакте. Как было указано в замечании 2, по правилу 1 минимизируется несколько более простая функция на более сложном множестве, по правилу 2 – несколько более сложная функция на более простом множестве.

Согласно правилу 3 следует минимизировать $\omega $-вогнутую функцию на выпуклом компакте; если критериальные функции можно считать вогнутыми, в линейном приближении задача минимизации сводится к решению ряда задач линейного программирования.

Сходимость вычислительной процедуры сохраняется, если правило выбора меняется от этапа к этапу процедуры. Следует лишь подчеркнуть, что правило 3 обеспечивает отыскание следующей опорной точки, если выполняются условия леммы 3.