full_book

ННГУ. Учебный курс «Модели и методы конечномерной оптимизации». Часть 2. Нелинейное программирование и многоэкстремальная оптимизация.

близкий к ε-оптимальному методу Фибоначчи ([46], а также [8] и [48]). Однако во многих задачах локальной оптимизации функции ϕ(x) являются достаточно гладкими, что позволяет применять к поиску минимума алгоритмы, основанные на построении квадратичных аппроксимаций ϕ(x) по результатам ее измерений. Такие методы называют квазиньютоновыми Известно, что при определенных условиях они способны обеспечить скорость сходимости более высокого порядка, чем метод золотого сечения. Если же условия их сходимости будут нарушены, то такие методы могут расходиться.

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

РЕГУЛЯРИЗОВАННАЯ ПРОЦЕДУРА ОДНОМЕРНОГО ПОИСКА состоит в следующем.

ШАГ 0. Полагаем A=0, B=X, τ = (-1+51/2)/2, 0<δ < τ .

ШАГ 1. Выполняем три вычисления по методу золотого сечения:

ШАГ 1.1. Вычисляем x1 = B - (B-A) τ, x2 = A+τ (B-A) и ϕ1 =ϕ(x1), ϕ2 =ϕ(x2). ШАГ 1.2. Если ϕ1≤ϕ2, то полагаем B = x2 и x3 = B – (B–A)x, ϕ3 =ϕ(x3). При

ϕ1≤ ϕ3 полагаем A=x3, x=x1, иначе B = x1, x = x3. Если ϕ1 > ϕ2, то полагаем A=x1 и x3 =A+(B-A) τ, ϕ3 =ϕ(x3). При ϕ2 >ϕ3, полагаем A=x2, x=x3, иначе B=x3, x=x2.

В результате выполнения шага 1 получаем три точки с вычисленными значениями функции, а также интервал [A,B] с расположенной внутри него точкой x, соответствующей лучшему вычисленному значению функции.

ШАГ 2. Определяем u — точку измерения функции по квазиньютоновскому правилу. А именно, u определяется как точка минимума квадратичной аппроксимации функции ϕ(x), построенной по значениям x1,ϕ1; x2,ϕ2; x3,ϕ3:

u = ( -ϕ1(x32-x22)+ϕ2(x32-x12) - ϕ3(x22-x12) )/( 2(ϕ1(x3-x2) - ϕ2(x3-x1)+ϕ3(x2-x1)) ).

ШАГ 3. Определяем ν — точку измерения функции по правилу золотого сечения

A + (x − A)τ при x > (A + B)/ 2

ν= B − (B − x)τ при x < (A + B)/ 2 .

незначительно уклоняется от середины отрезка [A,B], то в качестве точки нового измерения выбирается точка w = u, однако, чтобы предотвратить ее слишком близкое размещение к точке прежнего измерения x, ее положение корректируется

Если же u не принадлежит указанному интервалу, полагаем w = ν.

ШАГ 5. Вычисляем ϕw = ϕ(w). Проверяем, принадлежит ли w множеству Π из (7.13). Если она принадлежит, или же достигнут предельный уровень сжатия интервала, т.е. |B–A|<σX, то переходим на шаг 7, если нет, переходим на шаг 6.

ШАГ 6. Через y обозначим левую из точек w, x , (а через ϕy соответствующее ей значение функции), через z - правую из точек w, x (а через ϕz - соответствующее значение функции). Если ϕy ≤ϕz, то полагаем B=z, x=y. Если ϕy >ϕz, то полагаем A=y, x=z. Выделяем из точек x1,x2,x3,w три точки с наименьшими значениями функции и обозначаем их через x1,x2,x3, а соответствующие им значения функции — через ϕ1,ϕ2,ϕ3. Переходим на шаг 2.

ННГУ. Учебный курс «Модели и методы конечномерной оптимизации». Часть 2. Нелинейное программирование и многоэкстремальная оптимизация.

ШАГ 7. Выполняем завершающие операции: вычисляем ϕ(x) на концах интервала [A,B], в качестве xk выбираем ту из трех точек w, A, B, где достигается меньшее значение функции ϕ, останавливаем поиск.

7.3. Аппроксимационные принципы построения алгоритмов. Анализ свойств классического градиентного метода и метода Ньютона

Прежде чем перейти к изучению эффективных методов поиска локальнооптимальных решений, следует рассмотреть простейшие классические методы. К ним следует отнести градиентные методы и метод Ньютона [1,4–6,8,10].

Идея градиентного метода была высказана О. Коши в середине XVIII века, но еще в 40-ые годы XX века градиентные методы представлялись вполне достаточным средством практического решения задач.

