Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python

Автор: admin от 13-08-2017, 08:25, посмотрело: 873

Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python


Trust-region метод (TRM) является одним из самых важных численных методов оптимизации в решении проблем нелинейного программирования (nonlinear programming problems). Метод базируется на определении региона вокруг лучшего решения, в котором квадратичная модель аппроксимирует целевую функцию.



Методы линейного поиска (line search) и методы trust-region генерируют шаги с помощью аппроксимации целевой функции квадратичной моделью, но использую они эту модель по-разному. Линейный поиск использует её для получения направления поиска и дальнейшего нахождения оптимального шага вдоль направления. Trust-region метод определяет область (регион) вокруг текущей итерации, в котором модель достаточно аппроксимирует целевую функцию. В целях повышения эффективности направление и длина шага выбираются одновременно.



Trust-region методы надежны и устойчивы, могут быть применены к плохо обусловленным задачам и имеют очень хорошие свойства сходимости. Хорошая сходимость обусловлена тем, что размер области TR (обычно определяется модулем радиус-вектора) на каждой итерации зависит от улучшений сделанных на предыдущих итерациях.
->

Категория: Программирование

 

Программирование ? информатика

Автор: admin от 9-08-2017, 00:00, посмотрело: 389

Разработка программного обеспечения как будто в худшую сторону отличается от других дисциплин информатики.



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



А теперь я работаю с разработкой ПО, и это невыносимо скользкая тема. Ни одна концепция точно не определена. Результаты оцениваются с характеристиками «обычно» или «в целом». Сегодняшние исследования могут или не могут помочь завтрашней работе. Новые подходы часто опровергают предыдущие методы, а сами ярко горят недолгое время, а потом выходят из моды, когда всплывают их ограничения. Мы верили в структурное программирование. Затем начали верить в языки четвёртого поколения, потом в объектно-ориентированные методы, потом в экстремальное программирование, а теперь, может быть, в open source.
->

Категория: Программирование, Веб-разработка

 

Решение закрытой транспортной задачи с дополнительными условиями средствами Python

Автор: admin от 7-08-2017, 19:35, посмотрело: 794

Постановка задачи



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



Решение закрытой транспортной задачи средствами Python с классическим условиями для поставщиков и потребителей товара приведено в моей статье “Решение задач линейного программирования с использованием Python” [1].



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

Категория: Веб-разработка, Windows

 

Математический пакет для Android — «Микро-Математика» — теперь с открытым исходным кодом

Автор: admin от 2-08-2017, 05:00, посмотрело: 338

Некоторое время назад я писал здесь о «Микро-Математике» — математическом пакете для Android, который я разработал в качестве хобби-поделки. Этим летом исполняется три года с тех пор, как «Микро-Математика» была выложена в Google Play на всеобщее обозрение. С тех пор программа развивалась дальше, и вот настал момент, когда доход от Google Play окупил разработку. В связи с этим я не вижу смысла дальше утаивать исходный код от общественности и перевожу проект в разряд Open Source. Тех, кому интересно познакомиться с репозиторием «Микро-Математики» на github, и, быть может, поучаствовать в дальнейшем развитии проекта, прошу под кат.

->

Категория: Веб-разработка, Android

 

Разбор задач финала Яндекс.Алгоритма 2017

Автор: admin от 27-07-2017, 14:55, посмотрело: 434

На днях завершился Яндекс.Алгоритм 2017 — наш чемпионат по спортивному программированию. В финальном раунде 25 финалистам нужно было за два с половиной часа решить шесть задач. Первое место вновь завоевал Геннадий Короткевич из питерского ИТМО — это уже четвёртая его победа после состязаний 2013, 2014 и 2015 года. Никола Йокич из Швейцарской высшей технической школы Цюриха и выпускник Университета Токио Макото Соэдзима стали вторым и третьим, повторив свои прошлогодние результаты. Вот как распределились денежные призы: победа — 300 тысяч рублей, второе место — 150 тысяч, третье — 90 тысяч.



Разбор задач финала Яндекс.Алгоритма 2017



Заявки на участие в Алгоритме 2017 подали 4840 человек. Более 60% из них — россияне. На втором месте по количеству заявок — Беларусь, далее следуют Украина, Индия и Китай. В общей сложности на чемпионат зарегистрировались жители нескольких десятков стран, включая Сингапур, Камерун, Венесуэлу и Перу.



Мы по традиции публикуем формулировки и разобранные решения задач финала.

->

Категория: Программирование, Яндекс

 

Точное вычисление средних и ковариаций методом Уэлфорда

