Векторная оптимизация

Задача многокритериальной оптимизации

Задача нелинейного программирования

В задачах линейного программирования глобальный экстремум целевой функции достигается в вершине симплекса и симплекс-метод за конечное число шагов определяет эту вершину.

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

Задачи нелинейной оптимизации с точки зрения методов решения делятся на два класса [42]: 1) задачи безусловной оптимизации; 2) задачи условной оптимизации.

Задача безусловной оптимизации представляет собой поиск оптимума целевой функции без всяких дополнительных условий, что записывается

.

Задача условной оптимизации в общем случае записывается в известном виде:

Такая задача оптимизации, кроме целевой функции, включает дополнительные условия в виде ограничений и граничных условий.

Задачи безусловной нелинейной оптимизации могут решаться различными методами поиска. Чтобы составить маршрут поиска, нужно, во-первых, знать начальную точку, во-вторых, выбрать путь движения и, наконец, определить, достижение какой точки следует считать достижением цели.

Путь движения можно представить как последовательность шагов, а каждый шаг при этом определяется направлением движения и расстоянием, которое следует пройти в данном направлении.

Идея поиска экстремума заключается в следующем:

1. Задать начальную точку .

2. В заданной точке определить направление движения на первом шаге .

3. Принять величину шага .

4. Определить координаты конца первого шага .

5. Вычислить значения признака экстремума на первом шаге.

6. Проверить выполнение признака экстремума.

Если условие признака выполняется, то принимается, что экстремум находится в точке , если нет - аналогично выполняется второй шаг и так далее до выполнения условия, характеризующего достижение экстремума.

Важный вопрос поиска - признак достижения экстремума, то есть вершины, обычно таким признаком является величина относительного приращения функции на каждой итерации:

.

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

Методы выбора направления и длины шага бывают различных типов, но их порядок определяется порядком производных целевых функций, используемых в них.

Методами нулевого порядка поиска называются такие методы, которые для определения направления и величины шага используют только значение целевой функции.

Методы первого порядка или градиентные методы - это такие методы, в которых для определения направления и шага используются значения первых производных целевой функции, и определяется ее градиент.

Методами второго порядка или методами Ньютона называются такие методы, в которых для определения направления и шага используются значения вторых производных целевой функции.

Чем выше порядок методов, тем больше вычислений на каждой итерации, но тем меньше требуется итераций и, естественно, наоборот. Наиболее распространенными являются градиентные методы. Такое положение объясняется тем, что с одной стороны, они не требуют на каждой итерации очень больших вычислений, так как вычисляется только целевая функция и ее первые производные, а с другой - у этих методов достаточно хорошая сходимость, то есть они обеспечивают нахождение экстремума за небольшое число итераций.

Задачи условной оптимизации решаются с использованием следующих подходов:

1. Если число переменных , то возможно графическое решение задачи.

2. Классический метод условной оптимизации с помощью определения стационарных, граничных точек и точек разрыва.

3. Метод множителей Лагранжа, если ограничения имеют вид равенств. При этом идея метода заключается в преобразовании задачи условной оптимизации в задачу безусловной оптимизации.

4. Метод штрафных функций, если ограничения имеют вид неравенств и равенств.

5. Метод определения седловой точки, если ограничения имеют вид неравенств.

Подробно указанные методы излагаются в литературе [42], [43]

1.2.4. Задача стохастического программирования

Математическая модель задачи оптимизации включает в себя три элемента: 1) целевую функцию; 2) ограничения; 3) граничные условия. При этом допустим ряд вариантов задач стохастического программирования.

Если коэффициенты в целевой функции - случайные величины, то возможно две постановки задачи оптимизации:

1. Максимизация (минимизация) среднего значения целевой функции, которая называется М-постановкой: .

2 Максимизация вероятности получения максимального (минимального) значения, которая называется Р-постановкой: .

Если случайными являются величины и , входящие в ограничения, то i-e ограничение записывается так: , где- заданная вероятность, с которой должно выполняться i-е ограничение

Запись граничных условий может быть выполнена в двух вариантах. Если в ограничении - детерминированные величины, то ограничение остается в виде . Если - случайные величины, то рассматриваются два ограничения, .

В практических задачах граничные условия случайными величинами являются крайне редко. Объединяя целевую функцию, ограничения и граничные условия, можно сформулировать две постановки задачи стохастического программирования:

М-постановка

Р- постановка

Обе постановки представляют собой задачи нелинейного программирования.

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

