Методи мінімізації без обмежень. Метод Пауелла

Зміст 1. Вступ. 2. Спряженість і спряжені напрями. 3. Метод Пауелла. 4. Алгоритм Пауелла. 5. Приклад 1. (Метод Пауелла). 6. Приклад 2.( Метод Пауелла для функції Розенброка). 7. Висновок. 8. Список використаної літератури. 9. Додаток. Вступ За допомогою методів, що використовують похідні (або

їх апроксимації), в розглядаються методи оптимізації, що не використовують похідні. Ці методи зазвичай називають методами пошуку. У типовому методі пошуку напряму мінімізації повністю визначаються на підставі послідовних обчислень цільвої функції . Як правило, при вирішенні завдань нелінійного програмування за відсутності обмежень градієнтні методи і методи, що використовують другі похідні, сходяться швидше, ніж прямі методи пошуку.

Проте, застосовуючи на практиці методи, що використовують похідні, доводиться стикатися з двома головними перешкодами. По-перше, в завданнях з достатньо великим числом змінних досить важко або навіть неможливо отримати похідні у вигляді аналітичних функцій, необхідних доячи градієнтного алгоритму або алгоритму, що використовує похідні другого порядку. Хоча обчислення аналітичних похідних можна замінити обчисленням похідних за допомогою різницевих схем, що виникає при цьому, особливо в околиці екстремуму, може обмежити

застосування подібної апроксимації. В принципі можна використовувати символічні методи для аналітичних виразів похідних, але ці методи вимагають значного розвитку, перш ніж вони стануть відповідним практичним інструментом. В усякому разі, методи пошуку не вимагають регулярності і безперервності цільової функції і існування похідних. Другою обставиною, правда, пов'язаним з попередньою проблемою,

є те, що при використанні методів оптимізації, заснованих на обчисленні перших і при необхідності других похідних, потрібний в порівнянні з методами пошуку досить великий час на підготовку завдання до рішення. Унаслідок викладених вище за труднощі були розроблені алгоритми оптимізації, що використовують прямий пошук, які, хоча і повільніше реалізуються у разі простих завдань, на практицідругі похідні, і рішення задачі з їх допомогою може обійтися дешевше, якщо вартість підготовки завдання до

рішення висока в порівнянні з вартістю машинного часу. Одним з таких методів є метод Пауелла. Спряженість і спряжені напрями Як буде видно нижче, квадратична цільова функція п незалежних змінних, що має мінімум, може бути мінімізована за п кроків (або менше), якщо кроки робляться в так званих спряжених напрямах. Хоча використовувані в реальних завданнях схеми оптимізації, що виявляються ефективними для квадратичних

цільових функцій, іноді можуть погано працювати (і в загальному випадку заснований на цьому підхід не дасть спряжених напрямів пошуку) при складніших цільових функціях, проте цей підхід представляється цілком розумним. Перш ніж описувати які-небудь алгоритми, слід спочатку визначити і проілюструвати властивість зв'язаності. У цьому розділі передбачається, якщо це не обмовляється особливо, що цільова функція квадратична і має вигляд (1) де — додатньо визначена матриця.

Припустимо, що процес мінімізації починається в з початковим напрямом , вибраним довільно або за яким-небудь певним правилом. Для зручності візьмемо його у вигляді одиничного вектора, тобто . Тоді вектор буде рівний Таким чином Після того, як по формулах (1) і (2) обчислений для продовження процесу мінімізації повинно бути вибрано новий напрям. Цей новий напрям називається Iспряженим до старого напрамку , якщо .

В загальному випадку система лінійно незалежних напрямів пошуку називається спряженою по відношенню до деякої додатньо визначеної (квадратної) матриці , якщо (Ми припускаємо, що - невироджена матриця.) Прикладом може служити матриця Гессе цільовій функції . Спряженість – поняття, аналогічне ортогональності; дійсно, коли , то відповідно до рівняння (3). Відмітимо далі, що якщо цільова функція перетворена до канонічного вигляду, скажімо , то власні значення

знаходяться на діагоналі . Таким чином, спряженість можна інтерпретувати як ортогональность в просторі перетворених координат, якщо напрями пошуку масштабовані відповідними функціями власних значень. У нових координатах маємо де і Оскільки зв'язані напрями лінійно незалежні, то будь-який вектор в просторі можна виразити через таким чином: де Для деякої матриці завжди існує принаймні одна система з п взаємно спряжених напрямів, оскільки