Градиентные методы предельно просты. Их можно описать общим итерационным соотношением (7.5), имеющим вид y k+1=y k+x kd k, где направление смещения из точки y k совпадает с направлением антиградиента d k= - f k.

В этом направлении дифференцируемая функция f(y) локально (в бесконечно малой окрестности точки y k) убывает быстрее всего, т.к. производная ∂ f(y k)/∂v k функции f в точке y k, вычисленная в некотором направлении v k (||v k||=1), может быть представлена в виде скалярного произведения ∂ f(y k)/∂ v k=( f(y k),v k), которое достигает своего минимума именно в направлении антиградиента.

Заметьте, что в общем случае направление антиградиента в точке y k не совпадает с направлением на локальный минимум (рис.7.3). Более того, это направление не инвариантно по отношению к растяжениям пространства переменных.

Рис.7. 3. Отличие направления антиградиента от направления на локальный минимум

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

(метод наискорейшего градиентного поиска). Приведем правило выполнения шага в этом методе в том случае, когда в задаче оптимизации отсутствуют ограничения–неравенства из (7.2), то есть допустимая область Y=D (общие принципы учета ограничений–неравенств рассмотрены в разделе 7.6). Применительно к этой задаче в методе наискорейшего градиентного поиска величина одномерного смещения x k определяется из условия

ННГУ. Учебный курс «Модели и методы конечномерной оптимизации». Часть 2. Нелинейное программирование и многоэкстремальная оптимизация.

Таким образом, x — величина, определяющая смещение вдоль d k, выбирается из условия достижения минимума функции f в области Y на луче y k+xd k, где x≥ 0. С вычислительной точки зрения правило (7.15) реализуется методом аккуратного одномерного поиска, описанным в пункте 7.2.4.

На градиентные методы можно также посмотреть с несколько иных позиций, а именно с позиций тех представлений о поведении минимизируемой функции, на которых основано правило выбора направления поиска. Градиентные методы основаны на локальной линейной модели функции f(y) в окрестности точки yk последнего испытания. Именно для линейной модели функции направление антиградиента является наилучшим с точки зрения задачи поиска минимума (для квадратичной модели это уже не так). Заметим, что методом используется не только локальная линейная модель. Выбор величины смещения по правилу (7.15) неявно предполагает нелинейность функции, особенно в задаче без ограничений.

В случае двух переменных правила поиска в методе наискорейшего градиентного поиска иллюстрирует рис.7.4. Следует заметить, что направления поиска на двух последовательных шагах d k и d k+1 взаимно ортогональны, если решение вспомогательной задачи (7.15) достигается во внутренней точке допустимой области.

Сходимость процедур градиентного поиска может быть доказана при достаточно слабых предположениях о функции, минимум которой ищется. Одна из теорем о сходимости для случая использования метода при отсутствии ограничений (когда D = RN) имеет следующую формулировку.

Рис.7. 4. Наискорейший градиентный поиск

Теорема 7.1. Пусть в задаче (7.4) функция f(y) непрерывно дифференцируема, ограничена снизу и ее градиент удовлетворяет условию Липшица с некоторой

наискорейшего градиентного поиска для любой начальной точки y0 строит последовательность yk такую, что || f (y k)||→ 0 при k→∞.

ННГУ. Учебный курс «Модели и методы конечномерной оптимизации». Часть 2. Нелинейное программирование и многоэкстремальная оптимизация.

ДОКАЗАТЕЛЬСТВО [39] проведем следующим образом. Рассмотрим точки, лежащие на луче, порожденном направлением антиградиента y(x) = y k – x f (y k). И сделаем верхнюю оценку для приращения функции, используя некоторую промежуточную точку θ [y(x) – y k ],

± f ( y k )

f( y(x)) − f ( yk ) = ( f (θ) , y(x) − yk ) = ( f (θ) − f ( yk ) , y(x) − yk ) +

+( f ( yk ) , y(x) − yk ) ≤ x2 L f ( yk ) 2 − x f ( yk ) 2 = ϕ(x).

ограниченности снизу, получаем, что f ( yk+1 ) − f ( yk ) → 0 при k → ∞, но тогда из

предыдущего неравенства || f (y k)||→ 0 при k→∞. Теорема доказана.

При определенных дополнительных предположения относительно функции f из утверждения теоремы будет следовать сходимость yk к точке минимума y*.

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

с положительно определенной матрицей Г (т.е. строго выпуклых).

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

