Градиентные методы оптимизации

Задачи оптимизации с нелинейными или трудно вычислимыми соотноше­ниями, определяющими критерий оптимизации и ограничения, являются предметом нелинейного программирования. Как правило, решения задач не­линейного программирования могут быть найдены лишь численными мето­дами с применением вычислительной техники. Среди них наиболее часто пользуются градиентными методами (методы релаксации, градиента, наиско­рейшего спуска и восхождения), безградиентными методами детерминиро­ванного поиска (методы сканирования, симплексный и др.), методами случай­ного поиска. Все эти методы применяются при численном определении опти-мумов и достаточно широко освещены в специальной литературе.

В общем случае значение критерия оптимизации R может рассматри­ваться как функция R (х_ь хь..., х_п), определенная в л-мерном пространстве. Поскольку не существует наглядного графического изображения я-мерного пространства, воспользуемся случаем двумерного пространства.

Если R (л_ь х₂) непрерывна в области D, то вокруг оптимальной точки M°(xi°, х_г°) можно провести в данной плоскости замкнутую линию, вдоль ко­торой значение R = const. Таких линий, называемых линиями равных уровней, вокруг оптимальной точки можно провести множество (в зависимости от шага

Среди методов, применяемых для решения задач нелинейного програм­мирования, значительное место занимают методы поиска решений, основан­ные на анализе производной по направлению оптимизируемой функции. Если в каждой точке пространства скалярная функция нескольких переменных принимает вполне определенные значения, то в данном случае имеем дело со скалярным полем (поле температур, поле давлений, поле плотностей и т.д.). Подобным образом определяется векторное поле (поле сил, скоростей и т.д.). Изотермы, изобары, изохроны и т.д. — все это линии (поверхности) равных уровней, равных значений функции (температуры, давления, объема и т.д.). Поскольку от точки к точке пространства значение функции меняется, то ста­новится необходимым определение скорости изменения функции в простран­стве, то есть производной по направлению.

Понятие градиента широко используется в инженерных расчетах при на­хождении экстремумов нелинейных функций. Градиентные методы относятся к численным методам поискового типа. Они универсальны и особенно эффек­тивны в случаях поиска экстремумов нелинейных функций с ограничениями, а также когда аналитическая функция неизвестна совсем. Сущность этих мето­дов заключается в определении значений переменных, обеспечивающих экс­тремум функции цели, путем движения по градиенту (при поиске max) или в противоположном направлении (min). Различные градиентные методы отли­чаются один от другого способом определения движения к оптимуму. Суть заключается в том, что если линии равных уровней R{xu ^xi) характеризуют графически зависимость R(x\jc?), то поиск оптимальной точки можно вести по-разному. Например, изобразить сетку на плоскости х\, хг с указанием зна­чений R в узлах сетки (рис. 2.13).

Затем можно выбрать из узловых значений экстремальное. Путь этот не рациональный, связан с большим количеством вычислений, да и точность не­велика, так как зависит от шага, а оптимум может находиться между узлами.

Численные методы

Математические модели содержат соотношения, составленные на основе теоретического анализа изучаемых процессов или полученные в результате обработки экспериментов (таблиц данных, графиков). В любом случае мате матическая модель лишь приближенно описывает реальный процесс. Поэтом} вопрос точности, адекватности модели является важнейшим. Необходимости приближений возникает и при самом решении уравнений. До недавних пор модели, содержащие нелинейные дифференциальные уравнения или диффе ренциальные уравнения в частных производных, не могли быть решены ана литическими методами. Это же относится к многочисленным классам небе рущихся интегралов. Однако разработка методов численного анализа позво лила необозримо раздвинуть границы возможностей анализа математических моделей, особенно это стало реальным с применением ЭВМ.

Численные методы используются для приближения функций, для реше ния дифференциальных уравнений и их систем, для интегрирования и диффе ренцирования, для вычисления числовых выражений.

