21. Что понимают под термином «штрафная функция», «барьерная функция» в задачах оптимизации?

22. Как определяются точки измерений при поиске оптимума функции методом Ньютона?

Альтернативная версия ответа на тот же вопрос:

(Как определяются точки измерений при поиске оптимума функции методом Ньютона? )

В методе Ньютона последовательность точек спуска определяется формулой:

Для текущей точки xk направление и величина спуска определяется вектором pk = – (f''(xk)) –1·f'(xk). Хотя в определении вектора pk фигурирует обратная к f''(xk) матрица (f''(xk)) –1, на практике нет необходимости вычислять последнюю, так как направление спуска pk можно найти как решение системы линейных уравнений

23. Сформулируйте идею «овражных» методов поиска.

24. Возможно ли применение градиентных методов при отсутствии аналитической записи целевой функции?

25.Какие задачи стохастического программирования называют «задачами с риском» и «задачами с неопределенностью»?

26. Сформулируйте алгоритмы случайного поиска с последовательной тактикой.

К ним относятся: Метод с возвратом при неудачном шаге, поиском с пересчетом, поиском с линейным пересчетом, поиск с «наказанием» случайностью, поиск с «поощрением» случайностью, поиск с парными пробами, поиск по наилучшей пробе, поиск с самообучением, поиск с обучением по одной попытке, «нежесткое» обучение по одной попытке, поиск экстремума по статистическому градиенту

27. Сформулируйте алгоритм слепого случайного поиска.

Имеем какую-то многомерную (n-мерную) функцию W()

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

Если, например, мы ищем минимальное значение (W(X)) и у нас задано какое-то минимальное значение целевой функции (W_min), к которому нужно стремиться, то поиск осуществляется до тех пор, пока мы не приблизимся к этому значению на какое очень близкое расстояние:

Вот и все! Недостатком метода является большая трудоемкость, достоинством – универсальность (можно использовать для функций любого вида). Чем больше точек возьмём, тем больше вероятность того, что получим оптимальное решение задачи. Чаще всего максимальное количество точек для вычисления определенно заранее, было бы иначе - считать можно было бы до бесконечности и все равно была бы вероятность никогда не достигнуть оптимального значения.

28. Сформулируйте алгоритм случайного поиска с возвратом.

Выбираем случайную точку X⁰, считаем в ней значение функции, задаем постоянный шаг h. Из этой точки делаем в случайном направлении пробный шаг (h), ну и считаем значение функции в получившейся точке (назовём её X¹), дальше сравниваем значения функции в предыдущей точке и в текущей. Если шаг удачный, то он считается рабочим (то есть новый шаг мы будем делать из точки X¹), иначе происходит возврат в точку X⁰ и снова делается пробный шаг, и так до тех пор, пока не найдет то что ищем.

Это был в общих словах алгоритм поиска, теперь всякие примечания, дополнения и тому подобные вещи (Вдруг кому интересно):

∆X^k+1 = hξ, шаг удачный

-∆X, шаг неудачный

Где ξ = (ξ₁,..,ξ_n) , где ξ_i - нормированные случайные числа, такие что i² = 1

Вектор ξ равномерно распределен в n-мерном пространстве, т.е. отдельные реализации этого вектора направлены равновероятно во всех направлениях пространства параметров.

Для выполнения условия i² = 1 элементы вектора нормируют, используя соотношение ξ_i =

, где ξ_i⁰— случайные числа, равномерно распределенные в интервале (-1,1)

Эти числа получают масштабированием случайных чисел r_i, равномерно распределенных в интервале (0, 1), в соответствии с формулой: ξ_i⁰ = -1+2r_i

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

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

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

При неудачном j-ом шаге, новым центром поиска служит точка X_j+1=X_j-2∆X_j