Алгоритм построения проекции

Lokomotiv59

Есть n-мерный выпуклый многогранник, заданный как решение системы линейных уравнений или неравенств. Надо построить его проекцию на заданное координатное k-мерное подпространство.
Какие есть для этого стандартные алгоритмы ?

Lokomotiv59

up,
неужели никто не знает ?

andy_null

Есть n-мерный выпуклый многогранник, заданный как решение системы линейных уравнений или неравенств. Надо построить его проекцию на заданное координатное k-мерное подпространство.
Какие есть для этого стандартные алгоритмы ?
Что-то не понял.
Что значит построить?
Например, например найти все вершины многогранника и спроецировать их.
Далее найти К-мерную выпуклую оболочку и получить в ответе вершины многогранника-проекции. (в силу выпуклости)
1ая задача должна быть известна
2ая описана в литературе, сам не разбирался. Существуют совсем простые алгоритмы с большой сложностью. А вообще что-то порядка NlogN (точно меньше N^2) по-моему существуюет. Но не гарантирую

Lokomotiv59

Построить - значит задать аналогичным образом --- системой линейных уравнений и неравенств. Строгие оценки сложности не сильно интересуют, главное, чтобы не было сильно дольше обычного симплекс-метода => перечисление вершин не покатит, их может быть слишком много. Что есть "N" в твоих оценках ?

andy_null

Что есть "N" в твоих оценках ?
В изолированной задаче построения выпуклой оболочки N - количество точек

andy_null

Строгие оценки сложности не сильно интересуют, главное, чтобы не было сильно дольше обычного симплекс-метода => перечисление вершин не покатит, их может быть слишком много
Как-то не стыкуется, по-моему.
Если симплекс-метод работает быстро, то и вершин немного.

Lokomotiv59

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

Lokomotiv59

Если симплекс-метод работает быстро, то и вершин немного
это никак не связано.
Симплекс метод в исключительных извратских случаях работает экспоненциальное время. А у большинства многогранников именно экспоненциальное число вершин от n - размерности пространства.

andy_null

В ответ на:
Если симплекс-метод работает быстро, то и вершин немного
это никак не связано.
Понял свою ошибку, извиняюсь. Перепутал названия

andy_null

А мне кажется, что твоя задача очень трудно разрешима при 2<=k<=n-1.
Ибо она почти эквивалента задаче с несколькими целевыми функциями. Точнее говоря, твоя задача сложнее.

Если имеется несколько целевых функций, может получиться так, что их оптимальные значения не достигаются ни на одном из решений. В таком случае придется искать такие решения, на которых достигается некоторая допустимая разница межну значениями целевых функций. Определение, какая разница является “допустимой” — тема для отдельного исследования. MCDM WorldScan (http://www.cba.uga.edu/mcdm/) — бюллетень International Society on Multiple Criteria Decision Making, занимающегося вопросами решения таких задач.
Есть несколько бесплатных пакетов, позволяющих решать задачи ЛП с несколькими целевыми функциями:
* ADBASE
* PROTASS (http://www.ekspert.szczecin.pl/protass/en/)
* NIMBUS (http://diana.math.jyu.fi/N2/)
Другие подходы к решению таких задач:
* Goal Programming (трактует целевые функции как ограничения с “штрафными” переменными или, что практически то же самое, формирование одной целевой функции, составленной из нескольких исходных целевых функций;
* Анализ Парето (практически “тупой” перебор всех вершин);
* Сначала взять наиболее важную из целевых функций в качестве единственной целевой функции и решить задачу с одной целевой функцией, затем зафиксировать эту целевую функцию в ее оптимальном значении и решить задачу с другой целевой функцией, и т. д.

ПС Я не очень хорошо знаю линейное программирование. И (вне зависимости от этого) могу ошибаться

ness73

Точнее говоря, твоя задача сложнее.
К такому утверждению неплохо бы и аргументы приписать =]

andy_null

К такому утверждению неплохо бы и аргументы приписать =]
Каждая целевая функция может быть проекцией на определенный вектор (в Евклидовом пространстве, чтоб проще было).
Выберем эти вектора за базисные k-мерного подпространства.
Найдя проекцию, ты получаешь множество возможных наборов целевых функций.
Дальше надо смотреть на то, какое приближенное решение для нескольких целевых функций ты выбрал. В большинстве случаев симплекс-методом это доделывается.
Примерное сведение такое

ness73

Тот факт, что задачу можно решить сложными методами, не означает, что она сложная. А о методах проецирования многогранников, заданных неравенствами, можно почитать, например, в обзоре B.L. Kaluzny "Polyhedral Computation: A Survey of Projection Methods."

andy_null

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

ness73

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

ness73

В общем, что я хочу сказать. Конечно, порисовав картинки, можно увидеть некоторую связь между поставленной задачей и задачей с несколькими функциями. Но, как мы с думаем, всё сильно зависит от того, как именно задаются входные и выходные данные в задачах — описания многогранников, например.

andy_null

В общем, что я хочу сказать. Конечно, порисовав картинки, можно увидеть некоторую связь между поставленной задачей и задачей с несколькими функциями. Но, как мы с думаем, всё сильно зависит от того, как именно задаются входные и выходные данные в задачах — описания многогранников, например.
Конечно зависит от формата входных/выходных данных. Но, получив неравенства, можно симплекс методом минимизировать любую линейную целевую функцию от исходных целевых.
Про сложность задачи я, конечно, погорячился. Мое предложение было в целом ориентировано на то, что задачи связаны и имеет смысл почитать литературу по сходной задаче (если не получилось найти по поставленной хотя бы раздел "References"

Lokomotiv59

Судя по всему в такой постановке задача действительно очень сложная. Тогда упростим ее следующим образом.
Фтпоку многогранники и проекции. Пусть есть просто система S линейных уравнений и неравенств от переменных x_1, ..., x_n, y_1, ..., y_m. Задача заключается в том, чтобы составить систему S' линейных уравнений или неравенств от переменных x_1, ..., x_n, но такую, что из системы S система S' должна вытекать. При этом, ессно, хочется, чтобы система S' была "побогаче".
Дополнительные свойства задачи.
1. В матрице системы S много нулей.
2. Хочется, чтобы в системе S' тоже было много нулей (чем больше, тем лучше)
Можете предложить какие-то алгоритмы (разумеется предпочтение более простым алгоритмам, которые позволяют строить более простые соотношения) построения системы S' ?

andy_null

При этом, ессно, хочется, чтобы система S' была "побогаче".
Не понял

Lokomotiv59

по условиям побогаче. значит, по возможности, она должна описывать множество наиболее близкое к проекции.
Оставить комментарий
Имя или ник:
Комментарий: