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

Abstract

Розглянуто класичну задачу оптимізації у скінченновимірному просторі, тобто знаходження мінімуму функції на непорожній множині. Пошук точного розв’язку цієї задачі аналітичними методами потребує множинних обчислювальних ресурсів або взагалі неможливий. Для реальних задач частіше застосовують методи пошуку наближеного розв’язку, серед яких одним з найпростіших і найвідоміших для задач безумовної оптимізації є метод градієнтного спуску. Узагальненням методу градієнтного спуску на випадок умовної оптимізації є запропонований у 1964 р. метод проекції градієнта. Для деяких типів множини (відрізок, паралелепіпед, куля) проекцію точки на множину можна знайти простими явними формулами, проте для складніших (напр., еліпс) проектування стає окремою задачею мінімізації. Однак у деяких випадках обчислення проекції не можна спростити афінним перетворенням — напр., еліпс афінним (і навіть лінійним) перетворенням можна звести до кулі. Спрощено задачу мінімізації функції на множині застосуванням афінного перетворення F(x) = Ax+b, де A — невироджена квадратна матриця, b — фіксований вектор відповідної розмірності.

Keywords

• проекція градієнта
• мінімізація
• афінне перетворення