Учебно-методическое пособие для студентов специальности 1-36 20 02 «Упаковочное производство»
Download 4.96 Mb. Pdf ko'rish
|
|
19. КЛАССИФИКАЦИЯ МЕТОДОВ
Возможны два подхода к решению задачи отыскания минимума функции многих переменных f(x) = f(x 1 , ..., х n ) при отсутствии огра- ничений на диапазон изменения неизвестных. Первый подход ле- жит в основе косвенных методов оптимизации и сводит решение задачи оптимизации к решению системы нелинейных уравнений, являющихся следствием условий экстремума функции многих пе- ременных. Как известно, эти условия определяют, что в точке экс- тремума х * все первые производные функции по независимым пе- ременным равны нулю: 0 i f x x x , i = 1, …, n. Эти условия образуют систему п нелинейных уравнений, среди ре- шений которой находятся точки минимума. Вектор ( ) f x , составлен- ный из первых производных функции по каждой переменной, т. е. 1 ( ) ( ( ) , ..., ( ) ) , T n f x f x x f x x называют градиентом скалярной функции f(x). Как видно, в точке минимума градиент равен нулю. Решение систем нелинейных уравнений – задача весьма сложная и трудоемкая. Вследствие этого на практике используют второй подход к минимизации функций, составляющий основу прямых ме- тодов. Суть их состоит в построении последовательности векторов х[0], х[1], …, х[n], таких, что f(х[0]) > f(х[1]) > f(х[n])>… В качестве начальной точки x[0] может быть выбрана произ- вольная точка, однако стремятся использовать всю имеющуюся ин- формацию о поведении функции f(x), чтобы точка x[0] располага- лась как можно ближе к точке минимума. Переход (итерация) от точки х[k] к точке х[k + 1], k = 0, 1, 2, ..., состоит из двух этапов: 1) выбор направления движения из точки х[k]; 2) определение шага вдоль этого направления. 95 Методы построения таких последовательностей часто называют методами спуска, так как осуществляется переход от больших зна- чений функций к меньшим. Математически методы спуска описываются соотношением x[k + 1] = x[k] + a k p[k], k = 0, 1, 2, ..., где p[k] – вектор, определяющий направление спуска; a k – длина шага. В координатной форме 1 1 1 2 2 2 1 1 . ........................................... 1 k k n n k n x k x k a p k x k x k a p k x k x k a p k Различные методы спуска отличаются друг от друга способами выбора двух параметров – направления спуска и длины шага вдоль этого направления. На практике применяются только методы, обла- дающие сходимостью. Они позволяют за конечное число шагов по- лучить точку минимума или подойти к точке, достаточно близкой к точке минимума. Качество сходящихся итерационных методов оце- нивают по скорости сходимости. В методах спуска решение задачи теоретически получается за бесконечное число итераций. На практике вычисления прекраща- ются при выполнении некоторых критериев (условий) останова ите- рационного процесса. Например, это может быть условие малости приращения аргумента 1 x k x k e или функции 1 . f k f x k g 96 Здесь k – номер итерации; e, g – заданные величины точности решения задачи. Методы поиска точки минимума называются детерминирован- ными, если оба элемента перехода от х[k] к x[k + l] (направление движения и величина шага) выбираются однозначно по доступной в точке х[k] информации. Если же при переходе используется какой- либо случайный механизм, то алгоритм поиска называется случай- ным поиском минимума. Детерминированные алгоритмы безусловной минимизации делят на классы в зависимости от вида используемой информации. Если на каждой итерации используются лишь значения минимизируемых функций, то метод называется методом нулевого порядка. Если, кроме того, требуется вычисление первых производных минимизи- руемой функции, то имеют место методы первого порядка, при необходимости дополнительного вычисления вторых производных – методы второго порядка. В настоящее время разработано множество численных методов для задач как безусловной, так и условной оптимизации. Естествен- ным является стремление выбрать для решения конкретной задачи наилучший метод, позволяющий за наименьшее время использова- ния ЭВМ получить решение с заданной точностью. Качество численного метода характеризуется многими фактора- ми: скоростью сходимости, временем выполнения одной итерации, объемом памяти ЭВМ, необходимым для реализации метода, клас- сом решаемых задач и т. д. Решаемые задачи также весьма разнооб- разны: они могут иметь высокую и малую размерность, быть унимо- дальными (обладающими одним экстремумом) и многоэкстремаль- ными и т. д. Один и тот же метод, эффективный для решения задач одного типа, может оказаться совершенно неприемлемым для задач другого типа. Очевидно, что разумное сочетание разнообразных ме- тодов, учет их свойств позволят с наибольшей эффективностью ре- шать поставленные задачи. Многометодный способ решения весьма удобен в диалоговом режиме работы с ЭВМ. Для успешной работы в таком режиме очень полезно знать основные свойства, специфику методов оптимизации. Это обеспечивает способность правильно ори- ентироваться в различных ситуациях, возникающих в процессе рас- четов, и наилучшим образом решить задачу. |
