Курсовая работа: Программная модель поиска глобального минимума нелинейных "овражных" функций двух переменных

Квадратичные одноэкстримальные функции (1.2) принадлежат к более широкому классу строго выпуклых функций. Функция f(x) называется строго выпуклой, если для любых точек х1 и х2 из области ее определения имеет место неравенство:

F(lx1+(1-l)x2)< lf(x1)+(1-l)f(x2), lÎ(0,1).

Строго выпуклые функции унимодальные и обладают достоинством, облегчающим исследование и процесс численной минимизации, - это строгая выпуклость, а следовательно, одноэкстримальность вдоль любого направления. Более широким классом является класс линейно унимодальных функций [3]. Характерное свойство этого множества – унимодальность функций вдоль любой прямой в допустимой области. Функции, унимодальные по любому направлению, если это направление происходит через точку минимум, образуя класс строго унимодальных функций [3].

На рисунке 2 представлены : А – строго выпуклая; Б – линейно-унимодальная; В – строго унимодальная функции.

Специфика каждого из описанных классов может быть использована при построении методов минимизации.

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

В начале 60-х годов И.М. Гельфондом и М.Л. Цетлиным [4] был дескриптивно задан класс невыпуклых функций многих переменных. Элементы класса характеризуются следующей структурой: в любой точке некоторого подмножества области определения функции существует такой базис, что все независимые переменные можно разделить на две группы. Первая группа состоит из тех аргументов, изменение которых приводит к значительному изменению целевой функции (в [4] они названы несущественными переменными). Изменение переменных второй группы (существенных переменных) приводит к незначительному изменению функции. При этом для любой точки подмножества вторая группа содержит лишь небольшое число параметров. Функция, допускающая такое разбиение переменных в некоторой области, называется хорошо организованной (овражной) функцией в этой области, а число существенных переменных определяет размерность оврага [4]. Иными словами, для овражной функции точность линейного приближения

f(x) + Ñf(x) * Ñx в значительной степени зависит от Ñx [5].

В математическом энциклопедическом словаре под редакцией Ю.В. Прохорова дано строгое определение овражной функции.

Пусть «ограниченная снизу функция многих переменных

J * (x) = J(x1, x2, …, xm) Î c²(D), DÌR,

обладает той особенностью, что в исследуемой области собственные значения матрицы Гессе

, i, j = 1, 2, …, m,

упорядоченные в любой точке xÎD, удовлетворяют неравенствам

0 < |minli(x) | << l1(x).

В этом случае поверхность уровня J(x)=const имеют структуру, сильно отличающуюся от сферической. Такие функции J(x) называются овражными. Степень овражности характеризуется числом

S = l1(x) / |minli(x) |, li(x) ╪ 0.

Если собственные значения удовлетворяют неравенствам |lm(x)| <= … <= |lm-r+1(x)| << lm-r(x) << l1(x) , а отношение | lm-r+1(x) | / | lm(x) | невелико, то число r называется размерностью оврага.»

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

«Конечно, такое разбиение параметров невозможно для любой функции, которую мог бы задать математик. Однако, для функций, встречающихся в практической деятельности человека (здесь имеются в виду разумные задачи физики, техники), такое разбиение, по-видимому, имеет место в очень значительном числе случаев.» [4]

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

Простейшим примером овражной функции является квадратичная функция (1.2), где А – плохо обусловленная матрица. Число обусловленности симметрической матрицы является важной характеристикой ее свойств и определяется через собственные значения: k(A)=maxlA / minl4. Если k(A) велико, то А представляет собой плохо обусловленную матрицу, а задача (1.2) называется плохо обусловленной задачей минимизации. В этом случае f(x) определяет многомерную поверхность прямым (неизогнутым) оврагом.

Для неквадратичных функций вводится обобщение этого определения [6]: обусловленностью точки минимум х называется число

m = lim(sup||x-x’||²(inf||x-x’||²), xÎL, L = {x:f(x)=f(x’)+d}.

Если m велико, функция имеет овражный характер.

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

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