Первая лаба в виде буклетика (774587), страница 3
Текст из файла (страница 3)
Проверяем выполнение достаточного условия в Х1 и Х2. Для этого находим определители третьего, второго и первого порядков д2г матрицы Гессе А (Х) = — ' — (Х ) ~ дх1дх. = бх1(-1) + 1 2 + О(-1) + О 2 + Получаем Ь1(Х1) > О, Л;(Х2) < 0 (1= 1,3), поэтому Х1 точка минимума, а Х2 — точка перегиба (стационарная точка, не являющаяся ни точкой минимума, ни точкой максимума). При атом ~ (Х 1 ) = — 12, 1 (Х 2 ) = — 8 . Далее для изучения других методов решения задач безуслов- ной оптимизации функции согласно порядку выполнения лабора- торной работы выполняем вручную по одной итерации в решении заданной задачи с помощью трех итерационных методов: Ньютона, градиентного спуска при заданном Ь = 0,2 и наискорейшего спуска.
При этом начальную точку Х( ) выбираем исходя из полученной (о) классическим методом точки минимума Х'= Х1= (1; — 4; 2), тог- да Х ( ) = (2; — 3; 3), Применим метод Ньютона для поиска стационарных точек. Для заданной функции ,Г (Х ) = х 1+ х 2+ х з + х2 х з — 3 х1 + б х 2+ 2 З 2 2 находим Ф1(Х)= дх1 — 3, Ф2(Х)= 2х2+ хз+ б, Фз(Х) — 2хз+ х2, 2 Выбираем'Х()= (2; — 3„3) и е= 10, находим зательно является стационарной точкой, но стационарные точки — не обязательно точки экстремума.
Например, в случае ((х), изображенной на рис. 1.1, стационарными точками будут: х и Р х, причем х' — точка минимума, а х — точка перегиба функции, не являющаяся ни минимумом, ни максимумом. Классический метод нахождения безусловного экстремум» функции состоит в формировании на основе необходимого условия экстремума системы уравнений (1.4) для поиска стационарных точек исследуемой функции, решении данной системы и в вь;явлении точек минимума и максимума среди стационарных точек на основе использования достаточного условия экстремума. Достаточным условием максимума функции ((Х) в точке Х является отрицательная определенность матрицы Гессе А (Х ) этой функции в точке Х, а достаточным условием минимум» вЂ” положительная определенность А (Х ) .
По теореме Сильвестра матрица Гессе А(Х ) будет положительно определенной, если для всех ее определителей Ь.(Х ) с первого до и-го порядка выполняются условия: п1(Х ) = а „(Х") > О, ~~Х( ) )= — 5. Формируем систему уравнений: (1 14) 4( О = — 3, (о) 2(2 +13 = — 3, (0) (О) г2 +223 = 3. (о) (о) (1.3) ~х „х,...,х ~= О ~х= 1,и) 3х( — 3 2 2х2+ хз+ 6 2хч+ х2 Находим )7~(Х) = 5.
Задачи оптимизации физической структуры и геометрических размеров компонентов интегральных схем, оптимизации электронных схем. Они сводятся к задачам нелинейного программирования с непрерывными переменными. В данной лабораторной работе рассмотрим методы решении задач безусловной оптимизации функции ) (Х), т.е.
задач вида ех1г ) (Х ) . х Классический метод, основанный на необходимом и достаточном условиях экстремума Классический метод нахождения безусловного экстремума функции У(Х) можно использовать, когда известно ее аналитическое выражение и она по крайней мере дважды дифференцируема по Х. Р Градиентом 7У(Х ) функции ~(Х) в произвольной точке Р Х = (х(,...,х„) называется вектор первых частных производных У(Х) по всем х, '(1= 1, и ~в этой точке Х: чу(х)=~ ах (х),— ах (х),...,— ах (х) Р Р Матрицей Гессе А(Х ) функции У(Х) в точке Х называется симметрическая матрица размером и х п частных производных второго порядка функции ((Х) в точке Х: А.а )-(,,~х ~)-( — ~ — ~- <х'1~.
)„ах,.ах, Р Необходимое условие экстремума функции )".(Х) в точке Х имеет вид: ЧУ(Х)= О, или в скалярной форме: Р Точки Х, в которых выполняется (1.3), называются стационарными. Точка Х экстремума (минимума или максимума) обя- 6 х (а), (а) + О , (а) + О, (ь) 3 Т ® ') 2 х( ( + 2 + 3 = — х( + 011 + 212 + 1(3 = — 2х2 хз - 6, (а) (Й) (Й) (Й) (й) 01~'~+ 1«")+ 21~'~= — 2хро- х2)о ( 2 3 3 х2 Примем й= О. Подставляем в систему уравнений (1.14) значение Х „тогда система примет вид: (О) решив данную систему уравнений, получим Т( )= ( — 075; — 1; — 1). Поэтому Х()= Х()+ Т()= (1,25; — 4;2), ~~Х()~= — 11,7969. Выполнив аналогичные действия на ЗВМ, при й= 1 получим Т(~) = (- 0,225; 0; О), Х ( ) = (1,025; — 4; 2), У Х ( ) )= — 11,9981 и т.д.
вплоть до выполнения условия ~> ((()~ ь е при Й= 4. й ~2 ) )=$ Теперь применим метод градиентного спуска для нахождения минимума заданной функции ~(Х)= х(+ х2+ х3+ хвхз- Зх(+ бх2+ 2, 3 2 2 Выбираем Х = (2; — 3;3), е= 10 и й()= й= 0,2 для лю- (О) .. -4 й бого Й. При й = 0 получим 3(х(1 «) — 3 ,р~(Х(о«) 2х'О«+ х(О«+ 2 +из+ 1о« „ (о« ХЗ +Хг ~ ~ ~7у(Х1~«) Й = 9,9499, «".(Х(~«)= — 5. ~ ~ т,)(Х(~«')! ~ = 3,3428, ~(Х1~«)= — 10,1120. Выполнив аналогичные действия на ЗВМ, получим 0,776 — 1,1935 Х( «= — 3,84, ЧУ(Х( «)= 0,48 — 2,16 0,48 ~ ~ ~7,/'(Х1 «) ~ ~ = 1,3730, ~(Х1 «)= — 11,7839 и т.д. вплоть до выполнения условия (1.7) на итерации й= 12. Применим также методы наискорейшего спуска и сопряженных градиентов для поиска минимума заданной функции ~(Х) = х1+ хг+ хз+ хгхз — 3Х1+ бхг+ 2, 3 2 2 Выбираем Х(«= (2; — 3;3) и е= 10 Зх1 — 3 2 2хг+ хз+ 6 2Х,«+ хг Иаходим 7У(Х) = Согласно итерационной формуле для поиска минимума (см.
(1.6), (1.9) и (1.10)) Х(э+ 1«Х(э«й У~(Х(ь«) 2 9 0,2 определяем Х( «= — 3 — 0,2 3 = 3„6 . Тогда (1« 3 3 2,4 — 2,8 1гу(Х(1«) = ния, пропускная способность сети передачи данных. Требуемые значения Гг задаются в ТЗ. Кроме того, при необходимости ~(Х) может быть сформирована как функция нескольких выходных характеристик системы, не используемых в У(Х), в соответствии с уже рассмотренными способами нахождения обобщенного критерия оптимальности. Примеры задач первой группы: 1.1. Задача выбора количества х, (1= 1, и) устройств каждого типа (процессоров, модулей памяти, устройств ввода-вывода и т.д.) в вычислительной системе. При этом х; н 10, 1,2, ..., и«1, где и« вЂ” максимально возможное число устройств 1-го типа в системе.
1.2. Задача выбора каналов связи х, между пунктами з и 1 в сети передачи данных, где х, и ~0,1~ н О будет означать отсутствие в структуре сети соответствующего устройства или соединения, а 1 — наличие. Задачи 1.1 и 1.2 сводятся к задачам целочисленного линейного программирования, если в качестве «(Х) и у (Х) выбирай ются аддитивные функции числа устройств (стоимость, производительность, энергопотребление, габариты, масса). Если исходная функция мультипликативная, то ее можно свести к аддитивпой путем логарифмирования.
2. Задачи оптимизации вычислительной системы, рассматриваемой как система массового обслуживания, Часть этих задач формулируются в виде задач нелинейного программирования, другие сводятся к задачам дискретного и частично-дискретного программирования. Примером задачи этой группы служит синтез структуры памяти специализированной ЗВМ. 3. Задачи параметрической оптимизации. Они сводятся к задачам нелинейного программирования с непрерывными переменными, К ним относятся задачи параметрической оптимизации при функционально- логическом проектировании, например, задача расчета оптимальных значений внутренних параметров фрагментов БИС (задержек распространения сигналов и мощности рассеяния в фрагментах БИС). 4.
Задачи оптимизации на конструкторском (топологическом) уровне проектирования БИС, СВИС и печатных плат. Чаще всего это задачи коммутационно-монтажного проектирования, а именно компоновка, размещение и трассировка. Большинство из них сводится к задаче целочисленного линейного программирования. кая точка Х" н ХР, для которой при любом- Хн ХР выполняется ,) (Х ) ~,) (Х) . Для глобального максимуиа выполняется т" (Х ) > ~(х).
Точке в Е" соответствует и-мерный вектор. Точка Х н ХР называется локальныи минимумом функции ~(х) на множестве ХР~: Е", если существует е> О, при котором для всех Хя ХР, и таких, что ~ Х- Х ~ < е (т.е. для Х из еокрестности точки Х ), справедливо ) (Х )<,)(Х). Для локального максимумж т (Х ) > ((Х). Локальных минимумов и максимумов может быть несколько, а глобальный — только один. Задача нахождения шах ) (Х ) сводится к нахождению Х ш1в(- ((Х) ), т.е. достаточно изучить иетоды решения задачи по- Х иска минимума.
Типовые задачи оптимального проектирования ЭВМ, систем, сетей и ВИС Перечислим несколько групп типовых задач оптимального проектирования: $. Многие задачи выбора состава оборудования в вычислительных системах и сетях сводятся к задачам дискретного и целочисленного программирования: ех1г ((Х), Хв Х)) ХР= ~(Х~ У(Х) Ут, Х Р~, где Х= (х(,...,хз), У= (у(,... У ) Ъ'т= (ит( - ит„).
Вектор Х управляемых параметров определен на дискретном множестве Р или на множестве целых чисел, Значение Х может характеризовать количество элементов каждого типа в системе или сети, указывать на наличие или отсутствие каждого элемента и соединения в структуре системы или сети.
В качестве целевой функции ~(Х), а также каждой из функций ограничений р . (Х) 7 ) = «, «и) может выступать одна из выходных характеристик системы илн сети, например среднее время решения задачи в системе, вероятность отказа в решении, производительность системы, надежность системы нли сети, коэффициент загрузки оборудова- На итерации Ь= О, т.е. при нахождении Х ), оба метода сов- (О д -. - х"'= х"'- ь") чУ(х") ) Получаем '()',т" (Л ( ) ) = ( 9; 3; 3 ), ~ ~ 'г,т (Х ( ) ) ~ ~ = 9,9499, т" (Х ( ) ) = — 5 . Для определения оптимального шага Ь в направлении по- (О) иска минимума находим з (Ь (О) ) У(Х (1) ) У(Х (О) Ь (0) УУ(Х (О) ) ) 2 — 9Ь( ) — 3 — ЗЬ() 3 — ЗЬ (О) = (2- 9Ь()) + (- 3- ЗЬ()) + (3- Зь()) + +( )(-.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
