Optimization Toolbox – ОптимизацияOptimization Toolbox включает программы широко известных методов минимизации и максимизации линейных и нелинейных функций. Эти программы могут быть использованы для решения сложных задач оптимизации стоимости, надежности и качества для различных приложений. В пакет включены версии традиционных и новейших алгоритмов оптимизации, в том числе безусловная оптимизация (метод симплексного поиска Нелдера-Мида и квази-ньютоновский метод БФШ), условная, многокритериальная оптимизация и метод минимакса, методы линейного и квадратичного программирования. Ведущий раздела Optimization Toolbox:^ Трифонов Александр Георгиевич - доктор технических наук, главный научный сотрудник лаборатории моделирования Объединенного института энергетических и ядерных исследований Национальной Академии наук Беларуси. Материалы раздела Optimization Toolbox: Optimization Toolbox 2.2 Руководство пользователя А.Г.Трифонов. "Постановка задачи оптимизации и численные методы ее решения" Optimization Toolbox 3 Список литературы по материалам Optimization Toolbox Список функций Optimization Toolbox Статьи, материалы по практическим приложениям Список Интернет-ресурсовMathWorks: Documentation (Release 14) \ Optimization Toolbox^ А.Г.Трифонов. "Optimization Toolbox 2.2 Руководство пользователя ": Содержание А.Г.Трифонов. Optimization Toolbox - обзор Новая версия - Optimization Toolbox 2.2 Примеры решения оптимизационных задач Установка принимаемых по умолчанию параметров Вывод отображения итерационных значений Многократный способ вызова функции вывода информации Оптимизация встроенных объектов вместо М-файлов Типичные проблемы и способы их решения Преобразование старых кодов в синтаксис Версии 2 Стандартные алгоритмы Обзор методов оптимизации Оптимизация без наличия ограничений Квазиньютоновские методы Линейный поиск Квадратичная интерполяция Кубическая интерполяция Реализация квазиньютоновского метода Корректировка Гессиана Методы линейного поиска Кубический полиномиальный метод. Процедура кубического полиномиального линейного поиска Смешанный кубический/квадратичный полиномиальный метод Оптимизация методом наименьших квадратов Метод Ньютона-Гаусса Метод Левенберга-Гаусса Реализация нелинейного метода наименьших квадратов Реализация метода Ньютона-Гаусса Реализация метода Левенберга-Марквардта Системы нелинейных уравнений Метод Ньютона-Гаусса Метод ломаных доверительных областей Реализация решения нелинейных уравнений Реализация Ньютона-Гаусса Реализация метода ломаных доверительных областей Оптимизация при наличии ограничений Последовательноое квадратичное программирование (SQP) Подзадача квадратичного программирования QP Реализация метода (SQP) Корректировка матрицы Гессе Решение задачи квадратичного программирования Линейный поиск и функции выгоды Алгоритм симплексного метода Основной алгоритм. Предварительная подготовка. Использование симплексного алгоритма. Основные и не основные переменные. Литература Многокритериальная оптимизация Введение в многокритериальную оптимизацию. Стратегия взвешенных сумм Метод ε-ограничений Метод достижения цели. Алгоритм реализации метода достижения цели Избранная библиография Алгоритмы большой размерности Методы на основе использования доверительных областей в задачах нелинейной оптимизации Сопряженные градиенты с предварительной обработкой данных АлгоритмЗадачи с линейными ограничениями Ограничения типа линейных равенств Боксовые ограничения Нелинейный метод наименьших квадратов Квадратичное программирование Линейный метод наименьших квадратов Линейное программирование для задач большой размерности Основной алгоритм Этапы предварительной обработки данных Избранная библиография Аргументы функций Входные аргументы Выходные аргументы Параметры опций оптимизации Функции вывода Структура функции вывода Поля для optimValues Соответствующие выходные аргументы Отображение командной строки Вырождение Состояния алгоритма Флаг остановки Остановка операции оптимизации на основе данных в параметре optimValues Остановка оптимизации по вводу из GUI Алфавитный список функций ^ А.Г.Трифонов. "Постановка задачи оптимизации и численные методы ее решения"Содержание 1. Характеристика методов решения задач оптимизации2. Методы безусловной оптимизации2.1. Численные методы безусловной оптимизации нулевого порядка Основные определения Классификация методов Общая характеристика методов нулевого порядка Метод прямого поиска (метод Хука-Дживса) Метод деформируемого многогранника (метод Нелдера—Мида) Метод вращающихся координат (метод Розенброка) Метод параллельных касательных (метод Пауэлла)2.2. Численные методы безусловной оптимизации первого порядка Минимизация функций многих переменных. Основные положения Метод наискорейшего спуска Метод сопряженных градиентов2.3. Численные методы безусловной оптимизации второго порядка Особенности методов второго порядка Метод Ньютона3. Методы условной оптимизации3.1. Линейное программирование3.2. Транспортная задача линейного программирования Постановка задачи Венгерский метод Метод потенциалов3.3. Прямые методы условной оптимизации Основные определения Метод проекции градиента Комплексный метод Бокса3.4. Методы штрафных функций Основные определения Методы внутренних штрафных функций Методы внешних штрафных функций Комбинированные алгоритмы штрафных функций4. Динамическое программированиеСписок литературы^ 1. Характеристика методов решения задач оптимизации При решении конкретной задачи оптимизации исследователь прежде всего должен выбрать математический метод, который приводил бы к конечным результатам с наименьшими затратами на вычисления или же давал возможность получить наибольший объем информации об искомом решении. Выбор того или иного метода в значительной степени определяется постановкой оптимальной задачи, а также используемой математической моделью объекта оптимизации.В настоящее время для решения оптимальных задач применяют в основном следующие методы: методы исследования функций классического анализа; методы, основанные на использовании неопределенных множителей Лагранжа; вариационное исчисление; динамическое программирование; принцип максимума; линейное программирование; нелинейное программирование. В последнее время разработан и успешно применяется для решения определенного класса задач метод геометрического программирования.Как правило, нельзя рекомендовать какой-либо один метод, который можно использовать для решения всех без исключения задач, возникающих на практике. Одни методы в этом отношении являются более общими, другие - менее общими. Наконец, целую группу методов (методы исследования функций классического анализа, метод множителей Лагранжа, методы нелинейного программирования) на определенных этапах решения оптимальной задачи можно применять в сочетании с другими методами, например динамическим программированием или принципом максимума.Отметим также, что некоторые методы специально разработаны или наилучшим образом подходят для решения оптимальных задач с математическими моделями определенного вида. Так, математический аппарат линейного программирования, специально создан для решения задач с линейными критериями оптимальности и линейными ограничениями на переменные и позволяет решать большинство задач, сформулированных в такой постановке. Так же и геометрическое программирование предназначено для решения оптимальных задач, в которых критерий оптимальности и ограничения представляются специального вида функциями позиномами.Динамическое программирование хорошо приспособлено для решения задач оптимизации многостадийных процессов, особенно тех, в которых состояние каждой стадии характеризуется относительно небольшим числом переменных состояния. Однако при наличии значительного числа этих переменных, т. е. при высокой размерности каждой стадии, применение метода динамического программирования затруднительно вследствие ограниченных быстродействия и объема памяти вычислительных машин.Пожалуй, наилучшим путем при выборе метода оптимизации, наиболее пригодного для решения соответствующей задачи, следует признать исследование возможностей и опыта применения различных методов оптимизации. Ниже приводится краткий обзор математических методов решения оптимальных задач и примеры их использования. Здесь же дана лишь краткая характеристика указанных методов и областей их применения, что до некоторой степени может облегчить выбор того или иного метода для решения конкретной оптимальной задачи.^ Методы исследования функций классического анализа представляют собой наиболее известные методы решения несложных оптимальных задач, с которыми известны из курса математического анализа. Обычной областью использования данных методов являются задачи с известным аналитическим выражением критерия оптимальности, что позволяет найти не очень сложное, также аналитическое выражение для производных. Полученные приравниванием нулю производных уравнения, определяющие экстремальные решения оптимальной задачи, крайне редко удается решить аналитическим путем, поэтому, как, правило, применяют вычислительные машины. При этом надо решить систему конечных уравнений, чаще всего нелинейных, для чего приходится использовать численные методы, аналогичные методам нелинейного программирования.Дополнительные трудности при решении оптимальной задачи методами исследования функций классического анализа возникают вследствие того, что система уравнений, получаемая в результате их применения, обеспечивает лишь необходимые условия оптимальности. Поэтому все решения данной системы (а их может быть и несколько) должны быть проверены на достаточность. В результате такой проверки сначала отбрасывают решения, которые не определяют экстремальные значения критерия оптимальности, а затем среди остающихся экстремальных решений выбирают решение, удовлетворяющее условиям оптимальной задачи, т. е. наибольшему или наименьшему значению критерия оптимальности в зависимости от постановки задачи.Методы исследования при наличии ограничений на область изменения независимых переменных можно использовать только для отыскания экстремальных значений внутри указанной области. В особенности это относится к задачам с большим числом независимых переменных (практически больше двух), в которых анализ значений критерия оптимальности на границе допустимой области изменения переменных становится весьма сложным.^ Метод множителей Лагранжа применяют для решения задач такого же класса сложности, как и при использовании обычных методов исследования функций, но при наличии ограничений типа равенств на независимые переменные. К требованию возможности получения аналитических выражений для производных от критерия оптимальности при этом добавляется аналогичное требование относительно аналитического вида уравнений ограничений.В основном при использовании метода множителей Лагранжа приходится решать те же задачи, что и без ограничений. Некоторое усложнение в данном случае возникает лишь от введения дополнительных неопределенных множителей, вследствие чего порядок системы уравнений, решаемой для нахождения экстремумов критерия оптимальности, соответственно повышается на число ограничений. В остальном, процедура поиска решений и проверки их на оптимальность отвечает процедуре решения задач без ограничений.Множители Лагранжа можно применять для решения задач оптимизации объектов на основе уравнений с частными производными и задач динамической оптимизации. При этом вместо решения системы конечных уравнений для отыскания оптимума необходимо интегрировать систему дифференциальных уравнений.Следует отметить, что множители Лагранжа используют также в качестве вспомогательного средства и при решении специальными методами задач других классов с ограничениями типа равенств, например, в вариационном исчислении и динамическом программировании. Особенно эффективно применение множителей Лагранжа в методе динамического программирования, где с их помощью иногда удается снизить размерность решаемой задачи.^ Методы вариационного исчисления обычно используют для решения задач, в которых критерии оптимальности представляются в виде функционалов и решениями которых служат неизвестные функции. Такие задачи возникают обычно при статической оптимизации процессов с распределенными параметрами или в задачах динамической оптимизации.Вариационные методы позволяют в этом случае свести решение оптимальной задачи к интегрированию системы дифференциальных ' уравнений Эйлера, каждое из которых является нелинейным дифференциальным уравнением второго порядка с граничными условиями, заданными на обоих концах интервала интегрирования. Число уравнений указанной системы при этом равно числу неизвестных функций, определяемых при решении оптимальной задачи. Каждую функцию находят в результате интегрирования получаемой системы.Уравнения Эйлера выводятся как необходимые условия экстремума функционала. Поэтому полученные интегрированием системы дифференциальных уравнений функции должны быть проверены на экстремум функционала.При наличии ограничений типа равенств, имеющих вид функционалов, применяют множители Лагранжа, что дает возможность перейти от условной задачи к безусловной. Наиболее значительные трудности при использовании вариационных методов возникают в случае решения задач с ограничениями типа неравенств.Заслуживают внимания прямые методы решения задач оптимизации функционалов, обычно позволяющие свести исходную вариационную задачу к задаче нелинейного программирования, решить которую иногда проще, чем краевую задачу для уравнений Эйлера.^ Динамическое программирование служит эффективным методом решения задач оптимизации дискретных многостадийных процессов, для которых критерий оптимальности задается как аддитивная функция критериев оптимальности отдельных стадий. Без особых затруднений указанный метод можно распространить и на случай, когда критерий оптимальности задан в другой форме, однако при этом обычно увеличивается размерность отдельных стадий.По существу метод динамического программирования представляет собой алгоритм определения оптимальной стратегии управления на всех стадиях процесса. При этом закон управления на каждой стадии находят путем решения частных задач оптимизации последовательно для всех стадий процесса с помощью методов исследования функций классического анализа или методов нелинейного программирования. Результаты решения обычно не могут быть выражены в аналитической форме, а получаются в виде таблиц.Ограничения на переменные задачи не оказывают влияния на общий алгоритм решения, а учитываются при решении частных задач оптимизации на каждой стадии процесса. При наличии ограничений типа равенств иногда даже удается снизить размерность этих частных задач за счет использования множителей Лагранжа. Применение метода динамического программирования для оптимизации процессов с распределенными параметрами или в задачах динамической оптимизации приводит к решению дифференциальных уравнений в частных производных. Вместо решения таких уравнений зачастую значительно проще представить непрерывный процесс как дискретный с достаточно большим числом стадий. Подобный прием оправдан особенно в тех случаях, когда имеются ограничения на переменные задачи и прямое решение дифференциальных уравнений осложняется необходимостью учета указанных ограничений.При решении задач методом динамического программирования, как правило, используют вычислительные машины, обладающие достаточным объемом памяти для хранения промежуточных результатов решения, которые обычно получаются в табличной форме.^ Принцип максимума применяют для решения задач оптимизации процессов, описываемых системами дифференциальных уравнений. Достоинством математического аппарата принципа максимума является то, что решение может определяться в виде разрывных функций; это свойственно многим задачам оптимизации, например задачам оптимального управления объектами, описываемыми линейными дифференциальными уравнениями.Нахождение оптимального решения при использовании принципа максимума сводится к задаче интегрирования системы дифференциальных уравнений процесса и сопряженной системы для вспомогательных функций при граничных условиях, заданных на обоих концах интервала интегрирования, т. е. к решению краевой задачи. На область изменения переменных могут быть наложены ограничения. Систему дифференциальных уравнений интегрируют, применяя обычные программы на цифровых вычислительных машинах.Принцип максимума для процессов, описываемых дифференциальными уравнениями, при некоторых предположениях является достаточным условием оптимальности. Поэтому дополнительной проверки на оптимум получаемых решений обычно не требуется.Для дискретных процессов принцип максимума в той же формулировке, что и для непрерывных, вообще говоря, несправедлив. Однако условия оптимальности, получаемые при его применении для многостадийных процессов, позволяют найти достаточно удобные алгоритмы оптимизации.^ Линейное программирование представляет собой математический аппарат, разработанный для решения оптимальных задач с линейными выражениями для критерия оптимальности и линейными ограничениями на область изменения переменных. Такие задачи обычно встречаются при решении вопросов оптимального планирования производства с ограниченным количеством ресурсов, при определении оптимального плана перевозок (транспортные задачи) и т. д.Для решения большого круга задач линейного программирования имеется практически универсальный алгоритм - симплексный метод, позволяющий за конечное число итераций находить оптимальное решение подавляющего большинства задач. Тип используемых ограничений (равенства или неравенства) не сказывается на возможности применения указанного алгоритма. Дополнительной проверки на оптимальность для получаемых решений не требуется. Как правило, практические задачи линейного программирования отличаются весьма значительным числом независимых переменных. Поэтому для их решения обычно используют вычислительные машины, необходимая мощность которых определяется размерностью решаемой задачи.^ Методы нелинейного программирования применяют для решения оптимальных задач с нелинейными функциями цели. На независимые переменные могут быть наложены ограничения также в виде нелинейных соотношений, имеющих вид равенств или неравенств. По существу методы нелинейного программирования используют, если ни один из перечисленных выше методов не позволяет сколько-нибудь продвинуться в решении оптимальной задачи. Поэтому указанные методы иногда называют также прямыми методами решения оптимальных задач.Для получения численных результатов важное место отводится нелинейному программированию и в решении оптимальных задач такими методами, как динамическое программирование, принцип максимума и т. п. на определенных этапах их применения.Названием “методы нелинейного программирования” объединяется большая группа численных методов, многие из которых приспособлены для решения оптимальных задач соответствующего класса. Выбор того или иного метода обусловлен сложностью вычисления критерия оптимальности и сложностью ограничивающих условий, необходимой точностью решения, мощностью имеющейся вычислительной машины и т.д. Ряд методов нелинейного программирования практически постоянно используется в сочетании с другими методами оптимизации, как, например, метод сканирования в динамическом программировании. Кроме того, эти методы служат основой построения систем автоматической оптимизации - оптимизаторов, непосредственно применяющихся для управления производственными процессами.^ Геометрическое программирование есть метод решения одного специального класса задач нелинейного программирования, в которых критерий оптимальности и ограничения задаются в виде позиномов - выражений, представляющих собой сумму произведений степенных функций от независимых переменных. С подобными задачами иногда приходится сталкиваться в проектировании. Кроме того, некоторые задачи нелинейного программирования иногда можно свести к указанному представлению, используя аппроксимационное представление для целевых функций и ограничений.Специфической особенностью методов решения оптимальных задач (за исключением методов нелинейного программирования) является то, что до некоторого этапа оптимальную задачу решают аналитически, т. е. находят определенные аналитические выражения, например, системы конечных или дифференциальных уравнений, откуда уже отыскивают оптимальное решение. В отличие от указанных методов при использовании методов нелинейного программирования, которые, как уже отмечалось выше, могут быть названы прямыми, применяют информацию, получаемую при вычислении критерия оптимальности, изменение которого служит оценкой эффективности того или иного действия.Важной характеристикой любой оптимальной задачи является ее размерность п, равная числу переменных, задание значений которых необходимо для однозначного определения состояния оптимизируемого объекта. Как правило, решение задач высокой размерности связано с необходимостью выполнения большого объема вычислений. Ряд методов (например, динамическое программирование и дискретный принцип максимума) специально предназначен для решения задач оптимизации процессов высокой размерности, которые могут быть представлены как многостадийные процессы с относительно невысокой размерностью каждой стадии.В таблице 1.1 [2] дана характеристика областей применения различных методов оптимизации, при этом за основу положена сравнительная оценка эффективности использования каждого метода для решения различных типов оптимальных задач. Классификация задач проведена по следующим признакам: вид математического описания процесса; тип ограничений на переменные процесса число переменных. Предполагается, что решение оптимальной задачи для процессов, описываемых системами конечных уравнений, определяется как конечный набор значений управляющих воздействий (статическая оптимизация процессов с сосредоточенными параметрами), а для процессов, описываемых системами обыкновенных дифференциальных уравнений, управляющие воздействия характеризуются функциями времени (динамическая оптимизация процессов с сосредоточенными параметрами) или пространственных переменных (статическая оптимизация процессов с распределенными параметрами).Классификация задач по группам с числом независимых переменных, большим и меньшим трех или равным трем как характеристика размерности задач с большим и малым числом переменных, разумеется, весьма условна и в данном случае выбрана скорее из соображений наглядности графического изображения пространства изменения переменных задачи - фазового пространства (при числе переменных большем трех графическое изображение фазового пространства обычными приемами отсутствует). Тем не менее, такая классификация до некоторой степени все же отражает действительные трудности, возникающие при решении задач с размерностью выше трех. ^ ТАБЛИЦА 1.1. Области применения методов оптимизации Вид описания процесса Конечные уравнения Дифференциальные уравнения Тип ограничений на переменные Нет Равенства Неравенства Нет Равенства Неравенства Число переменных п ?3 >3 ?3 >3 ?3 >3 ?3 >3 ?3 >3 ?3 >3 ТТип метода Методы классического анализа 1 2 4 4 4 4 3 4 4 4 4 4 Множители Лагранжа - - 1 2 - - - - 2 3 - - Вариационное исчисление - - - - - - 2 3 2; 7 3; 7 - - Динамическое программирование 1; 5 3; 5 1;5;7 3; 5; 7 1; 5 3; 5 2 3 3 3 3 3 Принцип максимума 2; 5 1; 5 2; 5 2; 5 2; 5 2; 5 1 1 2 2 2 2 Линейное программирование - - - 2; 6 2; 6 1; 6 - - - - - - Методы нелинейного программирования 2 1 2 .1 2 1 4 4 4 4 4 4 Геометрическое программирование 2; 8 2; 8 - - 2; 8 2; 8 - - - - - - Примечания: 1. Эффективное применение метода. 2. Используется. 3. Возможно применение. 4. Используется как вспомогательный метод. 5. Многостадийные процессы (размерность указывается для отдельной стадии). 6. Задачи с линейными критериями оптимальности и линейными ограничениями. 7. Используются множители Лагранжа. 8. Задачи с критериями и ограничениями в форме позиномов. ^ 2. Методы безусловной оптимизации 2.1. Численные методы безусловной оптимизации нулевого порядкаОсновные определенияРешение многих теоретических и практических задач сводится к отысканию экстремума (наибольшего или наименьшего значения) скалярной функции f(х) n-мерного векторного аргументах. В дальнейшем под x будем понимать вектор-столбец (точку в n-мерном пространстве):Вектор-строка получается путем применения операции транспонирования:.Оптимизируемую функцию f(x) называют целевой функцией или критерием оптимальности.В дальнейшем без ограничения общности будем говорить о поиске минимального значения функции f(x) записывать эту задачу следующим образом:f(x ) --> min.Вектор х*, определяющий минимум целевой функции, называют оптимальным.Отметим, что задачу максимизации f(x) можно заменить эквивалентной ей задачей минимизации или наоборот. Рассмотрим это на примере функции одной переменной (Рис. 2.1). Если х* - точка минимума функции y = f(x), то для функции y =- f(x) она является точкой максимума, так как графики функций f(x) и - f(x), симметричны относительно оси абсцисс. Итак, минимум функции f(x) и максимум функции - f(x) достигаются при одном и том же значении переменной. Минимальное же значение функции f(x), равно максимальному значению функции - f(x), взятому с противоположным знаком, т.е. min f(x) =-max(f(x)).Рассуждая аналогично, этот вывод нетрудно распространить на случай функции многих переменных. Если требуется заменить задачу минимизации функции f(x1, …, xn) задачей максимизации, то достаточно вместо отыскания минимума этой функции найти максимум функции f(x1, …, xn). Экстремальные значения этих функций достигаются при одних и тех же значениях переменных. Минимальное значение функции f(x1, …, xn) равно максимальному значению функции - f(x1, …, xn), взятому с обратным знаком, т.е. min f(x1, …, xn) =max f(x1, …, xn). Отмеченный факт позволяет в дальнейшем говорить только о задаче минимизации.Рис. 2.1. ЭкстремумВ реальных условиях на переменные xj, i=1, …. n, и некоторые функции gi (х), hi(х), характеризующие качественные свойства объекта, системы, процесса, могут быть наложены ограничения (условия) вида:gi (х) = 0, i=1, …. n,hi (х) a где; Такую задачу называют задачей условной оптимизации. При отсутствии ограничений имеет место задача безусловной оптимизации.Каждая точка х в n-мерном пространстве переменных х1, …, хn, в которой выполняются ограничения, называется допустимой точкой задачи. Множество всех допустимых точек называют допустимой областью G. Решением задачи (оптимальной точкой) называют допустимую точку х*, в которой целевая функция f(х) достигает своего минимального значения.Точка х* определяет глобальный минимум функции одной переменной f(x), заданной на числовой прямой Х , если x * X и f(x*) Рис. 2.2. Глобальный минимум. а - строгий, б - нестрогийТочка х* Х определяет локальный минимум функции f(x) на множестве Х , если при некотором достаточно малом > 0 для всех х, не равных х*, x X, удовлетворяющих условию ¦х - х*¦Рис. 2.3. Экстремумы функции^ Классификация методовВозможны два подхода к решению задачи отыскания минимума функции многих переменных f(x) = f(x1, ..., хn) при отсутствии ограничений на диапазон изменения неизвестных. Первый подход лежит в основе косвенных методов оптимизации и сводит решение задачи оптимизации к решению системы нелинейных уравнений, являющихся следствием условий экстремума функции многих переменных. Как известно, эти условия определяют, что в точке экстремума х* все первые производные функции по независимым переменным равны нулю:, i=1, …, n.Эти условия образуют систему п нелинейных уравнений, среди решений которой находятся точки минимума. Вектор f’(х), составленный из первых производных функции по каждой переменной, т.е.,называют градиентом скалярной функции f(x). Как видно, в точке минимума градиент равен нулю.Решение систем нелинейных уравнений - задача весьма сложная и трудоемкая. Вследствие этого на практике используют второй подход к минимизации функций, составляющий основу прямых методов. Суть их состоит в построении последовательности векторов х [0], х [1], …, х [n], таких, что f(х[0])> f(х [1])> f(х [n])>… В качестве начальной точки x[0] может быть выбрана произвольная точка, однако стремятся использовать всю имеющуюся информацию о поведении функции f(x), чтобы точка x[0] располагалась как можно ближе к точке минимума. Переход (итерация) от точки х [k] к точке х [k+1], k = 0, 1, 2, ..., состоит из двух этапов: выбор направления движения из точки х [k]; определение шага вдоль этого направления. Методы построения таких последовательностей часто называют методами спуска, так как осуществляется переход от больших значений функций к меньшим.Математически методы спуска описываются соотношениемx[k+1] = x[k] + akp[k], k = 0, 1, 2, ...,где p[k] - вектор, определяющий направление спуска; ak - длина шага. В координатной форме:Различные методы спуска отличаются друг от друга способами выбора двух параметров - направления спуска и длины шага вдоль этого направления. На практике применяются только методы, обладающие сходимостью. Они позволяют за конечное число шагов получить точку минимума или подойти к точке, достаточно близкой к точке минимума. Качество сходящихся итерационных методов оценивают по скорости сходимости.В методах спуска решение задачи теоретически получается за бесконечное число итераций. На практике вычисления прекращаются при выполнении некоторых критериев (условий) останова итерационного процесса. Например, это может быть условие малости приращения аргументаили функции.Здесь k - номер итерации; , - заданные величины точности решения задачи.Методы поиска точки минимума называются детерминированными, если оба элемента перехода от х[k] к x[k+l] (направление движения и величина шага) выбираются однозначно по доступной в точке х [k] информации. Если же при переходе используется какой-либо случайный механизм, то алгоритм поиска называется случайным поиском минимума.Детерминированные алгоритмы безусловной минимизации делят на классы в зависимости от вида используемой информации. Если на каждой итерации используются лишь значения минимизируемых функций, то метод называется методом нулевого порядка. Если, кроме того, требуется вычисление первых производных минимизируемой функции, то имеют место методы первого порядка, при необходимости дополнительного вычисления вторых производных - методы второго порядка.В настоящее время разработано множество численных методов для задач как безусловной, так и условной оптимизации. Естественным является стремление выбрать для решения конкретной задачи наилучший метод, позволяющий за наименьшее время использования ЭВМ получить решение с заданной точностью.Качество численного метода характеризуется многими факторами: скоростью сходимости, временем выполнения одной итерации, объемом памяти ЭВМ, необходимым для реализации метода, классом решаемых задач и т. д. Решаемые задачи также весьма разнообразны: они могут иметь высокую и малую размерность, быть унимодальными (обладающими одним экстремумом) и многоэкстремальными и т. д. Один и тот же метод, эффективный для решения задач одного типа, может оказаться совершенно неприемлемым для задач другого типа. Очевидно, что разумное сочетание разнообразных методов, учет их свойств позволят с наибольшей эффективностью решать поставленные задачи. Многометодный способ решения весьма удобен в диалоговом режиме работы с ЭВМ. Для успешной работы в таком режиме очень полезно знать основные свойства, специфику методов оптимизации. Это обеспечивает способность правильно ориентироваться в различных ситуациях, возникающих в процессе расчетов, и наилучшим образом решить задачу.^ Общая характеристика методов нулевого порядкаВ этих методах для определения направления спуска не требуется вычислять производные целевой функции. Направление минимизации в данном случае полностью определяется последовательными вычислениями значений функции. Следует отметить, что при решении задач безусловной минимизации методы первого и второго порядков обладают, как правило, более высокой скоростью сходимости, чем методы нулевого порядка. Однако на практике вычисление первых и вторых производных функции большого количества переменных весьма трудоемко. В ряде случаев они не могут быть получены в виде аналитических функций. Определение производных с помощью различных численных методов осуществляется с ошибками, которые могут ограничить применение таких методов. Кроме того, на практике встречаются задачи, решение которых возможно лишь с помощью методов нулевого порядка, например задачи минимизации функций с разрывными первыми производными. Критерий оптимальности может быть задан не в явном виде, а системой уравнений. В этом случае аналитическое или численное определение пр