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

Рейтинг: 0Ответов: 1Опубликовано: 03.02.2023

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

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

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

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

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

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

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

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

математика оптимизация класс
Источник: Stack Overflow на русском

Ответы

▲ 4Принят

Это зависит от того, что вы понимаете под понятием свести и что такое оптимизация. Я отвечал на идентичный вопрос на 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.

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