Математическое

[ny_quant]

Рассмотрим задачу минимизации в Rn:

F(x) -> min

при ограничениях

G(x)=0 Edit: обсуждение показало, что это условие лишнее.
H(x)>=0

Хочется сформулировать такого типа теорему, что при разумных ограничениях на функции F,G,H (скажем F, видимо, должна быть выпуклой) решение задачи (Edit: под этим понимается точка, где достигается инфимум по допустимой области если таковая существует) либо совпадает с глобальным минимумом F(x) либо лежит на границе допустимой области.

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

Comments

[ex-juan-gan.livejournal.com]

Как вообще на многомерном пространстве определяется выпуклость? По-моему, если взять сферу, то минимум достигается на границе. Соответственно, какая бы ни была фигура, если минимум достигается внутри, то есть такая сфера, нарушающая условие.

[ny-quant.livejournal.com]

Выпуклость функции определяется точно также как и в одномерном случае: «надграфик», т.е. множество {F(X)>=a} является выпуклой фигурой.

Последнего не понял. Сфера вся состоит из границы. Вот если допустимой областью является шар, то минимум может достигаться и внутри. Например, в одномерном случае шар это отрезок, скажем [-1, 1]. Функция x^2 достигает минимума внутри при x=0, в точке глобального минимума. Но функция (x-2)^2 уже имеет глобальный минимум за пределами [-1, 1] и она уже достигает минимума на границе при x=1.

[ex-juan-gan.livejournal.com]

В смысле шар.

Начнем с выпуклости функции. Тогда (локальный) максимум один, это как бы очевидно (а то прямая между двумя локальными не входит в надграфик). Ну и взять этот глобальный максимум; он или внутри фигуры, или нет (логика у нас пока что булева). Если нет, то ни один открытый шар внутри фигуры не содержит максимума - доказывать? А раз нет, то максимум по фигуре будет на границе.

[ny-quant.livejournal.com]

Именно.

[ex-juan-gan.livejournal.com]

Я тоже так думаю.

[fortran-only.livejournal.com]

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

Для невыпуклых функций нет ничего.

[ny-quant.livejournal.com]

См выше: функция (x-2)^2 имеет глобальный минимум за пределами допустимой области. То что этот глобальный минимум также и единственный локальный действительно тривиально, но никак мне не помогает доказать, что в моей задаче минимум лежит на границе. Вернее, помогает, но это другая теорема.

[fortran-only.livejournal.com]

Если допустимая область образует выпуклый сет, то локальный минимум также является глобальным минимумом в допустимой области.

Все. Насчет где именно лежит минимум на то есть теорема Каруша-Кун-Такера от 1939 года, которую знает каждый экономист буквально с пеленок.

[ny-quant.livejournal.com]

Первое тривиально, но это другая теорема.

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

Либо моё утверждение верно, либо нет, либо накрайняк это новая теорема и никто не знает.

[sovkista.livejournal.com]

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

[misha-b.livejournal.com]

A convex function has exactly one minimum on a convex domain. If that minimum is different from the global minimum (in R^n), то он очевидно лежит на границе области, т.к. у выпуклой функции есть только один локальный (он же глобальный) минимум.

[ny-quant.livejournal.com]

Я и говорю. А нужна ли выпуклость области?

[misha-b.livejournal.com]

Да. Простейший пример -- минимизировать y=x^2 по области
[-2,-1]U[1,2].

[ny-quant.livejournal.com]

Может всё же односвязности достаточно?

[ny-quant.livejournal.com]

Подождите. Ну, два минимума +1 и -1, оба на границе. Чего я не понял?

[spamsink.livejournal.com]

Будем в R^2. Возьмем параболоид вращения, это у нас выпуклая F(x), проведем на его поверхности какую-нибудь замкнутую извилистую загогулину, это у нас G(x)=0, и сотрем половину загогулины; стёртое - это у нас H(x) < 0, а оставшееся - H(x) >= 0. Понятно, что самая нижняя точка оставшейся части загогулины может с легкостью быть вовсе не на конце.

[ny-quant.livejournal.com]

Не понял что отсюда следует.

Но вот juan_gandhi предложил простое доказательство, в котором не используется выпуклость области. Что не так?

http://ny-quant.livejournal.com/595516.html?thread=4899900#t4899900

[spamsink.livejournal.com]

Раз не на конце, то, значит, не на границе допустимой области.

[ny-quant.livejournal.com]

Этого тоже не понял.

[spamsink.livejournal.com]

Ганди доказывал без учета G(x) = 0.

[ny-quant.livejournal.com]

G(x) = 0 снижает размерность допустимой области. Любая допустимая точка лежит на границе допустимой области, так что утверждение становится тривиальным. Не надо было мне это ограничение добавлять. Не подумал.

[f-b-dima.livejournal.com]

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

[ny-quant.livejournal.com]

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

[f-b-dima.livejournal.com]

Использовались свойства выпуклости (монотонность, либо единственный экстремум) такая лемма была точно.

Если у любителя фортрана есть проблемы с установлением программным способом факта выпуклости, то могу помочь )