7.1. ОСНОВНАЯ ИДЕЯ И ОСОБЕННОСТИ ВЫЧИСЛИТЕЛЬНОГО МЕТОДА ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ
Динамическое программирование - это вычислительный метод для решения задач оптимизаци специальной структуры с адитивними или мультипликативными целевыми функциями.
Динамическое программирование возникло и сформировалось в 1950-1953 гг. благодаря работам Р. Беллмана и его сотрудников. Первые задачи, которые привели к появлению вычислительного метода, были динамическими задачами управления запасами.
Идею вычислительного метода динамического программирования (ДП) рассмотрим на следующем примере:
максимизировать 
(7.1.1)
при условиях 
(7.1.2 )
Как видно, целевая функция задачи и ограничение являются суммой функций от одной переменной каждая. Такая функция, как известно, называется адитивной. Если все 
выпуклые, то для решения задачи можно применить метод множителей Лагранжа.
Если имеется много локальных минимумов, то этот метод дает лишь один из них. Если надо найти глобальный максимум, метод множителей Лагранжа применить невозможно.
Поэтому рассмотрим другой метод, обеспечивающий отыскание глобально-оптимального решения. Предположим, что все 
- целые числа. Предположим также, что в рассматриваемой задаче все переменные могут принимать лишь целочисленные значения.
Через 
обозначим абсолютный (глобальный) максимум 
при условии 
. Выберем некоторое значение 
и, зафиксировав его, максимизируем по всем остальным переменным 
. Предположим, что такая максимизация проведена для всех возможных значений . Тогда будет наибольшим из всех возможных значений . Формально этот процесс (эта процедура) записывается так:
(7.1.3)
причем
. (7.1.4)
Поскольку 
для неотрицательных целых чисел, удовлетворяющих условию (7.1.4), зависит от 
, то обозначим
. (7.1.5)
Предположим, что мы вычислили 
для всех допустимых целых значений = 
, где 
означает целую часть 
.
Очевидно, что
. (7.1.6)
Для вычисления (7.1.6) определим 
и для всех допустимых значений и выберем максимальное . Одновременно найдем оптимальное решение . Таким образом, если бы была известна функция , то вся задача свелась бы к задаче с одной переменной.
Покажем, как вычислить .
Обозначим
при условии
.
Повторив вышеприведенные выкладки, получим
, (7.1.7)
где
, (7.1.8)
причем максимум в (7.1.7) отыскивается при условии
.
Аналогичным образом вычисляем 
и т.д. В конце концов на 
-м шаге мы используем 'основное рекуррентное соотношение (ОРС) динамического программирования'
(7.1.9)
при условии, что
.
Используя ОРС (7.1.9), организуем процесс вычислений, как многошаговый процесс, следующим образом. На первом шаге, зафиксировав начало интервала 0 и изменяя его правый конец 
, вычисляем
(7.1.10)
для всех возможных значений =0, 1, . , b. Оптимальное решение первого шага обозначим через 
. Составляем таблицу динамического программирования первого шага (табл. 7.1) и заполняем ее результатами вычислений.
На втором шаге (=2) находим 
в соответствии с соотношением
, (7.1.11)
причем значения 
берем из табл. 7.1.
Вычисляем последовательно для всех значений = 0,1,.,
, используя результаты табл. 7.1. Одновременно находим 
и 
. Результаты вычислений заносим в таблицу второго шага (табл. 7.2).
Таблица 7.1 |
Таблица 7.2 |
||||||
|
|
|
|
|
|
|
|
|
|
0 |
0 |
||||||
|
1 |
1 |
||||||
|
|
|
||||||
Дале, пользуясь соотношением (7.1.8), последовательно вычисляем 
для всех значений
= 0, 1, 2, ., .
В конце концов, на последнем шаге при 
находим
, (7.1.12)
а также соответствующее оптимальное значение для последней переменной 
. Для отыскания значений всех остальных переменных 
надо воспользоваться таблицей 
и т.д. шагов. Полагая 
, из таблицы предшествующего шага находим (без вычислений)
.
Следовательно, динамическое программирование - это направленный последовательный перебор вариантов, который обязательно приводит к глобальному максимуму. Для применения метода необходимо табулировать функции 
, . , 
для всех допустимых значений .
Сравним метод динамического программирования по числу необходимых операций с простым перебором вариантов. Для упрощения расчетов примем 
.
При простом переборе число возможных вариантов (при условии целочисленности всех переменных 
) равно числу способов, которыми можно разместить одинаковых шаров в 
урн. Оно составляет
.
Например, при = 5, = 20, 
= 10626.
Оценим число операций, требуемых для решения этой задачи методом динамического программирования.
Для вычисления 
при фиксированном необходимо выполнить (+1) вычислений функции 
при 
. Следовательно, чтобы заполнить одну таблицу (при =0,1, .,) необходимо 
операций.
Таким образом, для вычисления всех функций 
, необходимо 
операций.
С учетом вычислений функции 
общее число операций составляет
.
Это значительно меньше, чем 
, то есть имеем существенное сокращение объема вычислений сравнительно с простым перебором.
Подведем некоторые итоги. Рассмотренную выше задачу (7.1.1), (7.1.2) с экономической точки зрения можно трактовать как задачу распределения одного ограниченного ресурса между разными способами производства, где - объем производства по 
-му способу ; 
- прибыль от достижения объема ; 
- затраты ресурса на производство по -му способу (при ограничении на общий объем использованного ресурса 
).
Поэтому можно трактовать как максимальную прибыль от первых 
способов производства, когда общий объем ресурса (сырья) равен единиц.
Рассматриваемую задачу можно интерпретировать как -шаговый процесс принятия решений, где на -м шаге принимается решение о том, какое количество ресурса из общего объема следует выделить на переработку по -му способу производства. Как видим, структура этой задачи не изменяется от числа шагов, то есть задача инвариантна относительно .
Решение для -шаговой задачи получается из решения для (
)-шаговой задачи путем добавления -го шага и использования результатов предыдущего (
)-го шага.
Следовательно, сущность динамического программирования состоит в замене решения данной -шаговой задачи последовательностью одношаговых задач.
Подводя итоги, назовем главные признаки (свойства) задач, к которым можно применить метод динамического программирования:
Задача должна допускать интерпретацию как -шаговый процесс принятия решений.
Задача должна быть определена для любого числа шагов и иметь структуру, не зависящую от их числа.
Для k-шаговой задачи должно быть задано некоторое множество параметров, описывающих состояние системы, от которых зависят оптимальные значения переменных. Это множество не должно изменяться при увеличении числа шагов. (В рассматриваемом выше примере таким параметром было общее количество ресурса.)
Выбор решения (стратегии управления) на -м шаге не должен влиять на предыдущие решения, кроме необходимого пересчета переменных.
Пусть - вектор параметров, описывающих состояние процесса (вектор состояния). Тогда оптимальное значение целевой функции для -шагового процесса будем называть функцией состояния.
Пусть Xk - вектор переменных управления (стратегия), который необходимо определить на -м шаге. Тогда для задач, к которым можно применить метод динамического программирования, должно выполняться следующее основное рекуррентное соотношение:
,
где 
- вектор состояния предыдущего ()-го шага при условиях и 
. В рассматриваемой задаче 
.
Сформулируем принцип оптимальности Беллмана, который обосновывает это соотношения [4; 18].
Оптимальная стратегия обладает следующим свойством : для любых начального состояния и начальной стратегии 
, стратегия на -м шаге должна быть оптимальной только относительно текущего состояния системы и не должны зависеть от предыдущих состояний.
Таким образом, принцип оптимальности Беллмана утверждает, что оптимальное управление системой на каждом шаге не зависит от предыстории процесса, то есть как система достигла текущего состояния, а определяется только этим состоянием. Системы (процессы), которые имеют такое свойство, называются марковскими.
Задача о выборе траектории
Основной принцип динамического программирования можно продемонстрировать на следующем примере [7].
Пример 7.1. Пусть самолет (или другой летательный аппарат), находящийся в точке 
на высоте 
и имеющий скорость 
, должен быть поднят на заданную высоту 
, а его скорость доведена до значения 
. Известен расход горючего для подъема с любой высоты 
на высоту 
при постоянной скорости 
, и расход горючего для увеличения скорости от 
к 
при
неизменной высоте 
. Найти оптимальную траекторию набора высоты и скорости, при которой общий расход горючего будет минимальным.
Предположим, что весь процесс набора высоты и скорости можно разделить на ряд элементарных последовательных шагов (этапов), на любом из которых самолет увеличивает только высоту или только скорость. Изобразим состояние самолета точкой на плоскости 
, где абсцисса отвечает скорости , а ордината - высоте .
Тогда процесс перемещения точки из начального состояния в конечное 
отобразится на плоскости некоторой ступенчатой ломаной (рис. 7.1). Эта траектория и будет характеризовать управление набором высоты и скорости.
Из всех возможных траекторий нужно выбрать такую, на которой значение выбранного критерия (расход горючего 
) будет наименьшим.
Для решения задачи методом динамического программирования разделим отрезок высоты 
на 
равных частей, а скорости 
- на 
равных частей.
Таким образом, за первый шаг процесса происходит либо изменение высоты на величину 
, либо изменение скорости на величину 
.
Таким образом, суммарное число шагов процесса по переводу самолета из состояния в будет равно 
.
С кажым шагом связан определенный расход горючего. Запишем на каждом из отрезков соответствующее значение расхода горючего (в условных единицах - у.о.т.). Тогда условия задачи представлены на рис. 7.2, а произвольной траектории, отмеченной стрелками, соответствует расход горючего:
= 12 + 11 + 10 + 8 + 11 + 10 + 10 + 13 + 15 + 20 + 9 + 12 + 14 = 165 у.о.т.
Общее количество всех возможных траекторий достаточно велико, а потому простой их перебор неприемлем, и поэтому применим принцип оптимальности Беллмана. Поскольку конечное состояние системы известно, то процесс построения оптимальной траектории начинаем с конца.
Из принципа оптимальности Беллмана следует, что если система находится в некоторой промежуточной точке 
, и известна конечная точка, то оптимальной стратегией будет та, которая переводит из точки 
в конечную 
по оптимальной траектории, которой отвечают наименьшие затраты горючего. Поскольку это справедливо для любой промежуточной точки, то приходим к выводу: оптимальная траектория имеет такое свойство - ее каждый участок (фрагмент) составляет оптимальную траекторию. Применим этот вывод для построения оптимальной траектории, двигаясь из конечной точки . В точку можно переместиться только из двух соседних точек 
и 
(см. рис. 7.3), причем только одним возможным способом, а поэтому выбора оптимального управления на последнем шаге нет - оно единственное. Если на предпоследнем шаге мы находились в точке , то перемещение в происходит по горизонтали и тратится 17 у.о.т., а если мы находились в точке , то движемся по вертикали и тратим 14 у.о.т. Эти значения минимальных затрат ставим у точек и и обводим кружком. Таким образом, число в кружке у точки всегда означает минимальный расход горючего для перемещения самолета из данной точки в конечную, а оптимальная траектория показана стрелками (рис. 7.3).
Теперь переходим к выбору оптимальной стратегии на предпоследнем шаге. Для этого рассмотрим пункты, из которых можно попасть в и за один шаг. Такими точками являются 
, 
, 
(рис. 7.4). Для кажой из них необходимо найти оптимальную траекторию в точку и соответствующий расход горючего. В частности, для выбора нет, нужно двигаться только по горизонтали и тратить 15 + 17 = 32 у.о.т. Для точки выбор существует: 
из нее в можно идти через или . В первом случае израсходуется 13 + 17 = 30 у.о.т., а во втором - 17 + 14 = 31 у.о.т. Итак, оптимальная траектория из в проходит через . Покажем эту траекторию стрелками, а соответствующий минимальный расход, равный 30 - обведем кружком в точке .
В конце концов для точки путь в - единственный (по вертикали), ему соответствует расход в 12 + 14 = 26 у.о.т. Это число обведем кружком в точке и покажем оптимальную траекторию (рис. 7.4).
Таким образом, двигаясь последовательно от точки к точке справа налево и сверху вниз, находим для каждой узловой точки оптимальную траекторию, ведущую к , и соответствующее ей минимальное значение расхода горючего (которое обводим кружком). Этот процесс заканчивается, приведя к начальной точке . Двигаясь теперь от нее в противоположном направлении, которое показано стрелками, последовательно проходим искомую траекторию от к . Эта оптимальная траектория показана на рис. 7.5 дополнительными стрелками. Число 139 означает минимальный расход горючего, отвечающий этой траектории.
 |
