Файл: Сахарова Людмила Викторовна, Лукьянова Галина Викторовна Методы оптиизации для машинного обучения учебное пособие.doc

УПРАЖНЕНИЯ

1. Установить, являются ли выпуклыми следующие множества:

1. 
   U ={(x₁ , x₂) 2x₁ + x₂  2, 2x₁ – x₂  –2, x₂  0};
   
2. 
   U ={(x₁ , x₂) x₂ > x²₁};
   
3. 
   U ={(x₁ , x₂) x₁x₂ < 1, x₁ > 0, x₂ > 0};
   
4. 
   U ={(x₁ , x₂) x₁ – x₂  2, x²₁ + x²₂  4};
   
5. 
   U ={(x₁ , x₂ , x₃) x₃  x²₁ + x²₂}.
   

3.3. ОБЩИЕ ПРИНЦИПЫ n–МЕРНОЙ МИНИМИЗАЦИИ

Для численного решения задач безусловной минимизации:f (x) min, x  E_n разработано много алгоритмов, использующих итерационные процедуры видаx^k+1 =Ф(x^k , x^k–1 ,…, x⁰), x⁰  E_n , (3.25)позволяющие при определенных условиях построить последователь­ность {х^k} такую, чтогде U^* – множество точек глобального минимума функции f (х). Последовательность {х}, удовлетворяющая требованию (3.26), называется минимизирующей для функции f (х). Если, кроме того, для случая U^* дополнительно выполняется условие , (3.27)то говорят, что минимизирующая последовательность сходится к множеству U*. Если множество U^* состоит из единственной точки х*, то для сходящейся к U* минимизирующей последовательности .Замечание. Минимизирующая последовательность может не сходиться к точке минимума. Например, для f (x) =х²/(1+ х⁴), x  E₁ , последовательность x^k=k является минимизирующей, но не сходится к единственной точке минимума х^*= 0.Вопрос о существовании точки минимума обычно решается с по­мощью теоремы Вейерштрасса, которая гласит: если функция f (х) непрерывна в E_n и множество U_= {х |f (х)  } для некоторого  непу­сто и ограничено, то f (х) достигает глобального минимума в

---

E_n.Отметим, что если множество U_– выпукло, а функция f (х) стро­го выпукла, то точка ее минимума единственна (см. теорему 3.5).Среди итерационных процедур (3.25) можно условно выделить та­кие, которые гарантируют отыскание решения задачи за конечное число итераций (шагов). Однако их удается построить лишь для не­которых специальных типов задач минимизации. Как правило, прихо­дится иметь дело с бесконечными последовательностями {х^k}, поэ­тому говорить о достижении решения можно лишь в пределе. Важной характеристикой сходящихся минимизирующих последова­тельностей является скорость сходимости. Говорят, что последова­тельность {х^k} сходится к точке х^*линейно (со скоростью геомет­рической прогрессии), если существует такое число q  (0; 1), что выпол­няется неравенство (х^k, х^*)  q(х^k–1, х*), т. e. р(х^k, х^*)  q^k(х⁰, х^*).Сходимость называют сверхлинейной (т.е. более быстрой, чем определяемая любой геометрической прогрессией), если (х^k, х^*)  q(х^k–1, х*), q_k +0 при k .Наконец, термин квaдрaтичнaя сходимость используется, если справедлива оценка:(х^k, х^*)  [c(х^k–1, х^*)]², c > 0 или (х^k, х^*)  , где q= (х⁰, х^*). Для многих алгоритмов скорость сходимости последовательности {х^k} из (3.25) характеризуется и другими неравенствами, например,(х^k, х^*)  c/k^, при с > 0,  > 0.Установление факта сходимости последовательности {х^k} из (3.25) и оценка скорости сходимости дают существенную информацию об итерационном процессе (3.25).Конкретный вычислительный алгоритм на основе (3.25), в котором может получаться бесконечная последовательность {х^k}, необходимо дополнять условием остановки (критерием оконча­ния счета). На практике часто пользуются следующими условиями:(х^k+1, х^k) < ₁ ;  (3.28)f (x^k+1)–f (x^k) < ₂ ; (3.29) f  (x^k) < ₃ , (3.30)где _i– заранее заданные параметры точности.

---