Автор: admin от 24-07-2017, 13:45, посмотрело: 218

Метод Уэлфорда — простой и эффективный способ для вычисления средних, дисперсий, ковариаций и других статистик. Этот метод обладает целым рядом прекрасных свойств:




  • достигает отличных показателей по точности решений;

  • его чрезвычайно просто запомнить и реализовать;

  • это однопроходный онлайн-алгоритм, что крайне полезно в некоторых ситуациях.



Оригинальная статья Уэлфорда была опубликована в 1962 году. Тем не менее, нельзя сказать, что алгоритм сколь-нибудь широко известен в настоящее время. А уж найти математическое доказательство его корректности или экспериментальные сравнения с другими методами и вовсе нетривиально.



Настоящая статья пытается заполнить эти пробелы.



Точное вычисление средних и ковариаций методом Уэлфорда

->

Категория: Программирование

 

Быстрое восстановление данных. Схема бабочки для регенерирующих кодов

Автор: admin от 20-07-2017, 18:35, посмотрело: 280

Быстрое восстановление данных. Схема бабочки для регенерирующих кодов


Для кодов, описанных в предыдущей статье про восстановление данных, предполагалась постановка задачи, при которой минимизируется количество дисков, необходимых при операции восстановления. В [2] обсуждается применение сетевого кодирования к задачам хранения данных, получившее значительное внимание исследователей в последние годы. Здесь рассматривается не оптимизация количества дисков, необходимых для восстановления данных, а минимизация возникающего при этом сетевого трафика.



Предположим, что система хранения состоит из [i]n[/i] узлов. Рассмотрим файл, состоящий из B символов поля [i]GF(q)[/i], который кодируется в n? символов над [i]GF(q)[/i] и распределяется по узлам, так, что каждый узел хранит ? символов. Код построен таким образом, что данные могут быть целиком восстановлены по информации с [i]k[/i] узлов. При этом для восстановления данных одного узла достаточно получить [i]?

Категория: Программирование, Системное администрирование

 

Постквантовая криптография и закат RSA — реальная угроза или мнимое будущее?

Автор: admin от 17-07-2017, 09:20, посмотрело: 498

Постквантовая криптография и закат RSA — реальная угроза или мнимое будущее? RSA, эллиптические кривые, квантовый компьютер, изогении… На первый взгляд, эти слова напоминают какие-то заклинания, но все куда проще сложнее, чем кажется!



Необходимость перехода к криптографии, устойчивой к атаке на квантовом компьютере, уже официально анонсирована NIST и NSA, из чего вывод довольно-таки простой: пора вылезать из зоны комфорта!



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



Чтобы разобраться в тонкостях криптографии на эллиптических кривых, проследить новомодные веяния постквантовой криптографии и даже прикоснуться к ней с помощью библиотеки Microsoft SIDH, добро пожаловать под кат, %username%!
->

Категория: Информационная безопасность, Microsoft, Криптография

 

Метод BFGS или один из самых эффективных методов оптимизации. Пример реализации на Python

Автор: admin от 16-07-2017, 07:40, посмотрело: 869

Метод BFGS или один из самых эффективных методов оптимизации. Пример реализации на Python


Метод BFGS, итерационный метод численной оптимизации, назван в честь его исследователей: Broyden, Fletcher, Goldfarb, Shanno. Относится к классу так называемых квазиньютоновских методов. В отличие от ньютоновских методов в квазиньютоновских не вычисляется напрямую гессиан функции, т.е. нет необходимости находить частные производные второго порядка. Вместо этого гессиан вычисляется приближенно, исходя из сделанных до этого шагов.

Существует несколько модификаций метода:
L-BFGS (ограниченное использование памяти) — используется в случае большого количества неизвестных.
L-BFGS-B — модификация с ограниченным использованием памяти в многомерном кубе.

Метод эффективен и устойчив, поэтому зачастую применяется в функциях оптимизации. Например в SciPy, популярной библиотеки для языка python, в функции optimize по умолчанию применяется BFGS, L-BFGS-B.

Категория: Программирование

 

Безытеративное обучение однослойного персептрона. Задача классификации

Автор: admin от 16-07-2017, 00:45, посмотрело: 282

Я продолжаю цикл статей по разработке метода безытеративного обучения нейронных сетей. В этой статье будем обучать однослойный персептрон с сигмоидальной активационной ф-ей. Но этот метод можно применить для любых нелинейных биективных активационных ф-й с насыщением и первые производные которых симметричны относительно оси OY.
->

Категория: Программирование

 
Назад Вперед