Математическое
Jul. 22nd, 2016 10:27 am![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
ny_quant
Рассмотрим задачу минимизации в Rn:
F(x) -> min
при ограничениях
G(x)=0 Edit: обсуждение показало, что это условие лишнее.
H(x)>=0
Хочется сформулировать такого типа теорему, что при разумных ограничениях на функции F,G,H (скажем F, видимо, должна быть выпуклой) решение задачи (Edit: под этим понимается точка, где достигается инфимум по допустимой области если таковая существует) либо совпадает с глобальным минимумом F(x) либо лежит на границе допустимой области.
Поскольку я это придумал сегодня по дороге на работу, я вижу два варианта. Либо это совсем неверно по каким-то очевидным причинам, которые мне с утра не пришли в голову. Либо это давно все знают и умные люди легко подскажут где найти соответствующую теорему.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2016-07-22 03:02 pm (UTC)no subject
Date: 2016-07-22 03:23 pm (UTC)Выпуклость функции определяется точно также как и в одномерном случае: «надграфик», т.е. множество {F(X)>=a} является выпуклой фигурой.
Последнего не понял. Сфера вся состоит из границы. Вот если допустимой областью является шар, то минимум может достигаться и внутри. Например, в одномерном случае шар это отрезок, скажем [-1, 1]. Функция x^2 достигает минимума внутри при x=0, в точке глобального минимума. Но функция (x-2)^2 уже имеет глобальный минимум за пределами [-1, 1] и она уже достигает минимума на границе при x=1.
no subject
Date: 2016-07-22 03:23 pm (UTC)Для невыпуклых функций нет ничего.
no subject
Date: 2016-07-22 03:40 pm (UTC)См выше: функция (x-2)^2 имеет глобальный минимум за пределами допустимой области. То что этот глобальный минимум также и единственный локальный действительно тривиально, но никак мне не помогает доказать, что в моей задаче минимум лежит на границе. Вернее, помогает, но это другая теорема.
no subject
Date: 2016-07-22 03:52 pm (UTC)Все. Насчет где именно лежит минимум на то есть теорема Каруша-Кун-Такера от 1939 года, которую знает каждый экономист буквально с пеленок.
no subject
Date: 2016-07-22 04:35 pm (UTC)Первое тривиально, но это другая теорема.
Я не вижу чтоб теорема Куна-Таккера говорила о том, где находится точка минимума. Она говорит о существовании множителей Лагранжа с определёнными свойствами.
Либо моё утверждение верно, либо нет, либо накрайняк это новая теорема и никто не знает.
no subject
Date: 2016-07-22 04:45 pm (UTC)no subject
Date: 2016-07-22 05:00 pm (UTC)Начнем с выпуклости функции. Тогда (локальный) максимум один, это как бы очевидно (а то прямая между двумя локальными не входит в надграфик). Ну и взять этот глобальный максимум; он или внутри фигуры, или нет (логика у нас пока что булева). Если нет, то ни один открытый шар внутри фигуры не содержит максимума - доказывать? А раз нет, то максимум по фигуре будет на границе.
no subject
Date: 2016-07-22 05:02 pm (UTC)А что для выпуклой функции на выпуклом сете минимум может быть или внутри или на границе - это просто очевидность, а даже не теорема, такое стыдно вслух произносить даже.
no subject
Date: 2016-07-22 05:06 pm (UTC)Я и говорю. А нужна ли выпуклость области?
no subject
Date: 2016-07-22 05:06 pm (UTC)Именно.
no subject
Date: 2016-07-22 05:11 pm (UTC)Я специально для вас нагуглил теорему, но про границу ничего не нашел. Более того, я ничего не говорил про выпуклость области, учитесь читать внимательнее.
no subject
Date: 2016-07-22 05:13 pm (UTC)Да. Простейший пример -- минимизировать y=x^2 по области
[-2,-1]U[1,2].
no subject
Date: 2016-07-22 05:25 pm (UTC)no subject
Date: 2016-07-22 05:28 pm (UTC)Может всё же односвязности достаточно?
no subject
Date: 2016-07-22 05:30 pm (UTC)Подождите. Ну, два минимума +1 и -1, оба на границе. Чего я не понял?
no subject
Date: 2016-07-22 05:34 pm (UTC)Если вы хотите опровергнуть утверждение, то найдите пример где решение задачи оптимизации не лежит на границе и не является глобальным минимумом.
no subject
Date: 2016-07-22 06:15 pm (UTC)no subject
Date: 2016-07-22 06:26 pm (UTC)Я про единственность ничего не утверждал, только про границу. Даже и односвязность вроде бы не нужна.
no subject
Date: 2016-07-22 06:28 pm (UTC)no subject
Date: 2016-07-22 06:44 pm (UTC)О! И что, у этого фактоида от официального названия? Наверное все кому надо это и так понимают, просто лень записывать на бумаге.
no subject
Date: 2016-07-22 06:51 pm (UTC)берем тривиальную задачу о приближении матриц заданного размера матрицами c рангом меньше заданного
функция выпукла, сет невыпукл
like hell решение будет лежать на границе
no subject
Date: 2016-07-22 07:09 pm (UTC)Вы сформулируйте задачу полностью и покажите где решение на самом деле.
no subject
Date: 2016-07-22 07:38 pm (UTC)http://zoonek.free.fr/blosxom/R/2012-06-01_Optimization.html
Просто рекомендую в таких случаях задуматься - если об этом ничего нельзя найти, значит это просто невозможно, потому что люди ученые терпеть не могут признаваться что решить не могут что-то, причем буквально в полушаге от тривиально решаемого.
no subject
Date: 2016-07-22 08:52 pm (UTC)Спасибо, ваши рекомендации необычайно ценны, но было еще лучше если б вы указали что конкретно на этой странице или ещё где противоречит моему утверждению для невыпуклых областей. Вы ведь не собираетесь выдавать результаты численных экспериментов за математические аргументы, не правда ли?
Как я уже несколько раз сказал выше, утверждение может быть или неверным или очевидно верным (для тех кто понимает), но недостаточно интересным чтобы его записывать.