Век информации переходит в век киборгов

[Нгаан]

подкинул мысль, которую я и не собирался думать

"Люсенька, зараза, дались тебе эти макароны..."
(Кин-дза-дза)

[Alex Ivanov]

Как говорят шахматисты, она играет совсем не так, как гроссмейстер-человек. Например, часто непонятно зачем жертвует фигуры, при этом неизменно выигрывая. Более того, говорят, что среди теоретиков шахмат сейчас популярно изучение партий, сыгранных AlphaZero, для разработки новых шахматных идей.

Невозможное возможно если не знать что оно не возможно.
https://www.youtube.com/watch?v=CisHnhqQk9o

[Нгаан]

Невозможное возможно

На самом-то деле в ролике говорится, что эта задача не была решена, а не то, что найти решение невозможно.
Да и насчёт того, что он был единственным создателем линейного программирования, тоже есть вопросы. Вот если бы Светлов смотрел ролики, то он скорее всего сразу бы возмутился и привёл 100-500 аргументов к тому, что первым был Канторович.

[Н. Светлов]

А как тогда быть, если мне чужой фотон прилетел и подкинул мысль, которую я и не собирался думать?

Так всегда и бывает

Приходится либо игнорировать, либо увлекаться идеей, предназначавшейся не тебе. Фотон про Охижутика, быть может, Булычёву предназначался

Да и насчёт того, что он был единственным создателем линейного программирования, тоже есть вопросы. Вот если бы Светлов смотрел ролики, то он скорее всего сразу бы возмутился и привёл 100-500 аргументов к тому, что первым был Канторович.

А о ком там речь? О Данциге?

Если да, то тут вообще смешная ситуация. Ещё Эйлер умел решать намного более сложные задачи на экстремум, чем задачи линейного программирования, причём фундаментальная идея — использование множителей Лагранжа-Гамильтона — в обоих случаях одна и та же. Даже удивительно в связи с этим, почему алгоритмы решения задач линейного программирования появились лишь в XX веке. Думаю, что ещё Гаусс легко создал бы такой алгоритм, если б к нему кто-то обратился с задачей о раскрое фанеры. Он знал всё, что для этого нужно знать.

