close

Вход

Забыли?

вход по аккаунту

?

О сходимости обобщенного приведенного метода Ньютона.

код для вставкиСкачать
Приволжский научный вестник
ФИЗИКО-МАТЕМАТИЧЕСКИЕ НАУКИ
УДК 519.6
С.В. Панфёров
канд. физ.-мат. наук, доцент, кафедра высшей математики,
ГБОУ ВПО Московской области «Международный Университет природы,
общества и человека «Дубна»
О СХОДИМОСТИ ОБОБЩЕННОГО ПРИВЕДЕННОГО МЕТОДА НЬЮТОНА
Аннотация. Предлагается подход к решению задачи оптимизации с ограничениями. Описывается алгоритм, использующий синтез таких методов, как разделение переменных, редукцию размерности, сведение основной задачи к вспомогательной. Формулируются условия применимости
алгоритма и теорема о сходимости.
Ключевые слова: задачи нелинейной оптимизации, метод линеаризации, линейные ограничения, метод приведенного градиента, линейная сходимость
S.V. Panferov, International University of the nature, society and the person "Dubna"
ABOUT CONVERGENCE GENERALIZATION NEWTON’S RESULTED METHOD
Abstract. The approach to the decision of a problem of optimization with restrictions is offered. It is
described the algorithm using synthesis of such methods as division of variables, a dimension reduction,
primary goal data to the auxiliary. Conditions of applicability of algorithm and the theorem of convergence
are formulated.
Keywords: problems of nonlinear optimization, a linearization method, linear restrictions, a method
of the resulted gradient, linear convergence.
Введение
Необходимость решения задач глобальной оптимизации находит широкое применение в различных областях человеческой деятельности. Задачи проектирования,
распределения ресурсов, расчета траектории движения встречаются в ряде прикладных областей, в которых необходимо получить наилучший результат целевой функции
на множестве некоторых ограничений. Сложность решения задач глобальной оптимизации связана, вообще говоря, с невозможностью гарантировано получить решение за
конечное число шагов. Первым вопросом, возникающим при исследовании оптимизационного алгоритма, является вопрос о его сходимости.
1. Постановка задачи
Рассмотрим задачу
f  x   min

(1)

x  Q  x  R n : g i  x   0, i  1,2,..., m .
Будем считать, что функции f  x 
и g i  x   i  1,2,..., m  дважды непрерывно
дифференцируемы на множестве X , удовлетворяют условию Липшица и для всех
x  X векторы g i  x   i  1,2,..., m  линейно независимы.
В работе предлагается метод сведения задачи (1) к задаче безусловной опти4
№ 10 (14) – 2012
Приволжский научный вестник
мизации
F  z   min
(2)
z  R n m .
2. Описание алгоритма обобщенного приведенного метода Ньютона
Суть алгоритма обобщенного приведенного метода Ньютона состоит в следующем.
 
На первом этапе строится касательное подпространство N x k
размерности
n  m к множеству ограничений и выбирается координатное подпространство E I  той
же размерности n  m .

Через E I  обозначим ортогональное дополнение к E I  .
Аналогично алгоритмам с исключением переменных координат, происходит
xk
разбиение переменной
на пару переменных
y
k
, zk

следующим образом:

x k  y k  z k , y k  E  I  , z k  E (I ) .
 
Функция y k   z k

определяется как решение системы нелинейных уравнений

gi y k , z k  0, i  1,2,.., m .
В условиях теоремы о неявных функциях в окрестности точки z k определена
приведенная целевая функция F  z   f   z  , z  [1, с. 280].
Таким образом, задача (1) сводится к задаче безусловной оптимизации (2).
На втором этапе происходит сдвиг по методу Ньютона в координатном подпро-

странстве E (I ) : z k 1  z k  F ( z k )



1
F ( z k ) . При этом проверяется условие релаксации:
 
F z k 1  F z k .


Далее, решая уравнение y k 1   z k 1 , например, модифицированным методом
Ньютона, получаем следующую допустимую точку x k 1  y k 1  z k 1 .
Обоснование замены касательной плоскости координатной плоскостью той же
размерности, т.е. возможность разбиения пространства R n , обеспечивает нетриви-


альная нижняя оценка [2, с. 384] угла   ang N ( x k ), E (I ) между касательной плоско-
  и координатной E(I ) в случае dim N  x   dim E (I ) :
