Метод наискорейшего спуска

1. В чем основные отличия метода наискорейшего спуска от метода градиента?

2. По какому направлению осуществляется поиск из каждой текущей точки при

поиске minf(x)?

3. Как вычисляется градиент f(x) в методе наискорейшего спуска?

4. Каковы условия окончания поиска?

5. Можно ли методом наискорейшего спуска найти maxf(x)?

Глава 7. КРИТЕРИИ ОПТИМАЛЬНОСТИ В ЗАДАЧАХ

С ОГРАНИЧЕНИЯМИ

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

Задачи с ограничениями в виде равенств

Рассмотрим общую задачу оптимизации, содержащую несколько ограничений в виде равенств:

минимизировать f(x₁, x₂, …, x_N)

при ограничениях h_k(x₁, x₂, …,x_N) = 0, k = 1, … K.

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

Множители Лагранжа

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

Для начала рассмотрим случай для функции двух переменных.

Определение. Условным экстремумом функции z=f(x, y) называется экстремум этой функции, достигнутый при условии, что переменные x и y связаны уравнением j(x, y)=0 (уравнение связи).

Отыскание условного экстремума можно свести к исследованию на обычный экстремум так называемой функции Лагранжа u=f(x, y)+lj(x, y), где l - неопределенный постоянный множитель.

Необходимые условия экстремума функции Лагранжа имеют вид

Из этой системы из трех уравнений можно найти неизвестные x, y, l.

Для того, чтобы найти наибольшее и наименьшее значения функции в замкнутой области, надо:

1) найти стационарные точки, расположенные в данной области, и вычислить значения функции в этих точках;

2) найти наибольшее и наименьшее значения функции на линиях, образующих границу области;

3) из всех найденных значений выбрать наибольшее и наименьшее.

Рассмотрим задачу минимизации функции N переменных с учетом одного ограничения в виде равенства:

минимизировать f(x₁, x₂, …, x_N)

при ограничениях h₁(x₁, x₂, …,x_N) = 0

В соответствии с методом множителей Лагранжа эта задача преобразуется в следующую задачу безусловной оптимизации:

минимизировать L(x; v) = f(x) – vh₁(x).

Функция L(x; v) называется функцией Лагранжа, v – неизвестная постоянная, которая носит название множителя Лагранжа. На знак v никаких требований не накладывается.

Пусть при заданном значении v = v⁰ безусловный минимум функции L(x; v) по x достигается в точке x = x⁰ и x⁰ удовлетворяет уравнению h₁(x⁰) = 0. Тогда x⁰ минимизирует f(x₁, x₂, …, x_N) с учетом h₁(x₁, x₂, …,x_N) = 0, поскольку для всех значений x, удовлетворяющих h₁(x₁, x₂, …,x_N) = 0, h₁(x) = 0 и min L(x; v) = min f(x).

Необходимо подобрать значение v = v⁰ таким образом, чтобы координата точки безусловного минимума x⁰ удовлетворяла равенству h₁(x₁, x₂, …,x_N) = 0. Это можно сделать, если, рассматривая v как переменную, найти безусловный минимум функции L(x; v) = f(x) – vh₁(x) в виде функции v, а затем выбрать значение v, при котором выполняется равенство h₁(x₁, x₂, …,x_N) = 0.

Пример 66. Минимизировать

при ограничении

Решение. Соответствующая задача безусловной оптимизации записывается в следующем виде:

минимизировать

Приравняв две компоненты градиента L к нулю, получим

Для того чтобы проверить, соответствует ли стационарная точка x⁰ минимуму, вычислим элементы матрицы Гессе функции L(x; v), рассматриваемой как функция х,

которая оказывается положительно определенной. Это означает, что L(x; v) – выпуклая функция х. Следовательно, координаты определяют точку глобального минимума. Оптимальное значение v находится путем подстановки значений в уравнение 2х₁ + х₂ = 2, откуда 2v +v/2 = 2 или v⁰ = 4/5. Таким образом, условный минимум достигается при

При решении задачи из Примера 66 мы рассматривали L(x; v) как функцию двух переменных х₁ и х₂ и, кроме того, предполагали, что значение параметра v выбрано так, чтобы выполнялось ограничение. Если же решение системы

в виде явных функций v получить нельзя, то значения x и v находятся путем решения следующей системы, состоящей из N + 1 уравнений с N + 1 неизвестными:

Для нахождения всех возможных решений данной системы можно использовать численные методы поиска. Для каждого из решений (x₀; v₀) следует вычислить элементы матрицы Гессе функции L, рассматриваемой как функция х, и выяснить, является ли эта матрица положительно определенной (локальный минимум) или отрицательно определенной (локальный максимум).

Пример 67. Минимизировать

при ограничении

Решение.

Эта система трех уравнений с тремя неизвестными имеет два решения:

Матрица Гессе функции L(x; v), рассматриваемой как функция х, равна

Вычислив элементы матрицы H для каждого из двух решений, находим, что матрица

положительна определена,

а матрица отрицательно определена.

Следовательно, (x⁽²⁾; v₂) соответствует максимуму функции L, рассматриваемой как функция х; оптимальное решение

Заметим, что (x⁽¹⁾; v₁) соответствует минимуму L.

Здесь необходимо подчеркнуть, что если мы рассмотрим L как функцию трех переменных, а именно переменных х₁, х₂ и v, то точки (x⁽¹⁾; v₁) и (x⁽²⁾; v₂) не окажутся точками минимума или максимума L как функции x и v. На самом деле они являются седловыми точками функции L(x; v).

Метод множителей Лагранжа можно распространить на случай, когда задача имеет несколько ограничений в виде равенств. Рассмотрим общую задачу, в которой требуется

минимизировать f(x)

при ограничениях h_k(x) = 0, k = 1, 2, …, K.

Функция Лагранжа принимает следующий вид:

Здесь v₁, v₂, …, v_k – множители Лагранжа, т.е. неизвестные параметры, значения которых необходимо определить. Приравнивая частные производные L по х к нулю, получаем следующую систему N уравнений с N неизвестными:

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

Решение расширенной системы, состоящей из N + K уравнений с N + K неизвестными, определяет стационарную точку функции L. Затем реализуется процедура проверки на минимум или максимум, которая проводится на основе вычисления элементов матрицы Гессе функции L, рассматриваемой как функция х, подобно тому, как это было проделано в случае задачи с одним ограничением.

Для некоторых задач расширенная система N + K уравнений с N + K неизвестными может не иметь решений, и метод множителей Лагранжа оказывается неприменимым. Следует, однако, отметить, что на практике такие задачи встречаются достаточно редко.

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