0

Или какие задачи нельзя свести к классу оптимизационных?

Комментирую прямо тут, т.к. ответ не помещается в комментарий. @anton-menshov

Мои рассуждения таковы, просто идём от обратного и всё, например смотрим определение оптимизационных методов:

Оптимизация (в математике, информатике и исследовании операций) — это задача нахождения экстремума (минимума или максимума) целевой функции в некоторой области конечномерного векторного пространства, ограниченной набором линейных и/или нелинейных равенств и/или неравенств.

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

Проверяем следующие вопросы:

  1. Какие задачи нельзя представить в виде целевой функции в некоторой области конечномерного векторного пространства?
  2. В каких задачах нельзя найти экстремум (минимум или максимум) целевой функции?
  3. Какие целевые функции нельзя представить в виде ограниченного набора линейных и/или нелинейных равенств и/или неравенств?

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

5
  • Очень похожий вопрос
    – wchistow
    3 фев 2023 в 13:35
  • 3
    А в чем принципиальное отличие от вопроса ru.stackoverflow.com/q/1492642/195342? А то так и тянет закрыть как дубль...
    – Harry
    3 фев 2023 в 13:35
  • Не вижу противоречия моему определению с булевой функцией ) 3 фев 2023 в 14:49
  • Задачи на перечисление комбинаторных структур? Формальное их можно рассматривать как оптимизационные, но размерность векторного пространства будет так велика, что никакого практического смысла в этом нет. 3 фев 2023 в 14:59
  • Также новый ответ по теме: scicomp.stackexchange.com/a/42461/20688 7 фев 2023 в 20:25

1 ответ 1

3

Это зависит от того, что вы понимаете под понятием свести и что такое оптимизация. Я отвечал на идентичный вопрос на Computational Science SE и пока не нашел противоречий своему ответу. Я не являюсь экспертом в "чистой математике", поэтому "take my answer with a grain of salt".

Краткий обзор моего ответа с выборочным переводом:

It depends on the selected level of abstraction and chosen classification. The question would be in the usability of this abstraction and the chosen classification of problems.

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

If you are allowed to assume that an objective function can mean a boolean function that is true if and only if the found solution satisfies the given constraints (rules of the puzzle), – then any mathematical problem can be formulated in such a way.

Если целевая функция оптимизации может быть выбрана как логическая функция (правда или ложь), принимающая значение "правда" тогда и только тогда, когода решение удовлетворяет ограничениям (условиям задачи в вашем случае), то любая математическая проблема может быть сформулирована таким образом.

Moreover, in first lecture notes of UC Berkely course CS278: Computational Complexity, Luca Trevisan says:

we will deal with four types of computational problems: decision problems, search problems, optimization problems, and counting problems. This distinction is useful and natural, but it is also arbitrary: in fact every problem can be seen as a search problem.

Согласно первой лекции курса Беркли по "Вычислительной сложности", классификация вычислительных проблем очень произвольна, и каждую проблему можно рассматривать как проблему поиска.

Now, I don't think that it would be an overextension to say that every search problem can be thought of as an optimization problem.

На мой взгляд, легко расширить это и рассматривать проблему поиска как проблему оптимизации.

After writing this answer, I also found a discussion on Theoretical Computer Science. The additional piece there would be the mentioning of a sampling problem. However, even that is very arguable: This paper by Scott Aronsson draws an equivalence on sampling and searching.

Также есть следующее обсуждение на сайте теоретических компьютерных наук, где дается эквивалентность выборки и поиска (статья Скотта Аронссона).

0

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.