Задачка про выпуклые кривые

ETrohkina

Для любой выпуклой кривой (красная существует единственная вписанная ломаная (3 звена такая, что засекаемая площадь между кривой и ломаной минимальная.
Т.е. единственность такой ломаной при минимизации площади – это верное утверждение?
 
Пока мнения разделились, но доказательство не получено.
Есть еще такое предположение:
1. Ломаная единственна, при этом касательные в точках А и В (для гладких) - параллельны хордам ОВ и АС.

stm7543347

Если кривая является прямой, то существует континуальное семейство ломаных, или тебе невырожденный случай?

ETrohkina

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

muran

ROC что ли приближаешь?

ETrohkina

Не совсем :) ROC'и не выпуклы (теоретически могут уходить под диагональ но в первом приближении суть примерно та же.

iri3955

Если разрешить прямые участки, то не единственная.
Да даже если нет, это похоже неверно

incwizitor


подозреваю, что единственности может не быть
рассмотрим кривые, которые симметричны относительно диагонали (0,1)-(1,0)
если искомая ломанная единственная, то она симметрична относительно диагонали (иначе отобразив ее относительно диагонали получим вторую ломанную)
значит, AB перпендикулярен диагонали
подозреваю, что существует такая дуга (ГМТ что зоны S1 + S2 = const (требуется док-во)
значит, ломанная не единственная
в таком духе не получится доказать?

ETrohkina

Пока полного доказательства не получили. С симметричными как раз есть предположение, что единственна (пример: окружность).

incwizitor

а такую кривую можно?:)

а блин, задачка про выпуклые кривые :ooo:

muran

Действуем в квадрате [0;1].
Пусть S - площадь под исследуемой выпуклой кривой, тогда, если Ax, Ay - координаты точки A, то площадь под ломаной
Ax*Ay/2+ (Ay+By)*(Bx-Ax)/2+(1+By)*(1-Bx)/2= 1/2(Ay*Bx-By*Ax+1-Bx)
Значит наша задача F(x_1;x_2;x_3,x_4)=S-1/2(Ay*Bx-By*Ax+1-Bx) -> min
Необходимое условие минимума dF/dx_i=0, т.е. Ax=By=Bx=0, Ay=1.
Соответсвенно, минимум не достигается, значит таких точек A и B не существует.
Вроде так, но могу быть неправ :)

komBAR

А условие, что точки A и В на прямой лежат - так, фигня?

incwizitor

значит таких точек A и B не существует
сами же пришли к глючному заключению, значит, ваши рассуждения не верны ;)
в ваших рассуждениях нет кривой, а точки A, B лежат на ней

muran

Сообщение удалил

muran

А как это связано с минимизацией разницы плащадей?

komBAR

Да ну блин. В условии задачи они на кривой. А ты минимизируешь без этого условия. Вот и получается полная фигня.

incwizitor

Смотрите на картинку, не лежат они на кривой
как вы понимаете эту фразу?
существует единственная вписанная ломаная

muran

согласен, исправился.

muran

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

komBAR

