Силаева Т.А. - Методы решения задач оптимального проектирования ВС (774567), страница 2
Текст из файла (страница 2)
3. Задачи параметрической оптимизации. Они сводятся к задачам нелинейного программирования с непрерывными переменнымв. К ним относятся задачи параметрической оптвмвзации при функционально- логическом проектировании, яапример, задача расчета оптимальных значений внутренних параметров фрагментов БИС (задержек распространения сигналов и мощности рассеяния в фрагментах БИС). 4, Задачи оптимизации на конструкторском (топологическом) уровне проектирования БИС, СБИС и печатных плат. Чаще всего зто задачи коммутацвонно-моитажного проектирования, а именно компоновка, размещение и трассировка.
Большинство из ннх сводится к задаче целочисленного линейного программирования. Рва $Л (1.3) а ы (Х ) а ~г(Х ) аг1(Х ) агг(Х ) (1.4) Ьг(Х ) 5. Задачи оптимизации физической структуры и геометрических размеров компонентов интегральных схем, оптимизации. электронных схем. Они сводятся к задачам нелинейною программирования с непрерывными переменными. В данной лабораторной работе рассмотрим методы решения задач безусловной оптнмизацвн функции У(Х), т.е. задач вида ех(г У'(Х) .
х Классический метод, основанный на необходимом н достаточном условиях экстремума Класснческий метод нахождения безусловного экстремума функции Г(Х ) можно использовать, когда известно ее аналнтяче; ское выражение и она по крайней мере дважды дифференцируема по Х. Градиентом ЧГ(Х ) функции Г(Х) е произвольной точке Х = (х1, ..., х „) называется вектор первых частных производных У(Х) по всем х, ( с= 1,а) в этой точке Х РУ(Х)= ~ — '~-(Х), -"-(Х), -,— '"- (Х) . ( д~„ ' даг ' "'"дал Матрвцей Гессе А(Х ) функции У(Х) в точке Х называется симметрическая матрица размером ях и частных производных второго порядка функции Г(Х) в точке Х : ' 1 А(Х )= ~а — (Х )]= — "ь — (Х )~.
~ дх,дх) Необходимое условна экстремума функции у(Х) в точке Х имеет внд: ~7Г(Х)= О, нли в скалярной форме: †,' (.; .' ;)= ( = †) Точки Х, в которых выполняется (1.3), называются стациопарными. Точка Х экстремума (мкнимума иян максимума) обя- зательно является стационарной точкой, но стационарные точки — не обязательно точки экстремума. Например, в случае Г(а), изображенной па ркс. 1.1, стационарнымн точками будут: х н а, причем х — точка минимума, а х — точка перегиба функции, не являющаяся ни минимумом, ни максимумом. Классический метод нахождения безусловного экстремума функции состоит в формировании на основе необходимого условия экстремума системы уравнений (1А) для поиска стационарных точек исследуемой функцив, решении данной системы н в эь;явленви точек минимума и максимума среди стационарных точек на основе использования достаточного условня экстремума.
Достаточным условием максимума функции у(Х) в точке Х является отрицательная определенность матрицы Гессе А(Х ) этои функции в точке Х, а достаточным условием минимума — положительная определенность А (Х ') . По теореме Сильвестра матрица Гессе А(Х ) будет положительно определенной, если для всех ее определителей Л (Х ) с ) первого до и-го порядка выполняются условия: Ь1(Х )= а11(Х ) > О, а11(Х ) а1.(Х*) ь„(Х') = > О, а„((Х )... а„„(Х*) и отрицательно определенной, если Ь (Х ) < О при нечетных ) и Ь . (Х ) > О при четных,р' ) ) = 1, и 1. у Огсюда следует. что если все определвтелн Л . (Х ) > О (7'= 1, и ), то Х вЂ” точка минимума; если знаки определителей чередуются, начиная с отрицательного„то Х вЂ” точка максимума.
) 7 Отметим, что л = ~~) а(й Р,.ь — — ~, а(аРей а=1 1=1 (разложение по любой бй строке ()н 1,)) нли любому й-му столбцу (й н 1,)')), Р ( 1 ) й М где Р,„— алгебравческое дополнение элемента аг; М вЂ” дополнительный минор, получающийся из определителя Ь вычеркиванием строки 1 н столбца й. Метод Ньютона 10 В случае, когда точное решение системы уравнений (1.4) найти трудно, применяют приближенные численные методы ее решения. К ннм относят метод Ньютона, который обеспечивает быструю сходимость, но имеет трудность выбора начального приближения, гарантирующего сходимость.
Итерационный алгоритм нахождения стациояарных точек по методу Ньютона состоит в следующем. д г" 1. Находим <р,.(Х)= (Х) (1= 1,л). дх; 2. Выбираем начальную точку Х( )= (х)), ...,х( )) н точность решения е (малое положительное число, например е= 10 ), находим ('(Х( ) . — 4 (О) 3. Формируем систему уравнений относительно неизвестных (Х )1(1 + — (Х )1З~~+ ...+ — (Х )1(„ дх1 2 и = -д,(Х(")), (1.5) 4.
Примем й = О . 5. Подставляем значение Х() в систему (1.5) уравнений, в (з) результате чего она становится системой линейных алгебраических уравнений относительно неизвестных 1() (1= 1,л). 6. Решая данную систему, определяем Т(). 7. Находим Х( )= Х()+ Т() (или в координатной форме (й+ 1) (З) «+1) „(а),(м ( 1 )) ~(х(а+1)) 1 1 8.
Если ~~, (1( )) > е, тогда примем й= й+ 1 и переходим к п. 5, иначе к п, 9. 9. Конец алгоритма. Общий алгоритм решения задач безусловной оптимизации с помощью итерационных методов поиска безусловного экстремума Существует две группы таких итерационных методов: 1) градиентные методы; 2) методы случайного поиска. Основными в первой группе являются следующие методы: — градиентного спуска: — наискорейшего спуска; — сопряженных градиентов. Во второй группе выделнют следующие основные методы: — с возвратом на неудачном шаге; — наилучшей пробы; — с обучением.
Общий алгоритм решения задач безусловной оптимизации с помощью итерационных методов состоит в следующем: 1. Выбираем начальное приближение Х(.) и точность реше(о) ния е, принимаем й= О. 2. Определяем направление я поиска экстремума на итера- (а) цин й . 3. Выбираем величину шага й ( ) в направлении поиска. (а) 4.
Вычисляем Х (а + () Х (л) + й (ь) ~ (а) (1.6) 5. Рассчитываем «( Х(" ) ) и дополнительно для градиент))а его норму ~~'т'«(Х( ))~~ = нь 2 (,„ ( 6. Если выполняется критерий завершения поиска экстремума, то переходим к п. 7, вначе принимаем й= й+ 1 и переходим к и.
2, 7. Конец алгоритма. Критерием завершенвя поиска экстремума служит: 1) для градиентных методов ) ) (7«(Х(я+ О ) ) ) (1.7) 2) для методов случайного поиска ~«(Х~ + ) ) — «(Х( "~~! < е (г= 0,1~; Метод градиентного спуска Направленве градиента Ч«(Х) есть направление наибыстрейшего возрастания функции «(Х) з точке Х. Поэтому за направление поиска максимума на итерации й принимаем последний критерии означает, что на протяжении трех итераций значение функции практически не изменяется.
Итерацвонные методы отличаются между собой тем, как выбираются направление л( ) н шаг й( ) поиска экстремума. Особен(ь) (Ф) ности этого выбора в гпести перечисленных методах будут рассмотрены ниже. (а) ~«(Х(а) ) (а) д«~Х(ь) ) )' (1.6) а минимума где — (7«( Х ~ называют антиградиентом. / (а) ) В обоих случаях используем постоянный шаг в направлении поиска экстремума на всех итерациях й( = й= сове( прв любом й, (а) (1.10) «(Х ) < «( Х ! прн поиске минимума, (1.11) «~Х ) > «( Х ) при поиске максимума .
В противном случае надо уменьшить значение й, иначе итерационный процесс может быть расходящимся вли зацикливаться. В общем случае при невыполнении на (й,+ 1)-й итерации (г= 1, 2, ... ) условия (1Л1) выбираем шаг в направлении поиска экстремума на итерации й следующим образом; Ь = й= сопя( прн й= О, й (, (й) й(~)= й,= сола((г) при й= й,+ 1,й, (, з= 1,2,. где й> й,> й,+( (з= 1,2,...) и данные константы й, выбираются (путем их уменьшения с ростом з) так, чтобы выполнялось условие (1.11). На рис.
1.2 показан пример влиянвя выбора значения шага й( на сходнмость итерационного процесса нахождения миниму(ь) ма функции «(х ) = ах , а > О . Прв й = — происходит зацякли- 1 а ванне: х = — х, х = х (рнс. 1,2, а), В случае (ь + 1) (й) (ь + 2) (а) где й необходимо выбирать достаточно малым положительным числом, чтобы процесс нахождения экстремума сходился. В общем случае в методе градиентного спуска (с фиксированным шагом й) может не обеспечиваться сходимость итерационного процесса нахождения экстремума.
На каждой итерации й следует проверять выполнение условия: 13 Юпь( Р«с. 1.3 а) Ря«. 1.2 (1= 1,н); (й) и 1)~(Х(/с) ) й(" 1) (1 12) 1 1 Ь> — процесс расходится (рис. 1.2, 6); при Ьс — — сходится (рис. 1.2, в). В связи с малостью шага Ь данный метод не обеспечивает быстроту сходимостн, требуется больше итераций, чем прн применения метода Ньютона н метода нанскореншего спуска.
Отметим, что так как в данном методе градиент вычисляется на каждой итерации, то прн слишком громоздком выражении для градиента его значение находят по приблвженной формуле: ддХ) У(х1, ...,х;+ г,, ...,*„) — У(х(,...,х,, ...,х,) дх( где г,с Ь. Рассмотрим геометрический смысл метода градиентного спуска. Направление градиента и антиградиента функции у(Х) в любой точке перпендикулярно касательной к поверхности (при и= 2 к линни) постоянного уровня функции в этой точке. Такой поверхностью (линией) называется поверхность (лнния), на которой значение функции постоянно.
На рнс. 1.3 изображены липин постоянного уровня функции У(х(,хэ)= с„(У= 1,4, причем с1> сз> сз> сз), выбранная начальная точка Х( ) и полученные э соответствии с мето- (О) дом градиентного спуска первые три точки Х (Ь = 1, 3 ) прн по- 14 иске минимума ~(Х), При этом точки Х н Х расположены (ь+ 1) (а) (ь) х на расстоянии Ь ~ ~ т',((Х( ) ) ~ ~ друг от друга. Методы наискорейшего спуска и сопряженных градиентов Расчетная формула для направления у( ) поиска экстремума (ы э методе наискорейшего спуска имеет тот же ввд (1,8) — (1.9), что в в методе градиентного спуска: где «+» используют при поиске максимума, «-» при минимуме.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
