Сдам Сам

ПОЛЕЗНОЕ


КАТЕГОРИИ







Сведение задачи с ограничениями к безусловной методом штрафных функций





Задачу минимизации целевой функции f (x) в допустимой области

min f (x), j(x)£ 0

можно привести к эквивалентной задаче безусловной минимизации

min L (x),

где L (x) = f (x) + l {j(x)} – комплексная целевая функция, учитывающая как целевую функцию исходной задачи, так и ограничение, l – коэффициент штрафа за нарушение ограничений. Выражение в фигурных скобках (функция штрафа) равно нулю, если ограничение не нарушено, в противном случае равно степени нарушения ограничения (рис. 2 а):

{j(x)} =

Свободный минимум комплексной целевой функции L (x) при надлежащем выборе коэффициента штрафа совпадает с условным минимумом истинной целевой функции f (x).

Рис. 2. Сведение задачи минимизации с ограничением к безусловной методом штрафных (а) и барьерных (б) функций

 

Комплексную целевую функцию можно представить в виде

L (X) = ± W (X) + ,

с выбором знака в зависимости от того, нужно найти минимум (+) или максимум (–) целевой функции W (X). Задача поиска условного экстремума целевой функции W (X) эквивалентна минимизации функции L (X), если удачно выбраны коэффициенты штрафа. Объективных способов выбора коэффициентов штрафа не существует. Ясно, что надежность приближения точки, минимизирующей L (X), к истинному решению тем надежнее, чем больше коэффициенты штрафа (в пределе – до бесконечности), но надежность приближения к оптимуму при этом снижается. Поэтому обычно решают последовательность задач с возрастающими коэффициентами штрафа или используют накопленный опыт оптимизации аналогичных задач.

 

Метод барьерных функций

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

L (x) = f (x) + ,

где С – достаточно малая величина. В пределах допустимой области вдали от ее границ функция L (x)практически совпадает с f (x), но с приближением к границам знаменатель стремится к нулю, а функция L (x) – к бесконечности. Таким образом, минимизация L (x)приводит почти к тому же результату, что и условная минимизация f (x)(рис. 2 б). Степень близости приближенного решения к истинному зависит от значения коэффициента С (обычно решается последовательность задач с уменьшающимся С). В комплексной целевой функции некоторые штрафные слагаемые, которые соответствуют «непреодолимым» ограничениям, можно заменить выражениями

.


Классификация методов оптимизации по математическим свойствам функционалов

Принципиальным образом методы решения задач вида:

 

min W (X)

Fk (X) ³ Fk тр, k = 1, …, m,

ai £ x i £ bi, i= 1, …, n,

 

зависят от характера целевой функции W (X) и функций-ограничений Fk (X).

 

Линейное программирование

Простейший частный случай задачи математического программирования – линейное программирование (ЛП) – состоит в минимизации или максимизации линейной функции на допустимом множестве, заданном линейными ограничениями:

, k = 1, …, m.

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

а б в

Рис. 3. Иллюстрация двумерной (а) и трехмерной (б) задач ЛП и задачи КП (в)

 

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

 

Квадратичное программирование

Целевая функция, заданная квадратичной формой с симметричной, положительно определенной матрицей g

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

 

Выпуклое программирование

Из всех задач оптимизации с нелинейными функционалами самые благоприятные для решения задачи выпуклого программирования, в которых целевая функция и функции-ограничения обладают свойствами выпуклости. Как известно, график выпуклой функции лежит выше касательной в любой его точке. Ограничения сверху на выпуклые функции образуют выпуклую допустимую область, содержащую вместе с любой парой точек и отрезок между ними. Это очень важное свойство с точки зрения поиска экстремума, но еще важнее то, что экстремальная точка единственна и является искомым решением задачи. Большинство методов нелинейного программирования (НЛП) предполагают наличие единственного локального экстремума, но только в выпуклой области может существовать не более одной точки, в которой выполняется критерий оптимальности выпуклой целевой функции.

 

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

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

 

Рис. 4. Многоэкстремальная целевая функция








ЧТО ТАКОЕ УВЕРЕННОЕ ПОВЕДЕНИЕ В МЕЖЛИЧНОСТНЫХ ОТНОШЕНИЯХ? Исторически существует три основных модели различий, существующих между...

Что вызывает тренды на фондовых и товарных рынках Объяснение теории грузового поезда Первые 17 лет моих рыночных исследований сводились к попыткам вычис­лить, когда этот...

Что способствует осуществлению желаний? Стопроцентная, непоколебимая уверенность в своем...

Система охраняемых территорий в США Изучение особо охраняемых природных территорий(ООПТ) США представляет особый интерес по многим причинам...





Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:


©2015- 2024 zdamsam.ru Размещенные материалы защищены законодательством РФ.