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

12

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

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


источник
Интересно, получите ли вы больше ответов того типа, который вы ищете на физике.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-сложным. Сам по себе этот факт мало говорит об аппроксимациях.
Сашо Николов
PBPP
1
@ Turbo Очевидно, что это не доказывает, что P не равен BPP, потому что эти два класса не о модели оракула. Я считаю, что детерминированное приближение объема многогранника, представленного неравенствами, открыто.
Сашо Николов
@SashoNikolov Если бы вы знали эту, казалось бы, простую проблему, было бы неплохо mathoverflow.net/questions/336369/… .
Т ....
4

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

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

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

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

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

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