самі власні вектори є такою системою. Надалі при використанні зв'язаних напрямів буде потрібно наступне співвідношення для квадратичної функції: Можна показати, що вектори , побудовані як зв'язані напрями, лінійно незалежні. Єдиний можливий додатковий вектор,який взаємно спряжений зі всіма напрямами , – нульовий. Таким чином, загальне правило, що полягає в тому, що якщо використовуються спряжені напрями, то будь-яка квадратична функція п змінних, що має мінімум, може бути мінімізована за п кроків, поодинці

в кожному із зв'язаних напрямів. Більш того, порядок використання цих напрямів несуттєвий. Це правило для спряжених напрямів можна довести таким чином. Запишемо цільову функцію у вигляді , при цьому і в точці мінімуму , де . Слід також відмітити, що з комутативності скалярного добутку (що можна отримати і безпосереднім перемножуванням елементів). На п-м кроці в результаті маємо

На кожному кроці ми мінімізуємо у напрямі , щоб отримати , що приводить до виразу Після виклаення деяких важливих властивостей спряженості можна перейти до розгляду алгоритмів мінімізації , що використовують спряжені напрями. МЕТОД ПАУЕЛЛА У методі Пауелла, визначається місце знаходження мінімуму деякої квадратичної функції при шляхом проведення послідовних одновимірних пошуків, починаючи з точки, уздовж системи отриманих спряжених напрямів.

Нагадаємо, що два напрями пошуку і називаються спряженими, якщо де — додатньо визначена квадратна матриця. Нижні індекси позначають вектори одного етапу (останні позначаються верхнім індексом). Ідея алгоритму Пауелла по суті полягає в тому, що якщо на даному етапі пошуку визначається мінімум квадратичної функції уздовж кожного із спряжених напрямів і якщо потім в кожному напрямі робиться деякий крок, то повне переміщення від початку до -го кроку спряжене

до всіх піднапрямів пошуку. Перехід від точки в точку визначається формулою Обчислювальна процедура даного алгоритму проводиться таким чином. В точці в початкові напрямки вибираються паралельні координатним осям . Перший крок виконується в напрямку , тобто мінімізується по (за допомогою одновимірного пошуку) для обчислення . Потім вважається . Мал.1. Метод пошуку

Пауелла. Як видно на мал. 1, в точці має місце перший виявлений мінімум. Потім уздовж кожного з напрямів у свою чергу мінімізується , визначається відповідне і послідовно обчислюються за формулою (1) нові значення . На мал.1 показано розташування точок і для наступної цільової функції, що являє собою функцію двох змінних: Координатні осі в мають напрями Вони ортогональні, тобто , але не спряжені, оскільки .

Місце знаходження відповідних мінімумів показане в наступній таблиці: Ітерація у точці мінімуму 0 1 2 [0 1] [1 0] [0 1] –1 –1,75 –0,875 [2 1] [0,25 1] [0,25 0125] 7 0,875 0,109 Щоб зрозуміти, яку роль в алгоритмі Пауелла відіграють спряжені напрями, розглянемо наступну теорему, що має місце для квадратичних цільових функцій: Теорема Якщо при початковій точці пошуку в напрямку мінімум знаходиться в деякій точці пошуку в тому ж самому

напрямку мінімум знаходиться в точці ; то при напрямок спряжений з . Приведемо доведення цієї теореми. Для першого пошуку для другого Віднімаючи, отримаємо Отже, і спряжені. З мал. 1 видно, що де відповідає точці у формулюванні теореми, а будь-яка точка на прямій відповідає . Для прикладу мал.1 Ця теорема безпосередньо може бути поширена на випадок декількох спряжених напрямів; якщо, починаючи

з , точка визначається після використання спряжених напрямів і аналогічно якщо, починаючи з , точка визначається після використання тих же напрямів і мінімізується на кожному кроці, то вектор спряжений до всіх напрямів. Таким чином, ми визначили два спряжені напрями, в яких слід вести пошук. Отже, напрям повинен бути замінений на напрям вектора , що