Ниже будут рассмотрены вычислительные алгоритмы простейших процедур (3.25), как правило, основанные на рекуррентных формулах видаx^k+1= x^k + _kp^k , k = 0, 1, …, (3.31)где р^k – направление поиска точки x^k+1 из точки x^k , а число _k – величина шага, которая выбирается так, чтобы выполнялось условиеf (x^k+1) < f (x^k). (3.32)Эти алгоритмы различаются способом построения вектора р^k и выбора шага _k .Будем говорить, что в итерационном процессе (3.31) производится исчерпывающий спуск, если величина шага _k находится из решения одномерной задачи минимизацииФ_k()min, Ф_k() = f (x^k +  р^k). (3.33)Таким образом, при исчерпывающем спуске на каждом шаге пол­остью реализуется возможность уменьшить значение целевой функции f (х) при перемещении из точки x^k в направлении, коллинеарном вектору р^k. Величина шага _k может быть найдена, например, с помощью методов, описанных в гл. 2.Теорема 3.6.Для дифференцируемой в Е_n функции f (x)в итерационном процессе (3.31) с выбором шага _kв соответствии с (3.33) для всех k1 выполняется условие< f  (x^k+1), р^k > = 0. (3.34)Запишем необходимое условие минимума функции одной переменной Ф_k() из (3.33), используя правило дифференцирования сложной функции: .Учитывая, что x_j^k+1= x_j^k +  р_j^k получаем условие (3.34).Дадим геометрическую иллюстрацию соотношения (3.34) пространстве Е₂. При перемещении из точки x^k вдоль прямой, задаваемой вектором p^k в направлении убывания функции, происходит пересечение линий уровня функции f (х) до тех пор, пока либо не будет до­стигнута стационарная точка f  (x^k+1) = 0, либо прямая не коснется в точке x^k+1 некото­рой линии уровня функции f (x). Равенство (3.34) и есть условие касания (рис. 3.2).

---

Свойство (3.34) позволяет в явном виде найти величину _k для квадратичной функции.Теорема 3.7. Для квaдрaтичной функцииf (х) = 1/2<Aх,х>++c

величинa _k исчерпывaющего спускa в итерaционном процессе (3.31) будет равна
. (3.35)

Умножив равенство (3.31) слева на матрицу А квадратичной функции f (х) и прибавив к обеим частям вектор b, получим: Ax^k+1 + b = Ax^k + b + _kAp^k . Учитывая, что градиент квадратичной функции равен f  (x) = Ax + b, имеем:

f  (x^k+1) = f  (x^k)+ _kAp^k . Под­ставляя выражение для f  (x^k+1) в равенство (3.34), получаем фор­мулу (3.35).

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

В итерационном процессе (3.31) используются, как правило, на­правления убывания. Сформулируем признак направления убывания.

Теорема 3.8. Пусть функция f (x) дифференцируема в точке х^k . Если вектор p^k удовлетворяет условию

, (3.36)

то направление вектора р является направлением убывания.

Из свойства дифференцируемой функции (3.8) и условия (3.36) следует, что = k), p^k > + () = < 0 при всех достаточно малых  > 0, т.е. вектор р^k задает направление убывания функции f (х) в точке х^k.

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

1   2   3   4   5   6   7   8   9   10

---

УПРАЖНЕНИЯ

1. 
   Убедиться в том, что последовательность { х^k}, х^k = является минимизирующей для функции f (х) = (x₁ + x₂)/(1 + x₁²+ x₂²).
   
2. 
   Проверить, что последовательность { х^k }: х^k+1 = х^k – _kf ( х^k) является минимизирующей для функции f (х) = x₁²+ x₂² , если:
   

а) _k = 1/10;б) _k= 1/(k+1).Установить скорость сходимости этой последовательности.

3. 
   Пусть множество U^* точек минимума функции f (х) в E_n непусто и ограничено. Доказать, что для сходимости любой минимизирующей последовательности { х^k } к U^* необходимо и достаточно, чтобы существовало число  > 0 такое, что множество U_= { х | f (х) < f ^* + } ограничено ( f ^*= f (x) ).
   
4. 
   Выяснить, будет ли произвольная минимизирующая последователь­ность сходиться к множеству точек минимума функции f (х), если:
   

f (х) = x E_n ;б) f (х) = ||х||, x E_n ;в) f (х) = ||х||/(1+||х||)² , x E_n.5. Для функции f (х) = 4x₁²+ 4x₂² – 6 x₁x₂ изобразить линию уровня f (х)=(x₁, x₂) = f (2,2) и векторы f '(2,2), f '(2,l), f '(1,–2), f '(–l, –1) с началом в точке (2, 2). Установить, какие из них задают направления убывания функции f (х) в точке (2, 2). Выполнить по каждому из этих направлений один шаг ис­черпывающего спуска.3.4. ПРЯМЫЕ МЕТОДЫ БЕЗУСЛОВНОЙ МИНИМИЗАЦИИРассмотрим конкретные вычислительные алгоритмы решения задачи безусловной минимизации f (х)  min, x E_n, которые опираются только на вычисление значений функции f (х), т.е. прямые методы ми­нимизации. Важно отметить, что для их применения не требуется дифференцируемость целевой функции и даже ее аналитиче­ское задание. Нужно лишь иметь возможность вычислять или измерять значения

---