1. Нахождение стационарной точки

Целевая функция:

Для того, чтобы в точке функцияf(x) имела безусловный локальный экстремум необходимо, чтобы все её частные производные обращались в точке в нуль.

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

по и:

Приравняв полученные выражения к нулю, получим систему уравнений:

Решение системы уравнений даёт результат:

Таким образом, экстремум целевой функции является точка с координатами х^*=^Т, значение целевой функции, в которой: .

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

Так как гессиан функция - положительно определенная матрица (выполняются условия Сильвестра: все диагональные элементы матрицы Гесса - положительные величины, все ведущие главные определители положительные величины), стационарная точка является точкой минимума.

Рис 1. Линии уровня функции и стационарная точка

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

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

обоснование процедур решения задач с ограничениями.

2.1.Метод поиска по симплексу

Описание алгоритма:

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

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

Процедура продолжается до тех пор, пока не будет накрыта точка минимума.

Некоторые правила:

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

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

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

При заданной начальной точке и масштабном множителе, координаты остальныхвершин симплекса в- мерном пространстве вычисляются по формуле:

Приращения иопределяется по формулам:

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

Вычисление центра тяжести:

Если - точка, подлежащая отражению, то координаты центра тяжести определяются по формуле:

Координаты новой вершины удовлетворяют уравнению:

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

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

Алгоритм метода:

Шаг 1. Задать: 1. Начальную точку х⁽⁰⁾;

2. Масштабный множитель α;

3. Приращения δ₁ и δ₂;

4.Условие окончания поиска. Перейти к шагу 2.

Шаг 2. Вычислить координаты вершин х⁽¹⁾ и х⁽²⁾ симплекса. Перейти к

шагу 3.

Шаг 3. Определить значения целевой функции в вершинах симплекса. Перейти к шагу 4.

Шаг 4. Вершина, которой соответствует наибольшее значение целевой функции, построена на предыдущей итерации?

Да: отображается вершина, которой соответствует следующее по величине значение целевой функции

Нет: отображается точка с наибольшим значением целевой функции относительно двух других вершин симплекса. Перейти к шагу 5.

Шаг 5. Проверка на условие окончания.

Да: закончить поиск; результат- точка с наименьшим значением целевой функции;

Нет: перейти к шагу 3.

Ход решения :

Исходные данные:

- целевая функция;

_{Шаг 1.} - начальная точка;

- масштабный множитель;

Минимизируем целевую функцию до первого уменьшения размера симплекса:

Пусть масштабный множитель -

;

;

Шаг 2-3.

1-я итерация:

- максимально, следовательно, заменяем

Шаг 3-5.

2-я итерация:

- максимально, следовательно, заменяем

3-я итерация:

- максимально, следовательно, заменяем

4-я итерация:

_{-максимально, следовательно, заменяем}

5-я итерация:

_{- максимально, следовательно, заменяем}

6-я итерация:

_{- максимально, следовательно, заменяем}

7-я итерация:

- максимально, следовательно, заменяем

8-я итерация:

- максимально, следовательно, заменяем

9-я итерация:

-максимально, следовательно, заменяем

10-я итерация:

-максимально, следовательно, заменяем

11-я итерация:

- максимально, но построено на предыдущем шаге, следовательно, заменяем x⁽⁹⁾

12-я итерация:

- максимально, но построено на предыдущем шаге, следовательно, заменяем x⁽¹²⁾

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

Таким образом, точка - точка минимума, значение функции в которой.