Канторович научился решать задачи линейного программирования раньше Данцига, но сформулировал не алгоритм, а свод правил, приводящих к решению. Свод правил не годился для программирования (по крайней мере, до появления Prolog'а), поэтому процедура решения по Канторовичу была человеко-машинной: человек выбирал разрешающий столбец, а машина вычисляла симплексные отношения и выполняла преобразования Гаусса. В результате, благодаря интуиции человека, задача решалась, как правило, за меньшее число итераций, чем по более примитивному, но зато строгому симплексному методу. Собственно, разница в том, что в симплексном методе выбирается столбец с экстремальной оценкой, тогда как Канторович интуитивно выбирал столбец при условии, что оценка имеет «правильный» знак. Часто это бывал столбец с экстремальной оценкой — но не всегда. Процедура Канторовича всегда гарантированно сходится к оптимуму при его наличии; симплексный метод Данцига as is, без расширений, может не сходиться к оптимуму при наличии у симплекса вырожденных вершин.

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

[Нгаан]

А о ком там речь? О Данциге?

Таки да. Мол был гениальный мальчик, который "чисто по-приколу и незнанию" решил великую "неразрешимую" задачу.

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

[Н. Светлов]

"чисто по-приколу и незнанию"

Ложь.

[skor]

Вот ведь, заинтриговали прям.
Неужели придётся смотреть ролик?
Если в ролике речь про симплекс-метод, то у меня с ним связано забавное воспоминание.

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

Потом ходил два дня по Бауманке и у всякого встречного-поперечного спрашивал: как адаптировать симплекс-метод к строгим неравенствам? Особенно страшно я пытал преподов, которые читают курсы по методам оптимизации. И никто не ответил.

А потом случайно в середине одной статьи нашёл полстраницы, где рассказывалось, как это делается

[Нгаан]

Особенно страшно я пытал преподов... И никто не ответил.
...
нашёл полстраницы, где рассказывалось, как это делается

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

[skor]

Ну так теперь ты наверняка можешь давать платные консультации по реализации метода

Увы, я, как человек непрактичный, поручил одной не особенно сильной студентке реализовать метод в рамках выпускной работы бакалавра. И на защите бауманские преподы узнали секрет

[Н. Светлов]

А потом случайно в середине одной статьи нашёл полстраницы, где рассказывалось, как это делается

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

Впрочем, студенту это, конечно, не очевидно, особенно если он симплекс-метод "прошёл", а математику нет, как это и практикуется обычно при подготовке менеджеров или экономистов.

Правда вот, мне в голову не приходит ни одна прикладная задача, требующая решения численными методами, где бы требовались строгие ограничения.

[skor]

Очевидно же, что если бы мы заменили строгие неравенства на нестрогие и получили бы оптимум в вершине

Это было бы очевидно, если бы мы заменили все нестрогие неравенства на строгие. А вот если часть неравенств остаются нестрогими, как в исходной постановке задачи линейного программирования, а другая часть становится строгими, тогда всё гораздо интереснее.

Отправлено спустя 7 минут 12 секунд:

Правда вот, мне в голову не приходит ни одна прикладная задача, требующая решения численными методами, где бы требовались строгие ограничения.

Вот поэтому почти никто и не умеет со строгими неравенствами работать.

P.S. А мне этот вариант симплекс-метода понадобился не для решения какой-то практической задачи, а как решающая процедура для теории линейных неравенств в SMT-солвере. В этой теории нельзя ограничиться нестрогими неравенствами, потому что в логической формуле всегда может встретиться отрицание неравенства, и тем самым нестрогое неравенство превратится в строгое.

[Н. Светлов]

Это было бы очевидно, если бы мы заменили все нестрогие неравенства на строгие. А вот если часть неравенств остаются нестрогими, как в исходной постановке задачи линейного программирования, а другая часть становится строгими, тогда всё гораздо интереснее.

Ну да, в вырожденных вершинах оптимум может существовать даже в том случае, если через вершину проходит гиперплоскость строгого ограничения. Но если вершина не вырождена и через неё проходит гиперплоскость строгого ограничения (хотя бы одна) — оптимум не существует, и баста.

Суть дела в простой и очевидной истине: строгое ограничение никогда не может быть эффективным. В принципе. Ни в одной наперёд заданной точке. Значит, либо оптимума не существует, либо он полностью определяется нестрогими ограничениями.

Отправлено спустя 4 минуты 1 секунду:

P.S. А мне этот вариант симплекс-метода понадобился не для решения какой-то практической задачи, а как решающая процедура для теории линейных неравенств в SMT-солвере. В этой теории нельзя ограничиться нестрогими неравенствами, потому что в логической формуле всегда может встретиться отрицание неравенства, и тем самым нестрогое неравенство превратится в строгое.

Да, проблема известная, хотя на практике её обычно решает нестрогий подход к логическому отрицанию: оболочка замкнутого множества M принимается принадлежащей также множесту not M. Для численных методов этого достаточно. После решения, при необходимости, — опять-таки уступка (впрочем, её обычно не делают: и без того всегда есть люфт по найденному решению).

[skor]

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

Отправлено спустя 11 минут 38 секунд:

Для численных методов этого достаточно.

Возможно. Но для SMT-солвера нужен строгий подход, т.к. он должен порождать доказательство.

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

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

[Н. Светлов]

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

Да, согласен. Сочетание вырожденных вершин с альтернативными решениями — довольно вкусная задача для теории; но ключ к её решению всё тот же: строгое неравенство не может быть эффективным. Я-то смотрю на проблему через призму численных методов (ибо экономист) — там всё это вообще значения не имеет.

Вообще с отрицанием над симплексами связана гораздо более трудная проблема: результатом, как правило, оказывается невыпуклое множество, и отсюда сразу возникает спрос на те самые видеокарты

[skor]

Вообще с отрицанием над симплексами связана гораздо более трудная проблема: результатом, как правило, оказывается невыпуклое множество, и отсюда сразу возникает спрос на те самые видеокарты

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

[Н. Светлов]

Ага, а когда ещё дополнительно у нас некоторым переменным разрешено принимать только целочисленные значения

Ага, а давай ещё применим логическое отрицание в духе задач SMT к вот этой вот постановке

Резервы веселья безграничны

[skor]

Ага, а давай ещё применим логическое отрицание в духе задач SMT к вот этой вот постановке

Разрешим только нецелочисленные значения?
Да, я такого ни в одном SMT-солвере не видел. В принципе, можно было бы даже реализовать, за-ради цирка.

[Нгаан]

В принципе, можно было бы даже реализовать, за-ради цирка.

Вот так, мимоходом, и родились многие выдающиеся теории современной теоретической науки.

[Alex Ivanov]

Старые клетки перепрограммировали, и они стали моложе на 30 лет: как это работает
https://hightech.fm/2022/04/08/skin-cells-reprogrammed

Отправлено спустя 8 часов 37 минут 31 секунду:

Вот ведь, заинтриговали прям.
Неужели придётся смотреть ролик?

George Dantzig “If I had known that the problems were not homework but were in fact two famous unsolved problems in statistics, I probably would not have thought positively, would have become discouraged, and would never have solved them.”

George Dantzig "Если бы я знал, что эти задачи не были домашним заданием, а на самом деле были двумя известными нерешенными проблемами в статистике, я, вероятно, не стал бы мыслить позитивно, впал бы в уныние и никогда бы их не решил."

[Нгаан]

Осторожно, это робот!

В cледующем году Илон Маск начнет производство роботов-гуманоидов Tesla Bot. Роботам планируют придать черты индивидуальной личности. Они смогут работать на заводах, ходить за покупками и заниматься прочими скучными вещами вместо людей.