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

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

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

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

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

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

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

1. «Waterfall Model» — не подходит по причине как минимум того, что четко определенных требований у меня нет, есть лишь набор идей, между которыми придется впоследствии наладить взаимодействие,
2. «V-Model» — не подходит по той же причине,
3. «Incremental Model» — более подходящая по сравнению с предыдущими модель, однако тут так же требуется подробная формализация
4. «RAD Model» — модель, которая больше подходит команде опытных специалистов,
5. «Agile Model» — отлично подходит по критерию отсутствия необходимости конкретизации требований, а также по гибкости в процессе разработки,
6. «Iterative Model» — несмотря на то что в работе указана необходимость четкого определения целей, идейно такая модель кажется близкой (учитывая слова «Основная задача должна быть определена, но детали реализации могут эволюционировать с течением времени»),
7. «Spiral Model» — направлена для реализации больших проектов, к которым вряд ли можно отнести предполагаемое ПО.

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

Итак, в этой работе я расскажу:

1. О задаче оптимизации и причинах ее выбора в качестве основополагающего объекта изучения,
2. Об основных абстракциях и их реализациях, которые позволят использовать подход, основывающийся на решении прикладных задач путем сведения к задаче оптимизации,
3. Об алгоритме K-Means, простейшем алгоритме Random Search и как заставить их дружить и работать на благо единой цели.

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

Обычно под решением задачи оптимизации, как бы это банально и косноязычно ни звучало, понимается поиск некоторого «оптимального» (с точки зрения условий задачи) объекта. Понятия «оптимальности» варьируются от одной предметной области к другой. Например, в задаче поиска минимума функции требуется найти точку, которой соответствует наименьшее значение целевой функции, в задача мета-оптимизации требуется определить параметры алгоритма, при которых он дает наиболее точный результат/наиболее быстро отрабатывает/дает наиболее стабильный результат, в задаче синтеза оптимального управления требуется синтезировать контроллер, позволяющий перевести объект в терминальное состояние за наименьшее время и т.д. Уверен, что каждый специалист сможет продолжить это список задачами, связанными с его профессиональной сферой.

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

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

Существует огромное количество алгоритмов решения этой задачи. Условно их можно разделить на две группы:

аналитические алгоритмы:

• имеют более узкий круг решаемых задач в связи с тем, что могут накладывать ограничения на компоненты задачи,
• могут вводить в задачу объекты более высокого уровня (например, производные определенного порядка),
• несомненным достоинством таких методов является то, что по большей части они позволяют гарантированно получить результат определенной точности.

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

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

Вследствие того что почти любую процедуру/функцию/алгоритм можно рассматривать как некоторое преобразование, будем оперировать с этим объектом как с одним из базовых.

Предлагается следующая иерархия между различными типами преобразований:

Остановимся на элементах поподробнее:

• Неоднородное преобразование (Inhomogeneous Transformation) — самый общий вид преобразования, когда классы входного и выходного объекта могут быть различными,
• Однородное преобразование (Homogeneous Transformation) — частный вид неоднородного преобразования, когда классы входного и выходного объекта одинаковые,
• Векторная функция (Vector Function) — преобразование, которой трансформирует вектор, состоящий из элементов множества A, в другой вектор, состоящий из элементов того же множества,
• Функция (Function) — аналогична векторной функции (за исключением того, что выходной элемент теперь является скаляром),
• Метрика (Metric) — некоторое оценивающее преобразование, ставящее в соответствие объекту числовое значение.

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

Я думаю, что естественным будет определить алгоритм как набор трех операций: инициализация, итеративная часть и терминация. На вход алгоритма подается некоторое задание (Task). В ходе инициализации происходит генерация начального состояния (State) алгоритма, которое модифицируется в ходе повторения итеративной части. В конце с помощью процедуры терминации из последнего состояния алгоритма создается объект, соответствующий типу R выходного параметра алгоритма.

Таким образом, для создания конкретного алгоритма, необходимо будет переопределить три описанные ранее процедуры.

Что ж, первые два пункта обещанной программы освещены, пора переходить к третьему.

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

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

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