Проекція градієнта: спрощення області мінімізації афінним перетворенням
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...
Збережено в:
| Дата: | 2024 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | English |
| Опубліковано: |
The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute"
2024
|
| Теми: | |
| Онлайн доступ: | http://journal.iasa.kpi.ua/article/view/286064 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | System research and information technologies |
Репозитарії
System research and information technologies| id |
journaliasakpiua-article-286064 |
|---|---|
| record_format |
ojs |
| 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 http://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 http://journal.iasa.kpi.ua/article/view/286064/301165 |
| institution |
System research and information technologies |
| baseUrl_str |
|
| datestamp_date |
2024-08-11T01:12:49Z |
| collection |
OJS |
| language |
English |
| topic |
проекція градієнта мінімізація афінне перетворення gradient projection minimization affine transformation |
| spellingShingle |
проекція градієнта мінімізація афінне перетворення gradient projection minimization affine transformation Spectorsky, Igor Проекція градієнта: спрощення області мінімізації афінним перетворенням |
| topic_facet |
проекція градієнта мінімізація афінне перетворення gradient projection minimization affine transformation |
| format |
Article |
| author |
Spectorsky, Igor |
| author_facet |
Spectorsky, Igor |
| author_sort |
Spectorsky, Igor |
| title |
Проекція градієнта: спрощення області мінімізації афінним перетворенням |
| title_short |
Проекція градієнта: спрощення області мінімізації афінним перетворенням |
| title_full |
Проекція градієнта: спрощення області мінімізації афінним перетворенням |
| title_fullStr |
Проекція градієнта: спрощення області мінімізації афінним перетворенням |
| title_full_unstemmed |
Проекція градієнта: спрощення області мінімізації афінним перетворенням |
| title_sort |
проекція градієнта: спрощення області мінімізації афінним перетворенням |
| title_alt |
Gradient projection: simplifying minimization area by affine transform |
| 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. |
| publisher |
The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" |
| publishDate |
2024 |
| url |
http://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 |
| first_indexed |
2024-08-11T04:01:29Z |
| last_indexed |
2024-08-11T04:01:29Z |
| _version_ |
1811501759163531264 |