Функция может быть задана аналитически, таблицей, графиком. При вы полнении исследований распространенной задачей является приближение функции аналитическим выражением, удовлетворяющим поставленным уело виям. При этом решаются четыре задачи:

• выбор узловых точек, проведение экспериментов при определен­ных значениях (уровнях) независимых переменных (при непра­вильном выборе шага изменения фактора либо «пропустим» ха­рактерную особенность изучаемого процесса, либо удлиним про­цедуру и повысим трудоемкость поиска закономерности);

• выбор приближающих функций в виде многочленов, эмпириче­ских формул в зависимости от содержания конкретной задачи (следует стремиться к максимальному упрощению приближающих функций);

• выбор и использование критериев согласия, на основе которых на­ходятся параметры приближающих функций;

• выполнение требований заданной точности к выбору приближаю­щей функции.

В задачах приближения функций многочленами используются три класса

функций:

• линейная комбинация степенных функций (ряд Тейлора, много­члены Лагранжа, Ньютона и др.);

• комбинация функций соз пх, ш их (ряды Фурье);

• многочлен, образуемый функциями ехр (-а, г).

При нахождении приближающей функции используют различные крите­рии согласия с экспериментальными данными:

• точное совпадение значений функций с экспериментом в узловых точках (параболическое приближение);

минимум квадратов отклонений значений приближающей функ­ции от эксперимента в узловых точках (метод наименьших квадра­тов);

• минимум максимального отклонения (равномерное, чебышевское приближение).

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

АППРОКСИМАЦИЯ ФУНКЦИЙ

Аппроксимация — приближенное выражение математических величин (чисел, функций и др.) через другие, более простые. Известно, что аппрокси­мация непрерывной на отрезке хе [а,Ь] функции алгебраическими или триго­нометрическими многочленами Р(х) возможна с любой степенью точности) теорема Вейерштрасса). Мерой точности служит максимум разности между Ах) и Р(х):

5«тах|/(х)-/»00|.

В приближенных вычислениях и при оценке погрешностей используется понятие дифференциала. Применяются формулы

Дх₀ + Ах) ш Дх₀) +/'(х₀) Ах

или Д* + Дх, у + Ау) - Д*о, у₀) + -+- (х₀, у₀) Ах+^- (х₀, у₀) Ау. (3.1)

дх ду

Для решения уравнений применяют метод итераций или метод последова­тельных приближений.

Метод итераций является одним из самых общих методов приближенного решений уравнений. Многие другие способы — частные случаи метода итера­ций. Задача решения уравнения Дх) = 0 равносильна отысканию точек, в кото­рых график функции у = Дх) пересекает ось абсцисс.

Метод хорд состоит в последовательном приближении к значению X, яв ляющемуся точным решением Дх) = 0 путем расчетом по формулам

Пример 55.

Решить по методу Ньютона уравнение лг - Зх - 5 = 0 с точностью до 0,001, приняв за первое приближение х₀ = 3.

Решение.

Производной х^ъ - Зх - 5 =Дх) является/ \х) = Зх² - 3.

По формуле (3.6) х_п+1 -х„-(х„³-Зх„ -5)/(Зх,,² -3) рассчитываем

х, = 3 - (27 - 9 - 5) / (27 - 3) = 2,46;

х₂ = 2,46 - (14,89 - 7,38 - 5) / (18,16 - 3) = 2,295;

х₃ = 2,295 - (12,088 - 6,885 - 5) / (15,801 - 3) = 2,279;

х₄ = 2,279 - (11,837 - 6,807 - 5) / (15,582 - 3) = 2,279.

Таким образом, с точностью до 0,001 выполняется равенство х₄ = х₃ и по­этому корень уравнения х³ - Зх - 5 = 0 равен 2,279 (с указанной точностью).

Значительное место в разделе аппроксимации функций занимает приближение функций степенным рядом Тейлора