стью N x k
k


cos ang N ( x k ), E (I ) 
1
m( n  m )  1
.
Отметим, что эта оценка является общей характеристикой евклидова пространства, и зависит только от размерностей задачи, и служит хорошей числовой характеристикой качества разделения переменных.
С её помощью также получаем равномерные оценки норм градиента и гессиана
приведенной целевой функции, необходимые для доказательства сходимости метода
№ 10 (14) – 2012
5
Приволжский научный вестник
 
F z k
где min
1
f  x  ,
cos 

 
 2F z k

2
1 max  L  x,  
,
cos2  min2L  x,  
и max наибольшее и наименьшее сингулярные числа матрицы вторых
производных функции Лагранжа задачи (1).
Используя эти оценки, получаем доказательство сходимости обобщённого приведённого метода Ньютона.
Теорема 1. Если последовательность
 xk 
определяется алгоритмом обоб-
щённого приведённого метода Ньютона и каждая стационарная точка функции Лагранжа Морс-регулярна, то найдется     такое, что последовательность x
схоk
 
дится к точке x  , в которой L( x  ,   )  0 и найдётся q  (0,1) такое, что
f ( x k 1 )  f ( x  )  q(f ( x k )  f ( x  )).
3. Приведенный метод линеаризации для решения задач нелинейной оптимизации
Рассмотрим задачу, которая характеризуется тем, что допустимое множество
представлено в виде пересечения двух множеств, одно из которых задано системой
нелинейных уравнений, а другое системой линейных ограничений (для простоты будем
считать, что в формировании допустимого множества участвуют только линейные ограничения-неравенства).
f  x   min
x  X , X  X1  X 2 ,

 x  R
(3)

X 1  x  R n : g i  x   0, i  1,2,..., m ,
X2
Так же,
gi  x 
n

: Ax  b , A  aij  Rk  n , b  bij  Rk 1, m  n, k  n.
как и
 i  1,2,..., m 
в задаче
(1),
будем
считать,
что
функции
f x
и
дважды непрерывно дифференцируемы на множестве X , удовле-
творяют условию Липшица и для всех x  X векторы g i  x   i  1,2,..., m  линейно независимы.
Аналогично тому, как это сделано в работе [3], строится эффективный вычислительный алгоритм, использующий обобщенный приведенный метод Ньютона для отыскания стационарных точек рассмотренного класса задач нелинейной оптимизации.
В дополнение к условиям гладкости мы потребуем от нашей задачи классических условий регулярности [4]:
Предположение 1. Для всех   fopt существуют k  0 и   0 такие, что
  x, X stat   k x   X  x  f  x   ;
x  X : f  x   v ; x   X  x  f  x    .
Предположение 2. Для всех v  fopt следующее множество является конечным:
6
№ 10 (14) – 2012
Приволжский научный вестник
f
x  X
stat

| f  x   v   R1.
На основе схемы, предложенной в работе [3], строится алгоритм «последовательных приближений», генерирующий очередную ( k  1) -ю итерацию как оптимальное
решение вспомогательной задачи, являющейся аппроксимацией исходной, и доказывается теорема о линейной сходимости метода [5].
Теорема 2. Пусть выполнены Предположения 1 и 2, тогда каждая бесконечная
последовательность итераций алгоритма сходится к точке x   X stat .
Более того, для всех v  fopt существуют q1, q2 ( 0  q1, q2  1 ) такие, что для любой
   
бесконечной последовательности x k , f x1  v справедливы следующие оценки:
lim sup
k 
f ( x k 1 )  f ( x * )
 q1 ,
f (xk )  f (x* )
lim sup q2 k  ( x k , X stat )   .
k 
При этом каждая конечная последовательность итераций алгоритма останавливается в стационарной точке x
kstop
 X stat .
