Мотивация для оценки объема

12

Какие конкретные и убедительные приложения для оценки объема выпуклых многогранников того типа, которые рассматривались в более поздних статьях о методах случайного блуждания?

В этих работах по оценке объема упоминается численная интеграция как одна из причин. Какие примеры интегралов, которые люди хотят вычислить на практике, которые очень сложно вычислить с использованием предыдущих методов? Или есть какое-то другое убедительное практическое применение для вычисления объема многогранного многогранника?

cg.comp-geom na.numerical-analysis markov-chains
источник
Интересно, получите ли вы больше ответов того типа, который вы ищете на физике.stackexchange.com ... Кроме того, для тех из нас, кто не знаком с этой конкретной областью теории, не могли бы вы включить некоторые ссылки для "более свежие статьи о методах случайного блуждания"?
Джошуа Грохов
больше думать об этом после ответа и ковыряться. в некоторых работах, кажется, указывается или идет в том направлении, что вычисление объема многогранника является чем-то вроде фундаментальной проблемы в теории сложности. это неудивительно, учитывая, что вычисление детерминанта является еще одной ключевой проблемой в теории сложности, а детерминант является объемом параллелепипеда. таким образом, один разумный ответ, кажется, состоит в том, что в теории сложности существуют глубокие или естественные связи. Еще одним доказательством этого может быть связь с каким-то конкретным классом сложности .... об этом можно больше покопаться ....
vzn
см. также mathoverflow, алгоритм определения объема сложного многогранника . да, этот вопрос выше требует приложений, а не алгоритмов, но некоторые из статей, посвященных алгоритмам, дадут мотивации / приложения.
vzn

Ответы:

7

Оценка объема выпуклого многогранника и тесно связанная с ним задача отбора проб из него имеют приложения для публикации частных данных.

Грубо говоря, проблема, которую вы хотите решить, заключается в следующем: учитывая набор числовых запросов к базе данных, придумайте ответы на те вопросы, которые максимально приближены к реальным ответам, но при этом соблюдайте дифференциальную конфиденциальность. В некотором диапазоне параметров оптимальный алгоритм решения этой задачи имеет геометрическое описание, и его реализация включает в себя выборку из выпуклого многогранника. Смотрите здесь: http://arxiv.org/pdf/0907.3754v3.pdf

Аарон Рот
источник
4

ss

В области компьютерной безопасности при работе с потоком количественной информации эти методы применялись для оценки объема конфиденциальной информации, которая может быть утечка определенной программой. Здесь мы строим многогранник, представляющий возможные состояния программы в конкретный момент ее выполнения, а затем мы хотим оценить кое-что о количестве возможных состояний (это связано с объемом выпущенной информации). Таким образом, в определенный момент анализа они пытаются подсчитать количество целых точек, содержащихся внутри многогранника. Этот запах связан с оценкой объема (для меня).

Вот ранняя статья, которая является представительной:

Тем не менее, это может быть не совсем то, что вы ищете. Требуются методы для подсчета количества целых точек внутри многогранника, которое не совпадает с объемом многогранника. Кроме того, я не думаю, что им нужно анализировать многогранники размером 1000 или выше (хотя я не уверен в этом).

DW
источник
Спасибо. Я думаю, что проблема определения числа целочисленных решений для набора линейных неравенств является # P-полной ( math.ucdavis.edu/~deloera/RECENT_WORK/semesterberichte.pdf имеет еще несколько приложений). Принимая во внимание, что оценка объема может быть сделана в поли времени. Очевидно, что вы можете использовать последнее для аппроксимации первого, но я действительно ищу прямые конкретные приложения оценки объема.
Вычисление объема многогранника также является # P-сложным. Сам по себе этот факт мало говорит об аппроксимациях.
Сашо Николов
P≠BPP
1
@ Turbo Очевидно, что это не доказывает, что P не равен BPP, потому что эти два класса не о модели оракула. Я считаю, что детерминированное приближение объема многогранника, представленного неравенствами, открыто.
Сашо Николов
@SashoNikolov Если бы вы знали эту, казалось бы, простую проблему, было бы неплохо mathoverflow.net/questions/336369/… .
Т ....
4

Хари Нараянан недавно опубликовал статью об arXiv, в которой он использует оценку объема выпуклого многогранника, чтобы доказать определенные результаты о коэффициентах Литтлвуда-Ричардсона (ЛР). Коэффициенты LR являются определенными целыми числами в теории представлений, которые имеют приложения в теории геометрической сложности, физике элементарных частиц и многих других областях (дополнительные ссылки см. Во введении вышеупомянутой статьи). Опять же, вероятно, не совсем то, что вы хотели, но тем не менее интересная связь.

Джошуа Грохов
источник
3

см., например: Оценка N-мерного объема выпуклых тел: алгоритмы и приложения Шарма, Прасанна, Асвал для примера / тематического исследования в области экономического прогнозирования, то есть управления цепочкой поставок.

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

в основном идея заключается в том, что многогранник может моделировать «будущий сценарий» параметров конфигурации управления цепочкой поставок. неопределенность (или «ошибка») в модели оценки / берется пропорционально объему многогранника (S). см. слайды 3,4. тогда это позволяет:

  • количественная оценка неопределенности
  • генерация эквивалентной информации
  • помощь в анализе "что если"
ВЗН
источник
Спасибо. Эти примеры хороши, но мне все еще трудно поверить в то, что они имеют в виду, когда люди говорят, что оценка объема многомерного выпуклого тела является одним из наиболее важных приложений метода цепей Монте-Карло Маркова.
согласился, что пример на слайдах - это «размер игрушки» в отношении количества измерений, но, возможно, некоторые проблемы управления цепочкой поставок имеют большие измерения на практике. Кроме того, эта линия исследований, кажется, предлагает мне, что она может иметь некоторое применение в некоторых формах анализа данных.
vzn