Материал: ММвСС. Экзаменационные вопросы и ответы

44. Численные методы оптимизации. Общая структура алгоритма. Привести примеры численных методов условной и безусловной оптимизации.

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

Численные методы оптимизации:

•Безусловная оптимизация (функции одной переменной, функции нескольких переменных).

•Условная оптимизация (функции нескольких переменных).

Оптимизация функции одной переменной:

•Прямой поиск (безусловная оптимизация)

•Дихотомия

•Метод золотого сечения

•Метод чисел Фибоначчи

•Метод квадратичной интерполяции

Оптимизация функции нескольких переменных:

•Детерминированные методы:

oПокоординатный спуск

oМетод Хука-Дживса

oСимплекс метод Нелдера-Мида

oКомплексный метод Бокса

oМетод штрафных функций

•Стохастические методы:

oСлепой случайный поиск

oЭволюционный метод (генетический алгоритм)

45.Оптимизация функции одной переменной. Метод дихотомии.

Пример (из лекции)

Функция Розенброка

( ) = (1 − 1)2 + 100( 2 − 12)2

Шаги поиска экстремума (на каждом из шагов используется метод золотого сечения)

Результат: 0 = (1.16, 1.36).

Вывод: маленькая точность. Должно быть (1,1). Потребовалось около 1138x20 вычислений функции.

48. Оптимизация функции нескольких переменных. Безусловная оптимизация. Симплекс метод Нелдера-Мида (поиск по деформируемому многограннику).

Пусть задана выпуклая функция переменных ( ) = ( 1, 2, … , ). Данный метод предполагает следующие шаги:

1.Подготовка. Задается исходный многогранник, содержащий + 1 вершину (т.е. + 1 точка – симплекс).

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

3.Отражение. Относительно «наихудшей» точки определяется центр тяжести противоположной грани. Выполняется попытка отражения наихудшей точки через найденный центр тяжести. В результате чего получают точку .

4.Растяжение. Если отраженная точка «лучше» «лучшей», то делается попытка растянуть многогранник в данном направлении. Если растяжение успешное, то полученная точка включается в список вершин многогранника, в противном случае в список вершин включается отраженная точка .

5.Сокращение. Сокращение производится, если отраженная точка хуже точки . Если лучше , то выполняется внешнее сокращение, в результате которого получают точку 1. Если хуже выполняется внутреннее сокращение , в результате которого получают точку 2. Если ( 1) или ( 2) < ( ), то соответствующая точка включается в список вершин.

6.Перемещение. Включенная в многогранник точка замещает наихудшую точку . Точка исключается, этим достигается перемещение многогранника.

7.Сжатие. Сжатие многогранника производится во всех направлениях. При этом лучшая вершина остается на месте, а остальные пересчитываются.

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

Пример (из лекции)

Функция Розенброка

( ) = (1 − 1)2 + 100( 2 − 12)2

Шаги поиска экстремума из точки (3,3)

Результат: 0 = (1.000, 1.002).

Вывод: высокая точность. Должно быть (1,1). Потребовалось всего 243 вычислений функции.

49. Оптимизация функции нескольких переменных. Условная оптимизация. Метод штрафных функций.

Метод заключается в замене исследуемой функции некоторой модифицированной функцией, которая в области допустимых значений близка к исходной функции, а вблизи области ограничений ее значение резко увеличивается. Задача: минимизировать функцию ( ) при ограничениях ( ) ≥ 0, = 1 … .

Начальный этап.

2.Если ∑=1 ( ( )) < , то остановиться. Решение является искомым.

Иначе положить +1 = . Изменить = + 1 и перейти к первому шагу ( + 1)-й итерации.

Пример (из лекции)

( ) = 2

( ): > 2 − 2 > 0( , ) = 2 + 1

− 2

Пример на C++

Программа нахождения минимума функции Розенброка.

// C++14

#include <iostream> #include <cmath> #include <functional> #include <algorithm> using namespace std;

//Константы: точность и макс. кол-во итераций const double EPS = 1e-8;

const int ITERATIONS = 10000;

//Функция Розенброка

double f(double x, double y) {

return (1.0 - x) * (1.0 - x) + 100 * (y - x * x) * (y - x * x);

}

// Требование 1: x > 3

double psi_1(double x, double y) { return x - 3;

}

// Требование 2: y > 3

double psi_2(double x, double y) { return y - 3;

}

// Покоординатный спуск как часть метода штрафных функций

void minimize(int k, double &x, double &y, std::function<double(double, double)> &func) { double phi = (1.0 + sqrt(5.0)) / 2.0; // золотое сечение

double startX = x - x / (k * phi), stopX = x + x / (k * phi); double startY = y - y / (k * phi), stopY = y + y / (k * phi); for (int i = 0; i < ITERATIONS; ++i) {

if (i % 2 == 0) { // оптимизируем X double a = startX, b = stopX; while (fabs(b - a) >= EPS) {

double x1 = b - (b - a) / phi, x2 = a + (b - a) / phi; double f1 = func(x1, y), f2 = func(x2, y);

a = (f1 >= f2) ? x1 : a; b = (f1 <= f2) ? x2 : b;

}

x = a + (b - a) / 2.0;

}

else { // оптимизируем Y

double a = startY, b = stopY; while (fabs(b - a) >= EPS) {

double y1 = b - (b - a) / phi, y2 = a + (b - a) / phi; double f1 = func(x, y1), f2 = func(x, y2);

a = (f1 >= f2) ? y1 : a; b = (f1 <= f2) ? y2 : b;

}

y = a + (b - a) / 2.0;

}

}

}

// Метод штрафных функций int main() {

int i = 1;

//координаты начальных точек следует устанавливать больше, чем может находится экстремальная точка, например, (20, 20); Экстремальная точка находится f(3, 9) = 4.

//значение r устанавливается равным 1

//b в данном случае характеризует приоритет ограничений: чем больше, тем выше вероятность соблюдения ограничений, но 0 < b < 1

double point_x = 20, point_y = 20, r = 1.0, b = 0.7;

//Создаем указатель на функцию типа "double func(double, double)".

std::function<double(double, double)> func; do {

cout << point_x << ' ' << point_y << " -> " << f(point_x, point_y) << endl;

//Меняем функцию в соответствии со значением r func = [r] (double x, double y) {

return f(x, y) + r / psi_1(x, y) + r / psi_2(x, y);

};

//Минимизируем

minimize(i, point_x, point_y, func); r *= b;

++i;

} while (i < ITERATIONS && func(point_x, point_y) >= EPS); cout << "Result: " << endl;

cout << point_x << ' ' << point_y << " -> " << f(point_x, point_y); return 0;

}