Методы, связанные с градиентом

1шаг. Определяем, принадлежит ли точка абсолютного многоугольника ограничений. Если да, то задача решена; если нет то будет на границе многоугольника ограничений.

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

Применяя метод Лагранжа, можно найти на этом ребре точку (но это не всегда так). Поэтому можно поступить иначе. Найдя точку , из нее организуем движение по этому ребру, приближаясь к , опять допустим градиентным методом или используя идеи метода Лагранжа.

По Лагранжу .

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

.

И в нужном направлении двигаемся до тех пор, пока два градиента будут лежать на одной линии. Это 1-ая модификация обхода с помощью соотношения градиентов. Есть и другая модификация:

2) Спроектируем на грань градиент. В точке .

Если мы ищем «», то указывает нужное направление, если ищем «», то указывает другое направление. В нужном направлении двигаемся до тех пор, пока не станет равен 0.

Линия уровня  

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

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

Пример. (рис. **)

1 шаг. Находим точку абсолютного

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

2 шаг Выбираем начальную точку и организуем движение к .

Из этой точки любым известным методом организуем движение к точке абсолютного .

Воспользуемся, например, метод наискорейшего спуска.

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

!

Следовательно, линия градиента пересекает 1ребро, а 2-ое не пересекает. Т.е. проходит через 1ребро, а не через пересечение 1-го и 2-го ребра.

3 шаг. Найдем точку пересечения направления градиента с ребром. Составим уравнение прямой, проходящей через две точки и .

в числах имеем:

.

У нас есть уравнение , т.к. ребро поэтому строгое равенство.

Решение:

Отсюда координаты точки пересечения

тока

Является ли эта точка решением задачи? Т.е. касается ли сечение уровня в этой точке ребра ?

4 шаг. Это выявим на 4 шаге. Если нет, то необходимо организовать движение по ребру.

Проверим это

должно быть, если это решение задачи.

Тогда т.е. точка не является решением задачи. Куда двигаться –вверх или вниз от точки пересечения? Сделаем пробные шаги в обоих направлениях.

Неравенство усилилось, следовательно это направление движения по ребру неправильное.

Тогда возьмем

Видно, что шаг слишком большой т.к. было , а стало

Возьмем шага

Ещё итерация

т.е. точка (3.4;2.6) является решением задачи.

Таким образом для приведенной задачи большая трудоемкость.

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

Методом наискорейшего спуска делаем 1-ый шаг и получаем точку ;

Двигаемся по ребру, но по ребру то , а мы уже знаем, что решение на ребре 1. Поэтому мы должны перейти вершину. Это большая неприятность, ибо в многомерном случае – по какой грани двигаться дальше? (В плоскости ясно – там в вершине 2 ребра, значит надо двигаться по другому). В принципе в вершине можно определить углы между вектором градиента и всеми гранями и двигаться туда (по той грани) где угол наименьший (т.е. проекция градиента и антиградиента – наибольший). Это весьма трудоемкое дело. Значит надо избегать обхода вершин. Это можно сделать, если использовать метод наискорейшего спуска с постоянным шагом по одной координате. Тогда мы пресечем ту грань, которую надо, т.е. на которой лежит .

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

Итак:

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

Движение по ограничению можно ограничивать не по Лагранжу, как мы сейчас делали, а по проекциям градиента.

В любой точке записывается уравнение касательной к и нормальной к и проектируется эта нормальна на касательной.

Уравнение нормали в многомерном случае в точке

Уравнение касательной к в точке .

В точке нормаль к касательной, т.е. скалярной произведение нормали и касательной должно быть =0.

Пример.

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

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

Запишем уравнение нормали:

Это 2 плоскости, пересечение которых и дает линию градиента.

1-ая плоскость

или после преобразований

; где

Уравнение второй плоскости

Пересечение этих двух плоскостей и дает нормаль к . Запишем уравнение касательной. В нашем случае уравнение касательной и есть наше ограничение т.е. =0. Для неё

Запишем условие экстремальности, т.е. =0 скалярного произведения.

Отсюда 1-ое условие для начальной точки т.е. для произвольно выбранной точки (если он имеет место).

Второе условие:

имеем (2)

Зададим начальную точку

Из получаем при заданном координату .

Подставим их в 1-ое и 2-ое условие и увидим, что она не является точкой. Как же нам двигаться по плоскости чтобы попасть в ? Возьмем

Неравенство (2) только усилилось, следовательно, шагнули не в ту сторону. Попробуем взять точку ниже:

. Неравенство стало ближе к равенству, следовательно, в этом направлении и необходимо двигаться дальше.

перескочили точки. Так, постепенно мы подойдем к точке.

Литература

1. Д. Химмельблау. Прикладное программирование. М.:, Мир, 1975.

2. Лященко И.Н. и др. Линейное и нелинейное программирование. В.шк., Киев, 1975.

3. Монахов В.М. и др. Методы оптимизации М.: Просвещение, 1978.

Глава II

Дата добавления: 2014-01-11