Проекція градієнта: спрощення області мінімізації афінним перетворенням

One of the classical problems of optimization theory in a finite-dimensional space is to find a minimum of a function on a nonempty set. Usually, finding the precise solution to this task analytically requires a lot of computational resources or is even impossible at all. So, approximate methods are...

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2024
1. Verfasser:	Spectorsky, Igor
Format:	Artikel
Sprache:	Englisch
Veröffentlicht:	The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" 2024
Schlagworte:	проекція градієнта мінімізація афінне перетворення
Online Zugang:	https://journal.iasa.kpi.ua/article/view/286064
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	System research and information technologies
Завантажити файл:

Institution

System research and information technologies

_version_	1866302930455363584
author	Spectorsky, Igor
author_facet	Spectorsky, Igor
author_sort	Spectorsky, Igor
baseUrl_str	http://journal.iasa.kpi.ua/oai
collection	OJS
datestamp_date	2024-08-11T01:12:49Z
description	One of the classical problems of optimization theory in a finite-dimensional space is to find a minimum of a function on a nonempty set. Usually, finding the precise solution to this task analytically requires a lot of computational resources or is even impossible at all. So, approximate methods are used most often in practical cases. One of the simplest and the most well-known among such approximate methods for unconditional optimization is the method of gradient descent; its generalization for conditional optimization was found in 1964, the method of projected gradient. For some simple sets (line segment, parallelepiped, ball), the projection of the point on the set can be easily found by an explicit formula. However, for more complicated sets (e.g., an ellipse), projecting becomes a separate task. Nevertheless, sometimes computing projection can be simplified by affine transform; e.g., an ellipse can be transformed into a ball by affine (moreover, by linear) transformation. The paper aims to simplify the problem of minimizing function on the set by changing the condition set by affine transform F(x)= Ax+b, where A is a non-degenerated square matrix, and b is a fixed vector of proper dimension.
doi_str_mv	10.20535/SRIT.2308-8893.2024.2.09
first_indexed	2025-07-17T10:28:20Z
format	Article
fulltext	 І.Я. Спекторський, 2024 Системні дослідження та інформаційні технології, 2024, № 2 117 UDC 519.6:519.8 DOI: 10.20535/SRIT.2308-8893.2024.2.09 ПРОЕКЦІЯ ГРАДІЄНТА: СПРОЩЕННЯ ОБЛАСТІ МІНІМІЗАЦІЇ АФІННИМ ПЕРЕТВОРЕННЯМ І.Я. СПЕКТОРСЬКИЙ Анотація. Розглянуто класичну задачу оптимізації у скінченновимірному про- сторі, тобто знаходження мінімуму функції на непорожній множині. Пошук точного розв’язку цієї задачі аналітичними методами потребує множинних об- числювальних ресурсів або взагалі неможливий. Для реальних задач частіше застосовують методи пошуку наближеного розв’язку, серед яких одним з най- простіших і найвідоміших для задач безумовної оптимізації є метод градієнт- ного спуску. Узагальненням методу градієнтного спуску на випадок умовної оптимізації є запропонований у 1964 р. метод проекції градієнта. Для деяких типів множини (відрізок, паралелепіпед, куля) проекцію точки на множину можна знайти простими явними формулами, проте для складніших (напр., еліпс) проектування стає окремою задачею мінімізації. Однак у деяких випад- ках обчислення проекції не можна спростити афінним перетворенням — напр., еліпс афінним (і навіть лінійним) перетворенням можна звести до кулі. Спро- щено задачу мінімізації функції на множині застосуванням афінного перетво- рення F(x) = Ax+b, де A — невироджена квадратна матриця, b — фіксований вектор відповідної розмірності. Ключові слова: проекція градієнта, мінімізація, афінне перетворення. ВСТУП Класичною задачею оптимізації у скінченновимірному просторі є знахо- дження мінімуму функції  nf : на непорожній множині nD  (тут і надалі символ « » позначає нестроге вкладення, тобто можливий випадок nD  — задача безумовної оптимізації). Як правило, пошук точного розв’язку цієї задачі аналітичними методами потребує надто багато обчис- лювальних ресурсів або взагалі неможливий. Тому для реальних задач най- частіше застосовують методи пошуку наближеного розв’язку, серед яких одним з найпростіших і найвідоміших для задач безумовної оптимізації є метод градієнтного спуску (див., напр., [1–6]). Узагальненням методу граді- єнтного спуску на випадок умовної оптимізації ( nD  ) є запропонований у 1964 р. метод проекції градієнта (див. [7]). Для деяких типів множини D (відрізок, паралелепіпед, куля) проекцію точки nx  на D можна знайти простими явними формулами, проте для дещо складніших областей (напр., якщо 2D — еліпс) проектування стає окремою задачею мінімізації. Од- нак у деяких випадках обчислення проекції на D можна спростити афінним перетворенням — напр., еліпс афінним (і навіть лінійним) перетворенням можна звести до кулі. Мета роботи — звести задачу мінімізації функції  nf : на множині nD  до мінімізації функції ))~(()~( ~ 1 xFfxf  на множині І.Я. Спекторський ISSN 1681–6048 System Research & Information Technologies, 2024, № 2 118   )(: ~ DFDxbAxD  , де bAxxF )( , A — невироджена матриця розмірності nn , nb  — фіксований вектор. ОПУКЛІ МНОЖИНИ ТА ФУНКЦІЇ Означення 1. Множину nD  називають опуклою, якщо Dyx  )1( для будь-яких ]1,0[,,  DyDx . Інакше кажучи, D є опуклою, якщо ра- зом з точками DyDx  , містить відрізок ],[ yx : Dyxyx Dy Dx       ]}1,0[:)1({],[ , . Приклад 1. На площині (простір 2 ) будь-який круг є опуклою фігу- рою (множиною), будь-яке коло — ні (рис. 1). Інші приклади опуклих та не- опуклих фігур зображено на рис. 2. Зауваження 1. Надалі вважатимемо, що будь-який еліпс та будь-який багатокутник містять внутрішню ділянку, яку вони обмежують. Таким чи- ном, еліпс та трикутник завжди є опуклими фігурами, однак чотирикутник може не бути опуклим (рис. 3). Означення 2. Функцію  nf : називають опуклою, якщо для будь-яких ]1,0[,,  DyDx справджується нерівність )()1()())1(( yfxfyxf  . (1) Означення 3. Функцію  nf : називають строго опуклою, якщо для будь-яких )1,0(,,  DyDx , таких, що yx  , справджується нерівність )()1()())1(( yfxfyxf  . Круг — опукла фігура Коло — неопукла фігура Рис. 1. Круг і коло — властивість опуклості Опуклі фігури Неопуклі фігури Рис. 2. Опуклі та неопуклі фігури Опуклі фігури Неопуклі фігури Рис. 3. Еліпс та багатокутники — властивість опуклості Проекція градієнта: спрощення області мінімізації афінним перетворенням Системні дослідження та інформаційні технології, 2024, № 2 119 Приклад 2. 1. Одновимірна ( 1n ) лінійна функція cbxxf )(1 за будь-яких фіксованих констант   cb , є опуклою, але не строго опук- лою, оскільки для будь-якої ]1,0[ нестрога нерівність (1) виконується, проте перетворюється в рівність:  cyxbyxf ))1(())1((1 )()1()())(1()( 11 yfxfcbycbx  . (2) 2. Одновимірна квадратична функція 2 2 )( axxf  ( a — фіксована константа) є опуклою тоді і тільки тоді, коли 0a . Дійсно, для будь-якої ]1,0[ маємо: .))(1()()1()( )1(2)1()1()1( )1(2)1())1(())1(( 2 22 2222 22222 2 yxayfxf xyayaxayaxa xyayaxayxayxf    (3) Очевидно, у випадку 0a функція 2 2 )( axxf  є строго опуклою. Зазначимо, що отриманий результат з урахуванням рівностей (2) та (3) легко поширити на загальну одновимірну квадратичну функцію cbxaxxf  2 3 )( ; функція опукла, якщо 0a (зокрема, строго опукла, якщо 0a ); константи   cb , на опуклість (строгу опуклість) функції cbxax 2 не впливають. Із означень 1 та 2 негайно випливає простий факт, що пов’язує обидва означення: функція  nf : опукла тоді і тільки тоді, коли її надграфік })(:),{(Epi yxfyxf n   є опуклою множиною в просторі   nn 1 . На рис. 4 схематично показано надграфіки функцій cbxxf )(1 та cbxaxxf  2 3 )( . Означення 4. Функцію  nf : називають сильно опуклою з пара- метром 0 , якщо для будь-яких ]1,0[,,  DyDx справджується нерівність 2 2 1 \|\|\|\|)1()()1()())1(( yxyfxfyxf  . cbx  c ax2+bx+c, a>0 ax2+bx+c, a<0 Рис.4. Надграфіки лінійної та квадратичної функцій І.Я. Спекторський ISSN 1681–6048 System Research & Information Technologies, 2024, № 2 120 Приклад 3. Квадрат евклідової норми 2\|\|\|\| x як функція   n:\|\|\|\| 2 є сильно опуклою з параметром 2 . Дійсно, для будь-якої ]1,0[ аналогі- чно (3) отримуємо:  ))1((,)1((\|\|)1(\|\| 2 yxyxyx  ),)(1(2\|\|\|\|)1(\|\|\|\| 2222 yxyx .\|\|\|\|)1(\|\|\|\|)1(\|\|\|\| 222 yxyx  Зауваження 2. Деякі автори (напр., [4, 5, 8]), визначаючи сильну опук- лість функції, випускають коефіцієнт 2 1 у доданку перед параметром опук- лості, що зменшує параметр опуклості вдвічі. Так, згідно з таким визначен- ням, функція 2\|\|\|\| x є сильно опуклою з параметром 1 . Відомі критерії опуклості для гладких функцій. Так, для двічі непере- рвно диференційовної функції  nf : справджуються логічні еквівале- нтності (див., напр., [2, 4–6, 8]):  Функція f опукла тоді й тільки тоді, коли 0),(  hhf для будь- якого nh  (гесіан f  є невід’ємно визначеною матрицею).  Функція f сильно опукла з параметром 0 тоді і тільки тоді, ко- ли 2\|\|\|\|),( hhhf  для будь-якого nh  (матриця nIf  є невід’ємно визначеною матрицею). Для строго опуклих функцій аналогічна еквівалентність неправильна, проте справджується наслідок: для строгої опуклості функції f достатньо, щоб 0),(  hhf для будь-якого ненульового nh  (гесіан f  є додатно визначеною матрицею). Приклад 4. Одновимірна функція 4)( xxf  опукла, і навіть строго опукла. Дійсно, враховуючи строгу (навіть сильну) опуклість функції 2)( xxg  (див. приклад 3) та строгу монотонність 2)( xxg  на ),0[  , отримуємо: )()1()()1()1( ))1(()))1((())1(())(()( 444242 222224 yfxfyxyx yxyxyxxggxf   для будь-якої )1,0( . Проте функція 4)( xxf  не сильно опукла, оскільки для будь-якої константи 0 нерівність  212)( xxf не справджується для 12 \|\| x . Сформулюємо у вигляді лем три відомі (див., напр., [2, 4, 5, 8]) власти- вості щодо мінімізації опуклої функції на опуклій множині. Лема 1. Нехай nD  — опукла множина, .  nf : — опукла фу- нкція, Dx * — локальний мінімум f на D , тобто існує таке 0 , що )()( * xfxf  для всіх Dx , для яких  xx . Тоді Dx  — глоба- льний мінімум f на D , тобто )()( * xfxf  для всіх Dx . Проекція градієнта: спрощення області мінімізації афінним перетворенням Системні дослідження та інформаційні технології, 2024, № 2 121 Доведення. Нехай Dx * — локальний мінімум f на D , 0 — та- ке число, що )()( * xfxf  для всіх Dx , для яких  xx . Зафіксуємо довільне Da . Тоді для ),(min 1 1 2 ax  маємо:  ))1(( xxa  )( xaxa , звідки, з урахуванням опуклості множини D та функції f , )()1()())1(()( * xfafxafxf  . Отже, )()1()()( xfafxf  , звідки )()( * afxf  і, оскільки 0 , )()( * afxf  . Таким чином, ураховуючи довільність вибору Da , точка Dx * дійсно є глобальним мінімумом функції f на D .□ Лема 2. Нехай nD  — опукла множина, .  nf : — строго опу- кла функція. Тоді f досягає глобального мінімуму на D не більш ніж в од- ній точці. Доведення. Припустимо, що f досягає глобального мінімуму y на D принаймні у двох різних точках Dm 1 , Dm 2 , тобто )( 1mf 2 )( ymf  , та 21 mm  . Тоді, враховуючи опуклість D та строгу опук- лість f , отримуємо, що Dmm  2 21 та * 212 1 2 ))()(()( 21 ymfmff mm  , що суперечить глобальності мінімуму * 21 )()( ymfmf  на множині D .□ Лема 3. Нехай nD  — опукла множина, .  nf : — сильно опукла функція. Тоді f досягає глобального мінімуму на D у точності в одній точці. Доведення (див., напр., [4, 5, 8]) спирається на обґрунтуванні обмеженості знизу множин Лебега  vxfDxDv  )(: та неперервності f на n . Детальніше про властивості опуклих множин і функцій див., [2, 4–6, 8]. АФІННЕ ПЕРЕТВОРЕННЯ ОПУКЛИХ МНОЖИН ТА АРГУМЕНТІВ ОПУКЛИХ ФУНКЦІЙ Уведемо до розгляду афінне перетворення nnF  : , тобто відображення bAxxF )( , де A — фіксована невироджена матриця розмірності nn , nb  — фіксований вектор. Зазначимо, що завдяки невиродженості A іс- нує обернене (також афінне) перетворення bAxAxF 111 )(   . Лема 4. Нехай nD  — непорожня опукла множина. Тоді опуклою є також множина   )(: ~ DFDxbAxD  . Доведення. Нехай DyDx ~~, ~~  . За визначенням множини D ~ , маємо еле- менти DyDx  , , такі, що bAyybAxx  ~ ,~ , звідки   bAxAx 11~ ,D DbAyAy   11~ . Тоді, зафіксувавши довільну ]1,0[ , отримуємо:  ))(1()(~)1(~ bAybAxyx DyxFbyxA ~ ))1(())1((  , І.Я. Спекторський ISSN 1681–6048 System Research & Information Technologies, 2024, № 2 122 оскільки Dyx  )1( завдяки опуклості D . Отже, Dyx ~~)1(~  , що доводить опуклість множини D ~ . Приклад 5. Розглянемо в 2 множину, обмежену прямокутником (сторони повернуті відносно координатних осей):                   103x42 543x2 : 21 21 2 1 x x x x D . Очевидно, область D можна отримати афінним (навіть лінійним) перетво- ренням із прямокутника D ~ , сторони якого паралельні координатним осям:                                   2 1 2 1 21 21 6.08.0 8.06.0 5 34 43 34 43 x x x x xx xx . Таким чином, афінне перетворення                                2 1 2 1 2 1 6.08.0 8.06.0 ~ ~ x x x x F x x (у даному випадку — пово- рот) переводить повернутий прямокутник                   103x42 543x2 : 21 21 2 1 x x x x D у прямокутник )( 2~0.4 1~0.4 :~ ~ 10~52 5~52 :~ ~~ 2 1 2 1 2 1 2 1 DF x x x x x x x x D                                      , сторони якого паралельні координатним осям (рис. 5). Приклад 6. Розглянемо в 2 множину, обмежену кривою другого порядку:               1)10()5(24)10(41)5(34 : 21 2 2 2 1 2 1 x xxx x x D                                            1 10 5 ,10 5 4112 1234 : 2 1 2 1 2 1 x x x x x x . Процедурою діагоналізації отримуємо:                          6.08.0 8.06.0 250 050 6.08.0 8.06.0 4112 1234 . 1 2 1 -2 -1 0 1x 2x 2 D 1 ~x 2 1 2 ~x 0 D ~ 1 1 Рис. 5. Область                   103x42 543x2 : 21 21 2 1 x x x x D — повернутий прямокутник, область                   2~0.4 1~0.4 :~ ~~ 2 1 2 1 x x x x D — прямокутник, сторони якого паралельні координатним осям Проекція градієнта: спрощення області мінімізації афінним перетворенням Системні дослідження та інформаційні технології, 2024, № 2 123 Оскільки матриця       4112 1234 , як і матриця       250 050 , є додатно визначеною, область D є повернутим та зсунутим еліпсом і може бути отримана афінним перетворенням з одиничного круга              1~~ :~ ~~ 2 2 2 1 2 1 xx x x D , рис. 6. Еліптичну криву 1)10()5(24)10(41)5(34 21 2 2 2 1  x xxx , або, у записі через квадратичну форму, 1 10 5 ,10 5 4112 1234 2 1 2 1                             x x x x , можна отримати з одиничного кола 1 2 2 2 1  xx послідовно зсувом, повертанням та розтягненням:                             1 10 5 ,10 5 4112 1234 2 1 2 1 x x x x                                           1 10 5 ,10 5 6.08.0 8.06.0 250 050 6.08.0 8.06.0 2 1 2 1 x x x x                                          1 10 5 6.08.0 8.06.0 ,10 5 6.08.0 8.06.0 250 050 2 1 2 1 x x x x                                                      1 10 5 6.08.0 8.06.0 ,10 5 6.08.0 8.06.0 50 025 50 025 2 1 2 1 x x x x 1 10 5 6.08.0 8.06.0 50 025 ,10 5 6.08.0 8.06.0 50 025 2 1 2 1                                                      x x x x . Отже, афінне перетворення                                                                50 225 34 2423 10 5 6.08.0 8.06.0 50 025 ~ ~ 2 1 2 1 2 1 2 1 x x x x x x F x x -10.0 -10.2 5.0 4.8 5.2 -9.8 0.0 1x 2x D 1 ~x 1.0 1.0 -1.0 -1.0 1 ~x D ~ Рис. 6. Область D — еліпс 1)102()51(242)102(412)51(34  x xxx , область              1~~ :~ ~~ 2 2 2 1 2 1 xx x x D — одиничний круг І.Я. Спекторський ISSN 1681–6048 System Research & Information Technologies, 2024, № 2 124 пов’язує одиничний круг                                               1~~ :~ ~ 1~ ~ ,~ ~ :~ ~~ 2 2 2 1 2 1 2 1 2 1 2 1 xx x x x x x x x x D і зсунутий повернутий еліпс                                             1 10 5 ,10 5 4112 1234 : 2 1 2 1 2 1 x x x x x x D               1)10()5(24)10(41)5(34 : 21 2 2 2 1 2 1 x xxx x x ). ~ (1~~:~ ~ 1 , : 12 2 2 1 2 11 2 1 2 1 2 1 DFxx x x F x x F x x F x x                                                                       Для матриці A уведемо позначення ),(max T 1\|\|:\|\| max xxAA xx n    та ),(min T 1\|\|:\|\| min xxAA xx n    відповідно максимальне та мінімальне власне чи- сло матриці TAA ; нагадаємо, що матриці TAA та AAT мають однаковий набір додатних (завдяки невиродженості A ) власних чисел. Лема 5. Нехай функція  nf : — опукла (строго опукла, сильно опукла з параметром 0 ). Тоді функція  nf : ~ , )~( ~ xf )~())~(( 111 bAxAfxFf   теж опукла (відповідно строго опукла, сильно опукла з параметром 01 max  ). Доведення. 1. Нехай функція  nf : опукла. Зафіксувавши ]1,0[ , дістаємо:   ))~)(1()~(()~)1(~( ~ 1111 bAyAbAxAfyxf )~( ~ )1()~( ~ )~()1()~( 1111 yfxfbAyAfbAxAf   для довільних nn yx   ~,~ , що доводить опуклість функції g . □ 2. Нехай функція  nf : строго опукла; nn yx   ~,~ і yx ~~  . За умовою, матриця A невироджена, а отже, матриця -1A існує і невироджена, звідки bAyAbAxA 1111 ~~   . Зафіксувавши )1,0( , маємо )~( ~ )1()~( ~ )~()1()~( ))~)(1()~(()~)1(~( ~ 1111 1111 yfxfbAyAfbAxAf bAyAbAxAfyxf     для довільних nn yx   ~,~ , що доводить строгу опуклість функції f ~ . □ 3. Нехай функція  nf : сильно опукла з параметром 0 . Зазна- чимо, що матриця TAA симетрична і, завдяки невиродженості матриці A , додатно визначена. Це означає, що всі власні числа матриці TAA дійсні до- Проекція градієнта: спрощення області мінімізації афінним перетворенням Системні дослідження та інформаційні технології, 2024, № 2 125 датні числа. Очевидно, ),)((min 1 1\|\|:\|\| 1 max xxAAT xx n      — мінімальне власне число матриці 1)( TAA . Отже, зафіксувавши ]1,0[ , отримуємо: 1 max2 1 2 11 2 21 2 1111 1111 )1()~( ~ )1()~( ~ ))~~(),~~()(()1()~( ~ )1()~( ~ ))~~(),~~(()1()~( ~ )1()~( ~ \|\|)~~(\|\|)1()~()1()~( ))~)(1()~(()~)1(~( ~           yfxf yxyxAAyfxf yxAyxAyfxf yxAbAyAfbAxAf bAyAbAxAfyxf T для довільних nn yx   ~,~ , що доводить сильну опуклість функції f ~ з параметром 1 max  . Приклад 7. Нехай  nf : , 2\|\|\|\|)( xxf  . Функція 2\|\|\|\|)( xxf  си- льно опукла з параметром 2 (див. приклад 3), а отже, функція )~( ~ xf 21121 \|\|~\|\|\|\|)~(\|\| bAxAxF   є сильно опуклою з параметром 01 max  . Цікаво, що у випадку 0b білінійний функціонал )~,~)((~,~ 1T yxAAyx  , завдяки симетричності та додатній визначеності матриці 1T )( AA , визначає інший скалярний добуток, а функція 2121 \|\|~\|\|\|\|)~(\|\|)~(~,~ xAxFxgxx   іншу норму в n . У [4] наведено теорему про збереження опуклості функції (без умови строгої чи сильної опуклості) за застосування до аргумента довільного пере- творення bAx  . ПРОЕКЦІЯ ТОЧКИ НА МНОЖИНУ Означення 5. Проекцією точки na  на непорожню множину nD  називають точку DaD Pr , найближчу до a серед усіх точок Dx : \|\|\|\|inf\|\|Pr\|\| axaa DxD   . (4) Оскільки норма \|\|\|\|  невід’ємна, рівність (4) можна подати через квад- рат норми 2\|\|\|\|  : 22 \|\|\|\|inf\|\|Pr\|\| axaa DxD   . (5) Очевидно, aaD Pr тоді й тільки тоді, коли Da . Приклад 8. Для кола 222 2,02 2 1,01 2 1 )()( :               rxxxx x x D радіуса 0r із центром у        2,0 1,0 0 x x x проекцію точки              2,0 1,0 2 1 x x a a a І.Я. Спекторський ISSN 1681–6048 System Research & Information Technologies, 2024, № 2 126 можна обчислити за формулою )( \|\|\|\| Pr 0 0 0 xa xa rxaD    , тобто aDPr міститься на перетині відрізка ],[ 0 ax з колом D (див. рис.7, а, б).; проекцією центра кола 0xa  є кожна точка кола (рис. 7, в). Приклад 9. Для відкритого круга 222 2,02 2 1,01 2 1 )()( :               rxxxx x x D радіуса 0r із центром в        2,0 1,0 0 x x x проекції точки Da ( ra \|\|\|\| ) не існує. Дійсно, raxax Dx   \|\|\|\|\|\|\|\|inf 0 міг би досягатись лише в точці )( 0\|\|\|\|0 0 xax xa r   (рис. 8), але Dxax xa r   )( 0\|\|\|\|0 0 , оскільки   \|\|)(\|\|(\|\|))((\|\| 0\|\|\|\|00\|\|\|\|0 00 xaxxax xa r xa r rxa xa r   \|\|\|\| 0\|\|\|\| 0 . У загальному випадку точка na  мо- же мати кілька проекцій на множину nD  (приклад 8) або не мати жод- ної (приклад 9). Проте відомий класичний факт (див., напр., [1, 4, 5]), який наводимо як лему. Лема 6. 1. Нехай множина nD  непорожня і замкнена. Тоді будь- яка точка na  має принаймні одну проекцію на D . 2. Нехай множина nD  опукла. Тоді будь-яка точка na  має не більше однієї проекції на D . Доведення. 1. Проекція aDPr на замкнену множину D існує за теоремою Веєрштраса: неперервна функція   n\|\|:\|\| досягає свого найменшого значення \|\|\|\|min\|\|\|\|inf axax DxDx   на непорожній замкненій множині nD  . 2. Функція   n:\|\|\|\| 2 є строго (і навіть сильно) опуклою (див. при- клад 3) і, за лемою 2, має не більше одного глобального мінімуму на опуклій множині nD  .□ 2,0x 0 1x 2x a )( 0\|\|\|\|0 0 xax xa r   Рис. 8. Проекція точки на від- критий круг не існує Рис. 7. Проекція точки на коло 2,0x 0 1x 2x D 1,0x a aDPr 1x 2,0x 0 2x D 1,0x a aDPr aDPr aDPr 0 2,0x 1x 2x D 1,0x a aDPr a б в Проекція градієнта: спрощення області мінімізації афінним перетворенням Системні дослідження та інформаційні технології, 2024, № 2 127 Приклад 10. 1. Нехай 2 0 }\|\|\|\| :{  rxxxD замкнений круг раді- уса 0r із центром в 2 0 x . Очевидно, D опукла і замкнена і, за ле- мою 6, для будь-якого 2a існує єдина проекція aDPr         Daxax Daa xa r ),( ;, 0\|\|\|\|0 0 точки 2a на множинуD (див. приклад 8). 2. Нехай   2)2,1( :  iMxmxD iii прямокутник (рис. 9), визна- чений точками 2m , 2M , )2,1(  iMm ii . Очевидно, D опукла і за- мкнена, і, за лемою 6, для будь-якого 2a існує єдина проекція aDPr )2,1( i :        ,, ;, ; )(Pr iii iiii i iD MaM Mama m a Формули для проекцій на круг і прямокутник (сторони якого паралельні координатним осям), наведені у прикладі 10, природним чином узагальнюються на кулю та паралелепіпед у n . Детальніше про проекції на деякі прості множини nD  (куля, пара- лелепіпед, півпростір та ін.) див., напр. [5]. Однак для проекцій на більш складні множи- ни (зокрема, на еліпс) надати прості явні фо- рмули неможливо. Приклад 11. Нехай              1)10()5(24)10(41)5(34 : 21 2 2 2 1 2 1 x xxx x x D повернутий еліпс (див. приклад 6),         7.9 5 a . Оскільки Da , проекція aDPr лежить на еліптичній кривій  2 2 2 1 )10(41)5(34 xx 1)10()5(24 21  x x , яка обмежує область D . Застосовуючи до пошуку екстремуму у рівності (5) метод множників Лагранжа, запишемо відповідну функцію Лагранжа:  2 1 2 2 2 121 )5(34()7.9()5(),,( xxxxxL )1)10()5(24)10(41 21 2 2  x xx . Мінімум функції ),,( 21 xxL можливий лише в нулях часткових похідних:  LLL xx ,, 21 :         01)10()5(24)10(41)5(34 0))10(82)5(24()79(2 0))10(24)5(68()5(2 21 2 2 2 1 212 211 x xxx xx.x xxλx (6) 2M 0 1x 2x 1m a aDPr 2m 1M Рис. 9. Проекція точки на прямокутник І.Я. Спекторський ISSN 1681–6048 System Research & Information Technologies, 2024, № 2 128 Легко перевірити, що аналітичне розв’язання системи (6) зводиться до рівняння 4-го степеня відносно  — такі рівняння, хоч і допускають явний розв’язок, але відповідні формули складні і містять радикали до 4-го степеня включно. Тому раціональним бачиться чисельне розв’язання системи (6), у результаті чого, після відкидання «зайвих» коренів (які не можуть бути мінімумом правої частини рівності (5)), отримуємо:        9.8381- 4.9757 Pr aD (множ- ник -0.0218 , але це значення безпосередньо не входить до aDPr ), рис. 10. Приклад 12. Нехай                   103x42 543x2 : 21 21 2 1 x x x x D повернутий пря- мокутник (див. приклад 5),        4 1 a . Для обчислення aDPr проаналізуємо розташування точки a відносно пар паралельних прямих 243x 21  x і 543x 21  x та 23x4 21  x і 103x4 21  x . Оскільки 5194413  , проекція aDPr лежить на прямій 543x 21  x . Оскільки 10843142  , проекція aDPr ле- жить на прямій, яка проходить через точку a та паралельна прямим 23x4 21  x і 1034 21  xx , тобто на прямій 0)4(3)14( 21  xx , або, в іншому ви- гляді, на прямій 834x 21  x . Розв’язуючи систему      834x 543x 21 21 x x , дістаємо: aDPr                76.1 68.0 25 44 25 17 , рис. 11. Зауваження 3. У прикладах 11 і 12 вектор aa DPr ортогональний до- тичній у точці a до кривої, що обмежує область D (рис. 10 та 11 відповід- но). Така властивість є загальною і поширюється на множини D з неглад- кою межею (див., напр., [1, 4, 5]). -10.0 -10.2 2x -9.6 5.0 4.8 5.2 -9.8 0.0 1x D a aDPr a aDPr D Рис. 10. Проекція точки на еліпс 1)102()51(242)102(412)51(34  x xxx Рис. 11. Проекція точки на прямокутник      103x42 543x2 21 21 x x 2 2 -2 0 1x 2x 4 D a aDPr Проекція градієнта: спрощення області мінімізації афінним перетворенням Системні дослідження та інформаційні технології, 2024, № 2 129 АФІННЕ ПЕРЕТВОРЕННЯ В ОПЕРАТОРІ ПРОЕКТУВАННЯ Нехай nD  — непорожня опукла та замкнена множина, a довільна точ- ка в n . Згідно з лемою 6, проекція aDPr існує і єдина, тобто інфімум у рівності (4) досягається у єдиній точці \|\|\|\|minargPr axa Dx D   . Розглянемо заміну змінних )(~ xFx  за афінним перетворенням nnF  : , bAxxF )( ( A —невироджена матриця розмірності nn , nb  ). Позначивши, як і в п. 0,   )(:)( ~ DFDxxFD  , )(~ xFx  , )(~ aFa  , уведемо оператор aF DPr , пов’язаний з обчисленням проекції aD ~Pr~ з подальшою заміною змінних )(~ xFx  : )~(PrPr ~1 aFa D F D  (7) Очевидно, множина )( ~ DFD  є непорожньою, за лемою 4 )( ~ DFD  є опуклою і, завдяки замкненості множини D та неперервності відображення F — замкненою. Таким чином, проекція aD ~Pr~ за лемою 6 існує і єдина. Ураховуючи визначення оператора aDPr , подамо рівність (7) через minarg :     \|\|)()(\|\|minarg\|\|)~~\|\|minarg(Pr ) ~ ()~(~~~ 1 11 aFxFaxFa DFx:FxDx F D n   \|\|)()(\|\|minarg bAabAx Dx .\|\|\|\|minarg\|\|)(\|\|minarg F DxDx axaxA   Отже, оператор aF DPr , як і оператор aDPr , визначає на D точку, най- ближчу до a , але найближчу — у сенсі метрики, визначеної нормою \|\|\|\|\|\|\|\| xAx F  (див. також приклад 7). Зазначимо, що норма \|\|\|\|\|\|\|\| xAx F  (а отже, і оператор aF DPr ) визначається матрицею A і не залежить від b . Оче- видно, що у випадку ортогональної матриці A маємо рівність норм: 222 \|\|\|\|),(),(\|\|\|\|\|\|\|\| xxxAxAxxAx F  , а отже, aa D F D PrPr  . Приклад 13. Розглянемо в 2 еліпс (див. приклади 6 і 11):               1)10()5(24)10(41)5(34 : 21 2 2 2 1 2 1 x xxx x x D                                             1 10 5 ,10 5 4112 1234 : 2 1 2 1 2 1 x x x x x x                                                                    1 50 225 34 2423 ,50 225 34 2423 : 2 1 2 1 2 1 x x x x x x . І.Я. Спекторський ISSN 1681–6048 System Research & Information Technologies, 2024, № 2 130 Очевидно (див. також приклад 6), еліпс D пов’язаний з одиничним кругом              1~~ :~ ~~ 2 2 2 1 2 1 xx x x D афінним перетворенням             2 1 2 1 ~ ~ x x F x x                         50 225 34 2423 2 1 x x : ) ~ (1 DFD  , або )( ~ DFD  . Обчислимо aF DPr для         7.9 5 a . Оскільки DaFa ~ 90.0 70,1 )(~        , отримуємо (див. приклад 10, п. 1):                89.0 46.0 \|\|~\|\| ~ ~~),0~(0 ; ~~,~ ~Pr \|\|0~\|\| 1~ a a Daa Daa a a D , звідки остаточно маємо:                             50 225 \|\|~\|\| ~ 34 2423 )~(PrPr 1 ~1 a a aFa D F D 50 1                                  84.9 5 50 225 \|\|~\|\| ~ 624 823 a a . Зауважимо, що aa D F D PrPr  (рис. 12). Приклад 14. Розглянемо в 2 повернутий прямокутник (див. та- кож приклади 5 та 12)                   103x42 543x2 : 21 21 2 1 x x x x D . Оскільки                      2 1 21 21 6.08.0 8.06.0 5 34 43 x x xx xx , область D пов’язана афінним перетво- ренням                                2 1 2 1 2 1 6.08.0 8.06.0 ~ ~ x x x x F x x із прямокутником D ~ )( 2~0.4 1~0.4 :~ ~ 2 1 2 1 DF x x x x                    , сторони якого паралельні координатним a aDPr D D a Центр еліпса aF DPr Рис. 12. Оператори aDPr і aF DPr для еліпса  )5(24)10(41)5(34 1 2 2 2 1 xxx 1)10( 2  x Проекція градієнта: спрощення області мінімізації афінним перетворенням Системні дослідження та інформаційні технології, 2024, № 2 131 осям (детальніше див. приклад 5). У цьому випадку, оскільки матриця         6.08.0 8.06.0 A є ортогональною (матрицею повороту), оператор aF DPr збігається із проекцією: aa D F D PrPr  для довільного na  (див. приклад 12, рис. 11). МЕТОД ПРОЕКЦІЇ ГРАДІЄНТА З АФІННИМ ПЕРЕТВОРЕННЯМ Нехай nD  — непорожня опукла та замкнена множина,  nf : ди- ференційовна строго опукла функція на n За сформульованих умов, згідно з лемою 3, існує єдиний мінімум функції f на D : )(minarg* xfx Dx  . Аналі- тичне обчислення x у практичних випадках є складним і почасти немож- ливим. Для чисельного розв’язання задачі )(minarg xfx Dx  у 1964 р. амери- канським вченим А. Голдштейном був запропонований (див. [7]) ітераційний метод, нині відомий як метод проекції градієнта:  nx 0 — обрана початкова точка;  )(Pr1 kkk D k hxx  ( 0k ), де )( kk xfh  напрямок кроку (ан- тиградієнт), nka  — довжина кроку (обирається залежно від модифікації методу). Одним з найпоширеніших методів вибору довжини кроку є метод найшвидшого спуску: 0 )(minarg   kkk hxf , який, разом з додатковими умовами на f і D , забезпечує збіжність xx k k    ; сформулюємо ві- домий (див., напр. [4]) результат у вигляді теореми. Теорема 1. Нехай nD  — непорожня опукла та замкнена множина,  nf : функція на n , яка задовольняє умови:  неперервна диференційовність на n ;  сильна опуклість з параметром 0 ;  градієнт є ліпшицевим з константою L , тобто  \|\|)()(\|\| yfxf \|\|\|\| yxL  . Тоді рекурентно задана послідовність  nx 0 довільно обрана початкова точка,  )(Pr1 kkk D k hxx  ( 0k ), де )( kk xfh  , k 0 )(minarg   kk hxf збігається до x з геометричною швидкістю: xx k k    , \|\|\|\|\|\|\|\| 1 xxqxx kk  ( 0kk  ), де )1,0[q — фіксована константа, 0k — фіксований номер. Доведення див., напр. у [4]. І.Я. Спекторський ISSN 1681–6048 System Research & Information Technologies, 2024, № 2 132 Зауваження 4. Очевидно, умова геометричної швидкості (або лінійної швидкості) \|\|\|\|\|\|\|\| 1 xxqxx kk  ( 0kk  ) еквівалентна умові  \|\|\|\| xxk kCq ( 0k ), де )1,0[q , 0C — фіксовані константи. Метод проекції градієнта пов’язаний з обчисленням проекції точки kx на множину D , що нескладно у простих випадках (наприклад, якщо D круг або прямокутник, див. приклад 10), проте ускладнюється до окремої задачі мінімізації для складніших випадків (наприклад, якщо D еліпс, див. приклад 11). Для спрощення задачі проектування застосуємо у задачі пошуку )(minarg* xfx Dx  заміну змінних, пов’язану з афінним перетворенням nnF  : , bAxxF )( ( A —невироджена матриця розмірності nn , nb  ). Позначивши, як і в п. 2, )(}:)({ ~ DFDxxFD  , )(~ xFx  , )~())~(()~( ~ 111 bAxAfxFfxf   , отримуємо область nD  ~ і функцію  nf : ~ . Таким чином, пошук )(minarg* xfx Dx  можна звести до пошуку )~( ~ minarg~ ~~ * xfx Dx  , )(~ 1 xFx  , з подальшим «поверненням» до )~(1 xFx  . Теорема 2. Нехай функція  nf : і область nD  задовольня- ють умови теореми 1, nFx 0, — довільна початкова точка, )) ~~)(((Pr ,11, kkkFF D kF hxFFx   ( 0k ), де )()( ~ ,1 kFTk xfAh   , 0~ , ) ~~(minarg~   kkFk hxf . Тоді послідовність kFx , ( 0k ) збігається до )(minarg* xfx Dx  зі швидкістю геометричної прогресії: , xx k kF    , kFkF qCxx )(\|\|\|\| ,  ( 0k ), де )1,0[Fq , 0C — фіксовані константи. Доведення. Розглянемо (див. також п. 2 і 4) отримані заміною змінних )(~ xFx  область )(}:)(~{ ~ DFDxxFxD  та функцію )~( ~ xf )~())~(( 111 bAxAfxFf   . Оскільки область D за умовою непорожня, опукла та замкнена, об- ласть )( ~ DFD  за побудовою також є непорожньою, за лемою 4 опуклою, за неперервністю відображення F замкненою. Оскільки f за умовою є си- льно опуклою з параметром 0 , функція f ~ за лемою 5 є сильно опуклою з параметром 01 max  . Функція f за умовою є неперервно диференційов- ною, тоді функція f ~ теж є диференційовною як композиція диференційов- них відображень f і 1F . Для обчислення f  ~ знайдемо ), ~ ( df  для довіль- ного фіксованого nd  : Проекція градієнта: спрощення області мінімізації афінним перетворенням Системні дослідження та інформаційні технології, 2024, № 2 133 )),~()(()),~(()),~( ~ ( 111111 dbAxAfAdAbAxAfdxf T   , звідки, враховуючи довільність nd  , отримуємо, що  )~( ~ xf ))~(()(( 11 xFfAT   є неперервним, і функція f ~ є неперервно диференці- йовною. Нарешті, із ліпшицевості f  з константою L , для f  ~ маємо:   21111112 \|\|)~()(()~()((\|\|\|\|)~( ~ )~( ~ \|\| bAyAfAbAxAfAyfxf TT )),~()~(()(( 11111 bAyAfbAxAfAAT     ))~()~( 1111 bAyAfbAxAf   21111 min \|\|))~()~(\|\| bAyAfbAxAf ,\|\|~~\|\|\|\|)~~(\|\| 222 min 212 min yxLyxAL   де ),(min 1\|\|:\|\| min xAxAT xx n    — мінімальне власне число матриці TAA . Таким чином, f  ~ ліпшицевий з константою Lmin . Отже, область D ~ і функція f ~ задовольняють умови теореми 1, тобто рекурентно задана послідовність kx~ ( 0k ), де nx 0~ довільно обрана початкова точка, ) ~~~(Pr~ ~1 kkk D k hxx  , ))~(()()~( ~~ 11 kTkk xFfAxfh   , 0~ ) ~~~( ~ minarg~   kkk hxf збігається до x з геометричною швидкістю: ~~ xx k k    , \|\|~~\|\|~\|\|~~\|\| *1 xxqxx kk  ( 0k ), де )1,0[~q фіксована константа. Увівши позначення kFx , )~(1 kxF  , дістаємо: )~( 010, xFxF  (початкова точка), )) ~~)(((Pr) ~~~((Pr)~( ,1~1111, kkkFF D kkk D kkF hxFFhxFxFx   . Оскільки за лемою 3 існує єдиний )~( ~ minarg~ ~~ xfx Dx  , за побудовою ма- ємо зв’язок )(~ ** xFx  , звідки , xx k kF    . Нарешті, оцінимо швид- кість збіжності , xx k kF    :   \|\|)~~(\|\|\|\|)~()~(\|\|\|\|\|\| 111111, xxAxFxFxx kkkF   )~~),~~()(( 111 xxxxAA kkkT ,~\|\|~~\|\|\|\|~~\|\| * ~ 11 minmin kkqk qCxxxx     тобто , xx k kF    із лінійною швидкістю, що завершує доведення тео- реми. □ Зауваження 5. Послідовності kx ( 0k ) та kFx , ( 0k ) мають одна- кову границю x , однак, взагалі кажучи, поточково розрізняються, тобто найчастіше kFk xx , . І.Я. Спекторський ISSN 1681–6048 System Research & Information Technologies, 2024, № 2 134 Приклад 15. Нехай  2:f ,             2 2 2 1 2 1 )11()6( xx x x f 4 1 )6(  x . Функція f сильно опукла з параметром 2 , оскільки                       20 0)6(122 2 1 2 1 x x x f . Розглянемо задачу мінімізації функції f на множині 2D в еліпсі (див. приклади 6, 11 і 13): ,1 50 225 34 2423 ,50 225 34 2423 : 1 10 5 ,10 5 4112 1234 : 1)10()5(24)10(41)5(34 : 2 1 2 1 2 1 2 1 2 1 2 1 21 2 2 2 1 2 1                                                                                                                              x x x x x x x x x x x x x xxx x x D який пов’язаний афінним перетворенням                                          50 225 34 2423 ~ ~ 2 1 2 1 2 1 x x x x F x x з кругом )(1~~ :~ ~~ 2 2 2 1 2 1 DFxx x x D               . Оскільки область D непорожня, опукла і замкнена, можемо засто- сувати результат теореми 2; формулу для обчислення проекції точки на круг D ~ наведено у прикладі 10. У табл. 1 подано результати роботи класичного методу проекції градієнта (послідовність kx , 0k ) та методу проекції гра- дієнта з афінним перетворенням (послідовність kFx , , 0k ); в обох випад- ках для збіжності з точністю до 510 . За початкову точку взято центр еліпса:         10 50,0 Fxx (те ж саме спостерігається і за інших початкових точок). Т а б л и ц я 1 k 0 1 2 3 4 5 kx        00000.10 00000.5        15950.10 10119.5        15380.10 11600.5        15380.10 11628.5        15380.10 11629.5        15380.10 11628.5 kFx ,        00000.10 00000.5       10.15750- 5.10640       10.15400- 5.11568        15380.10 11623.5       10.15380- 5.11626       10.15380- 5.11626 Отже, комп’ютерне моделювання підтверджує, що   k k x 0 lim          15380.10 1627.5 lim , 0 kF k x , що збігається зі значенням )(minarg xfx Dx  з точ- ністю до 510 , проте траєкторії kx і kFx , розрізняються. Проекція градієнта: спрощення області мінімізації афінним перетворенням Системні дослідження та інформаційні технології, 2024, № 2 135 Приклад 16. Нехай  2:f , 4 1 2 2 2 1 2 1 )1()1()1(             xxx x x f . Функція f сильно опукла з параметром 2 , оскільки              2 1 x x f         20 0)1(122 2 1x . Розглянемо задачу мінімізації функції f на множині 2D у повернутому прямокутнику (див. приклади 5, 10 і 12)                   103x42 543x2 : 21 21 2 1 x x x x D , який пов’язаний афінним перетворенням                                             2 1 2 1 2 1 2 1 6.08.0 8.06.0 34 43 5 1 ~ ~ x x x x x x F x x із прямокутником )( 2~0.4 1~0.4 :~ ~ 10~52 5~52 :~ ~~ 2 1 2 1 2 1 2 1 DF x x x x x x x x D                                      , сторони якого паралельні координатним осям. Оскільки область D непорожня, опукла і замкнена, можемо засто- сувати результат теореми 2, формула для обчислення проекції точки на пря- мокутник D ~ наведена у прикладі 10. У табл. 2 наведено результати роботи класичного методу проекції градієнта (послідовність kx , 0k ) та методу проекції градієнта з афінним перетворенням (послідовність kFx , , 0k ); в обох випадках для збіжності з точністю до 510 . За початкову точку взято центр прямокутника:                     2.1 7.0 28.1 54.0 10,0 Fxx F (схоже спостеріга- ється і за інших початкових точок). Т а б л и ц я 2 k 0 1 2 3 4 5 kx       28000.1 54000.0       1.13951 52688.0       1.15770 69478.0       1.15719 62678.0        1.15720 62778.0        1.15720 62778.0 kFx ,       28000.1 54000.0       1.13951 52688.0       1.15770 69478.0       1.15719 62678.0       1.15720 62778.0       1.15720 62778.0 Отже, комп’ютерне моделювання підтверджує, що   kF k k k xx , 00 limlim         15380.10 1627.5 , що збігається зі значенням )(minarg* xfx Dx  з точністю до 510 , і траєкторії kx і kFx , також збігаються, що пояснюється ортогональ- ністю матриці        6.08.0 8.06.0 , яка визначає             2 1 x x F . І.Я. Спекторський ISSN 1681–6048 System Research & Information Technologies, 2024, № 2 136 ВИСНОВКИ 1. Афінне перетворення координат у деяких випадках суттєво спрощує проектування точки на множину. 2. Афінне перетворення у методі проекції градієнта принаймні не погі- ршує швидкість збіжності методу. 3. Напрямом подальших досліджень може бути узагальнення отрима- ного результату на ширший клас перетворень; принциповим має бути збері- гання опуклості множин та сильної опуклості функцій. ЛІТЕРАТУРА 1. Andersen Ang, “Projected Gradient Algorithm,” Mathématique et recherche opération- nelle, 2021. Available: https://angms.science/doc/CVX/CVX_PGD.pdf 2. Sébastien Bubeck, “Convex Optimization: Algorithms and Complexity,” Foundations and Trends in Machine Learning, vol. 8, no. 3-4, pp. 232–357, 2015. doi: 10.1561/2200000050 3. H. Jongen, K. Meer, and E. Triesch, Optimization Theory. New York, Boston, Dordrechr, London, Moscow: Kluwer Academic Publisher, 2007, 443 p. 4. A. Sukharev, A. Timokhov, and V. Fedorov, Course Optimization Methods. M.: Nauka, 2005, 368 p. 5. F.P. Vasil’ev, Numerical Methods for Solving Extremal Problems. M.: Nauka, 1988, 552 p. 6. Y. Nesterov, Introductory Lectures on Convex Optimization. Boston, Dordrechr, London: Kluwer Academic Publisher, 2004, 236 p. 7. A. Goldstein, “Convex programming in Hilbert space,” Bulletin of the American Mathe- matical Society, no. 70, pp. 709–710, 1964. 8. M.P. Moklyachuk, Foundations of Convex Analysis: Textbook. Kyiv: TViMS, 2004, 240 p. 9. A. Ahmadi, Characterizations of convex functions, strict and strong convexity, optimality conditions for convex problems. 2021. Available: http://www.princeton.edu/ ~aaa/Public/Teaching/ORF523/ORF523_Lec7.pdf 10. R. Rockafellar, Convex Analysis. Princeton: Princeton University Press, 2015, 472 p. Received 02.08.2023 INFORMATION ON THE ARTICLE Igor Ya. Spectorsky, ORCID: 0000-0003-4863-7986, Educational and Research Institute for Applied System Analysis of the National Technical University of Ukraine “Igor Sikor- sky Kyiv Polytechnic Institute”, Ukraine, e-mail: i.spectorsky@gmail.com GRADIENT PROJECTION: SIMPLIFYING MINIMIZATION AREA BY AFFINE TRANSFORM / I.Ya. Spectorsky Abstract. One of the classical problems of optimization theory in a finite- dimensional space is to find a minimum of a function on a nonempty set. Usually, finding the precise solution to this task analytically requires a lot of computational resources or is even impossible at all. So, approximate methods are used most often in practical cases. One of the simplest and the most well-known among such ap- proximate methods for unconditional optimization is the method of gradient descent; its generalization for conditional optimization was found in 1964, the method of pro- jected gradient. For some simple sets (line segment, parallelepiped, ball), the projec- tion of the point on the set can be easily found by an explicit formula. However, for more complicated sets (e.g., an ellipse), projecting becomes a separate task. Never- theless, sometimes computing projection can be simplified by affine transform; e.g., an ellipse can be transformed into a ball by affine (moreover, by lin- ear) transformation. The paper aims to simplify the problem of minimizing function on the set by changing the condition set by affine transform F(x)= Ax+b, where A is a non-degenerated square matrix, and b is a fixed vector of proper dimension. Keywords: gradient projection, minimization, affine transformation.
id	journaliasakpiua-article-286064
institution	System research and information technologies
keywords_txt_mv	keywords
language	English
last_indexed	2025-07-17T10:28:20Z
publishDate	2024
publisher	The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute"
record_format	ojs
resource_txt_mv	journaliasakpiua/a6/a0c737d156c2463ed74de37f66a247a6.pdf
spelling	journaliasakpiua-article-2860642024-08-11T01:12:49Z Gradient projection: simplifying minimization area by affine transform Проекція градієнта: спрощення області мінімізації афінним перетворенням Spectorsky, Igor проекція градієнта мінімізація афінне перетворення gradient projection minimization affine transformation One of the classical problems of optimization theory in a finite-dimensional space is to find a minimum of a function on a nonempty set. Usually, finding the precise solution to this task analytically requires a lot of computational resources or is even impossible at all. So, approximate methods are used most often in practical cases. One of the simplest and the most well-known among such approximate methods for unconditional optimization is the method of gradient descent; its generalization for conditional optimization was found in 1964, the method of projected gradient. For some simple sets (line segment, parallelepiped, ball), the projection of the point on the set can be easily found by an explicit formula. However, for more complicated sets (e.g., an ellipse), projecting becomes a separate task. Nevertheless, sometimes computing projection can be simplified by affine transform; e.g., an ellipse can be transformed into a ball by affine (moreover, by linear) transformation. The paper aims to simplify the problem of minimizing function on the set by changing the condition set by affine transform F(x)= Ax+b, where A is a non-degenerated square matrix, and b is a fixed vector of proper dimension. Розглянуто класичну задачу оптимізації у скінченновимірному просторі, тобто знаходження мінімуму функції на непорожній множині. Пошук точного розв’язку цієї задачі аналітичними методами потребує множинних обчислювальних ресурсів або взагалі неможливий. Для реальних задач частіше застосовують методи пошуку наближеного розв’язку, серед яких одним з найпростіших і найвідоміших для задач безумовної оптимізації є метод градієнтного спуску. Узагальненням методу градієнтного спуску на випадок умовної оптимізації є запропонований у 1964 р. метод проекції градієнта. Для деяких типів множини (відрізок, паралелепіпед, куля) проекцію точки на множину можна знайти простими явними формулами, проте для складніших (напр., еліпс) проектування стає окремою задачею мінімізації. Однак у деяких випадках обчислення проекції не можна спростити афінним перетворенням — напр., еліпс афінним (і навіть лінійним) перетворенням можна звести до кулі. Спрощено задачу мінімізації функції на множині застосуванням афінного перетворення F(x) = Ax+b, де A — невироджена квадратна матриця, b — фіксований вектор відповідної розмірності. The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" 2024-06-28 Article Article application/pdf https://journal.iasa.kpi.ua/article/view/286064 10.20535/SRIT.2308-8893.2024.2.09 System research and information technologies; No. 2 (2024); 117-136 Системные исследования и информационные технологии; № 2 (2024); 117-136 Системні дослідження та інформаційні технології; № 2 (2024); 117-136 2308-8893 1681-6048 en https://journal.iasa.kpi.ua/article/view/286064/301165
spellingShingle	проекція градієнта мінімізація афінне перетворення Spectorsky, Igor Проекція градієнта: спрощення області мінімізації афінним перетворенням
title	Проекція градієнта: спрощення області мінімізації афінним перетворенням
title_alt	Gradient projection: simplifying minimization area by affine transform
title_full	Проекція градієнта: спрощення області мінімізації афінним перетворенням
title_fullStr	Проекція градієнта: спрощення області мінімізації афінним перетворенням
title_full_unstemmed	Проекція градієнта: спрощення області мінімізації афінним перетворенням
title_short	Проекція градієнта: спрощення області мінімізації афінним перетворенням
title_sort	проекція градієнта: спрощення області мінімізації афінним перетворенням
topic	проекція градієнта мінімізація афінне перетворення
topic_facet	проекція градієнта мінімізація афінне перетворення gradient projection minimization affine transformation
url	https://journal.iasa.kpi.ua/article/view/286064
work_keys_str_mv	AT spectorskyigor gradientprojectionsimplifyingminimizationareabyaffinetransform AT spectorskyigor proekcíâgradíêntasproŝennâoblastímínímízacííafínnimperetvorennâm

Проекція градієнта: спрощення області мінімізації афінним перетворенням

Institution

Ähnliche Einträge