Задачи оптимизации в евклидовом пространстве

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

УРАЛЬСКИЙ ГОСУДАРСТВЕННЫЙ ГОРНЫЙ УНИВЕРСИТЕТ

КАФЕДРА МАТЕМАТИКИ

ЗАДАЧИ ОПТИМИЗАЦИИ В ЕКВКЛИДОВОМ ПРОСТРАНСТВЕ

Курсовой проект по курсу «Численные методы»

Преподаватель: проф. Исрапилов Р.Б.

студент: Коуров Д.Е.

Группа: ПМ-02

Екатеринбург

2005

Оглавление:

Введение 2

1. Общая схема методов спуска 3

2. Метод покоординатного спуска 4

3. Градиентные методы 7

3.1 Обзор градиентных методов 7

3.2 Ограничения, накладываемые на функцию 9

3.3 "Овражный" характер функции 10

Список литературы 15

Введение

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

Эта задача записывается следующим образом

(1)

Задача (1) называется задачей без ограничений или задачей безусловной оптимизации, если и задачей с ограничениями или задачей условной оптимизации, если .

Решить задачу (1) означает найти точку (а также соответствующее значение ) такую, что ( ) или установить неразрешимость этой задачи. Решение называют оптимальным, а значение - оптимумом функции на множестве .

Задачи , и , называют соответственно задачей минимизации и максимизации функции на множестве .

Отметим, что задачу максимизации функции можно свести к задаче минимизации, заметив, что на .

Рассмотрим задачу безусловной минимизации

. (2)

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

(3)

удовлетворяющих условию

(4)

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

1. Общая схема методов спуска

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

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

,

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

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

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

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

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

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

Методы спуска в силу условия монотонности (4) обычно не приводят к точке локального (глобального) максимума.

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

2. Метод покоординатного спуска

Согласно этому методу, направление спуска выбирают параллельным координатным осям. Сначала осуществляют спуск вдоль первой оси , затем – вдоль второй - и т.д. до последней оси .

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

(5)

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

, .

Если (5) не имеет места, то делают шаг в противоположном направлении, т.е. проверяют неравенство

. (6)

В случае выполнения этого неравенства полагают

, .

Возможно, что оба неравенства (5) и (6) окажутся невыполненными. Тогда следует считать , .

Второй шаг производят вдоль координатной оси : если

,

то полагают

, .

Если же последнее неравенство не имеет места, то проверяют неравенство

И в случае его выполнения считают

, .

Если ни одно из двух неравенств не выполняется, то полагают

, .

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

Последующие итерации производят аналогично. На практике вычисления продолжают до тех пор, пока не выполнится некоторое условие окончания счета. Часто используют следующие условия:

или , (7)

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

На рис. 1 изображены несколько линий уровня некоторой функции двух переменных и проиллюстрирован описанный метод.

Рис. 1

Сходимость метода покоординатного спуска устанавливает следующее утверждение.

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

Заметим, что сходимость гарантируется, если начальная точка выбрана надлежащим образом.

Рассматриваемый метод относится к классу методов нулевого порядка и для его реализации не требуется вычислять