Все задачи можно решить методами оптимизации?

Question

[iskateli]

Какой класс задач нельзя решить методами оптимизации?

Comments

[Александр Скуснов]

Для начала список методов в студию, чтобы можно было прикинуть, что подходит, а что нет.
Вот пример из автоматики. Обычно используют гистерезисное или ПИД-регулирование. Вы хотите третий метод найти? Жду.

[iskateli]

чтобы можно было прикинуть, что подходит, а что нет

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

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

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

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

[Василий Банников]

iskateli,

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

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

[hint000]

Возмите любую из списка нерешенных проблем математики. Кажется довольно очевидным, что они не решаются методами оптимизации. Иначе их бы уже решили. :)

Да хоть бы и решенные. У серёзных математиков любимый тип задач - это доказательство теорем. Ладно, чёрт с ней, с великой торемой Ферма, попытаемся методами оптимизации доказать хоть какую-то теорему из геометрии... из матана... из дискретной математики... Мне слабО, а вам?

Ладно, забудем про доказательство теорем. Как там насчёт теории чисел... линейной алгебры... теории вероятностей... математической статистики... теории групп... комбинаторики... возмите наугад какую-нибудь задачу из этих областей математики и придумайте хотя бы приблизительно, как её решать методами оптимизации. Подозреваю, что ни хрена не получится.

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

[iskateli]

Кажется довольно очевидным, что они не решаются методами оптимизации.

нет, не кажется очевидным

Иначе их бы уже решили. :)

почему бы их решили? никакие методы численной оптимизации не помогут в поиске в пространстве состояний с сотнями ( например 10^180 степени) или тысячами измерений.

Answer 1

[iskateli]

https://scicomp.stackexchange.com/questions/31288/...