Поскольку в данной задаче фиксированы как начальная, так и конечная точки, то процесс построения оптимальной траектории можно было бы осуществлять и в противоположном направлении, от начала в конец. Тогда число в кружке означало бы минимальный расход горючего при перемещении самолета из
в точку, соответствующую числу в кружке. Очевидно, что при этом конечный результат - оптимальная траектория - не изменится.
Задачи последовательного принятия решений
Структура рассмотренной задачи распределения ресурсов такова, что переменные , 
по мере построения процесса можно было определять в произвольном порядке (то есть их можно было менять местами). Однако существует много задач, в которых решения должны определяться в строгой временной последовательности, и потому переменные 
, нельзя менять местами. Такие задачи называют задачами последовательного принятия решений. Для этих задач существует выбор между двумя разными схемами решения [18; 49]:
решение в прямом направлении, когда первый шаг схемы динамического программирования соответствует первому по времени принимаемому решению;
решение задачи в обратном направлении, когда последний шаг схемы динамического программирования отвечает первому фактически принимаемому решению.
Для объяснения этих двух схем рассмотрим такую задачу.
Задача об использовании трудовых ресурсов
Предпринимателю нужно определить оптимальное количество работников в каждый из месяцев. Производственные задания для каждого месяца известны, что дает возможность определить оптимальное количество рабочих на этот месяц. Предположим, что в
-й месяц идеальное число рабочих равно 
. Если бы предприниматель мог увольнять и набирать новых рабочих без дополнительных затрат, то он в -й месяц нанял бы равно рабочих 
.
Пусть - фактическое число рабочих в -й месяц. Затраты по изменению количества рабочих при переходе от 
-го к -му месяцу задаются функцией 
. В зависимости от знака разности 
функция определяет затраты по найму (если 
) или по увольнению. Очевидно, 
.
Отклонение численности от идеальной величины приводит к дополнительным производственным расходам, которые задаются функцией 
, причем 
. Предположим, что в начальный момент численность рабочих составляла 
. Целевая функция задачи - суммарные затраты на производство и набор рабочих определяется соотношением
,
где 
= . Нужно найти такую численность рабочих в каждый месяц , при котором суммарные затраты минимальны.
Решим эту задачу методом динамического программирования. Поскольку задано начальное состояние системы , то используем схему решения в обратном направлении. Обозначим
,
где 
.
Тогда основное рекуррентное соотношение будет иметь вид:
, (7.1.13)
где 
- минимальные суммарные затраты за месяцы от -го до -го включительно, если число рабочих в 
-и месяц равно .
Используя (7.1.13), последовательно вычисляем 
, 
, ., 
для всех возможных значений .
В конце концов, на последнем шаге при 
находим оптимальное число рабочих 
в первый месяц при начальном условии = .
Для этого находим
. (7.1.14)
Определив из (7.1.14) и положив 
= , из таблицы предыдущего шага находим 
, дальше 
и т.д.
В рассматриваемом случае решение в обратном направлении целесообразно, так как неизвестно число рабочих в конце работ, то есть на (
)-й месяц.
Рассмотрим случай, когда кроме задано также нужное количество рабочих после окончания работ 
. Будем искать целые числа, для которых достигает минимума выражение
. (7.1.15)
Здесь можно записать
Поскольку теперь задано конечное состояние системы, то будем решать задачу в прямом направлении.
Определим последовательность функций состояния
Тогда
Основное рекуррентное соотношение ДП для этого случая будет иметь вид:
(7.1.16)
Функция 
есть минимальные затраты за первые (
) месяцев при условии, что численность работников в (
)-й месяц равна .
Используя ОРС (7.1.16), последовательно вычисляем 
, 
для всех возможных значений .
Наконец, на последнем шаге при 
, положив 
, получим соотношение
. (7.1.17)
Определив из (7.1.17) оптимальное значение 
по таблице предыдущего (
)-го шага и, положив 
, найдем оптимальные значения всех остальных переменных 
, 
, ., . Подведем некоторые итоги рассмотренной выше задачи.
Пусть имеется задача последовательного принятия решений на периодов. Если задано начальное состояние системы, то задача решается методом динамического программирования в обратном направлении; если же задано конечное состояние системы, то - в прямом направлении. Наконец, если заданы как начальное, так и конечное состояния системы, то задачу можно решать как в прямом, так и в обратном направлениях. Результаты по обеим схемам совпадут.
Пример 7.2. Пусть задана задача об использовании трудовых ресурсов с такими данными: 
= 4 месяца; 
= 2, 
= 5, 
= 3, 
= 1, 
= 2.
Пусть функции 
и 
имеют следующий вид:
Поскольку зафиксировано начало (
= = 2), то будем решать задачу в обратном направлении. Для этого используем основное рекуррентное соотношение
Первый шаг.
Для отыскания 
составляем таблицу значений 
(табл. 7.3). Значение 
для всех 
выбираем из табл. 7.3 и записываем в основную таблицу - табл. 7.4. Поскольку все функции и выпуклы по 
, то и функция выпукла по 
для всех значений . Поэтому для нахождения достаточно найти первый минимум функции , который и будет глобальным. Соответственно этому выводу значения функции вычисляем лишь для области значений , содержащей этот минимум (табл. 7.3).
Вычисления выполняем следующим образом.
|
ξ = 0 , x4 = 0; Ω4 = 0 + 11(1 - 0) = 11; ξ = 0 , x4 = 1; Ω4 = 10(1 - 0) + 0 = 10; ξ = 0 , x4 = 2; Ω4 = 10(2 - 0) + 8(2 - 1) = 28. |
ξ = 1 , x4 = 0; Ω4 = 7(1 - 0) + 11(1 - 0) = 18; ξ = 1 , x4 = 1; Ω4 = 0 + 0 = 0; ξ = 1 , x4 = 2; Ω4 = 10(1 - 0) + 8(2 - 1) = 18. |
|
|
ξ = 2 , x4 = 0; Ω4 = 7(2 - 0) + 11(1 - 0) = 25; ξ = 2 , x4 = 1; Ω4 = 7(2 - 1) + 0 = 7; ξ = 2 , x4 = 2; Ω4 = 7.0 + 8(2 - 1) = 8. |
ξ = 3 , x4 = 0; Ω4 = 7(3 - 0) + 11(1 - 0) = 32; ξ = 3 , x4 = 1; Ω4 = 7(3 - 1) + 0 = 14; ξ = 3 , x4 = 2; Ω4 = 7(3 - 2) + 8(2 - 1) = 15. |
|
|
ξ = 4 , x4 = 0; Ω4 = 7(4 - 0) + 11(1 - 0) = 39; ξ = 4 , x4 = 1; Ω4 = 7(4 - 1) + 0 = 21; ξ = 4 , x4 = 2; Ω4 = 7(4 - 2) + 8(2 - 1) = 22. |
ξ = 5 , x4 = 0; Ω4 = 7(5 - 0) + 11(1 - 0) = 46; ξ = 5 , x4 = 1; Ω4 = 7(5 - 1) + 0 = 28; ξ = 5 , x4 = 2; Ω4 = 7(5 - 2) + 8(2 - 1) = 29. |
Нужно определить диапазон изменения параметра . Очевидно, 
, а 
. В рассматриваемом примере = 5.
|
Таблица 7.3 |
Таблица 7.4 |
|||||
|
|
|
|
|
|
|
|
|
0 |
11 |
0 |
10 |
1 |
||
|
0 |
1 |
10 |
1 |
0 |
1 |
|
|
2 |
28 |
2 |
7 |
1 |
||
|
0 |
18 |
3 |
14 |
1 |
||
|
1 |
1 |
0 |
4 |
21 |
1 |
|
|
2 |
18 |
5 |
28 |
1 |
||
|
0 |
25 |
|||||
|
2 |
1 |
7 |
||||
|
2 |
8 |
|||||
|
0 |
32 |
|||||
|
3 |
1 |
14 |
||||
|
2 |
15 |
|||||
|
0 |
39 |
|||||
|
4 |
1 |
21 |
||||
|
2 |
22 |
|||||
|
0 |
46 |
|||||
|
5 |
1 |
28 |
||||
|
2 |
29 |
|||||
Второй шаг. Используем ОРС при k = 3:
и выполним второй шаг аналогично первому. Вспомогательные результаты вычисления 
приведем в табл. 7.5, а итоговые - в табл. 7.6.
|
Таблица 7.5 |
Таблица 7.6 |
||||||
|
|
|
|
|
|
|
|
|
|
0 |
40 |
0 |
32 |
1 |
1 |
||
|
0 |
1 |
32 |
1 |
22 |
1 |
1 |
|
|
2 |
38 |
2 |
18 |
2 |
1 |
||
|
0 |
50 |
3 |
14 |
3 |
1 |
||
|
1 |
1 |
22 |
4 |
21 |
3 |
1 |
|
|
2 |
28 |
5 |
28 |
3 |
1 |
||
|
0 |
57 |
||||||
|
2 |
1 |
29 |
|||||
|
2 |
18 |
||||||
|
3 |
24 |
||||||
|
1 |
36 |
||||||
|
3 |
2 |
25 |
|||||
|
3 |
14 |
||||||
|
4 |
39 |
||||||
|
2 |
32 |
||||||
|
4 |
3 |
21 |
|||||
|
4 |
29 |
||||||
|
2 |
39 |
||||||
|
5 |
3 |
28 |
|||||
|
4 |
36 |
||||||
Третий шаг. Используем соотношения (1) и вычислим для всех
,
где 
. Результаты вычисления 
заносим в табл. 7.7, а значение 
и 
в основную таблицу 7.8.
|
Таблица 7.7 |
Таблица 7.8 |
|||||||
|
|
|
|
|
|
|
|
|
|
|
1 |
76 |
0 |
66 |
3 |
3 |
1 |
||
|
0 |
2 |
71 |
1 |
56 |
3 |
3 |
1 |
|
|
3 |
66 |
2 |
46 |
3 |
3 |
1 |
||
|
4 |
72 |
3 |
36 |
3 |
3 |
1 |
||
|
2 |
61 |
4 |
32 |
4 |
3 |
1 |
||
|
1 |
3 |
56 |
5 |
28 |
5 |
3 |
1 |
|
|
4 |
62 |
|||||||
|
Продолжение таблицы 7.7 |
||||||||
|
2 |
51 |
|||||||
|
2 |
3 |
46 |
||||||
|
4 |
52 |
|||||||
|
2 |
58 |
|||||||
|
3 |
3 |
36 |
||||||
|
4 |
42 |
|||||||
|
2 |
65 |
|||||||
|
4 |
3 |
43 |
||||||
|
4 |
32 |
Таблица 7.9 |
||||||
|
5 |
38 |
|
|
|
||||
|
4 |
39 |
1 |
74 |
|||||
|
5 |
5 |
28 |
2 |
2 |
46 |
|||
|
6 |
46 |
3 |
54 |
|||||
Четвертый шаг. Используя начальное условие 
и подставляя его в соотношение 
, находим 
и оптимальное значение переменной 
. Они приведены в табл. 7.9. Дальше из табл. 7.8 по значению 
вычисляем оптимальные значения всех остальных переменных: 
. При этом суммарные затраты составляют 
= 46 условн.ед., что является минимумом.
Применение динамического программирования при непрерывных переменных
В отличие от других вычислительных методов динамическое программирование наиболее подходит для задач, где переменные - дискретны. Вместе с тем его можно применить и для задач с непрерывными переменными. Для этого непрерывные переменные квантуют, выбирая шаг дискретизации из конкретного содержания задачи.
Рассмотрим, как решается задача о распределении ресурсов (7.1.1), (7.1.2) при непрерывных переменных. Определим последовательность функций состояния
при условии
.
Основное рекуррентное соотношение имеет вид:
(7.1.19)
Главное отличие по сравнению со случаем дискретных переменных , 
возникает в процессе вычисления максимума по и в способе построения таблицы значений 
.
Рассмотрим задачу определения при фиксированном . Обозначим
. (7.1.20)
Тогда
.
Если 
известна, то значения функции 
определены для всех . Предположим, что график такой, как на рис. 7.6. Для определения 
нужно отыскать все относительные максимумы и выбрать среди них абсолютный.
|
табулируют. При табулировании целесообразно применять сначала сетку с большим шагом, а в окрестности 'подозрительных' на существование максимума точек перейти на сетку с маленьким шагом.
Функции нужно табулировать при всех допустимых значениях , поскольку заранее неизвестно, какое из них может понадобиться при вычислении 
.
Заметим, что задача вычисления значительно упрощается при условии, что все 
выпуклы или вогнуты. Можно показать, что из выпуклости (или вогнутости) всех функций 
следует выпуклость (вогнутость) функции . Рассмотрим такие случаи.
Случай 1. Все функции 
выпуклы. Поскольку выпуклая
функция, то и 
выпуклая относительно переменной . Нас интересует 
при фиксированном . Как известно, максимум выпуклой функции на замкнутом ограниченном множестве достигается в одной из крайних точек. В данном случае такими точками являются: 1) = 0; 2) = 
.
Итак, в случае выпуклости всех 
, 
для нахождения 
достаточно проверить лишь крайние точки = 0 и = .
Случай 2. Все функции -- вогнуты. Тогда есть вогнутая функция от при каждом фиксированном значении , и потому всякий ее относительный максимум будет одновременно и глобальным. Отыскать относительный максимум можно одним из известных поисковых методов оптимизации, например, градиентным.
