Оптимизация

[vlad_light]

Пусть дано $\mathbf a\in \mathbb R^n:\sum _ia_i = 1$. Нужно решить задачу:

$$ \begin{cases} \sup _i |x_i - a_i|\to \min \\ \sum _i x_i = 1 \\ 0\leq x_1 \leq x_2 \leq \ldots \leq x_n \leq 1 \end{cases} $$

Как такое вообще решается? Если что -- могу пару условий убрать/добавить/заменить.

[Brukvalub]

vlad_light в сообщении #1002168 писал(а):

Пусть дано $\mathbf a\in \mathbb R^n:\sum _ia_i = 1$. Нужно решить задачу:

$$ \begin{cases} \sup _i |x_i - a_i|\to \min \\ \sum _i x_i = 1 \\ 0\leq x_1 \leq x_2 \leq \ldots \leq x_n \leq 1 \end{cases} $$

Как такое вообще решается? Если что -- могу пару условий убрать/добавить/заменить.

Это решается устно, с очевидным ответом: $\infty$ .

[Deggial]

Если решить графически для $n=2;3;4$, то мы видим, что $x^*$, в зависимости от $\mathbf a$, лежит на разных гранях допустимой области. Если компоненты $\mathbf a$ упорядочены, то, конечно, $x^* = \mathbf a$, в других случаях $x^*$ лежит на одной из $n$ гиперплоскостей многогранника допустимых решений. Для многих случаев $x^* = \left(\frac{1}{n},...,\frac{1}{n}\right)$. Есть комбинированные варианты: часть $x_i=a_i$, остальные компоненты берутся из условия, что $x^*$ лежит на грани.

vlad_light в сообщении #1002168 писал(а):

Если что -- могу пару условий убрать/добавить/заменить.

Какое-то странное условие. Какие Вы условия, например, можете убрать, а какие - добавить?

[vlad_light]

Прошу прощения, я вчера неправильно записал задачу Нужно вот такую решать:

$$ \begin{cases} \sup _i |x_i - a_i|\to \min \\ \sum _i x_i = 1 \\ x_i \geq 0 \end{cases} $$

Идея в том, чтоб функция $\sum _i x_i\mathbf 1\{t_i < t\}$ была похожа на функцию распределения (или её кусок). Изначально у меня есть набор $\mathbf a$ такой, что $\hat F(t) = \sum _i a_i\mathbf 1\{t_i < t\}$ сходится к истинной ф. р. Проблема в том, что некоторые $a_i$ могут быть отрицательными, следовательно, $\hat F$ не будет монотонной. Т. е. задача изначально была такая:

$$ \begin{cases} \|F - \hat F\| \to \min \\ F \text{ -- функция распределения} \end{cases} $$

Deggial в сообщении #1002225 писал(а):

Какое-то странное условие. Какие Вы условия, например, можете убрать, а какие - добавить?

Например, можно заменить $\sum _i x_i = 1$ на $\sum _i x_i \leq 1$; $\infty$-норму поменять на $2$-норму; поменять сам вид аппроксимирующей функции и т. д.

(Оффтоп)

Brukvalub в сообщении #1002203 писал(а):

Это решается устно, с очевидным ответом: $\infty$ .

Расскажите, пожалуйста, по-подробнее, а то как-то не смешно

[Brukvalub]

Мне тоже перестало быть смешно - сначала я понял задачу так: вектор $a$ тоже может произвольно меняться...

[мат-ламер]

vlad_light в сообщении #1002260 писал(а):

Прошу прощения, я вчера неправильно записал задачу Нужно вот такую решать:

$$ \begin{cases} \sup _i |x_i - a_i|\to \min \\ \sum _i x_i = 1 \\ x_i \geq 0 \end{cases} $$

Задача сводится к задаче линейного программирования.

[vlad_light]

мат-ламер в сообщении #1002571 писал(а):

Задача сводится к задаче линейного программирования.

Я в этом совсем не разбираюсь, поэтому перепишу определение из википедии:

$$ \begin{cases} \mathbf c^\top \mathbf x \to \min \\ \mathbf A\mathbf x = \mathbf b \\ \mathbf x \geq \mathbf 0 \end{cases} $$

В моей задаче в качестве ограничений можно взять $\mathbf A = (1,\ldots ,1), \mathbf b = 1$. Но я пока не понимаю, как можно переформулировать целевую функцию в виде $\mathbf c^\top \mathbf x$? Намекните, пожалуйста.

[пианист]

К переменным добавляем $u$, к условиям
$u \ge x_i - a_i$,
$u \ge a_i - x_i$.
Целевая функция
$u \to \min$.
Как-то так.