Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 31
Простите, а о чем этот текст? Вы предлагаете, чтобы мы Вам данных и задач для тестирования Вашего авторского метода накидали? Или просто поделиться биографией? Или я что-то существенно упустил?
Текст о том какие реальные задачи можно решать методами оптимизации, об их широкой применимости.
Методы не авторские.
Предложение помочь хабра-читателям в применении и расширение кругозора.
А, если пожелают и есть задор, могут попробовать сами получить параметры описанной модели и оценят свой инструментарий.
Методы не авторские.
Предложение помочь хабра-читателям в применении и расширение кругозора.
А, если пожелают и есть задор, могут попробовать сами получить параметры описанной модели и оценят свой инструментарий.
Спасибо, хороший ответ.
Мне показалось, что если Вы хотите расширить кругозор и помочь в освоении, то надо сами алгоритмы и описывать. Если же Вы предлагаете посоревноваться, то хорошо бы дать файл с данными, а не только картинку с графиком. Дайте данные, я бы, из интереса, попробовал бы на стандартных матлабовских функциях.
Мне показалось, что если Вы хотите расширить кругозор и помочь в освоении, то надо сами алгоритмы и описывать. Если же Вы предлагаете посоревноваться, то хорошо бы дать файл с данными, а не только картинку с графиком. Дайте данные, я бы, из интереса, попробовал бы на стандартных матлабовских функциях.
arxiv.org/pdf/1308.4008.pdf развлекайся)
Спасибо, есть полезная инфо… 40 страниц :)
Но хотелось бы и прикладных, реальных задач, людям (и себе) помочь.
Но хотелось бы и прикладных, реальных задач, людям (и себе) помочь.
Вначале надо проверить же на тестовых задачах и сравнить с другими.
Вы своим глазам (последний график в статье) верите?
Почитайте комментарии.
Почитайте комментарии.
Эм… А что из данного графика следует? О_о Я разве говорил, что у вас алгоритмы фуфло, и программа хрень? Данный график говорит, что ваша программа что-то там решила. Это хорошо.
Но алгоритмов оптимизации, которые смогут решить подобные задачи много. Вот и нужно их сравнивать.
P.S. Может я пропустил, но я не увидел описания алгоритмов, которые использовались в качестве оптимизационных процедур.
Но алгоритмов оптимизации, которые смогут решить подобные задачи много. Вот и нужно их сравнивать.
P.S. Может я пропустил, но я не увидел описания алгоритмов, которые использовались в качестве оптимизационных процедур.
Уважаемый коллега, это, конечно, не довод, что прога «что-то там» решала ещё почти за 10 лет до вашего рождения, но если вам не понятно
А там, глядишь и станет понятно о чём пост и почему излишни описания алгоритмов (вы сами привели кучу отсылок в PDF, тягаться с инетом и вики?), и почему сравнивать алгоритмы — это, как ныне ваше поколение говорит, «ни о чём», ибо всё от задач зависит.
Если вам предлагают товар, качество которого вы объективно можете определить сами (предпоследний абзац статьи и комментарий 18 февраля 2015 в 15:41), то интересовать вас станет только цена и сроки, но никак не цвет обивки багажника Mini, на котором ездит любовница соседа продавца.
Спилите мушку почитайте-таки комментарии!
что из данного графика следует, может быть стоит самому поближе познакомиться с вопросом (начать можно с простейшего алгоритма, ссылка дана)?
А там, глядишь и станет понятно о чём пост и почему излишни описания алгоритмов (вы сами привели кучу отсылок в PDF, тягаться с инетом и вики?), и почему сравнивать алгоритмы — это, как ныне ваше поколение говорит, «ни о чём», ибо всё от задач зависит.
Если вам предлагают товар, качество которого вы объективно можете определить сами (предпоследний абзац статьи и комментарий 18 февраля 2015 в 15:41), то интересовать вас станет только цена и сроки, но никак не цвет обивки багажника Mini, на котором ездит любовница соседа продавца.
Кстати, более 72% упомянутых там статей были написаны когда программа уже работала :)
Довольно давно (при защите диссертации и работе на военно-космическом предприятии, Краснодар) был разработан инструментарий для решения задач оптимизации — поиска локального экстремума многопараметрической функции на некотором множестве ограничений для её параметров.
Можно поподробнее о том, как работали с ограничениями, и какие типы ограничений рассматривались?
На уровне интерфейса — задаётся (вычиляется при работе алгоритма) массив, все элементы которого д.б. положительны.
На уровне алгоритма — при вычисленных значениях элементов массива менее нуля — достраивается крутая гора вверх для целевой функции, заставляющая поиск вернуться на положительные значения улетевшего с минус эл-та массива ограничений.
Что внутри вычисления вектора ограничений не важно, важен знак результата.
На уровне алгоритма — при вычисленных значениях элементов массива менее нуля — достраивается крутая гора вверх для целевой функции, заставляющая поиск вернуться на положительные значения улетевшего с минус эл-та массива ограничений.
Что внутри вычисления вектора ограничений не важно, важен знак результата.
Какой математический вид у ограничений? Ограничения типа равенства/неравенства (если есть контроль знака, значит неравенства)? Какие требования на функции, которые их описывают? Что за «крутая гора»? Как я понимаю, это метод штрафных функций, но вы используете градиентный метод поиска экстремума. Можете сказать, какой вид у штрафа?
Напишите постановку задачи оптимизации, многое будет понятно.
Напишите постановку задачи оптимизации, многое будет понятно.
метод штрафных функций
Yes sir! Что и как вычисляется на каждом шаге поиска экстремума в каждом эл-те массива ограничений задаёте вы (программных ограничений нет), алгоритм «смотрит» на знак и коли < 0 — «штрафует».
… вы используете градиентный метод поиска экстремума
Э-э-э, где это сказано? Используется 4 разных метода! Иногда вручную их комбинирую для «дожимания» на финише поиска, по ситуации.
Напишите постановку задачи оптимизации
Это вы о последней 9-параметрической модели? Напишите «в личку» — пришлю исходные данные и ограничения. Можно и с Arastas'ом законтачиться, он, надеюсь, уже «пилит гирю», спасибо ему.
Э-э-э, где это сказано?
У Вас написано о градиентном спуске, а он относится к серии градиентных методов (методам первого порядка). Если целевая функция не дифференцируема в окрестности точки экстремума, применять градиентный метод для нее нельзя. В этом случае, что вычисляет программа, можно считать (прошу извинить) фикцией. Кроме того, для сходимости градиентного метода нужно, чтобы градиент целевой функции удовлетворял условию Липшица. Выход из ситуации — использовать методы нулевого порядка.
Это вы о последней 9-параметрической модели?
Это я о постановке задачи оптимизации с ограничениями (задача нелинейного программирования).
Внимательно читаем все буквы:
По поводу "постановки задачи оптимизации с ограничениями" — я ничего никуда не ставил :)
Вы полагаете, что прикладника интересуют дифференцируемость целевой в окрестности точки экстремума? Вы эти академические штучки это..., оставьте студентам :)
В реальной жизни намного проще добавить несколько лишних циклов с разными комбинациями методов и размеров начальных шагов (всё равно считается быстро), чем подбирать наилучший.
Вы уже свои мозги в программирование методов вложили, вылизали алгоритмы, теперь пусть работают. Да все сразу можно запустить для начала («возьмите молоток побольше»), а там они всё про себя (в этой конкретной ситуации) и скажут — какой двигает целевую, а какой топчется (у кого что дифференцируется :).
"Опыт — критерий истины" — целевая снизилась?, относительное ср.кв. отклонение составило единицы процента (соизмеримо с погрешностями измерений)?, график лёг хорошо? Гипс — параметры найдены достаточно точно!
Вот когда погрешности аппроксимации не устраивают — иликровати формулу меняем, или девок методы. Чтобы этой обоймы (4 метода) не хватало — не было такого.
Используется 4 разных метода!
По поводу "постановки задачи оптимизации с ограничениями" — я ничего никуда не ставил :)
Вы полагаете, что прикладника интересуют дифференцируемость целевой в окрестности точки экстремума? Вы эти академические штучки это..., оставьте студентам :)
В реальной жизни намного проще добавить несколько лишних циклов с разными комбинациями методов и размеров начальных шагов (всё равно считается быстро), чем подбирать наилучший.
Вы уже свои мозги в программирование методов вложили, вылизали алгоритмы, теперь пусть работают. Да все сразу можно запустить для начала («возьмите молоток побольше»), а там они всё про себя (в этой конкретной ситуации) и скажут — какой двигает целевую, а какой топчется (у кого что дифференцируется :).
"Опыт — критерий истины" — целевая снизилась?, относительное ср.кв. отклонение составило единицы процента (соизмеримо с погрешностями измерений)?, график лёг хорошо? Гипс — параметры найдены достаточно точно!
Вот когда погрешности аппроксимации не устраивают — или
По поводу «постановки задачи оптимизации с ограничениями» — я ничего никуда не ставил :)
Тогда у Вас не задача оптимизации, а что-то другое, местами похожее на неё :))
На мой взгляд, нельзя применять дилетантский подход к решению математических задач. Вы пишите о технической реализации алгоритма. Математика гарантирует правильность получения результата (выполнение такого свойства алгоритма, как массовость). То, что при определенных исходных данных у Вас получилось что-то похожее на истину, — это частные случаи.
Вы полагаете, что прикладника интересуют дифференцируемость целевой в окрестности точки экстремума?
О каких прикладниках идет речь? Перед тем, как бросаться решать задачу, хорошо бы иметь готовые теоремы, позволяющие установить, а есть ли решение у данной задачи и единственно ли оно. Только потом применять тот или иной метод, и то, проверив условия, когда это делать можно (условия сходимости). Иначе может случиться так, что мы будем искать черную кошку в темной комнате, когда ее там нет :)
P.S. Мои студенты тут ни при чем :))
… не задача оптимизации, а что-то другое, местами похожее на неё
Ок, перефразирую заключительную часть статьи: решается прикладная задача определить, описывает ли модель U3(X,Y,Z) приведённые экспериментальные данные, если да, то при каких параметрах (a1...a9). Поскольку модель теоретическая, её параметры имеют некий физический смысл и, следовательно, ограничения, которые прилагаются к постановке задачи (ОДЗ). Считаем, что модель хорошо описывает эмпирику, если средние отклонения не превышают удвоенной/утроенной погрешности измерения предоставленных данных. Последний критерий заказчик, хорошо знающий как в жизни близка обсуждаемая теория к практике, уточняет отдельно или оценивает сам по предоставленным расчётам.
Эта задача решается методом поиска/подбора параметров модели по минимуму среднеквадратического отклонения (или по максимальной/средней невязке) от предоставленных экспериментальных данных с учётом ОДЗ параметров модели.
Классическая прикладная задача оптимизации, не теоретическая. Если не согласны — дальше нет смысла дискутировать.
А если тут расхождений у нас нет — они начинаются:
целевая функция не дифференцируема в окрестности точки экстремума
О, а мы знаем «окрестности точки экстремума»?!
… хорошо бы иметь готовые теоремы, позволяющие установить, а есть ли решение у данной задачи и единственно ли оно. Только потом применять тот или иной метод, и то, проверив условия, когда это делать можно (условия сходимости).
Вот это всё по моему твёрдому мнению и опыту на практике — лишнее! Обратите внимание, не неправильное — лишнее! Нам ехать, а не шашечки (теории).
Слезайте со своего белоснежного сферического коня в теоретическом вакууме на грешную землю и
… будем искать черную кошку в темной комнате...
А вот есть она там или нет — покажет применение/комбинация разных методов, как уже описал выше.
Если такой, как Вы выразились, «дилетантский подход» даёт хорошую аппроксимацию эмпирики (критерии упомянуты) — задача решена… конечно же случайно
… получилось что-то похожее на истину
И случайно, но регулярно, получается так, что такого, чтобы «этой обоймы (4 метода) не хватало — не было...», если, конечно, нет вранья в модели и исходных данных (отдельные человеческие/измерительные ошибки МНК «прожуёт» или сами отсеете на графике при анализе).
А вот сможет ли кто-либо решать подобные задачи (в разумное время) Вашими способами, имея «готовые теоремы» — покажите! Готов прислать все исходные данные.
И последнее, по поводу
… есть ли решение у данной задачи и единственно ли оно.
Придумать полиэкстремальную функцию, на которой обломают зубы известные методы поиска, можно. Полагаю, у Harrix в вышеприведённой "простыне" таковые имеются, для того и существует стохастический алгоритм поиска, меня им ещё ~40 лет назад пугали.
Но это теория, точка. В реальной жизни не встречал, как и у подъезда — динозавра,
блондинки — попадались, одна женила :)
Итого:
1) если ищем аппроксимацию данных абстрактной функцией (не наш рассматриваемый случай, но задача распространённая, это для полноты анализа) — то неглобальный экстремум не опасен, ибо:
— критерием является «хорошее» сглаживание данных, а значит не важно какой это экстремум (результат устраивает), пусть их где-то рядом хоть килограмм ещё более глубоких;
— функции для аппроксимаций хорошо известны, обычно несложные и никакими полиэкстремумами не грозят по определению, иначе их бы не использовали;
2) наш случай, реальные модели, имеющие физический смысл, — полиэкстремальными быть не могут, иначе это плохая модель, точка.
Математика гарантирует правильность получения результата
с учётом нерешённости в общем случае вопроса о глобальном экстремуме — никто ничего не гарантирует, не так ли?
И для глобальноэкстремофобов скажу, что при современных настольных вычислительных ресурсах (и грамотно запрграммированных методах) ничто не мешает на ночь запустить расчёт с оч-ч-чень подробным перебором всех закоулков допустимой области параметров, ala brute force атака. Параноики могут и стохастический метод (Монте-Карло) добавить в обойму своих методов.
О, а мы знаем «окрестности точки экстремума»?!
Это какая-то часть (шар) области допустимых решений.
с учётом нерешённости в общем случае вопроса о глобальном экстремуме — никто ничего не гарантирует, не так ли?
Если целевая функция выпуклая, то экстремум есть, и он один (сколько бы варьируемых параметров у нее ни было). Это одна из теорем.
… И вместо поиска экстремума будем определять дифференцируемость в «окрестности»?
Спустимся на землю, «победителей не судят» — если результат получен, устраивает, единственное что можно, для очистки совести, сделать — покрутить все методы с вариациями начального шага — а вдруг есть ещё решение.
Никогда на реальных задачах не случалось. Вас устроит никогда?
И, чтобы уж совсем по земле, босиком: вот реальная задача (ей тоже лет 40 и она вечно актуальна):
техпроцесс, сложный и дорогой, например, производство интегральных микросхем. Есть некоторый, заведомо избыточный (!) набор параметров (хорошо измеряемых), влияющих на коэффициент выхода годных (только вот как?). Технологи за доли прироста этого процента маму родную продадут. Надо определить набор параметров, максимально повышающий выход годных.
От смены параметров до получения результата (КВГ= столько-то) может проходить несколько дней (!), и стоит эта точка на кривой ох уж какие деньги!
И новый шаг по параметрам — опять время и деньги.
И что тут делать, если живым не уволят?
Правильно, по ранее полученным точкам строим всё время уточняемую модель, по ней получаем наиболее перспективное сочетание следующего набора параметров и стартуем следующий шаг (процесс)…
Как представляете себе дифференцируемость в «окрестности»?
Если целевая функция выпуклая...Я тоже могу взобраться на сферического коня: в формулировке
Математика гарантирует правильность получения результатаникаких оговорок (если...) не было!
Спустимся на землю, «победителей не судят» — если результат получен, устраивает, единственное что можно, для очистки совести, сделать — покрутить все методы с вариациями начального шага — а вдруг есть ещё решение.
Никогда на реальных задачах не случалось. Вас устроит никогда?
И, чтобы уж совсем по земле, босиком: вот реальная задача (ей тоже лет 40 и она вечно актуальна):
техпроцесс, сложный и дорогой, например, производство интегральных микросхем. Есть некоторый, заведомо избыточный (!) набор параметров (хорошо измеряемых), влияющих на коэффициент выхода годных (только вот как?). Технологи за доли прироста этого процента маму родную продадут. Надо определить набор параметров, максимально повышающий выход годных.
От смены параметров до получения результата (КВГ= столько-то) может проходить несколько дней (!), и стоит эта точка на кривой ох уж какие деньги!
И новый шаг по параметрам — опять время и деньги.
И что тут делать, если живым не уволят?
Правильно, по ранее полученным точкам строим всё время уточняемую модель, по ней получаем наиболее перспективное сочетание следующего набора параметров и стартуем следующий шаг (процесс)…
Как представляете себе дифференцируемость в «окрестности»?
Чем предлагаемый вами подход ( программа ) лучше известных пакетов SCILAB , MATLAB, которые тоже позволяют решать оптимизационные задачи?
Можете ли вы привести пример задачи, которая средствами SCILAB, MATLAB не решаются, а вы решили?
+ По этим пакетам куча литературы.
Можете ли вы привести пример задачи, которая средствами SCILAB, MATLAB не решаются, а вы решили?
+ По этим пакетам куча литературы.
А вот на этот вопрос, надеюсь, поможет ответить уважаемый Arastas. Выслал ему исходные данные для проверки MathLab'а. И пришлю любому желающему тож.
Куча литературы требует кучу времени, а я предлагаю решение щас.
Начинал когда и слова такого (MathLab), да и «IBM PC» в России не знали.
Жизнь пока не заставила искать другую лошадь (*Lab/*Cad & Co), старая пока ладно скачет :)
Но интересно, конечно, сравнить/оценить!
По этим пакетам куча литературы
Куча литературы требует кучу времени, а я предлагаю решение щас.
Начинал когда и слова такого (MathLab), да и «IBM PC» в России не знали.
Жизнь пока не заставила искать другую лошадь (*Lab/*Cad & Co), старая пока ладно скачет :)
Но интересно, конечно, сравнить/оценить!
что пишет Википедия про Scilab Ссылка
т.е. продукту уже лет 20. Я верю, что у вас значительный опыт в решении задач оптимизации, но странно что вы сами не смотрели по сторонам. Мне кажется, что вычисления выполненные в Scilab легче проверить, чем ваши.
1 Учебная литература позволяет легко освоить пакеты ( довольно близкие ), без затрат лишнего времени.
2 Мне кажется, что вы предлагаете скорее не решение задачи, а услугу по ее решению.
3 На вопрос, чем ваш подход лучше и в какой области лучше, ответить все же должны вы самостоятельно.
С 1994 года распространяется вместе с исходным кодом через Интернет
т.е. продукту уже лет 20. Я верю, что у вас значительный опыт в решении задач оптимизации, но странно что вы сами не смотрели по сторонам. Мне кажется, что вычисления выполненные в Scilab легче проверить, чем ваши.
Куча литературы требует кучу времени, а я предлагаю решение щас.
1 Учебная литература позволяет легко освоить пакеты ( довольно близкие ), без затрат лишнего времени.
2 Мне кажется, что вы предлагаете скорее не решение задачи, а услугу по ее решению.
3 На вопрос, чем ваш подход лучше и в какой области лучше, ответить все же должны вы самостоятельно.
С 1994 года распространяется...
Вы не обратили внимание на мою реплику 18 февраля 2015 в 11:36.
Когда начал распространяться Scilab, программой уже более 15 лет пользовался :)
Мне кажется, что вычисления выполненные в Scilab легче проверить, чем ваши.
А мне кажется, извините, что Вы не всё правильно понимаете:
какой-либо обман исключён, ибо по предоставленным результатам каждый может сам оценить достигнутую реально точность расчёта.
т.е. вы сами (например, в Excel, да хоть в калькуляторе) подставляете в формулу исходные данные, полученные мною параметры модели и вычисляете любые точки на кривой. Всё и увидите, зачем Scilab?!
вы предлагаете скорее не решение задачи, а услугу по ее решению
Решение предложила теория (разными способами), я показал, что это работает и могу помочь.
чем ваш подход лучше и в какой области лучше, ответить все же должны вы
Отвечаю на то, что мне интересно. Желающие сравнивать имеют на это жизнь.
1 в реплике от 18 февраля 2015 в 11:36 нет слов о Scilab
2 про обман я нечего не говорил, вы цитируете сами себя. Проблема в том что достоверно найти глобальный экстремум функции многих переменных можно далеко не всегда, в том числе по причине недостатка вычислительных ресурсов.
3 если 15 лет вы отсчитываете от 1994, то с 1980 года вы пользовались видимо не программой, а алгоритмом. Ведь с тех пор в IT изменилось почти все, в том числе появился Excel и VBA.
2 про обман я нечего не говорил, вы цитируете сами себя. Проблема в том что достоверно найти глобальный экстремум функции многих переменных можно далеко не всегда, в том числе по причине недостатка вычислительных ресурсов.
3 если 15 лет вы отсчитываете от 1994, то с 1980 года вы пользовались видимо не программой, а алгоритмом. Ведь с тех пор в IT изменилось почти все, в том числе появился Excel и VBA.
нет слов о Scilab
Зато есть слова о времени…
найти глобальный экстремум… можно далеко не всегда
А зачем практику глобальный экстремум (необъятное не объять, кто ж спорит), зато, если он посмотрит на воспроизведение эксприментальных данных идентифицированной моделью, сам себе всё скажет (а заказчик заплатит влёгкую и за скорость добавит).
… вы пользовались видимо не программой, а алгоритмом
Вы не поверите, с 1972 пользуюсь Fortran'ом и это не алгоритм :)
Писанная на нём оптимизация работала ещё в 1977-м на перфокартах. Это сейчас она на VBA, прочитайте 4-й абзац статьи.
И, чтобы закруглить диспут и выйти из шор академического подхода (ничего против него не имею, но не в этой жизни и не в текущем бэкграунде):
Вы действительно полагаете, что прикладной математик (не академический преподаватель, а работающий «на земле»), имея давно освоенный инструмент, подходящий для решения текущих задач (ныне надо 2...5 часов, вместе с настройкой на задачу), решая очередную подобную (а с опытом они все подобные!), станет:
— проводить анализ всего к тому моменту наработанного софта под класс задач (ладно, такой анализ он делал прошлый раз, но надо же глянуть что нового появилось?);
— приобретать потенциально подходящее ПО (и не одно) и пробовать на тестовых задачах;
— глубже осваивать лучшее выбранное ПО и, наконец, решать с ним текущую задачу.
Это из какой жизни?!
Нет, он решит её привычно и быстро. И только если инструмент/результат его/заказчика не устроит, начнёт оглядываться по сторонам (какой другой «молоток» взять в руку).
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Прикладная практика оптимизации и немного истории