А.Г.Трифонов. Optimization Toolbox - обзор

• Обзор и основные особенности
• Стандартный алгоритм
• Крупно-масштабный алгоритм

Обзор

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

Основные особенности

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

• Современные стандартные алгоритмы оптимизации.
• Нелинейная минимизация без ограничений.
• Нелинейная минимизация с ограничениями, включая задачи минимакса, достижения цели и полубесконечной минимизации.
• Квадратичное и линейное программирование.
• Нелинейный метод наименьших квадратов и подбор кривых с границами.
• Решение системы нелинейных уравнений.
• Линейный метод наименьших квадратов с ограничениями.
• Специализированные крупно-масштабные алгоритмы (большой размерности) для решения больших разреженных задач.
• Подбор данных с помощью подбора кривых, нелинейный метод наименьших квадратов, определение нулей нелинейных уравнений и системы нелинейных уравнений.
• Гибкая среда, которая обрабатывает ввод скаляра, вектора или матрицы. (Оптимизируемые функции могут быть записаны в виде сохраняемых функций или интерактивно с помощью командной строки MATLAB.)

Стандартный алгоритм

В Тулбоксе Оптимизация реализованы современные алгоритмы оптимизации. Основными алгоритмами минимизации без ограничений являются  квази-Ньютоновский метод BFGS и метод прямого поиска Нелдера-Мида с линейным поиском. Для задач минимизации с ограничениями, минимакса, достижения цели и полубесконечной оптимизации используются разновидности последовательного квадратичного программирования (SQP). Нелинейная задача наименьших квадратов решается с помощью методов Гаусса-Ньютона или Левенберга-Маркуарда. Подпрограммы для решения задач линейного и квадратичного программирования используют методы из активного набора в сочетании с проекционными методиками.

Стандартные алгоритмы обладают следующими особенностями:

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

Крупно-масштабный алгоритм

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

Данный тулбокс включает в себя алгоритмы решения крупно-масштабных задач, таких как:

• Линейное программирование.
• Нелинейный метод наименьших квадратов с границей.
• Нелинейная минимизация без ограничений.
• Нелинейная минимизация с ограничениями в виде границ.
• Нелинейная минимизация с линейными равенствами.
• Решение систем нелинейных уравнений.
• Квадратичная минимизация с ограничениями в виде границ.
• Квадратичная минимизация с линейными равенствами.
• Линейный метод наименьших квадратов с ограничениями в виде границ.

Новый крупно-масштабный алгоритм линейного программирования основан на методе Жин-Занга LIPSOL (Линейное программирование с расчетом внутренних точек), алгоритм одновременного решения прямой и двойственной задач с внутренними точками на основе метода Мерота предиктор-корректор.

Также для крупно-масштабного метода доступны некоторые формулировки квадратичного программирования и нелинейных объектов с ограничениями в виде границ или ограничениями в виде линейных равенств. Эти методы основаны на разработанных Томасом Ф. Колеманом алгоритмах крупно-масштабных доверительных областей и используют методы отражения Ньютона и проекционными методы для оперирования с ограничениями.

Крупно-масштабные алгоритмы обладают следующими особенностями:

• Матрицы Якобиана и Гессе рассчитываются автоматически с использованием метода конечных разностей (за исключением случая, когда они вводятся вместе с целевыми функциями).
• Образ разреженности матриц Якобиана или матрицы Гессе может обеспечить повышение эффективности использования конечных разностей.
• Принимаемые по умолчанию параметры оптимизации могут быть изменены посредством структуры параметров опций.
• Зависимые от задачи параметры могут быть переданы непосредственно в функции, что устраняет необходимость использования глобальных переменных.
• Выбор типа программы обработки разреженности, непосредственно или итеративно, задается в алгоритме оптимизации.
• Выбор типа предварительной обработки для решения систем линейных уравнений задается в алгоритме оптимизации.