Главная страница | Контакты | Случайная страница Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Глава 5

5.1. Функции какого вида называются квадратичными функциями n переменных?

Функция вида: – называется квадратичной функцией n переменных.

5.2. Чему равны градиент и гессиан квадратичной функции?

Для градиента квадратичной функции справедлива формула , где А – симметрическая матрица (матр. Гессе), b – вектор.

Гессиан квадратичной функции совпадает с матрицей A; H(x)=A

5.3. Каким свойством обладает квадратичная функция с положительно определенной матрицей A?

Квадратичная функция (5.2) с положительно определенной матрицей A сильно выпукла.

v Так как матрица H(x)=A симметрична и положительно определена, то все ее собственные значения положительны и существует ортонормированный базис из собственных векторов этой матрицы. В этом базисе все угловые миноры матрицы A и матрицы A-lE положительны при достаточно малом , а это означает, что функция f(x) сильно выпукла.

5.4. При каких a, b, c функция f(x)=ax₁² + bx₁x₂ + cx₂² будет выпукла?

5.5. Выписать матрицу A квадратичной функции f(x)=x₁² + 3x₃² + 2x₁x₂ – x₂x₃ + 2x₂ + x₃.

5.6. Какая последовательность { x^k }, k = 0, 1, 2,…называется минимизирующей?

последовательность { x^k }, удовлетворяющая требованию и , где U* - множество точек глобальногоминимума ф-и,называется минимизирующей.

5.7. Привести пример минимизирующей последовательности, не сходящейся к точке минимума.

Например, для функции , последовательность x^k = k является минимизирующей, но не сходится к единственной точке минимума x* = 0. Напротив, минимизирующая последовательность x^k = 1/ k сходится к точке минимума x* = 0.

5.8. Что такое скорость сходимости минимизирующей последовательности? Какие скорости сходимости Вы знаете?

Последовательность { x^k } сходится к точке x* линейно (со скоростью геометрической прогрессии), если существует такое число , что выполняется неравенство .

Сходимость называется сверхлинейной, если .

Сходимость называется квадратичная, если .

5.9. Когда говорят, что в итерационном процессе x^k+1 = x^k +a_kp^k, k = 0, 1,… производится исчерпывающий спуск?

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

5.10. Какие направления дифференцируемой в точке x^k функции f(x) называются направлениями убывания? Каков геометрический смысл направления убывания?

Направление вектора p^k называется направлением убывания функции f(x) в точке x^k, если при всех достаточно малых положительных α выполняется неравенство f(x^k+ αp^k)<f(x^k)

Геометрически это означает, что вектор составляет тупой угол с градиентом gradf(x^k).

5.11. Какова скорость сходимости метода градиентного спуска для квадратичной функции f(x) с положительно определенной симметрической матрицей A, где 0<l<L − ее наименьшее и наибольшее собственные значения?

При любых α ϵ (0, 2/L) и x⁰ϵ E_n итерационная последовательность x^k+1=x^k- αgradf(x^k) сходится к единственной точке глобального минимума х* функции f(x) линейно (т.е. со скоростью геометрической прогрессии), а именно ρ(x^k,x*)≤q^kρ(x⁰,x*), где q=max {|1-αl|, |1-αL|}.

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

μ=L/l – число обусловленности функции, где L и l – наибольшее и наименьшее собственные значения матрицы. Если μ велико, то линии уровня сильно вытянуты и говорят, что функция имеет овражный характер, т.е. резко меняется по одним направлениям и слабо − по другим. В этих случаях задачу минимизации называют плохо обусловленной. Если же число μ близко к единице, то линии уровня близки к окружностям и задача минимизации является хорошо обусловленной.

5.13. В чем состоят преимущества и недостатки метода наискорейшего спуска по сравнению с методом градиентного спуска?

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

5.14. Каков главный недостаток градиентных методов?

Градиентные методы оказываются очень медленным при движении вдоль оврага.

5.15. В чем состоит идея метода сопряженных градиентов? Чем этот метод отличается от методов градиентного и наискорейшего спуска?

Идея методов сопряжённых градиентов заключается в нахождении локального экстремума минимума функции, основываясь на информации о её значении и её градиенте (направлении антиградиента p^k=-gradf(x^k)). От других методов отличается тем, что в них не используется информация о направлении спуска на предыдущем шаге.

5.16. Какова скорость сходимости метода Ньютона для дважды дифференцируемой выпуклой функции f(x) многих переменных? Какова трудоемкость этого метода?

При выборе достаточно хорошего начального приближения x⁰ϵ E_n, минимизирующая последовательность {x^k} для сильно выпуклой дважды дифференцируемой функции f(x) сходится к точке минимума с квадратичной скоростью ρ(x^k,x*)≤[cρ(x⁰,x*)]². Если точка x⁰ выбрана недостаточно близко к точке x*, то последовательность может расходиться. Метод Ньютона трудоёмок, что обусловлено необходимостью вычисления и обращения на каждом шаге матрицы вторых производных минимизируемой функции.

5.17. Чем отличаются классический и обобщенный методы Ньютона для сильновыпуклой дважды дифференцируемой функции многих переменных?

Даже сходящаяся последовательность {x^k} метода Ньютона не всегда обеспечивает монотонное убывание f(x), т.е. неравенство f(x^k+1)<f(x^k) для некоторых k=0,1,… может нарушаться. Этот недостаток устранен в обобщенном методе Ньютона:

x^k+1=x^k- α_kH-1(x^k)gradf(x^k), где величина α_k >0 находится на каждом шаге из условия исчерпывающего спуска по направлению p^k=-H^-1(x^k)gradf(x^k).

5.18. Сформулировать общий принцип построения квазиньютоновских методов. Какую скорость сходимости следует ожидать от квазиньютоновских методов? Оценить их трудоемкость.

Квазиньютоновские методы – это методы оптимизации, основанные на накоплении информации о кривизне целевой функции по наблюдениям за изменением градиента, чем принципиально отличаются от ньютоновских методов. Класс квазиньютоновских методов исключает явное формирование матрицы Гессе, заменяя её некоторым приближением. Так как квазиньютоновские методы объединяют достоинства метода наискорейшего спуска и метода Ньютона, они сочетают высокую (квадратичную) скорость сходимости с невысокой трудоемкостью итерации (поскольку не нужно инвертировать матрицу Гессе).