Как оценивается эффективность одномерного поиска.

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

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

2. Скорость сходимости – число итераций, необходимое для достижения заданной точности.

3. Время счета – время поиска на ЭВМ локального оптимума с заданной точностью, отнесенное к коэффициенту сложности задачи (или к быстродействию ЭВМ).

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

5. Надежность - свойство алгоритма приводить к оптимуму при многократном повторении поиска из разных начальных точек.

Для сравнения алгоритмов по этим критериям следует производить расчеты в одинаковых или близких условиях.

17. Как определяется положение новой точки Хк+1 при поиске оптимума функции методом релаксации?

Метод релаксации Этот метод имеет наиболее простую процедуру поиска. Его алгоритм заключается в отыскании осевого направления, вдоль которого функция цели изменяется наиболее сильно. Для этого в начальной точке поиска определяются производные оптимизируемой функции f(X) по всем переменным. Затем выбирается наибольшая по модулю производная, и соответствующая ей переменная изменяется до достижения частного оптимума. В новой точке определяются производные по всем остальным переменным, и осуществляется поиск следующего частного оптимума и т.д.

где Xр - точка, в которой последний раз определялись производные;

хi, - координата с наибольшей по модулю производной в точке Хр;

signZ -> возвращает знак Z или 0 если Z == 0

18. Как определяется положение новой точки Хк+1 при поиске оптимума функции равномерным градиентным методом?

Основная проблема в градиентных методах – это выбор шага k. Достаточно малый шаг k обеспечивает убывание функции, то есть выполнение неравенства:

но может привести к неприемлемо большому количеству итераций, необходимых для достижения точки минимума. С другой стороны, слишком большой шаг может вызвать неожиданный рост функции (невыполнение условия убывания) либо привести к колебаниям около точки минимума. Однако проверка условия убывания на каждой итерации является довольно трудоемкой, поэтому в методе градиентного спуска с постоянным шагом задают =k постоянным и достаточно малым, чтобы можно было использовать этот шаг на любой итерации. При этом приходится мириться с возможно большим количеством итераций. тешением является лишь то, что трудоемкость каждой итерации, в этом случае, минимальна (нужно вычислять только градиент f’(xk)).

Формула для нахождения Хк+1:

Где а – размер шага итерации.

19. Как определяется положение новой точки Хк+1 при поиске оптимума функции пропорциональным градиентным методом?

20. Как определяется положение новой точки Хк+1 при поиске оптимума функции методом наискорейшего спуска (подъема)?

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

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

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

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

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

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

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

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

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

Дата добавления: 2015-11-14