Метод минимизации с преобразованием пространства на основе квадратичной аппроксимации функции

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

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2015
Hauptverfasser:	Кузьменко, В.Н., Ненахов, Э.И.
Format:	Artikel
Sprache:	Russian
Veröffentlicht:	Інститут кібернетики ім. В.М. Глушкова НАН України 2015
Schriftenreihe:	Теорія оптимальних рішень
Online Zugang:	https://nasplib.isofts.kiev.ua/handle/123456789/112396
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:	Метод минимизации с преобразованием пространства на основе квадратичной аппроксимации функции / В.Н. Кузьменко, Э.И. Ненахов // Теорія оптимальних рішень: Зб. наук. пр. — 2015. — № 2015. — № 2015. — № 2015. — С. 46-51. — Бібліогр.: 5 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-112396
record_format	dspace
spelling	nasplib_isofts_kiev_ua-123456789-1123962025-02-09T14:27:35Z Метод минимизации с преобразованием пространства на основе квадратичной аппроксимации функции Метод мінімізації з перетворенням простору, що грунтується на квадратичній апроксімації функції The minimization method with space transformation based on quadratic approximation of function Кузьменко, В.Н. Ненахов, Э.И. Описываются метод минимизации гладких функций, основанный на локально-квадратичной оценке функции по разности ее градиентов. В случае квадратичной функции метод дает решение за конечное число шагов. Розглядається метод мінімізації гладких функцій, який грунтується на локально-квадратичній оцінці функції за різницею її градієнтів. У випадку квадратичної функції метод дає розв’язок за скінчену кількість кроків. A method for smooth function minimization based on local quadratic estimation of the function using difference of its gradients is considered. In case of quadratic function the method gives solution after finite number of steps. 2015 Article Метод минимизации с преобразованием пространства на основе квадратичной аппроксимации функции / В.Н. Кузьменко, Э.И. Ненахов // Теорія оптимальних рішень: Зб. наук. пр. — 2015. — № 2015. — № 2015. — № 2015. — С. 46-51. — Бібліогр.: 5 назв. — рос. XXXX-0013 https://nasplib.isofts.kiev.ua/handle/123456789/112396 519.85 ru Теорія оптимальних рішень application/pdf Інститут кібернетики ім. В.М. Глушкова НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
description	Описываются метод минимизации гладких функций, основанный на локально-квадратичной оценке функции по разности ее градиентов. В случае квадратичной функции метод дает решение за конечное число шагов.
format	Article
author	Кузьменко, В.Н. Ненахов, Э.И.
spellingShingle	Кузьменко, В.Н. Ненахов, Э.И. Метод минимизации с преобразованием пространства на основе квадратичной аппроксимации функции Теорія оптимальних рішень
author_facet	Кузьменко, В.Н. Ненахов, Э.И.
author_sort	Кузьменко, В.Н.
title	Метод минимизации с преобразованием пространства на основе квадратичной аппроксимации функции
title_short	Метод минимизации с преобразованием пространства на основе квадратичной аппроксимации функции
title_full	Метод минимизации с преобразованием пространства на основе квадратичной аппроксимации функции
title_fullStr	Метод минимизации с преобразованием пространства на основе квадратичной аппроксимации функции
title_full_unstemmed	Метод минимизации с преобразованием пространства на основе квадратичной аппроксимации функции
title_sort	метод минимизации с преобразованием пространства на основе квадратичной аппроксимации функции
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate	2015
url	https://nasplib.isofts.kiev.ua/handle/123456789/112396
citation_txt	Метод минимизации с преобразованием пространства на основе квадратичной аппроксимации функции / В.Н. Кузьменко, Э.И. Ненахов // Теорія оптимальних рішень: Зб. наук. пр. — 2015. — № 2015. — № 2015. — № 2015. — С. 46-51. — Бібліогр.: 5 назв. — рос.
series	Теорія оптимальних рішень
work_keys_str_mv	AT kuzʹmenkovn metodminimizaciispreobrazovaniemprostranstvanaosnovekvadratičnojapproksimaciifunkcii AT nenahovéi metodminimizaciispreobrazovaniemprostranstvanaosnovekvadratičnojapproksimaciifunkcii AT kuzʹmenkovn metodmínímízacíízperetvorennâmprostoruŝogruntuêtʹsânakvadratičníjaproksímacíífunkcíí AT nenahovéi metodmínímízacíízperetvorennâmprostoruŝogruntuêtʹsânakvadratičníjaproksímacíífunkcíí AT kuzʹmenkovn theminimizationmethodwithspacetransformationbasedonquadraticapproximationoffunction AT nenahovéi theminimizationmethodwithspacetransformationbasedonquadraticapproximationoffunction
first_indexed	2025-11-26T20:18:56Z
last_indexed	2025-11-26T20:18:56Z
_version_	1849885552754556928
fulltext	46 Теорія оптимальних рішень. 2015 ТЕОРІЯ ОПТИМАЛЬНИХ РІШЕНЬ Описываются метод минимиза- ции гладких функций, основанный на локально-квадратичной оценке функции по разности ее градиен- тов. В случае квадратичной функ- ции метод дает решение за ко- нечное число шагов.  В.Н. Кузьменко, Э.И. Ненахов, 2015 УДК 519.85 В.Н. КУЗЬМЕНКО, Э.И. НЕНАХОВ МЕТОД МИНИМИЗАЦИИ С ПРЕОБРАЗОВАНИЕМ ПРОСТРАНСТВА НА ОСНОВЕ КВАДРАТИЧНОЙ АППРОКСИМАЦИИ ФУНКЦИИ Введение. Существуют различные подходы в использовании методов, предназначенных для решения квадратичных задач, при мини- мизации не квадратичных, но гладких функ- ций. Среди таких подходов отметим методы, использующие квадратичную регуляризацию оптимизационной задачи [1, 2], методы по- следовательного квадратичного программи- рования [3], методы, основанные на квадра- тичном приближении значений функции [4], методы, использующие значения вторых производных [5]. В настоящей работе рассматривается ко- нечный метод минизации квадратичной функции и применение его процедур для ми- нимизации гладких функций. Метод не вы- числяет и не использует явно вторые произ- водные, но делает их оценку, которая для квадратичной функции является точной. При решении произвольной гладкой задачи метод после ряда шагов обновляет аппроксимаци- онную квадратичную матрицу, что позволяет изменять квадратичную аппроксимацию в зависимости от накопленной информации. Рассмотрим квадратичную задачу  1( ) , min, 2 f x x Ax bx   (1) где A – симметричная положительно опре- деленная невырожденная матрица; b – век- тор-строка;  , – знак скалярного произве- дения; Xx . Рассматриваем также невыро- жденное преобразование пространства xDx  . Говоря о преобразовании простран- ства будем иметь ввиду соответствующую матрицу и наоборот. МЕТОД МИНИМИЗАЦИИ С ПРЕОБРАЗОВАНИЕМ ПРОСТРАНСТВА ... Теорія оптимальних рішень. 2015 47 В пространстве переменных Xx  задача (1) имеет вид  1( ) , min, 2 x x D ADx bDx       (2) где знаком обозначено траспонирование. Матрицу квадратичной функции в пространстве X  обозначим .A D AD  Для произвольной точки 0x и произвольного вектора v значение    Avvxfvt ,)(, 0 задает сдвиг из точки 0x , при котором достигается минимум (1) функции )(xf при перемещении вдоль вектора v . Значение t сохраняется при переходе в пространство .X  Заметим также, что разность Avxfvxfw  )()( 00 не зависит от точки 0x . Построим преобразование D таким образом, чтобы выполнялись такие свойства: а) вектор vDv 1 – собственный для матрицы ,A т. е. ;vA v v    б) , v vi iA е е  где vi е орт с единицей по координате vi . То есть матрица A имеет единичный столбец и строку vi ; в) 1.v  Преобразование D построим как композицию трех преобразований ,D HBZ последовательно обеспечивающих выполнение свойств а), б) и в). Преобразование .H Рассмотрим такое преобразование и его свойства  ** vvIwwIH  . Символами vw, будем обозначать нормированные векторы. Скалярное произведение векторов ),( ba будем записывать также, как * .a b 1. Обратное преобразование 1H определяется следующим образом. Преобразование H можно представить в виде  ** ),( vvwwwIH  . Общая форма такого преобразования – это .B I a b   Обратное к нему )1/( 1 babaIB  существует, если 1 ba . Следовательно 1H    * * 2 ( , ) ( , ) w w w v v I w v    и 1H существует, если 0),( vw . 2. Транспонированное преобразование таково:   ** ),( wvvwwIH  . 3. Для преобразования H выполняется: vHv  и, следовательно, vvH 1 . То есть, вектор v – собственный для матриц H и 1H с собственным значением 1. В.Н. КУЗЬМЕНКО, Э.И. НЕНАХОВ 48 Теорія оптимальних рішень. 2015 4. Далее следует, что vH vv vw vvwwHAvHvHAHH 11 ),( ),( ),()(   . То есть вектор vHv 1 в преобразованом пространстве будет собственным для матрицы AHHA  с собственным значением ( , ) / ( , ).v w v v v  5. Если 0( ),v f x  то 1 vt   – шаг из точки 0x до минимума в направле- нии .v Заметим также, что .vH w v   6. Вектор w – собственный для матриц H и 1H соответственно с соб- ственными числами 2( , )H w w v  и 1 21 ( , ) .H w w v    7. Если 0,v  то 0),(),(),(  Avvwvvw в силу положительной определен- ности матрицы A . Следовательно, матрица 1H существует и существуют и не равны нулю вычисленные выше собственные числа. Преобразование .B В качестве преобразования B возьмем преобразование Хаусхолдера (преобразование отражения). Это преобразование «зеркально» от- ражает пространство относительно некоторой гиперплоскости, которая задается вектором нормали  и проходит через начало координат. Преобразование за- дается матрицей: 2 .B I   В нашем случае для того, чтобы сделать столбец и строку vi новой матрицы, содержащими один ненулевой элемент vi (т. е. диа- гональный элемент), «отразим» вектор v на орт , vi е и наоборот. В этом случае , vi e v  а B имеет вид * ( )( ) . 1 v v v i i i e v e v B I e v      К общим свойствам преобразования Хаусхолдера относятся: а) * ;B B * ;B B I ;B  ,Bv v если ( , ) 0;v   det( ) 1.B   Преобразование .Z Смысл преобразования Z заключается в том, чтобы сделать собственное число v равным 1. Выше было показано, что vA v v    после преобразования ,H где ( , ) / ( , ).v w v v v  Поскольку вектор v теперь «отражен» в единичный орт , vi е то для получения единичного собственного зна- чения в качестве матрицы Z достаточно взять диагональную матрицу со всеми элементами 1,iiz  кроме элемента  1 , . v vi i vz v w v   В результате непосредствено проверяем, что выполняются свойства а), б), в) для матрицы ,A а именно: а) * 1 * * * 1 1( ) ( )( ) ( ) ;A v D AD D v Z B H AHBZ HBZ v HBZ v v        б) * * ( ) ; v v vi i iA e Z B H AHBZ e e   в) из а) следует, что 1.v  МЕТОД МИНИМИЗАЦИИ С ПРЕОБРАЗОВАНИЕМ ПРОСТРАНСТВА ... Теорія оптимальних рішень. 2015 49 Дополнительно отметим, что вектор v в преобразованном пространстве X  содержит только одну ненулевую компоненту vi со значением ( , ) ( , ).w v v Av Рассмотрим следующий алгоритм решения квадратичной задачи (1). Начальное состояние: задана начальная точка 1x в исходном пространстве .X Положим 1,k  1 ,A A 0 ,D I 1 .X X 1. В начале шага k имеем точку kk Xx  , квадратичную матрицу kA и матрицу 1kD текущего преобразования пространства kX в пространство 1kX . 2. Выбираем направление движения )( k k k xgv  , где )( k k xg градиент квадратичной функции k в пространстве kX , и шаг kt , минимизирующий функцию вдоль этого направления. Вычисляем следующую точку 1 .k k k kx x t v    3. Вычисляем вектор ( ) ( ) ,k k k k k k k kw g x v g x A v    матрицу kD следу- ющего преобразования пространств 1kX в kX : kkkk ZBHD  , где  * kkkkk vvIwwIH  , 2 ,k k kB I    ,k k ke v   неединичный элемент в kZ равен ),(/ kkkkk vwvz  и квадратичную матрицу в преобразованном про- странстве kkkk DADA 1  . 4. Вычисляем текущую точку 1 1 1     kkk xDx в пространстве 1kX . 5. Если решение не найдено, то полагаем 1 kk и переходим к шагу 1. Свойства алгоритма. 1) kkk vvA 1 , где )(11 k k kkkk xgDvDv   , в силу построения kD ; 2) 1 kk Xv имеет одну не нулевую компоненту ;k 3) kkk vvD   1 1 , так как выполняются свойства 1), 2) и 0),( 1  kk vv , где )( 1 1 1     k k k xgv , а точка 1kx получена путем минимизации по направле- нию kv . То есть преобразование 1 1  kD не изменяет вектор ;kv 4) kkk vvA 2 , так как выполняются свойства 1), 2), 3); 5) на шаге 1k для всех , 1, ...,iv i k  направлений движения предыдущих шагов, пересчитанных в пространство 1,kX  выполняется: a) iik vvA 1 , б) 0),(  ji vv , kjiij ,...,1,,  , в) iv имеет одну не нулевую компоненту ;i 6) матрица 1kA имеет k первых единичных строк и столбцов. Матрица 1nA становится единичной; 7) алгоритм находит минимум функции не более, чем за n шагов, где n – размерность пространства ;X В.Н. КУЗЬМЕНКО, Э.И. НЕНАХОВ 50 Теорія оптимальних рішень. 2015 8) для работы алгоритма нет необходимости знать матрицу и вектор квадра- тичной фунции в пространсте kX . Достаточно уметь вычислять градиент )(xf в исходном пространстве X и знать полное преобразование kP пространства kX в исходное X : 1 2 ... .k kP D D D Свойство 5) доказывается по индукции. Действительно, для 2k это свой- ства 1) – 4). Имеем 0)),(( 1 1   kk k vxg в силу того, что 1kx минимум по направлению kv ; kkk k kkkkkkkkkkk k vtxgvtbxAbvtxAxg     )()()()( 1 11111 1 . Следовательно 0),)(( 1 1    kkkk k vvtxg , так как kx минимум по направле- нию 1kv и 1( , ) 0.k kv v     Далее )(1 k k xg  выражается через )( 1 1   k k xg и 1,  kk vv и так далее. Получаем, что 0),( 1  ik vv для всех 1, ..., .i k Отсюда по аналогии с 3), 4) получаем, что iik vvA 2 , для 1, ..., .i k Для 1kv выполняется 1( , ) 0,k iv v    1, ...,i k в силу 2). Свойство 8) приведенного алгоритма позволяет использовать его для мини- мизации не только квадратичных функций, но и гладких выпуклых функций. Пусть определена выпуклая гладкая функция )(xf в пространстве nRX  такая, что )(xf при x . Рассмотрим следующий алгоритм нахождения минимума )(xf . Начальное состояние: задана начальная точка 0x . Положим 0,k  0 .P I 1. В начале шага k имеем текущую точку kx в исходном пространстве ,X матрицу текущего преобразования пространства kP : .kx P x Положим ,kP I если k кратно n . 2. Вычисляем функцию )( kxf и градиент ( ).kf x Градиент в преобразо- ванном пространстве X  вычисляется как * ( ).k kP f x Преобразование этого век- тора обратно в пространство X дает вектор * ( ),k k k ks P P f x  вдоль которого будем искать минимум функции )(f из точки kx на текущей итерации. 3. Возьмем некий шаг длиной 0k  в направлении противоположном гра- диенту )(* kk xfP  в пространстве X  : * ( ),k k k kv P f x   рассмотрим также такую разность градиентов:  )()(* kkkkkk xfsxfPw   в .X  4. Изменим преобразование пространства следующим образом: 1kP   ,k k k kP H B Z где kkk ZBH ,, описаны выше. 5. Найдем  argmin ( )k k kf x s     и положим 1 .k k k kx x s   6. Положим 1.k k  Если не выполняются критерий останова ( ) ,k gf x   то перейдем на шаг 1. МЕТОД МИНИМИЗАЦИИ С ПРЕОБРАЗОВАНИЕМ ПРОСТРАНСТВА ... Теорія оптимальних рішень. 2015 51 При вычислительной реализации алгоритма необходимо уделять внимание численной устойчивости. Поэтому на некоторых итерация преобразования kH и kB могут не выполняться. А именно, kH не выполняется, если  , ,k kw v   kB не выполняется, если  1 , , ki ke v   что обусловлено сохранением устойчи- вости обратных преобразований. Второй необходимый момент – это обновление матрицы ,kP что связано со «сбросом» накопленных ошибок вычислений и(или) необходимостью изменения квадратичной аппроксимации. В.М. Кузьменко, Е.І. Ненахов МЕТОД МІНІМІЗАЦІЇ З ПЕРЕТВОРЕННЯМ ПРОСТОРУ, ЩО ГРУНТУЄТЬСЯ НА КВАДРАТИЧНІЙ АПРОКСІМАЦІЇ ФУНКЦІЇ Розглядається метод мінімізації гладких функцій, який грунтується на локально-квадратичній оцінці функції за різницею її градієнтів. У випадку квадратичної функції метод дає розв’язок за скінчену кількість кроків. V.M. Kuzmenko, E.I. Nenakhov THE MINIMIZATION METHOD WITH SPACE TRANSFORMATION BASED ON QUADRATIC APPROXIMATION OF FUNCTION A method for smooth function minimization based on local quadratic estimation of the function us- ing difference of its gradients is considered. In case of quadratic function the method gives solution after finite number of steps. 1. Пшеничный Б.Н., Ненахов Э.И., Кузьменко В.Н. Модифицированный метод отсечения для минимизации выпуклой функции // Кибернетика и системный анализ. – 1997. – № 6.– С. 142 – 149. 2. Пшеничный Б.Н., Ненахов Э.И., Кузьменко В.Н. Комбинированный метод решения общей задачи выпуклого программирования // Там же. – 1998. – № 4. – С. 121 – 134. 3. Gill P.E., Murray W., Saunders M.A. SNOPT: An SQP algorithm for large-scale constrained optimization // SIAM Journal on Optimization. – 2002. – Vol. 12. – P. 979 – 1006. 4. Бойко В.В., Кузьменко В.Н. Использование квадратичного приближения целевой функции в PNK-методе // Теорія оптимальних рішень. – К.: Ін-т кібернетики імені В.М. Глушкова НАН України, 2010. – С. 120 – 125. 5. Fletcher R. Practical Methods of Optimization // J. Wiley and Sons, Chichester, England. – 1987. – 276 p. Получено 14.04.2015

Метод минимизации с преобразованием пространства на основе квадратичной аппроксимации функции

Institution

Ähnliche Einträge