Минимизация квадратичной формы. Существование и единственность точки минимума

Санкт-Петербургский Государственный Университет

Факультет Прикладной Математики - Процессов Управления

Курсовая работа по методам вычислений

Минимизация квадратичной формы

(вариант 10)

                    Исполнитель

студентка 2 курса 28 гр.

                                            Кутявина К. А.

                   Руководитель

доцент Матросов А.В.

2003 год.

1.Задача минимизации квадратичной функции

А). Постановка задачи.

Пусть Х – евклидово n-мерное пространство Rⁿ.

В пространстве Rⁿ рассмотрим квадратичную функцию

f(x) =                                      (1)        

где А – положительно определенная симметричная матрица, т.е. имеют место неравенства:

        m>0                                                                       (2)

Для функции (1) рассмотрим задачу 1.

Б). Существование и единственность точки минимума.

Теорема 1. Квадратичная функция (1) при выполнении условия (2) имеет в Rⁿ единственную точку минимума, удовлетворяющую системе линейных алгебраических уравнений Aх + b = 0 .    

Доказательство.

Пусть точка минимума функции f(x) существует. Рассмотрим окрестность точки минимума, т.е. точки вида x = x^* + αq, где α  - произвольное число, а q -  произвольный, но фиксированный  вектор пространства Rⁿ. Подставим данное выражение в формулу (1):

f(x) = f(x^*+ α q) = f(x^*) + α (Ах^*+b)^Tq + α²q^TAq.                                                    (3)

Введем обозначение φ^*(α) = f(x^*+α q). Функция φ^*(α) является, очевидно, квадратным трехчленом относительно переменной α и этот трехчлен имеет минимум ввиду положительности старшего коэффициента q^TAq, причем этот минимум достигается при α = 0. Поэтому необходимое условие минимума функции (обращение в нуль ее производной) является в данном случае и достаточным. Выписывая это условие, получаем:

= (Ах^* + b)^Tq = 0                                                   (4)

откуда ввиду произвольности вектора q  следует :

Ах^*+b =0,                                                                    (5)

стоит только в соотношении (4) положить q = Ax^* + b и воспользоваться свойствами нормы. Таким образом, точка минимума функции (1) в предположении ее существовании ее существования удовлетворяет системе линейных алгебраических уравнений (5). Покажем, что точка х^*, найденная как решение системы уравнений (5), является точкой минимума функции f(x).

Действительно,

f(x) = f(x^* + (x-x^*)) = f(x^*) + q^T(Ax^*+b) + (x – x^*)^TA(x-x^*)  f(x^*) + m

ввиду неравенства (2) и с учетом того, что вектор х^* удовлетворяет системе (5). Более того, при хх^* имеет место строго неравенство: f(x) > f(x^*), на чем и заканчивается док-во.

2. Одношаговый градиентный метод наискорейшего спуска

Поскольку сходящаяся минимизирующая последовательность позволяет найти точку минимума рассматриваемой функции с произвольной наперед заданной точностью, то следует подробнее рассмотреть вопрос о постороении  такой последовательности. Поставим следующую задачу: имея точку х^k Rⁿ  построить точку x^k+1  Rⁿ  такую, чтобы выполнялось соотношение:

f(x^k+1) < f(x^k).                                                                          (1)

Будем искать точку x^k+1 в следующем виде :

x^k+1 = x^k + μq .                                                                           (2)

где q – заданный вектор из Rⁿ , называемый направлением спуска, а  μ – искомый  параметр, называемый обычно шагом метода в направлении спуска. Имеем:

f(x^k+1) = f(x^k + μq)  φ (μ) = φ(0) + μ,                  (3)

где

                                          φ(0) = f(x^k),                        (4)

Поскольку φ(μ) является квадратным трехчленом с положительным старшим коэффициентом, то у этого трёхчлена существует точка минимума μ_k^*_, которая может быть найдена из необходимого условия экстремума , откуда и получаем :

                                                        μ_k^* = - = - .                                        (5)

если в приведенных выше формулах считать, что q=Ax^k + b ( то есть вектор является вектором градиента функции f(x) в точке x^k),  то соответствующий метод построения последовательности называют градиентным методом. Если к тому же шаг метода μ выбирается по формуле (5), то такой метод называют одношаговым методом наискорейшего градиентного спуска.

Пусть последовательность убывания {x^k}для функции f(x) строится по формулам вида (2), т.е. x^k+1= x^k + μ_kq. Построение этой последовательности сопровождается построением еще двух последовательностей {q^k} и {μ_k}.

Теорема  2. Пусть для последовательностей {x^k}, {q^k},{μ^k}выполнены следующие условия:

1.  такое, что (Ax^k + b)^Tq^k  

2.    .

Тогда  

Лемма. (Свойства минимизирующей последовательности) Пусть - минимизирующая последовательность в задаче 2.

       Следующие три утверждения выполняются одновременно:

а). ;

б). ;

в). при

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

Доказательство леммы. Очевидно, что из а). следует б), ибо рассматриваемая функция непрерывна. Покажем, что из б) следует в), для чего оценим норму градиента функции f(x) через разность значений функции в точках x^k  и x^* :

(6)

В оценке (6) использовано  то обстоятельство, что матрица  A^-1 так же как и А является положительно определенной, причем для квадратичной формы с обратной