Постановку задачи можно представить следующим образом:

Различные методы решения подобных задач представлены в литературе [40], [42], [45], в разд. 1.4 подробно описывается метод свертывания векторного критерия .

1.3. Причины многокритериальности в задачах

оптимального проектирования

Наиболее общей математической моделью принятия оптимального решения является задача многокритериальной оптимизации. Приведем несколько причин, приводящих к многокритериальным задачам [40].

1. Одной из причин, приводящей к многокритериальности, является множественность технических требований, которые предъявляются к характеристикам проектируемого устройства. Их можно свести к системе неравенств.

, (1.1)

где предельное значение го технического требования.

В этом случае частные критерии оптимальности обычно в явном виде отсутствуют и их приходится вводить искусственно с помощью выражений:

Здесь - весовой коэффициент, учитывающий важность i-го ограничения ().

Таким образом, решение системы неравенств (1.1) сводится к решению задачи векторной оптимизации:

. (1.2)

2. Следующей причиной многокритериальности является необходимость обеспечения оптимальности проектируемого устройства при различных условиях его функционирования, то есть обеспечение экстремальных значений критерия оптимальности при неопределенности условий, в которых приходится работать устройству. При этом неопределенность может иметь либо количественный характер, выраженный с помощью параметра v, что приводит к задаче оптимизации.

для всех , (1.3)

либо качественный характер, связанный с указанием конкретных условий функционирования. В последнем случае эффективность и качество работы устройства для каждого режима могут быть охарактеризованы различными критериями оптимальности. Например, в зависимости от исходного состояния для логического элемента представляет опасность либо помеха Q₁(), вызывающая запирание схемы, либо помеха Q₂ (), приводящая к отпиранию схемы. Тогда, если под помехоустойчивостью логической схемы понимать минимальный порог срабатывания максимально чувствительной схемы, задача оптимального проектирования логического элемента может быть сформулирована как задача векторной оптимизации:

, ,

где допустимая область работоспособности логического элемента.

Если неопределенность функционирования имеет количественный характер, то задача оптимизации (1.3) сводится к задаче векторной оптимизации (1.2) путем дискретизации критерия оптимальности Q(,v) по параметру v и рассмотрению в качестве частных критериев оптимальности функций.

.

Такой подход к задаче оптимального проектирования позволяет учитывать влияние внешних факторов (температуры, ускорения, радиации и т. д.) на критерий оптимальности и ограничения проектируемого устройства.

3. При постановке задачи оптимального проектирования одним из основных вопросов является выбор критерия оптимальности Q (). С одной стороны, критерий должен иметь конкретный физический смысл, а с другой - от него требуется, чтобы он как можно полнее характеризовал проектируемое устройство. Однако требования функциональной полноты трудно удовлетворить с помощью только одного скалярного показателя, так как он обычно описывает конкретное свойство устройства. В связи с этим приходится рассматривать совокупность показателей (), каждый из которых имеет наглядную физическую интерпретацию и позволяет оценить качество оптимального решения с различных точек зрения.

Таким образом, необходимость обеспечения функциональной полноты показателей, конкретизирующих оптимальные свойства проектируемого устройства, при одновременной их физической наглядности приводит к многокритериальности, которая вытекает прямо из постановки задачи оптимального проектирования. Например, при проектировании транзисторного логического элемента бортовой ЭВМ автотракторного средства необходимо рассматривать одновременно несколько частных критериев оптимальности, отражающих различные свойства схемы, что приводит к следующей задаче векторной оптимизации:

,

где - допустимая область работоспособности схемы, - нагрузочная способность; , - статическая помехоустойчивость в закрытом состоянии к отпирающей по напряжению помехе и к запирающей по току, действующей в открытой схеме, соответственно, - рассеиваемая мощность, - среднее время задержки сигнала. Оптимальный вариант логической схемы должен иметь экстремальные значения по каждому из частных критериев ().

4. В тех случаях. когда проектируемое устройство состоит из нескольких взаимосвязанных узлов и блоков, оптимальность всего устройства определяется эффективностью и качеством его отдельных частей, каждая из которых может быть охарактеризована, по крайней мере, хотя бы одним частным критерием оптимальности .

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

5. Другой ситуацией, приводящей к многокритериальности, является случай, когда функционально-логическая модель проектируемого устройства отсутствует и требуется ее построить таким образом, чтобы внешние параметры устройства наилучшим образом соответствовали экспериментальным данным.

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