поиск ближайших соседей

[Alexey1]

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

[AndreyL]

Извиняюсь за молчание - чуть отвлекся.

Почти по предложенному Вами плану сделал так
$\min \sum_{i=1}^{m} z_i$
$a_i \leq z_i, i=1,...,m$
$\sum_{i=1}^{m} a_ix_i=y$
$\sum_{i=1}^{m} a_i=1$
$a_i \geq 0, i=1,...,m$
$z_i \geq 0, i=1,...,m$.
я сделал неизвестными $a_i $ и $z_i$.
По сравнению с предыдущей задачей результаты получились другие, оно и понятно, там целевая функция была $\min \sum_{i=1}^{m} a_i |\bar x_i-\bar y|$. Но количество опорных точек для каждой точки $Y$ остается прежним. Для 9-тимерного пространства опорных точек должно быть 9, т.е. для того, чтобы выполнялись все поставленные условия для описания любой точки достаточно девяти опорных точек, образующих выпуклый многогранник вокруг описываемой точки.
В предыдущем решении для описания всех 12-ти точек понадобилось 21 опорная, в новом 16 (для разных точек разный набор из 9-ти опорных, но некоторые присутствуют в нескольких наборах).
А вот когда пытался сделать для описания всех 12-ти точек, получилось, во-первых, что для каждой отдельной точки нужно от 19-ти до 24-х опорных, а всего надо 27 (чтобы описать все 12). Хотя есть подозрение, что для описания всех 12-ти точек понадобится опять же 9 опорных, просто они будут отстоять от изучаемых точек $Y^k$ чуть подальше.
В идеале целевая функция должна быть $\min \sum_{i=1}^{m} Sign \left( \sum_{k=1}^{l} a_i^k \right)$. Попытался сваять для одной точки $\min \sum_{i=1}^{m} Sign \left( a_i \right)$ - не дождался решения. Ваял в Вольфрамовской Математике, если интересно, с начальными условиями из линейной задачи. Наверное потому, что функция $Sign$ (взятие знака) - крайне неудобна для задач оптимизации.

[Alexey1]

Так задачу формулировать не надо, так как в этом случае $a_i=z_i$, и никакой роли $z_i$ не играют. Почему Вы не хотите $z_i=\{0;1\}$?

[AndreyL]

$z_i=\{0;1\}$, если я правильно понимаю, означает, что $z_i$ могут принимать значения либо 0, либо 1. тогда условие $a_i \leq z_i$ может быть трансформировано в $ Sign (a_i) = z_i$, или, что тоже самое:
$z_i= \left\{ \begin{array}{l} 0 \text{ если } a_i=0,\\ 1 \text{ если } a_i>0. \end{array} \right.$
Или я чего не понял и все как-то иначе?

[Alexey1]

Вы всё правильно поняли. Просто функция $sign(x)$ в целевой функции как-то не привычна, а вот ограничение $z_i=\{0;1\}$ часто встречается в задачах оптимизации. Поэтому решение данной задачи на компьютере должно быть проще.

[AndreyL]

А можно посмотреть, как реализуется ограничение $z_i=\{0;1\}$ в задачах оптимизации? Может какие то хитрые алгоритмы оптимизации используются? Классические градиенты тут не подходят.

[AndreyL]

Насколько я понял, это задача целочисленного программирования, точнее даже булевского программирования. Нашел, что "для решения задач этого типа разрабатываются специфические алгоритмы, основанные на комбинаторике, графах и т. д." У меня было подозрение, что решение где-то в этих областях, но тут я мало чего знаю.
Такой вопрос - есть ли методы, позволяющие выяснить, составляют ли несколько точек в $n$-мерном пространстве выпуклый многогранник и лежит ли заданная точка внутри этого многогранника?

[Alexey1]

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

AndreyL в сообщении #315140 писал(а):

Такой вопрос - есть ли методы, позволяющие выяснить, составляют ли несколько точек в $n$-мерном пространстве выпуклый многогранник и лежит ли заданная точка внутри этого многогранника?

Вы под многогранником имеете ввиду выпуклую комбинацию, т.е. для векторов $x_1,...,x_m$ их выпуклая комбинация есть $\sum_{i=1}^{m}a_ix_i, 0 \leq a_i \leq 1$? Поэтому, если есть несколько точек, то можно найти и их выпуклую комбинацию.
Порисуйте и посмотрите какому критерию должна удовлетворять точка, чтобы быть представленной в виде выпуклой комбинации других точек.

[AndreyL]

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

[Alexey1]

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