Теорема 7.2. Для квадратичной функции (7.16) с симметричной положительно определенной матрицей метод наискорейшего градиентного поиска сходится со скоростью геометрической прогрессии со знаменателем, не превосходящим значения q. При этом справедливы следующие оценки

a=a(y0), T>0 : 0 ≤ a ≤ q = (λmin/λmax–1)2/(λmin/λmax+1)2, f(y k) - f(y*) ≤ a k(f(y0) – f(y*)),

||yk– y*|| ≤ T a k/2||y0–y*||,

где λmin и λmax — минимальное и максимальное собственные числа матрицы вторых производных Гf =Г.

ДОКАЗАТЕЛЬСТВО теоремы можно найти в книге [10], здесь мы ограничимся его кратким изложением. Не снижая общности, будем считать, что в выражении для квадратичной функции (7.16) значение c=0.

Вначале получим оценку для q. Для этого достаточно исследовать один шаг алгоритма, поскольку остальные будут подобны первому. Пусть задана начальная точка y0. Найдем величину смешения x1 на шаге. Введем обозначение r = f(y0). Из условия достижения минимума вдоль направления –r имеем (при c=0)

f ( y0 − x1r) = Γ ( y0 − x1r) = r − x1Γr = 0 .

ННГУ. Учебный курс «Модели и методы конечномерной оптимизации». Часть 2. Нелинейное программирование и многоэкстремальная оптимизация.

Умножая последнее равенство скалярно на r, выразим значение x1=(r,r)/(r, Г r). Отсюда уже несложно показать, что f(y1)=f(y0) – 0,5(r,r)2/(r,Г r), и, учитывая что при c=0 f(y *)=0, получить выражение

( f ( y0 ) − f ( y* ))( f ( y0 ) − f ( y1 )) = 2( f ( y0 ) − f ( y* ))(r,Γr)(r,r)2 = = ((r,Γ−1r)(r,Γr))(r,r)2 .

Оценим его сверху, считая временно, что вектор r произволен. Представляя матрицу Г в виде разложения Г=RTD R с ортогональной матрицей R и диагональной матрицей D с элементами λ i на диагонали. Выполняя замену z=R r, получим

((r,Γ−1r)(r,Γr))(r,r)2 = ((z, D−1 z)(z, D z))(z, z)2 = Λ(α)Μ(α) ,

где Λ(α) = ∑λi−1αi , Μ(α) = ∑λiαi , αi = zi2 ∑z2j .

j

Рассмотрим на плоскости переменных Λ, Μ область Q в виде выпуклой линейной оболочки семейства точек

Q = L((λmin ; λ−min1 ),..., (λmax ; λ−max1 )).

Найдем верхнюю оценку C произведения Λ(α) Μ(α), аналитически решив экстремальную задачу

C = max { Λ(α) Μ(α): α ≥ 0, α =1 } = max { Λ Μ: (Λ;Μ) Q }.

Из геометрического вида множества Q понятно, что решение находится в точке верхней части его границы. Записывая систему условий Куна–Таккера

( f ( y0 ) − f ( y* ))( f ( y0 ) − f ( y1 )) ≤ C

или

( f ( y1 ) − f ( y* )) ≤ ((C −1)C)( f ( y0 ) − f ( y* ))

Отсюда видим, что q = ((C −1)C)= ((λmin / λmax −1)(λmin / λmax +1))2 . Требуемое выражение получено.

Чтобы получить оценку по координате полезно заметить, что квадратичная функция с λmin>0 является сильно выпуклой (см. определение 1.10 пункта 1.4.1.1) со значением параметра сильной выпуклости ρ = 0,5λmin (по свойству 1.8′ ). Используя свойство сильной выпуклости (а именно — следствие 1.7′.2) и полученную оценку для ошибки по значению функции, приходим к неравенству

||yk– y*||≤ ( (f(y k) - f(y*))/ρ)1/2≤ a k/2( (f(y0) – f(y*))/ρ)1/2.

Представляя начальную разность (f(y0) – f(y*)) в виде разложения в окрестности y* и оценивая сверху его квадратичный член, получим (f(y0) – f(y*))≤ λmax||y0–y*||2. Эти две оценки вместе дают нужное неравенство для ошибки по координате при

T = (2λmax λmin )12 . Теорема доказана.

Из оценок теоремы 7.2 следует, что конечная сходимость из любой начальной точки y0 возможна только при q=0 (λmin=λmax), когда поверхности равного уровня функции f являются сферами.

ННГУ. Учебный курс «Модели и методы конечномерной оптимизации». Часть 2. Нелинейное программирование и многоэкстремальная оптимизация.

