Дипломная (вкр): Оптимизационные методы оценки кредитоспособности предприятий

где ,  [18].

1.4.3 Сильно выпуклые функции

Непрерывная выпуклая функция на выпуклом замкнутом множестве может не достигать своей нижней грани на этом множестве. Например, если , , , но  при всех . Однако можно выделить подкласс выпуклых функций, для которых подобная ситуация невозможна [18].

Определение. Функция , определённая на выпуклом множестве , называется сильно выпуклой на , если существует постоянная  такая, что

при всех и всех , . Постоянную  называют постоянной сильной выпуклости функции  на множестве  [18].

Замечание. Очевидно, сильно выпуклая на  функция будет выпуклой и даже строго выпуклой на . Примером сильно выпуклой функции на всем пространстве  может служить функция [18]

,  

Теорема. Пусть  - выпуклое множество, . Тогда для сильной выпуклости  на  необходимо и достаточно существования константы  такой, что

(1.5)

При всех  и всех , принадлежащих под-пространству, параллельному аффинной оболочке множества (если , то (9) выполняется при всех ) [18].

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

, ,

были положительны.

.5 Метод Ньютона для оптимизации функций

Среди основных проблем вычислительной математики можно отметить задачи минимизации (максимизации) функций многих переменных (задачи оптимизации). Поиск минимума часто проводится при некоторых дополнительных ограничениях - условная оптимизация. Для численного решения таких задач используются итерационные методы [2], [18].

1.5.1 Метод Ньютона для нахождения экстремумов

Пусть  - числовая ось,  - некоторое множество из ,  - функция, определённая на множестве  и принимающая во всех точках  конечные значения. Примерами множеств из  являются: отрезок , интервал , полуинтервалы , , где  - заданные числа. Будем рассматривать задачу минимизации функции  на множестве .

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

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

Определение. Последовательность  называется минимизирующей для функции  на множестве , если

.

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

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

Заметим, что верхняя грань и минимизировать последовательность всегда существуют, а минимальное значение может не существовать. Если выполнены условия теоремы 1, то , , и любая минимизирующая последовательность  сходится .

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

Пусть  - некоторое начальное приближение. Если известно -е приближение , то приращение функции  в точке  можно представить в виде

(1.6)

Возьмём квадратичную часть этого приращения

, (1.7)

и определим вспомогательное приближение  из условий=

,(1.8)

Следующее -е приближение будем искать в виде

, (1.9)

В зависимости от способа выбора величины  в (4) можно получить различные варианты метода (1.7) - (1.9), называемого методом Ньютона. Укажем несколько наиболее употребительных способов выбора .

) В (1.9) можно принять

, (1.10)

В этом случае, как следует из (1.9), , , т.е. условие (1.8) сразу определяет следующее -е приближение. Иначе говоря,

, , (1.11)

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

(1.12)

Это значит, что на каждой итерации метода (1.7) - (1.10) или (1.11) нужно решать линейную алгебраическую систему уравнений (1.12) относительно неизвестной разности . Если матрица этой системы  - невырожденная, то из (1.12) имеем

, (1.12)

Широко известный метод Ньютона для решения системы уравнений

, ,

представляет собой итерационный процесс [18].

, (1.13)

Где  - матрица, -я строка которой равна .

Теорема: Пусть  - сильно выпукла на ,  и. кроме того

, , .(1.14)

Пусть начальное приближение  выбрано таким, что

(1.15)

где  - постоянная, а - некоторая константа . Тогда последовательности , определяемая условиями (1.12), существует, сходится к точке  минимума  на , причем справедлива оценка

, (1.16)

Как видно из оценки (14) и как показывает практика, метод Ньютона (1.12) сходится очень быстро. Однако у него есть существенный недостаток: для него сходимости начальная точка  должна выбираться достаточно близкой к искомой точке . Это требование в теореме 1 выражено условием (1.15), означающим, что .