є повним переміщенням з першого мінімуму. Напрями пошуку на наступному етапі такі: Другий етап пошуку знову починається мінімізацією, цього разу уздовж напряму . Потім здійснюються, якщо це виявляється необхідним, переміщення в напрямах і . Пригадаємо, проте, що для квадратичної цільової функції двох змінних після використання двох спряжених напрямів відразу досягається мінімум (мал.1). Алгоритм

Пауелла Алгоритм Пауелла дещо відрізняється від простих початкових кроків, описаних вище. У загальному випадку на k -м етапі методу Пауелла використовуються п лінійно незалежних напрямів пошуку; при цьому пошук починається в деякій крапці і проводиться таким чином: Крок 1. Починаючи з , за допомогою якого-небудь одновимірного пошуку визначається так, щоб приймала мінімальне значення, і вважається, що . Починаючи з визначається так, щоб перетворювалася в мінімум,

і вважається . Пошук продовжується послідовно в кожному напрямі, завжди починаючи з останньої точки послідовності, поки не будуть визначені все . Величина отримана при мінімізації в напрямі , використовується в кроці 4 (див. нижче). Крок 2. Пауелл відзначив, що пошук,який здійснюється відповідно до кроку 1, може привести до лінійно залежних напрямів пошуку, як, наприклад, у разі, коли одна з компонент стає тотожним нулем, оскільки в цьому напрямі не може бути руху.

Отже, два напрями можуть стати колінеарними. Таким чином, не слід заміняти старий напрям на новий, якщо після цього напряму нового набору стає лінійно залежними. Пауелл показав також (на прикладі квадратичної функції), що при нормуванні напрямів пошуку відповідно формули визначник матриці, стовпцями якої є напрями пошуку, приймає максимальне значення тоді і тільки тоді, коли взаємно спряжені відносно . Він прийшов до висновку, що напрям повного переміщення

на k -м етапі повинен замінювати попередній напрям тільки у тому випадку, коли замінюючий вектор збільшує визначник матриці напрямів пошуку, оскільки тільки тоді новий набір напрямів буде більш ефективнішим. Отже, після мінімізації в кожному з п напрямів, як на кроці 1, проводиться один додатковий крок величиною , відповідний повному переміщенню на -му етапі і що приводить в точку . Потім проводиться тест (див. крок 3), щоб переконатися, чи зменшується визначник матриці напрямів пошуку

шляхом включення нового напряму і відкидання старого. Крок 3. Позначимо найбільше зменшення в якому-небудь напрямі пошуку на -м етапі через Напрям пошуку, відповідний цій максимальній зміні позначимо через . Щоб зробити позначення компактнішими, покладемо , і , де і Тоді якщо (або) , то слід використовувати на -му етапі ті ж напрями , що

і на етапі, тобто для , і почати пошук з точки [або з , залежно від того, в якій точці функція приймає найменше значення]. Крок 4. Якщо тест на кроці 3 не задовольняється, то шукається мінімум у напрямі вектора проведеного з в ; точка цього мінімуму береться як початкова для наступного -го етапу. Система напрямів, що використовуються на -му етапі, та ж, що і на k -м етапі, за винятком напряму , який замінюється на .

Проте поміщають в останній стовпець матриці напрямів, а не на місце . Отже, на -му етапі використовуватимуться наступні напрями: Крок 5. Критерій задовільної збіжності для методу Пауелла, що використовується для визначення моменту закінчення пошуку в кінці будь-якого етапу, полягає в тому, що зміна по кожній незалежній змінній повинна бути менше, ніж задана точність , або

Приклад 1. Метод Пауелла Продемонструємо метод Пауелла на прикладі наступного завдання: мінімізувати , починаючи з точки . В точці функція приймає значенння 45,000. Спочатку мінімізується по за допомогою одновимірного пошуку в координатному напрямі ( залишається рівним 9,000); 8,000 7,992 7,952 7,752 6,752 1,752 5,460 4,043 6,335 4,919 . . . 5,000 45,000 44,808 43,857 39,294 21,278 51,198 9,847 12,657 16,135 9,026 . . .

9,000(мінімум ) Здійснення кроку приводить до У цій точці . При цьому значення рівне . Відмітимо також, що і Отже, на наступному етапі вектор пошуку буде той же, що і на попередньому. Проте пошук закінчується в точці, оскільки критерій збіжності задоволений. На мал.2 приведена траєкторія пошуку. Приклад 2. Метод Пауелла для функції Розенброка Застосування алгоритму