Есть еще такое предположение:
1. Ломаная единственна, при этом касательные в точках А и В (для гладких) - параллельны хордам ОВ и АС.
Насчет единственности пока не знаю, но предположение точно верное.
Площадь под ломаной равна bf(a)+(1-a)f(b) + (1-b хотим ее максимизировать. После взятия частных производных получим ровно то, что требуется:
по a: f'(a)=f(b)/b
по b: f'(b)=(1-f(a/(1-a)

komBAR

Домашнее задание:
Найти максимум ab, при условии что a,b положительны и a+b=10.
Могу подсказать.
Берешь производные по a и по b, получаешь a=b=0, точка не подходит. Значит необходимое условие не выполняется, значит решения нет?

incwizitor

еще можно через ломанную, состоящую из двух звеньев доказать:

оптимальная ломанная из трех звеньев состоит из двух оптимальных ломанных, состоящих из двух звеньев

muran

У тебя a и b зависимы, на самом деле ищется максимум 10a - a^2 , откуда чп 2a=10 и смотрите ка, все получается.
Но с решением основной задачи у меня и правда косяк

stm7543347

:facepalm:

incwizitor


вот кстати примерчик симметричной выпуклой "кривой", для которой вроде можно получить несколько оптимальных ломанных
рассматривать несимметричные варианты не будем, ибо они уже дают нам неединственность оптимальной ломанной
расположим точку R так высоко, чтобы площадь ORP совпало с площадью квадрата OSQP (OS = OP = 1, то R на высоте 2)
тогда любая симметричная трапеция OABP имеет площадь
 [math]$$h*(3-h)/2$$[/math], где h - высота планки AB
максимум функции достигается в точки h = 3/2 (то есть AB - средняя линия треугольника SRQ) (максимум равен 9/8, что больше площади квадрата OSQP)
отрезок PA (о чудо) параллелен отрезку RQ, а значит, можно передвинуть точку B, не меняя площадь четырехугольника (высота и основание треугольника ABP постоянны)
пришли к несимметричному варианту
зы: долго мудрствовал, мог перемудрить в рассуждениях =(

incwizitor

отсюда можно заключить, что если фигуру сгладить в углах, то решение все равно не единственное будет

iri3955

Вроде очевидно же, что есть пример, для которого минимум не один.
Но если запретить прямые, то сложнее.
Симметричных таких не существует.
Действительно. Пусть фиксированные точки (-x0, 0) и (x0, 0 f(x0) = 0, f''(x) > 0, f(x) > 0 при -x0 < x < x0, f - чётная функция
Допустим, минимум достигается в точках (-x1, f(x1 (x1, f(x1 и (-x2, f(x2 (x2, f(x2 x2 > x1 > 0.
Тогда
f(x1) > f(x2) (их монотонности на x > 0).
f'(x1) = -f(x1) / (x0 + x1) (из локальной минимальности
f'(x2) = -f(x2) / (x0 + x2) (из локальной минимальности
то есть f'(x1) < f'(x2 то противоречит f''(x) > 0.
Для кусочно-гладкой (да и просто симметричной выпуклой рассуждения повторяются, только вместо производных будут опорные прямые.

iri3955


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

blackout

Из "при этом касательные в точках А и В (для гладких) - параллельны хордам ОВ и АС." следует, что решение локально единственно, если нет прямолинейных кусков.
Теперь берем кривую, для которой решение единственно (например симметричную) и непрерывно переводим ее в нашу исходную кривую, при этом не проходя через кривые с прямолинейными кусками. По непрерывности решение снова будет единственно.
Upd: Чтобы это сработало нужно еще всякие равномерные непрерывности доказывать, так что эо просто размышления, а не доказательство.

iri3955

повторюсь
> Надо, конечно, еще аккуратно доказать, но вроде такой пример должен подойти
Но вообще, если взять просто выпуклую оболочку, то пример подходит (кроме того, что он содержит прямые).
Мне немного лень дальше строго доказывать, что можно построить кривую не содержащую прямых (она будет недалеко от оболочки для которой
это тоже выполнено. но оно строится, просто надо аккуратно расписать оценки
UPD. Про симметричный я наврал. Из того, что кривая симметрична не следует, что минимум достигается на симметричной ломаной

stm7543347

Из того, что кривая симметрична не следует, что минимум достигается на симметричной ломаной
По крайней мере на симметричной ломаной будет точка равновесия.

kroton45

Назовем ломаную ломаной равновесия, если касательная в [math]$A$[/math] параллельна [math]$OB$[/math], и касательная в [math]$B$[/math] параллельна [math]$OC$[/math].
Ясно, что максимум площади четырехугольника (что то же самое, что минимум суммы площадей обрезков) - достигается на равновесной ломаной.
Ясно, что, если кривая симметрична и строго выпукла, то симметричная равновесная ломаная единственная. Так что, если мы нарисуем симметричную кривую с симметричной равновесной ломаной, на которой максимум не достигается, то мы построим кривую, для которой максимум не единственный, ибо несимметричный.
Нарисуем трапецию [math]$OABC$[/math] с основаниями [math]$OC>AB$[/math], через ее вершины пойдет наша кривая с началом [math]$O$[/math] и концом [math]$C$[/math]. Прямые в точках [math]$A, B$[/math], параллельные соответственно [math]$OB, AC$[/math] будут для кривой опорными. Таким образом, ломаная [math]$OABC$[/math] равновесная.
Теперь сдвинем точку [math]$A$[/math] до точки [math]$A'$[/math] чуть вверх по своей опорной прямой, а [math]$B$[/math] до [math]$B'$[/math] чуть вниз. Тогда [math]$S_{OA'B'C}>S_{OABC}$[/math]
Осталось пошевелить точки [math]$A',B'$[/math], чтобы провести строго выпуклую кривую, и понять, что максимум на [math]$OABC$[/math] не достигается в силу [math]$OA'B'C$[/math].

blackout

Почему S(OA'B'C) > S(OABC) ?
Почему ты думаешь, что пошевелив A' и B' и построив новую кривую ты получишь кривую, для которой OABC все еще будет равновесной ломаной?
Так что, если мы нарисуем симметричную кривую с симметричной равновесной ломаной, на которой максимум не достигается, то мы построим кривую, для которой максимум не единственный, ибо несимметричный.
Выделенное - лишнее.

kroton45

Почему S(OA'B'C) > S(OABC) ?
Легче цифры написать.
O(0,0) A(2,7) B(7,7) C(9,0) A'(1,6) B'(6,8)
S(OABC)=49, S(OA'B'C)=50.
А, почему OABC после шевеления будет равновесной - так оно разве сложно отследить, чтобы нужные прямые остались опорными?

blackout

O(0,0) A(2,7) B(7,7) C(9,0) A'(1,6) B'(6,8)
Обрати внимание, что AA' параллельно OB, так что если кривая проходит через O,A,B,C,A',B' и OABC равновесная (что необходимо для контрпримера) то касательная в A параллельна OB и AA' и, следовательно, либо O,A,B,C,A',B' не выпуклая либо участок AA' прямой.
А, почему OABC после шевеления будет равновесной - так оно разве сложно отследить, чтобы нужные прямые остались опорными?

Тебе нужно доказать, что одновременно будут выполняться следующие условия:
1) S(OA'B'C) > S(OABC)
2) через O,A,B,C,A',B' проходит выпуклая кривая без прямолинейных кусков.
3) OABC равновесная для этой кривой.

ETrohkina


 
вот кстати примерчик симметричной выпуклой "кривой", для которой вроде можно получить несколько оптимальных ломанных
рассматривать несимметричные варианты не будем, ибо они уже дают нам неединственность оптимальной ломанной
расположим точку R так высоко, чтобы площадь ORP совпало с площадью квадрата OSQP (OS = OP = 1, то R на высоте 2)
тогда любая симметричная трапеция OABP имеет площадь
 [math]$$h*(3-h)/2$$[/math], где h - высота планки AB
максимум функции достигается в точки h = 3/2 (то есть AB - средняя линия треугольника SRQ) (максимум равен 9/8, что больше площади квадрата OSQP)
отрезок PA (о чудо) параллелен отрезку RQ, а значит, можно передвинуть точку B, не меняя площадь четырехугольника (высота и основание треугольника ABP постоянны)
пришли к несимметричному варианту
зы: долго мудрствовал, мог перемудрить в рассуждениях =(
Посмотрел, вроде все сошлось.
Оставить комментарий
Имя или ник:
Комментарий: