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

Глава 3

МЕТОДЫ БЕЗУСЛОВНОЙ МИНИМИЗАЦИИ ФУНКЦИЙ МНОГИХ ПЕРЕМЕННЫХ

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

3.1. ПРЕДВАРИТЕЛЬНЫЕ СВЕДЕНИЯ

3.1.1. ОСНОВНЫЕ ПОНЯТИЯ ЛИНЕЙНОЙ АЛГЕБРЫ

Будем рассматривать функции многих переменных f  =f (x₁ , …, x_n) как функции, заданные в точках хn–мерного евклидова пространства Е_n : f =f (х). Точки х  Е_n представляют векторами–столбцами координат: x = (х₁ ,.. , х_n)^T, где символ «Т» – знак транспонирования^*.Перечислим основные определения и из курса линейной алгебры, которые будут использованы в дальнейшем:1. В пространстве Е_n определены следующие операции:

• 
  сложение х + у = (x₁ + y₂ , …, x_n + y_n)
  
• 
  умножение на действительное число х = (x₁ , …, x_n)  R;
  
• 
  скалярное произведение <х, у> = с известными свойствами .
  

2. Напомним определение длины (нормы) вектора х:и расстояния между векторами x и у (точками пространства Е_n):Для норм произвольных векторов х, у  Е_n справедливо неравен­ство треугольника (3.1)Скалярное произведение оценивается по модулю неравенством Коши– Буняковского . (3.2)3. Остановимся на основных понятиях, связанных с числовыми матрицами.

---

Матрица A = (а_ij), i = 1, .., т; j= 1, …, n, представляет собой прямоугольный массив (таблицу) чисел, состоящий из т строк и п столбцов. Таким образом, вектор–столбец х является матрицей разме­ра n1.Матрица A^T = (а_ij), которая получается из матрицы A = (а_ij), если поменять местами ее строки и столбцы, называется транспонирован­ной по отношению к матрице A.Квадратная матрица A называется симметрической, если A^T =A. Матрицы одинакового размера A = (а_ij) и B = (а_ij) можно склады­вать: A + В = (а_ij+ b_ij).Результатом умножения матрицы A на число , является матрица A =(а_ij).Произведением Aх матрицы A = (а_ij) размера mnна вектор–столбец хE_mназывается вектор–столбец b  E_m, координаты котoрого вычисляют по формуле i=l,..,m, где – вектор коэффициентов i–й строки матрицы A.Для матриц A = (а_ij) и B = (b_kl) соответственно размера mn и nrопределено произведение AB = С =(c_st), где элемент c_stматрицы С размера mr определяется равенством .Можно показать, что (AB)^T = B^TA^T .Если рассматривать n –мерные векторы–столбцы х и у как матрицы размера n1, то формулу для их скалярного произведения можно получить по правилу умножения матриц х^T и у : . (3.3)Заметим, что для х и у  E_nпроизведение ху^T задает квадратную матрицу:

---

. (3.4)Если A – квадратная симметрическая матрица размера nn, то для любых векторов х и у  E_n<Aх,у>=<х,Aу>, так как <Aх,у>= (Aх)^Tу = x^TA^Ty= x^TAy =<х, Aу > .Каждой квадратной матрице размера nn можно поставить в соот­ветствие число – определитель матрицы A (обозначается detA или |A|), которое вычисляют по формуле ,где алгебраическое дополнениеA_ijэлемента A_ijопределяется соотношением A_ij= (–1)^i+jM_ij(минор – это определитель матрицы, полученной из матрицы A вычеркиванием 1–й строки и j–го столбца). Квадратная матрица A называется вырожденной, если ее определи­тель равен нулю, и невырожденной в противном случае.Для каждой невырожденной матрицы A существует обратная матрица А^–1 = (_ij) такая, что А^–1А =АА^–1= Е, где Е – единичная матрица (e_ij):Элементы обратной матрицы могут быть найдены по формуле ,где А_ij– алгебраическое дополнение элемента a_ijматрицы А.4. Пусть А = (a_ij) – симметрическая матрица размера п  п. Тогда функция п переменных h₁,.., h_n , Q(h) = = <Ah, h > называется квадратичной формой этих переменных, а матрица A – матрицей квадратичной формы.Квадратичная форма Q(h) называется положительно определен­ной,

---

если для всех h  0 имеет место неравенство Q(h) > 0.

Из курса линейной алгебры известен критерий Сильвестра по­ложительной определенности квадратичной формы: для того, чтобы квадратичная форма Q(h)=<Ah,h> была положительно определен­ной, необходимо и достаточно, чтобы ее матрица A = (a_ij) была поло­жительно определена, т.е. все ее угловые миноры были положитель­ными:

(3.5)

5. Ненулевой вектор , для которого A = , называется собст­венным вектором квадратной матрицы A, а число  – соответствую­щим ему собственным значением этой матрицы.

Собственные значения находят из характеристического уравнения det(A– E) = 0. Если _i – собственное значение матрицы А, то не­тривиальное решение однородной системы линейных уравнений (A–_iE) =0 дает соответствующий ему собственный вектор. Собст­венные значения симметрической положительно определенной матри­цы А положительны, и существует ортонормированный базис в Е_n из собственных векторов ₁, .., _n матрицы А. В этом базисе матрица А имеет диагональный вид: на ее главной диагонали стоят собствен­ные значения ₁, ..., _n, а на остальных местах – нули.

6. Нормой матрицы А размера п  п называется число ||А|| = ||А||. Очевидно, что для произвольного вектора х  Е_n выполняется неравенство

||Аx||  ||А||||x|| . (3.6)

Норма симметрической положительно определенной матрицы вдовлетворяет двойному неравенству

l  ||А||  L, (3.7)

где l и L – ее наименьшее и наибольшее собственные значения.

Справедлива оценка

3.1.2. МИНИМУМ ФУНКЦИИ МНОГИХ ПЕРЕМЕННЫХ

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

---

Е_n .1. Точка х^*Е_n , называется точкой глобального минимума функции f (х), если для всех х^*Е_n выполняется неравенство f (x^*)  f (х). Значение f (x^*) = = называется минимумом функции. Множество всех точек глобального минимума функции f (х) будем обозначать через U^*.Замечание. Если U^*  0, то вместо минимума функции f (х) иногда рассматривают ее точную нижнюю грань , определение которой в n–мерном случае практически не отличается от определения, данного в разд. 2.1.1.2. Точка называется точкой локального минимума функции f (х), если существует –окрестность точки : U_n ( )={x | (x, ) < } такая, что для всех х^*U_n ( ) выполняется неравенство f ( )  f (х). 3. Если допустимое множество Uв задаче минимизации (максимизации) функции n переменных совпадает со всем пространством E_n , то говорят о задаче безусловной оптимизации , x E_n .

3.1.3. ДИФФЕРЕНЦИРУЕМЫЕ ФУНКЦИИ МНОГИХ ПЕРЕМЕННЫХ

Многие алгоритмы минимизации и критерии оптимальности в E_n используются только для функций, дифференцируемых необходимое число раз.Напомним некоторые факты, известные из курса математического анализа.1. Если функция дифференцируема в точке х⁰ E_n, то ее прира­щение f (х⁰) = f (х⁰ + x) – f (х⁰) можно записать в видеf 

---