Результаты, изложенные в статье, докладывались автором на научных семинарах кафедр оптимального управления и исследования операций факультета ВМК МГУ
им. М.В.Ломоносова, а также на Международной конференции «Дифференциальные
уравнения и топология», посвященной 100-летию со дня рождения Л. С. Понтрягина.
Автор благодарит руководителей указанных семинаров профессоров Ф.П. Васильева и Н.М. Новикову за полезные обсуждения.
Список литературы:
1. Васильев Ф.П. Методы оптимизации-М.: Факториал Пресс, 2002.
2. Панфёров С.В. Оценка качества разделения переменных в обобщенном приведенном методе Ньютона // Международная конференция «Дифференциальные
уравнения и топология», посвященная 100-летию со дня рождения Л. С. Понтрягина
(1908-1988). Тезисы докладов. Москва 17-22 июня 2008 г. – М.: МАКС Пресс, 2008.
С.383-384.
3. Ferris M.C., Zavriev, S.K. The Linear Convergence of a Successive Linear
Programming Algorithm // Computer Scienses Department, University of Wisconsin,
Madison, WI 53706, Mathematical Programming Technical Report 96-112, December 1996.
4. Bertsecas D.P. Nonlinear Programming. Athena Scientific, Belmont,
Massachusetts, 1995.
5. Панфёров С.В. Приведенный метод линеаризации для решения задач нелинейной оптимизации // Вычислительные методы и программирование. 2012. Раздел 1.
C. 137-142. – URL: http://num-meth.srcc.msu.ru/.
List of references:
1. Vasilev F.P. Method of optimization. M.: Factorial the Press, 2002.
2. Panferov S. V. Estimation of quality of division of variables in the generalized Newton's resulted
method // The International conference «the Differential equations and topology» devoted to the 100
anniversary from the date of L.S.Pontrjagin's birth (1908-1988). Theses of reports. Moscow on June, 17-
№ 10 (14) – 2012
7
Приволжский научный вестник
22th, 2008 – M.MAX the Press, 2008, pp. 383-384.
3. Ferris M.C., Zavriev S.K. The Linear Convergence of a Successive Linear Programming
Algorithm // Computer Sciences Department, University of Wisconsin, Madison, WI 53706, Mathematical
Programming Technical Report 96-112, December 1996.
4. Bertsecas D.P. Nonlinear Programming. Athena Scientific, Belmont, Massachusetts. 1995.
5. Panferov S.V. The resulted method of a linearization for the decision of
problems nonlinear
optimization // Numerical Methods and Programming. 2012. Section 1. pp. 137-142. (http://nummeth.srcc.msu.ru/).
УДК 513.88
В.И. Филиппенко
канд. физ.-мат. наук, доцент, кафедра «Математика»,
ФГБОУ ВПО «Южно-Российский государственный университет экономики и сервиса»
РЕЗОЛЬВЕНТЫ И СПЕКТРАЛЬНАЯ ФУНКЦИЯ СИММЕТРИЧЕСКОГО
КВАЗИДИФФЕРЕНЦИАЛЬНОГО ОПЕРАТОРА
В ГИЛЬБЕРТОВОМ ПРОСТРАНСТВЕ L2  H ,  a, b  
Аннотация. Пусть L0 - минимальный оператор в пространстве L2  H,  a, b   для формально самосопряженного квазидифференциального оператора n - го порядка. В данной работе описываются
обобщенные спектральные функции, соответствующие обобщенной резольвенте оператора L0 .
Ключевые слова: обобщенные резольвенты, спектральная функция, минимальный оператор.
V.I. Filippenko, South-Russian State University of Economics and Service
RESOLVENTS AND SPECTRAL FAMILY SYMMETRIC QUASI-DIFFERENTIAL OPERATOR IN
HILBERT SPASE L2  H,  a, b  
Abstract. Let L0 be a minimal operator in L2  H,  a, b   for the formally self-adjoint quasi-differential
operator of order n . In this paper, we describe the generalized spectral family corresponding to a
generalized resolvents for operator L0 .
Keywords: generalized resolvents, spectral family, minimal operator.
Актуальность спектрального анализа квазидифференциальных операторов обусловлена возможностью исследования природы спектра операторов, более общих по
сравнению с классическими операторами.
1. Пусть H – сепарабельное гильбертово пространство со скалярным произведением ,  и нормой  , а L2  H,  a, b   – гильбертово пространство всех измеримых на
интервале a, b  вектор-функций со значениями из пространства H и с суммируемым
квадратом нормы. Скалярное произведение в L2  H,  a, b   определяется формулой
8
№ 10 (14) – 2012
Документ
Категория
Без категории
Просмотров
4
Размер файла
311 Кб
Теги
сходимость, обобщенного, приведенного, метод, ньютона
1/--страниц
Пожаловаться на содержимое документа