УПРАЖНЕНИЯ. 1. Установить, являются ли выпуклыми следующие множества:

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

a) U ={(x ₁, x ₂)ú 2 x ₁ + x ₂ £ 2, 2 x ₁ – x ₂ ³ -2, x ₂ ³ 0};

b) U ={(x ₁, x ₂)ú x ₂ > x ²₁};

c) U ={(x ₁, x ₂)ú x ₁ x ₂ < 1, x ₁ > 0, x ₂ > 0};

d) U ={(x ₁, x ₂)ú x ₁ - x ₂ £ 2, x ²₁ + x ²₂ £ 4};

e) 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 _a= {х |f(х) £ a} для некоторого a непу­сто и ограничено, то f(х) достигает глобального минимума в E _n.

Отметим, что если множество U _a— выпукло, а функция f (х) стро­го выпукла, то точка ее минимума единственна (см. теорему 3.5).

Среди итерационных процедур (3.25) можно условно выделить та­кие, которые гарантируют отыскание решения задачи за конечное число итераций (шагов). Однако их удается построить лишь для не­которых специальных типов задач минимизации. Как правило, прихо­дится иметь дело с бесконечными последовательностями {х ^k }, поэ­тому говорить о достижении решения можно лишь в пределе.

Важной характеристикой сходящихся минимизирующих последова­тельностей является скорость сходимости. Говорят, что последова­тельность {х ^k } сходится к точке х^* линейно (со скоростью геомет­рической прогрессии), если существует такое число q Î (0; 1), что выпол­няется неравенство

r(х ^k, х^*) £ qr(х ^k-1, х*), т. e. р(х ^k, х^*) £ q ^k (х⁰, х^*).

Сходимость называют сверхлинейной (т.е. более быстрой, чем определяемая любой геометрической прогрессией), если r(х ^k, х^*) £ qr(х ^k-1, х*), q_k ® +0 при k ® .

Наконец, термин квaдрaтичнaя сходимость используется, если справедлива оценка: r(х ^k, х^*) £ [ c r(х ^{k- 1}, х^*)]², c > 0 или r(х ^k, х^*) £ , где q = r(х⁰, х^*).

Для многих алгоритмов скорость сходимости последовательности {х ^k } из (3.25) характеризуется и другими неравенствами, например r(х ^k, х^*) £ c / k^a, при с > 0, a > 0.

Установление факта сходимости последовательности {х ^k } из (3.25) и оценка скорости сходимости дают существенную информацию об итерационном процессе (3.25).

Конкретный вычислительный алгоритм на основе (3.25), в котором может получаться бесконечная последовательность {х ^k }, необходимо дополнять условием остановки (критерием оконча­ния счета). На практике часто пользуются следующими условиями:

r(х ^{k+ 1}, х ^k) < e₁; (3.28)

|f(x ^{k +1})-f(x ^k)| < e₂; (3.29)

|| f ¢(x ^k)|| < e₃, (3.30)

где e _i — заранее заданные параметры точности.

Ниже будут рассмотрены вычислительные алгоритмы простейших процедур (3.25), как правило, основанные на рекуррентных формулах вида

x ^{k +1}= x ^k + a _k p ^k, k = 0, 1, …, (3.31)

где р ^k — направление поиска точки x ^{k +1} из точки x ^k, а число a _k — величина шага, которая выбирается так, чтобы выполнялось условие

f(x ^{k +1}) < f(x ^k). (3.32)

Эти алгоритмы различаются способом построения вектора р ^k и выбора шага a _k.

Будем говорить, что в итерационном процессе (3.31) производится исчерпывающий спуск, если величина шага a _k находится из решения одномерной задачи минимизации

Ф _k (a)® min, Ф _k (a) = f(x ^k + a р ^k). (3.33)

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

Теорема 3.6. Для дифференцируемой в Е_n функции f(x) в итерационном процессе (3.31) с выбором шага a_k в соответствии с (3.33) для всех k³ 1 выполняется условие

< f ¢(x ^{k +1}), р ^k > = 0. (3.34)

Запишем необходимое условие минимума функции одной переменной Ф _k (a) из (3.33), используя правило дифференцирования сложной функции:

.

Учитывая, что x_j ^{k +1}= x_j ^k + a р _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) позволяет в явном виде найти величину a _k для квадратичной функции.

Теорема 3.7. Для квaдрaтичной функции f(х) = 1/2 < Aх,х>+<b,x>+ c величинa a _k исчерпывaющего спускa в итерaционном процессе (3.31) будет равна

. (3.35)

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

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

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

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

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

, (3.36)

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

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

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