Рис.7. 5. Влияние масштабирования на скорость сходимости наискорейшего градиентного поиска

Если же поверхности равного уровня сильно вытянуты (рис.7.5), что соответствует λmin<<λmax, то значение q в оценке скорости сходимости будет близко к единице, и скорость сходимости к решению может оказаться чрезвычайно низкой, за исключением точек y0, лежащих на главных осях эллипсоидов f(y)=const (в этих точках a(y0)=0).

Таким образом, высокая скорость сходимости градиентного метода может быть обеспечена только за счет предварительного масштабирования задачи, т.е. выполнения такой замены переменных y=Cz, которая приводила бы (в новых переменных) к выполнению условия λmin≈λmax.

Как уже отмечалось выше, направление антиградиента не инвариантно по отношению к линейным заменам переменных. Если выполнен переход к переменным z: y=Cz (где C — матрица преобразования), то градиент функции в новых переменных z может быть вычислен как

То же правило пересчета сохраняется, очевидно, и для антиградиента. Если перевести антиградиентное направление, вычисленное в пространстве z, в направление в пространстве старых переменных y, то получим скорректированное направление поиска

Действительно, пусть в точке y k для f(y) измерено значение f k, градиент f k и матрица вторых производных Гkf= Г. В силу равенства нулю всех производных выше второго порядка f(y) из (7.16) совпадает со своей квадратичной

откуда y*–yk=(Гkf)–1(– f(yk)). Сравнивая полученное направление с направлением

(7.18), видим, что в качестве матрицы преобразования в (7.18) можно использовать CC T = (Гk f)–1.

Если бы f(y) была произвольной дважды непрерывно дифференцируемой функцией, то в (7.19) квадратичная аппроксимация P k(y) уже не совпадала бы с исходной функцией, а условие (7.20) определяло бы лишь стационарную точку

ННГУ. Учебный курс «Модели и методы конечномерной оптимизации». Часть 2. Нелинейное программирование и многоэкстремальная оптимизация.

для этой аппроксимации. Если именно в этой точке проводить очередное измерение локальных характеристик функции f (значения, градиента и матрицы вторых производных), приняв ее за yk+1 , получим классический метод Ньютона, имеющего вид итерационного соотношения

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

На метод Ньютона можно посмотреть с другой точки зрения. А именно, правило итерации (7.21) основано на использовании квадратичной модели поведения функции f(y), минимум которой ищется. Использование квадратичной модели приводит к отказу от использования направления антиградиента функции и применению вместо него скорректированного антиградиентного направления, приводящего в результате шага в стационарную точку текущей квадратичной аппроксимации функции.

Геометрическая интерпретация правила выбора направления поиска в методе Ньютона для выпуклой квадратичной функции приведена на рис.7.6.

Рис.7. 6. Выбор направления в методе Ньютона

Что можно в достаточно общем случае сказать о сходимости метода Ньютона? Ответ дает следующая теорема.

Теорема 7.3. Для дважды непрерывно дифференцируемых функций (т.е. для f C2(D) ) с невырожденной матрицей Гf(y*) всегда существует такая ε — окрестность стационарной точки y* функции f(y), что для любой начальной точки y0 из этой окрестности метод Ньютона будет сходиться сверхлинейно. Если при невырожденности матрицы Гf(y*) функция трижды непрерывно дифференцируема, то для начальных точек из некоторой ε — окрестности y* метод сходится к y* квадратично.

ННГУ. Учебный курс «Модели и методы конечномерной оптимизации». Часть 2. Нелинейное программирование и многоэкстремальная оптимизация.

Вначале поясним терминологию.

Определение 7.5. Линейной сходимостью называют сходимость по закону геометрической прогрессии.

Линейная сходимость характерна для метода наискорейшего градиентного поиска (теорема 7.2).

Определение 7.6. Говорят, что метод сходится сверхлинейно, если k>0 и последовательность чисел α k+1,…,α k+m из интервала (0,1), стремящаяся к 0 при

m→∞, что m>0 будет выполнено неравенство

|| y k+m – y*||≤ α k+1 … α k+m ||yk – y*||.

Определение 7.7. Говорят, что метод сходится квадратично, если T>0, что

||y k+1-y *|| ≤ T ||y k-y*|| 2 при ||y0-y*||<ε.

ДОКАЗАТЕЛЬСТВО теоремы 7.3. Предположим, что f C2(D). Тогда возможно следующее представление

f ( yk ) = 0 + Γ f ( y* )( yk − y* ) +ο( yk − y* )

Γ f ( y* ) = Γ f ( yk ) +α( yk − y* ),

