Научная электронная библиотека

Монографии, изданные в издательстве Российской Академии Естествознания

Прикладные методы оптимизации

Шукаев Д. Н.,

В.1. Основные понятия и положения методов оптимизации

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

Введем следующие основные понятия методов оптимизации:

– конечномерная задача оптимизации – эта задача, для которой выполняется условие X ⊆ Eⁿ, где Х – допустимое множество решений оптимизационной задачи, а Eⁿ – n-мерное евклидово пространство;

– множество Х называется компактом, если оно замкнутое ограниченное множество;

– множество Х является выпуклым, если любая его точка, лежащая между двумя допустимыми точками также допустимая;

– допустимое значение переменной оптимизационной задачи удовлетворяет условию х ∈ Х;

– целевая функция f(x), определенная на выпуклом множестве Х является выпуклой на Х, если

f(λx1 + (1 – λ)x2) ≤ λf(x1) + (1 – λ)f(x2)

при всех x1, x2 ∈ X, λ ∈ [0, 1]. Функция f(x) называется вогнутой, если {–f(x)} выпукла;

Наиболее общая постановка задачи оптимизации имеет следующий вид

f(x) > extremum, x λ X. (В.1)

Для конкретности предположим, что extremum это maximum

f(x) > maximum, x λ X. (В.2)

Решение x* λ X называется:

– глобальным максимумом целевой функции f(x) на множестве Х, если

f(x*) ≥ f(x) для ∀x ∈ X; (В.3)

– локальным максимумом целевой функции f(x) на множестве Х, если

f(x*) ≥ f(x) для «(x ± ε) ∈ X. (В.4)

Глобальный максимумом является локальным, но не наоборот.

Очевидно, при выполнении последних двух условий как строгие неравенства получаем строгие решения, если они вообще существуют.

Действительно, при рассмотрении задач оптимизации в первую очередь возникает вопрос о существования решения. На него дает ответ один из основополагающих теорем классического математического анализа, а именно, теорема Вейерштрасса [15, 37]. Назовем его первой основной теоремой теории оптимизации.

Основная теорема B1. «Пусть допустимое множество Х является компактом и непустым. Тогда непрерывная целевая функция f(x), определенная на этом множестве, достигает глобального максимума на внутренней или граничной точке множества Х».

Суть теоремы проиллюстрируем на следующих рисунках (рис. В.1)

Рис. В.1. Максимум достигается внутри (верхний график) и на границе (нижний график) допустимого множества Х

Покажем примеры нарушения условий теоремы Вейерштрасса [15]:

1) f(x) = x², при x ≥ 0 – здесь нарушено условие ограниченности множества Х и, следовательно, целевая функция не имеет максимума;

2) f(x) = 10x, при 0 ≤ x < 1 – здесь нарушено условие замкнутости множества Х и, следовательно, также целевая функция не имеет конкретного значения максимума;

3) f(x) = 10x³, при 0 < x ≤ 1 – здесь максимум достигается в точке x = 1 хотя допустимое множество Х не компакт. Следовательно, условия теоремы Вейерштрасса достаточны, но не необходимы.

Второй основной теоремой теории оптимизации является теорема 2: «Пусть допустимое множество Х является компактом и выпуклым, а целевая функция вогнута на Х тогда локальный максимум является глобальным».

Геометрическая интерпретация теоремы 2 показана на рис. В.2 [15]. Линия (поверхность) уровня целевой функции это множество точек для которых f(x) = const, т.е.

{x ∈ Eⁿ/f(x) = const}.

Рис. В.2. Граничное решение

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

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