Рубрика «методы оптимизации» - 2

Прикладное применение задачи нелинейного программирования

2017-05-15 в 5:43, admin, рубрики: k-means, random search, scala, Алгоритмы, кластеризация, математика, машинное обучение, методы оптимизации, оптимальное управление, Программирование, эвристические алгоритмы

Доброго времени суток!

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

Закончив специалитет и готовясь к защите кандидатской диссертации, я задался вполне логичным вопросом: «а что же дальше?» Имея за плечами опыт как обычной работы, так и исследовательской, я вновь вернулся к той самой идее, которая, казалось бы, должна была утонуть под толщей пыли. Но вернулся я к этой идее в более осознанной форме.

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

Ну что ж, всем заинтересовавшимся:
Читать полностью »

Алгоритм Левенберга — Марквардта для нелинейного метода наименьших квадратов и его реализация на Python

2016-08-26 в 16:16, admin, рубрики: curve-fitting, data mining, Алгоритмы, математика, машинное обучение, метод наименьших квадратов, методы оптимизации

Нахождение экстремума (минимума или максимума) целевой функции является важной задачей в математике и её приложениях (в частности, в машинном обучении есть задача curve-fitting). Наверняка каждый слышал о методе наискорейшего спуска (МНС) и методе Ньютона (МН). К сожалению, эти методы имеют ряд существенных недостатков, в частности — метод наискорейшего спуска может очень долго сходиться в конце оптимизации, а метод Ньютона требует вычисления вторых производных, для чего требуется очень много вычислений.

Для устранения недостатков, как это часто бывает, нужно глубже погрузиться в предметную область и добавить ограничения на входные данные. В частности: МНС и МН имеют дело с произвольными функциями. В статистике и машинном обучении часто приходится иметь дело с методом наименьших квадратов(МНК). Этот метод минимизирует сумму квадрата ошибок, т.е. целевая функция представляется в виде:

Алгоритм Левенберга — Марквардта для нелинейного метода наименьших квадратов и его реализация на Python - 2

Алгоритм Левенберга — Марквардта используется для решения нелинейного метода наименьших квадратов. Статья содержит:

объяснение алгоритма
объяснение методов: наискорейшего спуска, Ньтона, Гаусса-Ньютона
приведена реализация на Python с исходниками на github
сравнение методов

Читать полностью »

Алгоритм TILT или нестандартное использование ранга матрицы

2014-12-10 в 10:18, admin, рубрики: computer vision, линейная алгебра, методы оптимизации, обработка изображений

Сегодня мы рассмотрим алгоритм TILT (Transform Invariant Low-rank Texture) и множество его методов применения в области Computer Vision. Статья будет нести несколько обзорный характер, без плотного углубления в математические дебри.
Алгоритм TILT или нестандартное использование ранга матрицы - 1
Читать полностью »

Транспортная задача с партийными перевозками(«с трейлерами»)

2014-01-14 в 0:10, admin, рубрики: Алгоритмы, кибернетика, математика, методы оптимизации, Программирование, метки: Алгоритмы, кибернетика, методы оптимизации

Требуемые знания: знакомство с методами линейного программирования, методы решения транспортной задачи(особенно метод потенциалов).

Год назад, на третьем курсе в качестве одной из лабораторных работ по курсу «Методы оптимизации» мне задали реализовать решение транспортной задачи, но с одним небольшим условием: перевозки происходят партиями. Это значит, что теперь, в отличие от классической постановки, оплачивается перевозка партии товаров (e.g. 10 штук), и, даже если Вам надо перевезти 11 штук, Вы заплатите за две партии(в один трейлер 11 штук не влезут). Казалось бы, мелкое дополнение, однако как теперь решать задачу, да хотя бы как её формализовать? Как студенту кафедры прикладной математики, мне было не привыкать, что великий google.ru чего-то не знает, но каково же было моё удивление, когда ни его старший брат — англоязычный google, ни тьма перебранных мной книг по теории оптимизации не смогли ответить на этот вопрос.
Читать полностью »

Симплекс-метод

2013-07-04 в 12:46, admin, рубрики: Алгоритмы, методы оптимизации, Песочница, метки: методы оптимизации

Преамбула

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

Постановка

Крайне важную нишу в методах оптимизации занимают задачи линейного программирования (ЛП). Они заключаются в минимизации (или максимизации) целевого линейного функционала на многомерном пространстве при наличии ограничений, заданных в виде линейных неравенств. Формально каноническая задача ЛП выглядит следующим образом:
Требуется найти Симплекс метод при заданных ограничениях . Для ясности: x — вектор переменных, C — вектор коэффициентов (C^T[N]*x[N] и задает линейный функционал). Матрица А является матрицей полного ранга, иначе говоря rang A[M, N] = min(M, N).
Приведем тривиальный пример. Допустим, мы ищем Симплекс метод при условиях:
Для лучшего представления прикладываю график множества ограничений:

Читать полностью »