Пауелла до функції Розенброка Показує, що відбувається при мінімізації неквадраїчной функції. Почнемо з точки , де . Початковий напрям пошуку наступний: , . Спочатку мінімізація здійснюється у напрямі пошуку , тобто в напрямі (деталі цієї процедури тут не приводиться), що приводить до точки , в якій . Потім здійснюється пошук, що використовує вектор , тобто в напрямі , що дає , де . Після виконання кроку де , обчислюються нові , , , оскільки не задовольняється

згаданою вище (див. крок 3) критерій (a) і (б) Результати декількох додаткових етапів пошуку, починаючи з точки приведені в наступній таблиці: Етап 1 2 3 [0 1] [0 1] [0,453 -0,892] [0.205 -0.010] [0,453 -0,892] [0,608 -0,794] На мал. 3 представлена траєкторія пошуку. В цілому для отримання мінімуму цільова функція обчислювалася 1562 рази, при цьому мінімум мав місце в точці і . Висновок Алгоритм Пауелла, приведений в цьой роботі, може бути віднесений до методів нульового

порядку, оскільки не використовує похідних в явному вигляді, але він же може бути віднесений і до градієнтних алгоритмів, оскільки неявно формує оцінку матриці Гессе і використовує інформацію про поведінку похідних. Більш того, як метод квадратичної апроксимації цільової функції, він може навіть розглядатися як метод Ньютонівського типу. Таке проміжне положення методу зв'язаних напрямів

і спонукало викласти його в окремому роботі, не відносячи метод ні до прямого пошуку, ні до градієнтних алгоритмів. Список використаних джерел 1. Химельблау Д. Прикладное нелинейное програмирование. Москва, «Мир», 1975, с. 184. 2. Методи мінімізації без обмежень. Метод Пауелла ДОДАТОК Тексти програм function main global n; n=2; % кількість змінних clc eps=1e-4;

% початкова точка %fp(1)=8; %fp(2)=9; fp(1)=-1.2; fp(2)=1.0; x=Pawell(eps ,fp) f=func(x) * function result=func(x) result=100*(x(2)-x(1)^2)^2+(1-x(1))^2; %result=4*(x(1)-5)^2+(x(2)-6)^2; * function Result=MakeDichotomy(a,b,eps,prec,xk,uk) while (b-a)>eps xk1=(a+b)/2-prec; xk2=(a+b)/2+prec; if Pseudo1D(xk1,xk,uk)<Pseudo1D(xk2,xk,u k) if b~=xk2 b=xk2; else break; end else if a~=xk1 a=xk1; else break; end end end Result=(a+b)/2; * function z=Pawell(eps ,fp); global n; p_i=zeros(n,n); %початкові

напрямки for i=1:n p_i(i,i)=1; end curx=fp; lastx=fp; wavex=fp; lastxx=fp; k=1; %кількість ітерацій while true for i=1:n % знаходимо спряжений напрямок р for l=1:n xk=wavex; uk=p_i(l,:); % мінімізуємо f(xk+uk*p_i(l,:)) по uk в напрямку cappa=MakeDichotomy(-1000,1000,1e-5,eps/ 100,xk,uk); if abs(cappa)<1e-8 cappa=0; end wavex=wavex+cappa*p_i(l,:); end % for l % знаходимо спряжений напрямок p=wavex-lastx; xk=wavex; uk=p; % мінімізуємо по знайденому напрямку cappa=MakeDichotomy(-10000,10000,1e-5,ep s/100,xk,uk); if

abs(cappa)<1e-8 cappa=0; end z=wavex+cappa*p; % % переприсвоюємо напрямки for l=1:n-1 p_i(l)=p_i(l+1); end p_i(n,:)=p; % if i~=n wavex=z; lastx=z; end end %for i % переприсвоюємо сurx і lastx lastxx=curx; curx=z; % перевіряємо на знаходження x* if sqrt((curx(1)-lastxx(1))^2 + (curx(2)-lastxx(2)^2))<eps break; end % переприсвоюємо wavex і lastx wavex=curx; lastx=curx; k=k+1; end; k * function

Result=Pseudo1D(x,xk,uk) Result=func(xk+x*uk); * Результат роботи програм методу Пауелла для функції , . Результат роботи програм для метод Пауелла для функції Розенброка , .