Точні методи мінімізації квадратичних функцій. Часть 1
The unique approach to constructing various by character exact methods for minimization of square-law functions is studied. Possibility of application of these methods to the solution of nonlinear optimization problems and systems of linear equations is considered.
Збережено в:
| Дата: | 2018 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute"
2018
|
| Онлайн доступ: | https://journal.iasa.kpi.ua/article/view/127323 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | System research and information technologies |
| Завантажити файл: |  |
Репозитарії
System research and information technologies| _version_ | 1866302182157975552 |
|---|---|
| author | Danilin, Yu. Shubenkova, I. |
| author_facet | Danilin, Yu. Shubenkova, I. |
| author_sort | Danilin, Yu. |
| baseUrl_str | http://journal.iasa.kpi.ua/oai |
| collection | OJS |
| datestamp_date | 2018-04-11T11:11:24Z |
| description | The unique approach to constructing various by character exact methods for minimization of square-law functions is studied. Possibility of application of these methods to the solution of nonlinear optimization problems and systems of linear equations is considered. |
| first_indexed | 2025-07-17T10:23:33Z |
| format | Article |
| fulltext |
© Ю.М. Данилин, И.А. Шубенкова, 2007
Системні дослідження та інформаційні технології, 2007, № 4 85
УДК 519.8
ТОЧНЫЕ МЕТОДЫ МИНИМИЗАЦИИ КВАДРАТИЧНЫХ
ФУНКЦИЙ. ЧАСТЬ 1
Ю.М. ДАНИЛИН, И.А. ШУБЕНКОВА
Рассматривается единый подход к построению различных по характеру точ-
ных методов минимизации квадратичных функций. Описываются возмож-
ности применения этих методов к решению задач нелинейной оптимизации и
систем линейных уравнений.
Уже длительное время для построения быстросходящихся алгоритмов
безусловной нелинейной оптимизации на каждой итерации решается квад-
ратичная задача минимизации, в которой вместо матрицы вторых произ-
водных используется некоторая ее аппроксимация, строящаяся с примене-
нием только первых производных исходной функции или, даже, только ее
значений [1–7]. Алгоритмы такого типа (методы сопряженных направлений,
переменной метрики, двойственных направлений) используют различные
аппроксимационные матрицы, и соответствующие методы изучаются неза-
висимо друг от друга, что затрудняет выявление каких-либо общих идей
и свойств различных методов.
В данной работе предлагается достаточно общий подход к минимиза-
ции квадратичных функций, позволяющий строить и обосновывать раз-
личные по характеру алгоритмы минимизации (главным образом, будут
рассматриваться методы, использующие те или иные процессы ортогонали-
зации). В задачах нелинейной оптимизации результаты работы дают воз-
можность строить различные аппроксимационные матрицы, которые ис-
пользуются при разработке соответствующих алгоритмов. В области точных
методов решения линейных систем уравнений результаты дают возмож-
ность обосновывать свойства методов, базируясь на некоторых общих тео-
ретических результатах, справедливых для различных процессов ортогона-
лизации.
Под точными методами минимизации квадратичных функций подразу-
меваются процессы, дающие точное решение задачи за конечное число ша-
гов (итераций).
ПРЕОБРАЗОВАНИЕ ЗАДАЧИ
Пусть
cxbxAxxf ++= ,,
2
1)( , (1)
где nEx∈ — n -мерное евклидово пространство 0, ≥xAx . Пусть ранг
матрицы A равен nt ≤<0 . Будем считать, что функция (1) достигает ми-
нимального значения, т.е. уравнение
Ю.М. Данилин, И.А. Шубенкова
ISSN 1681–6048 System Research & Information Technologies, 2007, № 4 86
( ) 0=+≡′ bAxxf (2)
имеет решение. Обозначим подпространство вырождения матрицы A через
tnE − (подпространство, образованное такими линейно независимыми век-
торами ir , что 0=iAr , tni −≤≤1 ). Ортогональное дополнение к tnE − обо-
значим tE . Тогда ( ) tExf ∈′ ,
( ) ( ) tEArrxfxfe ∈=−′−′= , если tnEr −∉ . (3)
Задачу минимизации функции (1) можно по-разному свести к решению
системы линейных уравнений, определение которой не предполагает
использования матрицы вторых производных A . (Отметим, что при мини-
мизации конкретно функции (1) это чистая формальность, однако для нели-
нейных функций, где ( )xf ′′ — матрица с переменными коэффициентами,
использование лишь градиентов функции играет принципиальную роль.)
Рассмотрим некоторые из подходов.
Будем далее считать, что системы векторов ir и ii Are = , 10 −≤≤ ti
линейно независимы.
А. Определим систему уравнений
0, =+ irbAx , 10 −≤≤ ti , т.е. с учетом (3)
ii rbxe ,, −= , 10 −≤≤ ti . (4)
Лемма 1. Любое решение уравнения (2) является решением системы
(4) и наоборот, т.е. уравнение (2) и система (4) эквивалентны.
Доказательство. Первая часть утверждения очевидна: если *x — про-
извольное решение уравнения (2), то оно удовлетворяет и системе (4).
Пусть теперь x~ — некоторое решение системы (4), т.е. ii rbxe ,~, −= ,
10 −≤≤ ti . Если *x — произвольное решение уравнения (2), то
ii rbxe ,, * −= , 10 −≤≤ ti , и поэтому 0~, * =− xxei , 10 −≤≤ ti . Отсюда,
с учетом линейной независимости векторов t
i Ee ∈ , 10 −≤≤ ti вытекает,
что tnEwxx −∈=− *
~ , т.е. 0=Aw . Следовательно, ( ) =++=+ bwxAbxA *
~
0* =+= bAx , т.е. x~ — решение уравнения (2).
Лемма доказана.
Б. Функцию ( )xf (1) представим в виде
( ) ( ) ( ) *** ,
2
1 xxxxAxfxf −−+=
или
( ) ( ) ( ) ** ,
2
1 xxxfxfxf −′+= . (5)
Используя выражение (5), можно построить систему уравнений
Точные методы минимизации квадратичных функций. Часть 1
Системні дослідження та інформаційні технології, 2007, № 4 87
( ) ( ) ( ) xxxfxfxf iii −′+= ,
2
1 , ti ≤≤0 (6)
( ix , ti ,...,0= — произвольные точки).
Очевидно, любое решение уравнения (2) является и решением сис-
темы (6). С другой стороны, если система векторов ( ) ( ) ==′−′ + iii exfxf 1
( )ii xxA −= +1 , 10 −≤≤ ti линейно независима, то любое решение системы
(6) определяет некоторую точку *x (решение (2)) и значение ( )*xf . Дейст-
вительно, пусть ( )( )xfx ~,~ — произвольное решение системы (6). Вычитая
уравнения (6) друг из друга, получаем
( ) ( ) ( ) ( ) ( ) =−′+−′−′=− ++++ iiiiiiii xxxfxxxfxfxfxf 1111 ,
2
1~,
2
1
( ) iiiii xxxfxxe −′+−= ++ 11 ,
2
1~,
2
1 .
Поскольку в то же время
( ) ( ) ( ) ( ) =−−+−′=− ++++ iiiiiiiii xxxxAxxxfxfxf 1111 ,
2
1,
( ) iiiiii xxexxxf −+−′= ++ 11 ,
2
1, , устанавливаем
( ) iiiii xxxfxxe −′=− +1,
2
1~,
2
1 . (7)
Но ( ) ( )*xxAxf ii −=′ , т.е. из (7) следует
iiii exxxxe ,
2
1~,
2
1
*−=− , 10 −≤≤ ti .
Отсюда так же, как в А, устанавливается
wxx += *
~ , tnEw −∈ , т.е. x~ — решение уравнения (2). Следовательно,
( ) ( )*
~ xfxf = .
Приведенные рассуждения показывают, что справедлива
Лемма 2. Если система векторов ( ) ( ) ( )iiiii xxAexfxf −==′−′ ++ 11 ,
10 −≤≤ ti , линейно независима, то уравнение (2) и система (6) эквивалент-
ны в том смысле, что любое решение *x уравнения (2) удовлетворяет сис-
теме (6), и наоборот.
Тот факт, что решение системы (6) позволяет определять значение
( )*xf , при решении задачи (1) не играет особой роли, однако при миними-
зации нелинейных функций с использованием вспомогательных квадратич-
них задач это может иметь существенное значение.
Отметим, что системы вида (6), помимо минимизации квадратичних
функций, использовались также для минимизации функций более общего
вида — однородных [8].
Ю.М. Данилин, И.А. Шубенкова
ISSN 1681–6048 System Research & Information Technologies, 2007, № 4 88
В. Пусть ii Are = , λ,...,1,0=i , где 10 −≤< nλ — линейно независимая
система векторов, и
( ) ( ) ∑=−≡′
λ
β
0
*00 iiexxAxf . (8)
Тогда
∑=−
λ
β
0
*0 ii rxx . (9)
КОНЕЧНОШАГОВЫЕ ПРОЦЕССЫ РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ
УРАВНЕНИЙ
Итак, для отыскания точки минимума функции ( )xf (1) достаточно решить
одну из систем уравнений (4), (6). Далее будем рассматривать конечно-
шаговые методы решения систем линейных уравнений. Разработка та-
ких методов основывается на следующих соображениях (берем за основу
систему (4)).
Пусть 0x — произвольная точка, а точки txx ,...,1 строятся таким обра-
зом, чтобы выполнялись условия
1,...,1,0,0,,,1 −=≤≤−=+ tkkirbex iik . (10)
Тогда, как вытекает из сравнения систем (10) и (4), точка tx будет ре-
шением системы (4), т.е. *xxt = . Если выбирать точки txx ,...,1 по формуле
1,...,1,0,1 −=+=+ tkpxx kkkk α , (11)
где kα — скалярный множитель, а kp — вектор, то систему (10) можно за-
писать в виде
kiexrbep ikiikk ≤≤−−= 0,,,,α . (12)
При 1≥k точка kx должна удовлетворять условиям (10): =ik ex ,
irb,−= , 10 −≤≤ ki .
Следовательно, из (12) следует
1,10,0, ≥−≤≤= kkiep ikkα . (13)
При ki = оказывается
( ) kkkkkkkkkk rxfrbAxrAxrbexrb ,,,,,, ′−=+−=−−=−− ,
т.е.
( ) kkkkk rxfep ,, ′−=α . (14)
Условия (13), (14) будут, очевидно, выполнены, если вектор kp удов-
летворяет условиям
10,0, −≤≤= kiep ik , (15)
Точные методы минимизации квадратичных функций. Часть 1
Системні дослідження та інформаційні технології, 2007, № 4 89
0, ≠= kkk cep , (16)
а множитель
( )
kk
kk
k ep
rxf
,
,′
−=α . (17)
Таким образом, точка 1+kx , определяемая в виде (11), будет удовлетво-
рять условиям (10), если вектор kp и множитель kα определяется условия-
ми (15), (16) и (17) (при 0=k вектор kp , очевидно, определяется лишь ус-
ловием (16)).
Сформулируем некоторые утверждения, справедливые при условии,
что точка 1+kx и векторы kp определяются соотношениями (10), (15), (16),
причем 0≠kp .
Утверждение 1. Векторы kpp ,...,0 , удовлетворяющие условиям (15),
(16), линейно независимы.
Утверждение 2. При любом 10 −≤≤ tk в точке 1+kx , удовлетворяю-
щей условиям (10), реализуется минимум функции (1) на подпространстве,
образованном векторами krr ,...,0 , т.е.
( ) kirxf ik ≤≤=′ + 0,0,1 . (18)
Справедливость этого утверждения нетрудно установить, воспользо-
вавшись условиями (13) и (14), которые можно записать в следующем виде:
( ) =−= + ikkikk rxxAep ,, 1α
( ) ( ) 1,10,0,1 ≥−≤≤=′−′= + kkirxfxf ikk , (19)
( ) =−= + kkkkkk rxxAep ,, 1α
( ) ( ) ( ) 0,,,1 ≥′−=′−′= + krxfrxfxf kkkkk . (20)
Из (20) следует, что ( ) 0,1 −′ + kk rxf при любом k . Учитывая это и ис-
пользуя (19), получаем условия (18).
Утверждение 3. Если
( ) kixfr
i
j
jiji ≤≤′= ∑
=
0,
0
λ , (21)
где ijλ — произвольные коэффициенты, причем 0≠iiλ , то при любом
10 −≤≤ tk
( ) ( ) kixfxf ik ≤≤=′′ + 0,0,1 . (22)
Справедливость этого утверждения можно установить, используя вы-
ражения (21) в (19), (20) и рассуждая по индукции. (Параллельно устанавли-
вается линейная независимость векторов ( )ixf ′ , ki ≤≤0 .)
Ю.М. Данилин, И.А. Шубенкова
ISSN 1681–6048 System Research & Information Technologies, 2007, № 4 90
Замечание. Если 0H — некоторая невырожденная матрица, и
( ) kixfHr
i
j
jiji ≤≤′= ∑
=
0,
0
0λ , (23)
то при любом 10 −≤≤ tk
( ) ( ) kixfHxf ik ≤≤=′′ + 0,0, 01 . (24)
Справедливость (24) при выборе ir в виде (23) устанавливается точно
так же, как (22). В частности, если AH =0 , то условия (24) показывают, что
градиенты ( ) ( )10 ,..., +′′ kxfxf оказываются A -ортогональными (или сопря-
женными), т.е. при выборе ir в виде (23) (при условии AH =0 ) процесс (11)
является методом сопряженных градиентов.
Отметим еще следующее. Система векторов irr ,...,0 выбирается доста-
точно произвольно (при условии, что она линейно независима, а также ли-
нейно независима система векторов iee ,...,0 ). Поэтому можно полагать
kkk pr β= , 0≥k , 0≠kβ , где вектор 0p выбирается произвольно, а при
1≥k вектор kp удовлетворяет условиям (15). При этом условия (15), (16)
превращаются в условия A -ортогональности векторов ip .
0, =iki Appβ ,
0, ≠= kkkk cAppβ .
Коэффициент kα выбирается по формуле
( ) ( ) ( )
( ) ( )kkkk
kk
kk
kk
kkk
kkk
k xfpxfp
pxf
App
pxf
App
pxf
′−+′
′
−=
′
−=
′
−=
,
,
,
,
,
,
β
β
α .
Реализация процесса (11) таким способом ( kkk pr β= ) заведомо воз-
можна в случае, если матрица A невырожденная. Однако в случае, когда
A — вырожденная матрица, процесс (11) также может вырождаться. Это
происходит, если при некотором k оказывается 0, =kk App . Коэффици-
ент kα при этом определить невозможно.
Ситуация, когда процесс (11) вырождается, возможна только в случае,
если выбор векторов kr , ,...1,0=k связан с реализацией процесса (11), т.е.
зависит от вектора kp . Если же линейно независимая система векторов kr ,
10 −≤≤ tk , выбрана произвольно, то процесс (11) не вырождается. Ситуа-
ция, когда выполняются условия (15), (16), уже рассмотрена выше. Но мо-
жет оказаться, что в некоторой точке kx , 1−≤ tk , будет ( ) 0, =′ kk rxf . (С
учетом (18) это означает, что в точке kx реализуется минимум функции (1)
на подпространстве, образованном векторами krr ,...,0 .) В этом случае мож-
Точные методы минимизации квадратичных функций. Часть 1
Системні дослідження та інформаційні технології, 2007, № 4 91
но полагать коэффициент 0=kα , при этом kk xx =+1 . Вектор 1+kp опреде-
ляется условиями
kiep ikk ≤≤=++ 0,0,11α ,
( ) 11111 ,, +++++ ′−= kkkkk rxfepα .
Далее, в зависимости от значения ( ) ( ) 111 ,, +++ ′=′ kkkk rxfrxf (равна
ли эта величина нулю или нет) процесс (11) продолжается так, как описано
выше. По существу это означает, что процесс (11) может реализовывать
точку минимума функции (1) за число шагов, меньшее t .
В частности, если определить систему векторов 20 ,..., −trr таким обра-
зом, чтобы выполнялись условия
( ) 20,0,0 −≤≤=′ tirxf i ,
то можно полагать 0... 20 === −tαα , ( 0... 20 === −tpp ). В этом случае
110* −−+== ttt pxxx α .
Приведем еще одно свойство процессов (11).
Утверждение 4. Если
( ) ,0,
0
0 kixfHp
i
j
jiji ≤≤′= ∑
=
λ ,1 iiiii xxpr −== +α (25)
то
( ) 1,10,0, 01 ≥−≤≤=′ + kkieHxf ik . (26)
Действительно, в данном случае справедливо (23), а в силу (25)
( ) ( ) ( )iiiii xfxfxxAe ′−′=−= ++ 11 . С учетом этого справедливость (26) непо-
средственно вытекает из (24).
Как уже отмечалось выше, в случае, когда матрица A вырожденная,
соотношения (26) могут и не выполняться при некотором 1−≤ tk (процесс
(11) вырождается).
Наконец, отметим следующее.
Если определены векторы kp , λ≤≤ k0 , удовлетворяющие условиям
(15), (16), то это позволяет вычислить коэффициенты iβ в уравнении (8).
( )
λλ
λ
λβ ep
pxf
,
,0′
= ,
( ) 0,...,2,1,,,
,
1
0 −−=
⎥
⎥
⎦
⎤
⎢
⎢
⎣
⎡
−′= ∑
≤<
λλββ
λ
ipepxf
ep ji
ijji
ii
i .
Тем самым может быть определено решение по формуле (9). Опреде-
ление решения в виде (9) также можно трактовать как конечношаговый
процесс построения точек kkkk rxx β−=+1 , λ,...,1,0=k .
Ю.М. Данилин, И.А. Шубенкова
ISSN 1681–6048 System Research & Information Technologies, 2007, № 4 92
В заключение отметим, что выполнения условий (15), (16) можно до-
биться, используя различные процессы ортогонализации: собственно орто-
гонализацию векторов ie , A -ортогонализацию векторов ip при специаль-
ном выборе векторов ir , построение биортогональной системы векторов.
Разумеется, можно использовать и другие процессы ортогонализации, из-
вестные в линейной алгебре (например, [9]). Во второй части данной работы
будут подробно рассмотрены вопросы реализации различных способов
построения вектора kp .
ЛИТЕРАТУРА
1. Пшеничный Б.Н., Данилин Ю.М. Численные методы в экстремальных зада-
чах. — М.: Наука, 1975. — 320 с.
2. Полак Е. Численные методы оптимизации. — М.: Мир, 1974. — 384 с.
3. Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. — М.: Мир, 1985. —
510 с.
4. Данилин Ю.М. Методы сопряженных направлений для решения задач миними-
зации // Кибернетика. — 1971. — № 5. — С. 122–136.
5. Данилин Ю.М. Скорость сходимости методов сопряженных направлений //
Кибернетика. — 1977. — № 6. — С. 97–105.
6. Данилин Ю.М., Буланый А.П. Квазиньютоновские методы минимизации, осно-
ванные на построении сопряженных систем векторов // Журн. вычисл. ма-
тем. и мат. физики. — 1978. — № 4. — С. 877–885.
7. Данилин Ю.М. Методы сопряженных направлений, не требующие решения
одномерных задач минимизации // Докл. АН СССР. — 1974. — 218, №3. —
С. 513–516.
8. Данилин Ю.М. Об одном классе алгоритмов со сверхлинейной сходимостью //
Журн. вычисл. матем. и мат. физики. — 1974. — № 3. — С. 598–609.
9. Фаддеев Д.К., Фаддеева В.Н. Вычислительные методы линейной алгебры. —
М.: Наука, 1960. — 300 с.
Поступила 19.06.2007
|
| id | journaliasakpiua-article-127323 |
| institution | System research and information technologies |
| keywords_txt_mv | keywords |
| language | Russian |
| last_indexed | 2025-07-17T10:23:33Z |
| publishDate | 2018 |
| publisher | The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" |
| record_format | ojs |
| resource_txt_mv | journaliasakpiua/03/10a72835aa29a419eae1c3fe86d3c103.pdf |
| spelling | journaliasakpiua-article-1273232018-04-11T11:11:24Z Exact methods for minimization of square-law functions. Part 1 Точные методы минимизации квадратичных функций. Часть 1 Точні методи мінімізації квадратичних функцій. Часть 1 Danilin, Yu. Shubenkova, I. The unique approach to constructing various by character exact methods for minimization of square-law functions is studied. Possibility of application of these methods to the solution of nonlinear optimization problems and systems of linear equations is considered. Рассматривается единый подход к построению различных по характеру точных методов минимизации квадратичных функций. Описываются возможности применения этих методов к решению задач нелинейной оптимизации и систем линейных уравнений. Розглянуто єдиний підхід до побудови різних за характером точних методів мінімізації квадратичних функцій. Описано можливості застосування цих методів до розв’язування задач нелінійної оптимізації та систем лінійних рівнянь. The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" 2018-03-29 Article Article application/pdf https://journal.iasa.kpi.ua/article/view/127323 System research and information technologies; No. 4 (2007); 85-92 Системные исследования и информационные технологии; № 4 (2007); 85-92 Системні дослідження та інформаційні технології; № 4 (2007); 85-92 2308-8893 1681-6048 ru https://journal.iasa.kpi.ua/article/view/127323/122086 Copyright (c) 2021 System research and information technologies |
| spellingShingle | Danilin, Yu. Shubenkova, I. Точні методи мінімізації квадратичних функцій. Часть 1 |
| title | Точні методи мінімізації квадратичних функцій. Часть 1 |
| title_alt | Exact methods for minimization of square-law functions. Part 1 Точные методы минимизации квадратичных функций. Часть 1 |
| title_full | Точні методи мінімізації квадратичних функцій. Часть 1 |
| title_fullStr | Точні методи мінімізації квадратичних функцій. Часть 1 |
| title_full_unstemmed | Точні методи мінімізації квадратичних функцій. Часть 1 |
| title_short | Точні методи мінімізації квадратичних функцій. Часть 1 |
| title_sort | точні методи мінімізації квадратичних функцій. часть 1 |
| url | https://journal.iasa.kpi.ua/article/view/127323 |
| work_keys_str_mv | AT danilinyu exactmethodsforminimizationofsquarelawfunctionspart1 AT shubenkovai exactmethodsforminimizationofsquarelawfunctionspart1 AT danilinyu točnyemetodyminimizaciikvadratičnyhfunkcijčastʹ1 AT shubenkovai točnyemetodyminimizaciikvadratičnyhfunkcijčastʹ1 AT danilinyu točnímetodimínímízacííkvadratičnihfunkcíjčastʹ1 AT shubenkovai točnímetodimínímízacííkvadratičnihfunkcíjčastʹ1 |