Метод оценочных функций

из "Введение в теорию, методы и экономические предложения задач о дополнительности "

Гораздо сложнее построить оценочную функцию, которая обладала бы рядом свойств, полезных в вычислительном отношении. В частности, только что приведенные в качестве примера функции такими свойствами не обладают, — уже отмечалось, что д(х), вообще говоря, не является гладкой и даже не имеет конструктивно очерченной области определения вторая из приведенных функций, хотя и может считаться гладкой, порождает задачу, найти точки глобального оптимума которой достаточно сложно. [c.57]
Рассмотрим некоторые из известных оценочных функций, обладающих перечисленными свойствами. [c.57]
Очевидно, что оптимальное значение задачи (6.2) не положительно. [c.58]
Следующая теорема устанавливает эквивалентность этой задачи задаче решения вариационного неравенства VI(X,F). [c.58]
Теорема 6.1. Пусть функция М0(х) определена в соответствии с (6.3). Тогда М0(х) 0 при всех х X и М0(х) = 0 тогда и только тогда, когда х — решение задачи VI(X,F). [c.58]
Так как aF(x) совпадает с расстоянием между х и х— aF(x), a H(x)—x+aF(x) — с расстоянием между х — aF(x) и проекцией этой точки на X, то М0(х) О при всех х е X. Более того, определение Н(х) подразумевает, что эти расстояния равны, только если х = Н(х). Последнее имеет место в случае, когда х — решение задачи VI(X, F). [c.58]
Теорема 6.1 не накладывает особых условий на то, какими должны быть отображение F и функция М0. Однако практические соображения требуют, чтобы последняя обладала рядом полезных вычислительных свойств. К счастью, оказывается, что если X — непустое выпуклое замкнутое множество, то функция М0 непрерывно дифференцируема, если дифференцируемо отображение F. [c.59]
Формула (6.5) следует отсюда с учетом (6.6). [c.59]
Взглянем на связь задачи (6.4) с задачей решения вариационного неравенства VI(X, F) более пристально. Теорема 6.1 говорит, что решение VI(X, F) сводится к отысканию точек глобального оптимума в (6.4). Но поскольку функция М0, вообще говоря, не выпукла, задача (6.4) может иметь точки локального минимума и стационарные точки, которые не являются точками глобального минимума. К счастью, перечисленные трудности исчезают в случае, когда отображение F непрерывно дифференцируемо и матрица V F(x) положительно определена при всех х е X, т. е. ут V F(x)y 0 Vy е R , Уж е X. [c.59]
Теорема 6.3. Пусть X — непустое выпуклое замкнутое подмножество Rn, отображение F Rn — Rn непрерывно дифференцируемо и матрица Якоби V F(x) положительно определена при всех х Е X. Если х — стационарная точка в задаче (6.4), от. е. [c.59]
Таким образом, (Н(х) — x)1 VF(x) (Н(х) — х) О, что, в силу положительной определенности матрицы Якоби, влечет равенство х — Н(х) = О, т. е. х действительно оказывается решением VI(X, F), а значит, по теореме 6.1 и точкой глобального оптимума в задаче (6.4). [c.60]
Поскольку соотношение (6.8) не содержит V F(x), вектор d может быть определен с гораздо меньшими вычислительными затратами по сравнению с градиентным направлением VM0, особенно в случаях, когда вычисление матрицы VF затруднено. Следующее утверждение показывает, что при условии монотонности F вектор d, задаваемый соотношениями (6.8), действительно является направлением спуска функции М0 в точке х. [c.60]
Следующая теорема устанавливает глобальную сходимость алгоритма, использующего направление спуска d = Н(х)—х вкупе с точным правилом линейного поиска. [c.61]
Предположим также, что X — выпуклый компакт и отображение F Rn — Rn непрерывно дифференцируемо, причем матрица V F(x) положительно определена при всех х е X. Тогда независимо от начального приближения х° е X последовательность xk лежит в X и сходится к х — единственному решению задачи VI(X,F). [c.61]
Доказательство. Заметим вначале, что непрерывность отображения F вместе с условием компактности X гарантирует разрешимость задачи VI(X, F), а условие положительной определенности матрицы V F(x) — единственность ее решения. [c.61]
так как tk е [О, 1] и множество X — выпукло, то из включений xk e X, H(xk) = xk + dk e X следует, что xk+l е X. Но х° е X, и потому вся последовательность xk лежит в X. Следовательно, любая предельная точка х этой последовательности также лежит в X. [c.61]
Полученное строгое неравенство и очевидная монотонность последовательности значений M0(xk) противоречит ограниченности последней снизу. [c.62]
Рассмотренный метод тесно связан с методом простой итерации из 3 данной главы, поскольку и там и здесь участвует одно и то же направление d = Н(х) — х. Однако в методе простой итерации параметр а О постоянен и не связан с минимизацией какой бы то ни было функции. [c.62]
В заключение раздела приведем (без подробного анализа вычислительных свойств) две другие функции оценки, предназначенные для сведения нелинейной задачи о дополнительности N P(F) к обычной задаче безусловной оптимизации типа тшМ(ж). [c.62]

Вернуться к основной статье