где α(∆) – бесконечно малая при ∆→0. Подставляя второе выражение в первое и умножая на (Гf(yk))–1 получим

y* − yk+1 = y* −( yk + (Γ f ( y* ) )−1 (− f ( yk ) ) ) =ο( yk − y* ) .

Следовательно, при достаточной близости начальной точки к стационарной найдется такая бесконечно малая q=q(||y k–y *||), что yk +1 − y* ≤ q yk − y* . Это

обеспечивает сверхлинейную сходимость.

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

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

Таким образом, из теоремы 7.3 следует, что при достаточно общих условиях метод Ньютона обладает тем, чего лишены градиентные методы — высокой скоростью сходимости. Однако это свойство сохраняется только в некоторой (заранее не известной!) окрестности решения. Вне этой окрестности метод Ньютона может вообще расходиться. Кроме того, итерация (7.21) требует обращения матрицы. Существенно также то, что в прикладных задачах достаточно часто встречаются ситуации, когда в точках последовательности y k матрица Гf(y k) оказывается отрицательно определенной, знаконеопределенной или вырожденной. В последнем случае итерация (7.21) неприменима. Если же Гf(y*) не вырождена , но не знакоположительна, то, как следует из приведенной выше теоремы, метод Ньютона может сходиться к стационарной точке функции f,

ННГУ. Учебный курс «Модели и методы конечномерной оптимизации». Часть 2. Нелинейное программирование и многоэкстремальная оптимизация.

не являющейся точкой минимума, а представляющей собой точку максимума или седловую точку.

Пример ситуации со сложным и несколько неожиданным поведением метода Ньютона, вызванным изменением знакоопределенности матриц вторых производных вдоль траектории поиска, показан на рис.7.7.

Рис.7. 7. Неожиданное поведение метода Ньютона

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

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

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

)Замечание. Использование методом квадратичной модели вовсе не предполагает, что в нем обязательно явно используется матрица вторых производных функции или ее оценка. Есть методы, которые явно используют матрицу Гессе, а также методы, которые строят ее оценку, измеряя вдоль траектории поиска вектор градиента. Наконец, есть методы, которые явно матрицу Гессе не используют и не оценивают, хотя близость функции к квадратичной предполагают и используют.

Вразделах 7.3 – 7.6 рассмотрены методы каждого из этих видов.

ННГУ. Учебный курс «Модели и методы конечномерной оптимизации». Часть 2. Нелинейное программирование и многоэкстремальная оптимизация.

7.4. Эффективные методы второго порядка для гладких задач

В этом разделе изучаются методы локальной оптимизации, которые вычисляют в точке поиска y k значения f(y k), f(y k), Γ f(y k), т. е. явно используют значения матриц вторых производных. Эти методы являются улучшенными модификациями метода Ньютона, расширяющими область его сходимости и включающими методы борьбы с нарушением знакоположительности матриц Гессе.

7.4.1 Расширение области сходимости метода Ньютона за счет регулировки величины шага

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

Первая модификация связана с изменением правила выбора длины шага. Ее изучению посвящен данный раздел.

В классическом методе Ньютона коэффициент длины шага x k ≡ 1. В модифицированном методе (методе с регулировкой шага) x k выбирается по алгоритму "аккуратного" одномерного поиска, описанному в пункте 7.2.4. Это приводит к сходимости из любой начальной точки для достаточно широкого класса функций и сохранению высокой (обычно сверхлинейной) скорости сходимости в окрестности решения. Метод Ньютона с регулировкой шага называют методом Ньютона–Рафсона.

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

функций, обладающих тем свойством, что m> 0 и M <∞, m<M, что

y RN, z RN

Такие функции будут сильно выпуклы (см. свойство 1.8′).

Можно показать, что условие (7.22) равносильно тому, что все собственные числа λ1(y),…,λN(y) матриц Γ f(y) лежат между m и M. Для этого достаточно заменить матрицу Гессе ее разложением через ортогональную R и диагональную матрицы (с собственными числами на диагонали), а затем перейти к новым переменным w=R z.

)Замечание. Условие (7.22) гарантирует положительную определенность матрицы Γ f(y), достаточную для сходимости метода Ньютона к минимуму

f(y) из любой начальной точки, выбранной в достаточной близости от него. Однако из произвольно выбранной точки y0 метод Ньютона для функции f(y) из Φm,M может не сходиться.

ДОКАЗАТЕЛЬСТВО. Достаточно привести контр пример. Рассмотрим скалярный случай, когда y R1. Построим четную функцию с минимумом в точке 0 (ее производная при этом будет функцией нечетной), для которой при y0>0