МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ
НИЖЕГОРОДСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ 
им. Н.И.ЛОБАЧЕВСКОГО
МЕХАНИКО-МАТЕМАТИЧЕСКИЙ ФАКУЛЬТЕТ
Кафедра теоретической механики

Маркина М.В.

Численные методы оптимального проектирования механических систем
Методическое пособие

НИЖНИЙ НОВГОРОД
 2011
УДК 519.6

Численные методы оптимального проектирования механических систем. Методическое пособие / Сост.   М.В. Маркина  - Н.Новгород: изд-во ННГУ, 2011. - 25    с.

	Методическое пособие предназначено для студентов и магистров специальности «Прикладная математика» механико-математического факультета  ННГУ.

	Составители:      к.ф.-м.н.,  доцент  М.В. Маркина 

Рецензент: 
			   к.ф.- м..н ,  доцент  Т. А. Сабаева

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

Тема 1. Основные понятия теории оптимального проектирования 
1.	Управляемые и неуправляемые параметры
Для постановки задачи ОП объекта необходимо определить управляемые и неуправляемые параметры объекта.

Механические объекты при математическом моделировании имеют:
1) Подмножество геометрических параметров;
2) Подмножество параметров, описываемых физико-механическими свойствами материалов;
3) Подмножество параметров внешних и внутренних воздействий;
4) Условия нормативной эксплуатации;
5) Подмножества граничных и начальных условий эксплуатации объекта.
Неуправляемые ≈ неизменные параметры: 
Управляемые ≈ оптимизируемые ≈ искомые параметры: 
2. Критерий эффективности
Объект описывается не одной лишь целевой  функцией. Нужно уметь удовлетворять всем критериям в какой-либо мере, т.е. найти компромисс.
Критерии могут быть: 
1) Абсолютными – размерные критерии, обычно это геометрический характеристики объекта;
2) Относительными – безразмерные критерии, получаются путем нормирования;
3) Комплексными – объединение нескольких критериев в один.

3. Ограничения
Позволяют оценить допустимость или недопустимость полученного решения

Формы ограничений:
1) Размерная: ;
2) Безразмерная:    ();
3) Каноническая:    ().
4. Область поиска
Часть n-мерного пространства проектируется и задается следующим образом:

Разумно уменьшить область поиска (уменьшить объем области поиска)

5. Область допустимых решений

 – значения управляемых параметров, удовлетворяющих системе ограничений
ОДР может быть выпуклой/невыпуклой, односвязной/многосвязной.
6. Окрестность оптимального решения

7. Чувствительность оптимума

Постоянно поддерживать состояние Х* невозможно. При отклонении от  Х* можем получить не желаемый результат.
ЧО – это относительное изменение изучаемых функций при изменении оптимально управляемых параметров в пределах заданной окрестности.

Оптимальное решение:  

8. Классификация задач оптимизации
Спектр задач параметрической оптимизации определяется их свойствами. Основными свойствами являются:
•	число критериев эффективности (один или насколько);
•	наличие ограничений (одно или насколько) или их отсутствие;
•	число экстремумов (один или несколько);
•	свойства функций критериев эффективности или целевой функции (линейность, нелинейность, непрерывность, разрывность);
•	свойства функции ограничений;
•	свойства управляемых параметров (непрерывность, дискретность);
•	свойства области допустимых решений (односвязность, многосвязность).
Решение задач оптимизации всегда связано с некоторыми трудностями:
1. Неопределенность.  Она вызвана тем, что выбор решения происходит в условиях неполного знания проектируемой системы, а также характера и особенностей ее функционирования. Эта неопределенность не может быть устранена даже при предварительном изучении всей имеющейся априорной информации, то есть она не является следствием несовершенства математической модели, а отражает ее суть-противоречивость, конфликтность. Неопределенность может быть вызвана внешними причинами, не зависящими от проектировщика (естественная неопределенность), либо введена им преднамеренно (искусственная неопределенность). Следует различать:
•	Неопределенность обстановки, в которой нужно выбрать решение. Она обусловлена неполным знанием уравнений объектов, внешних воздействий, естественных ограничений.
•	Неопределенность требований (целей). Она обусловлена неполным знанием цели, которой система должна достигнуть, а также неполным знанием ряда дополнительных требований, предъявляемых к системе.
•	Неопределенность (случайность) самого решения, которая вводится преднамеренно.
2. Декомпозиционность – способность задач оптимизации разделяться на более простые. Она связана с возможностью декомпозиции цели, что в свою очередь, определяет функциональное деление объекта как системы на подсистемы.
3. Иерархичность. Проявляется в возможности оптимизации по нескольким уровням. Она отражает не только их декомпозиционность, но и качественное изменение задачи при переходе от одного иерархического уровня на другой. Другой особенностью, связанной с иерархичностью, является сильная связанность проектируемых подсистем. Она не позволяет закончить оптимизацию за один цикл, а делает ее итерационным процессом, который может привести к оптимальному решению (не всегда экстремальному) и для достижения более точного решения требует специальных процедур, использующих специфику свойств конкретных конструкций.
4. Многокритериальность – наличие многих целей проектирования. Она обусловлена стремлением оценить качество решения с различных точек зрения, а также неопределенностью условий и параметров, сложностью и иерархичностью оптимизируемых систем. Обычное сведение задачи оптимального проектирования к однокритериальной задаче обедняет возможности анализа ситуации. Ограниченность такого подхода в том, что проектировщик в этом случае полностью меняет смысл исходной задачи, в которой каждый показатель имеет свои параметры, экстремизирующие его значение. Выбирая один из показателей в качестве критерия оптимальности, проектировщик по существу игнорирует все возможные компромиссы между ними. 

1) Число критериев;
2) Наличие или отсутствие ограничений;
3) Число экстремумов функции, описывающей данную задачу;
4) Свойства функций;
5) Свойства управляемых параметров.
Тема 2. Методы перехода от векторного критерия эффективности к скалярной целевой функции
Постановка многокритериальной задачи оптимизации:

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

Хотя бы одно неравенство было бы строгое для любых двух точек, если они обе поретовского типа, то нельзя улучшить значение ни одного из частных критериев, не ухудшая один из оставшихся.
Множество Порето включает в себя множество слабой эффективности, оптимизированное по Слейтеру: является таковой, если 
Подходы к решению:
1) Решение о компромиссе, принимаемое до решения задачи (когда требуется конкретное задание параметров);
2) Решение принимается в результате  диалога с пользователем;

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

Где 
i - число критериев;
 - весовые коэффициенты, характеризующие важность критерия;
 - частный критерий эффективности, предварительно нормированный.

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

2. Метод последовательных уступок
Попытка избавиться от недостатков метода свёртки критериев предпринята в методе последовательных уступок.
В процессе принятия решений люди могут играть разные роли. Человека, фактически осуществляющего выбор наилучшего варианта действий, принято называть лицом, принимающим решения (ЛПР). Наряду с ЛПР иногда выделяют как отдельную личность владельца проблемы — человека, который должен ее решать и несет ответственность за принятые решения. Далеко не всегда владелец проблемы является также и ЛПР. 
В процессе подготовки к принятию сложных (как правило, стратегических) решений иногда принимает участие консультант по принятию решений. Его роль сводится к разумной организации процесса принятия решений: помощи ЛПР и владельцу проблемы в правильной постановке задачи, выявлении позиций активных групп, организации работы с экспертами. Консультант (или аналитик) обычно не вносит свои предпочтения, оценки в принятие решений, он только помогает другим взвесить все "за" и "против" и выработать разумный компромисс. Среди аналитиков выделяют специалистов по математическим аспектам поддержки принятия решений. Они помогают участниками процесса принятия решений воспользоваться современными средствами анализа решений.  

Суть метода последовательных уступок

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

Схема поиска оптимального решения по методу последовательных уступок:

 – критерии расположенные в порядке убывания их важности.

1) Ищем минимальное значение первого критерия  на всем
множестве допустимых решений. 

 - полученный результат;
Вычисляем   .
2) Если по какому-либо из критериев  результат не удовлетворительный, то ЛПР назначает величину допустимого снижения или уступки  по критерию 

Определяем наименьшее значение  второго критерия  при условии, что значение первого критерия должно быть не больше, чем . Затем вычисляем  , где  - результат полученный на втором шаге.

Если по какому-либо из критериев  полученный результат не удовлетворяет требованиям предъявляемым ЛПР, то назначается величина  по критерию . 
И так далее для m – 2 критериев.

При этом оптимальным решением многокритериальной задачи считается всякое решение последней из задач последовательности:
                         
   1) найти min(  =  в области x ∈ X;
   2) найти min( =  в области, задаваемой условиям  x ∈ X;  ;    
                 
   ………………………………………………………………...
                              
   m) найти min( =  в области, задаваемой условиями  x ∈ X;  ,   

      Очевидно, что если все  , то метод уступок находит только лексикографически оптимальные решения, которые доставляют первому по важности критерию наибольшее на Х значение. В другом крайнем случае, когда величины уступок очень велики, решения, получаемые по этому методу, доставляют последнему по важности критерию наибольшее на Х значение. Поэтому величины уступок можно рассматривать как своеобразную меру отклонения приоритета частных критериев от жесткого лексикографического.
      Метод последовательных уступок не всегда приводит к получению только эффективных точек, но среди получаемых этим методом точек всегда существует хотя бы одна эффективная, что следует из следующих утверждений.
                           
      Утверждение 1. Если XR - множество замкнутое и ограниченное, а функции  непрерывны, то решением m-й задачи является, по крайней мере, одна эффективная точка.

      Утверждение 2. Если  x - единственная (с точностью до эквивалентности) точка, являющаяся решением m-й задачи), то она эффективна.

3. Сведение многокритериальной задачи к задаче условной оптимизации
Существует теорема, что решение следующей задачи условной оптимизации является слейтеровской точкой исходной многокритериальной задачи

4. Определение весовых коэффициентов свертки с помощью существующего аналога оптимизируемого объекта
Пусть в природе существует хороший аналог проектируемого объекта. У него есть оптимальный. А каким коэффициентом свертки они обладают?  Ответив на этот вопрос мы могли бы в нашей задаче выбрать требуемые коэффициенты .

- система определена, следовательно можем найти .
Тема 3. Сведение многомерной задачи к одномерной. Два способа редукции
 
1. Многошаговая схема редукции
Пусть минимизируемая функция С (х) зависит от небольшого числа переменных (n ≤ 3). В этом случае для решения задачи поиска глобального минимума x* непрерывной функции С (х), определенной в n-мерном гиперпараллелепипеде Dx = {x|ai ≤ xi ≤ bi , i = 1, 2,…, n}
min С(x1, x2, …, xn),
можно использовать алгоритм , реализующий метод многошаговой редукции размерности. Основная идея этого метода состоит в том, что исходная задача сводится к последовательности «вложенных одна в другую» одномерных задач глобальной минимизации:
min С(x) = min min … min С(x1, …, xn). 
Например, для функции трех переменных (n=3) можно записать следующим образом:
min С(x1, x2, x3) = min С1(x1),
Из чего следует, что решение исходной задачи эквивалентно решению задачи минимизации функции одного переменного С1(х1). Вычисление значения функции С1(х1) для фиксированного значения x1 сводится к решению задачи одномерной минимизации функции С2(x1, х2) по переменной х2, а вычисление значения функции С2(x1, x2) для фиксированных значений переменных х1 и х2 — к решению задачи одномерной минимизации исходной функции по переменной x3.
Таким образом, локализация точки глобального минимума х* многопараметрической функции С (х) может быть осуществлена с помощью одного из методов одномерного глобального поиска в сочетании со схемой многошаговой редукции. 
Если через Nk обозначить число испытаний, необходимое для отыскания на интервале [аk, bk] точки глобального минимума одномерной функции Сk(x1, …, xk) с заданной точностью εk (при фиксированных значениях переменных  x1, …, xk-1, то общие затраты на решение задачи  будут равны
N = ∏ Nk
При одинаковом числе испытаний при одномерном поиске Nk = A, k = – 1, …, n, при увеличении размерности исходной задачи общие затраты на поиск будут расти экспоненциально
N = Аn.
Поэтому многошаговая схема редукции становится малоэффективной при большом числе переменных.
Другим недостатком алгоритма является то, что точность εi решения каждой «вложенной» одномерной задачи минимизации должна быть задана заранее. Если значения этих точностей (ε1, …, εn) окажутся недостаточными при оценке конечного результата, то решение исходной задачи по схеме  придется повторить заново с меньшими значениями εi, i = 1, 2, …, n. Если значения точностей заданы слишком! высокими, то решение исходной задачи (6.1) может прерваться в связи с тем, что исчерпано допустимое число испытаний N. В этом случае полученное приближение
С(xk) = min С(xi) 
будет соответствовать оценке минимума функции С(х) в некоторой подобласти множества Dx. Причем может оказаться, что в значительной части области испытания не проводились, хотя в другой ее части определены минимальные значения некоторых из функций Сk(x1,…, xk-1) с заданными точностями ε.

2. Редукция размерности с использованием развертки типа кривой Пеано
Построение кривой Пеано по Гильберту:
а) Любой n-мерный гиперкуб вида  можно привести к гиперкубу с единичными ребрами  с помощью линейного преобразования:
;
б) Гиперкуб разбивается на 2n гиперкубов первого разбиения координатными плоскостями m=1;
в) Полученные гиперкубы разбиваются числами от 0 до 2n-1 так, чтобы гиперкубы, с номерами различными на единицу, стояли рядом (имели общую грань):
.
г) Далее любой гиперкуб первого разбиения в свою очередь также разбивается плоскостями на 2n кубов.
Нумеруем так же, плюс нулевой гиперкуб второго разбиения, входящий в , должен иметь общую грань с последним гиперкубом 
Деление отрезка [0,1] на 2n равных частей:

, соответствующей точки  отрезка, содержится в некотором гиперкубе , принадлежит интервалу 
Формализация:

 позволяет для  указать гиперкуб, в котором находится одномерный образ 
.
Тема 4. Численные методы оптимизации многоэкстремальных задач 
Пусть С(х)  Липшицева функция: 
Испытания:  - узлы.

Задачу создания наилучшего алгоритма глобального поиска можно сформулировать таким образом:
Для заданного числа N нужно построить оптимальную сетку узлов (точек испытаний) т.о., чтобы минимизировать погрешность вычисления приближенного значения глобального минимума функции С(х) при условии, что это функция принадлежит классу функций с заданной L;

Таким образом, необходимо выбрать точки испытания.
1. Методы, основанные на построении апроксимационных моделей минимизируемой функции
1) Проводятся испытания в точках, расположенных определенным образом на отрезке ;
2) По полученным значениям  строится математическая модель функции;
3) Оценивается точность приближения модели к истинной функции;
4) Если точности аппроксимации недостаточно, то проводятся дополнительные испытания (с пункта 2), либо соглашаемся с математической моделью и принимаем решение о глобальном минимуме функции.
Согласно теореме Вейерштрасса, любая непрерывная функция может быть аппроксимирована равномерно сходящейся последовательностью алгебраических полиномов:

Как при фиксированном N получить полином, который наилучшим образом аппроксимирует функцию С(х)?

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

Степень тем выше, чем меньше отклоняется от нуля, таким образом,  точки  необходимо выбирать так:
1) При увеличении N надо обеспечивать равномерную сходимость последовательности полиномов  и ;
2) Необходимо обеспечивать максимальную скорость уменьшения .
Эти требования выполняются в том случае, если в качестве точек испытания выбирать нули множества Чебышева.

Алгоритм 1
1) На [a,b] расположены , ,  - вычисленные значения функции.
2) Строится математическая модель целевой функции в виде интерполяционного полинома Лагранжа:                                                                  
3) Находим  (первая производная). Решаем . Находим: 
4) В качестве нового интервала неопределенности  в котором предполагается наличие , выбирается такой интервал, который удовлетворяет условию: 

Для того, чтобы система узлов интерполируемой области обладала свойствами:
1) При увеличении числа испытаний новые узлы добавляются между старыми
2) Построенные полиномы обладают свойством равномерной сходимости к целевой функции, необходимо, чтобы они вычислялись с помощью полиномов, корни которых не изменяются при увеличении числа N.
Алгоритмический полином вида  
имеет корни, не зависит от N наиближайших приближений к многочленам  Чебышева, которые наименее отклонены от .
Алгоритм 2
Здесь используется последовательная стратегия, в отличии от предыдущей пассивной.
1) Первые два испытания производятся в точках ;
2) По информации  строится математическая модель функции  в виде полинома Лагранжа;
3) Путем решения уравнения  вычисляются корни алгоритмического полинома N-1 степени, и вычисляется: ;
4) Очередное к-ое испытание: - условие окончания.
Алгоритм 3. Алгоритм кусочно-линейной аппроксимации (алгоритм Пиявского)
На каждом шаге поиска в качестве аппроксимирующей модели непрерывной функции  используется кусочно-ломаная кривая  (полиномиальный сплайн первой степени). Точки испытаний на каждом -ом шаге выбираются независимо от информации о поведении функции  и равномерно располагаются на интервале :
;        
Общее число точек испытаний  определяется по итерационной формуле:
;             
В новых точках, не совпадающих с уже проведенными испытаниями

проводятся дополнительные вычисления функции . На первом шаге () используется информация об испытаниях в пяти точках, на втором шаге () — в девяти точках, среди которых в пяти уже проведены испытания, т. е. дополнительно вычисляется значение функции  только в четырех новых точках и т. д. Основной характеристикой аппроксимирующей модели  является число подынтервалов, в которых обеспечивается выполнение неравенства:
;                  
Эти подынтервалы называются «подозрительными» на существование в них локального минимума функции . В связи с простотой аппроксимирующей модели  поиск точек ее локальных минимумов, определяющих «подозрительные» подынтервалы, не представляет труда. Пусть известна константа Липшица  функции .

Кусочно – линейная модель функции  после проведения  испытаний может быть построена ( и  известны) следующим образом:

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

 - первая вершина ломаной.
На  шаге ищется минимум по  ():

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

На  шаге решаем задачу поиска  при условии (минимум из значений функции в двух вершинах):

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

2. Информационно-статистические алгоритмы оптимизации
Будем подразумевать, что математическая модель функции определяется вероятностным образом.
Предположим, что С(х) – аналитического вида неизвестная – есть распределение случайного процесса. Он описывается с помощью вероятностных характеристик, а именно:
С(х) ~ функциональный класс, в котором вероятностные свойства функции определяются при помощи плотности распределяемой вероятности .
Имеем k испытаний: .
Шаг k:  - на каждом шаге пересчитываем распределение .
.
Предположим, что: 
1. ;
2. Оценивать вероятность нахождения минимума на любом интервале можно с помощью. Оценка проводится на основе формулы Байеса.
Оценка вероятности. Находится минимум на i-том интервале: 
.
m – оценка константы Липшица в функции (максимальный из всех наклонов по всем интервалам).
Существуют и другие формулы, если на одном из концов интервала невозможно вычислить значение .
1. Алгоритм нахождения глобального минимума у многоэкстремальной функции
1) Первые два испытания на  – в концах интервала поиска . 
2) располагается таким образом, что .
3) Вычислим максимальное значение абсолютной первой разности (максимальное значение наклона функции при первых испытаниях) .
М искусственно увеличена, чтобы она была приблизительно равна константе Липшица: 

r может меняться.
4) На любом интервале вычисляется величина, называемая характеристикой интервала: 
.
5) .
6) .
7) Условие обстановки: .
3. Метод поэтапной параметрической оптимизации

Следуя системному подходу, процесс оптимизации можно построить с использованием принципа этапности, позволяющего разбить весь сложный процесс оптимизации на более простые этапы. Каждый этап представляет собой решение отдельных задач, последовательное решение которых может привести к решению исходной (поставленной) задачи. Сформулированная задача при достаточно общих предположениях о ее свойствах может быть разбита согласно принципу поэтапной оптимизации на следующие основные этапы:
1.	Подготовка исходной информации.
2.	Выбор начального приближения.
3.	Построение начальной области поиска.
4.	Движение из точки недопустимой области в область D допустимых решений.
5.	Спуск в точку Х локального экстремума.
6.	Проверка на многоэкстремальность.
7.	 Проверка на многосвязность области допустимых решений.
8.	Перестройка области П поиска.
Если каждый этап будет представлять собой самостоятельный блок со стандартным «входом» и «выходом» информации, то можно все этапы параметрической оптимизации разрабатывать независимо друг от друга и создать методику рационального движения к точке истинного экстремума с достаточно полной логической схемой.
Вариант укрупненной блок-схемы алгоритма поэтапной параметрической оптимизации представлен на рисунке
1.Итерационное движение к границе области допустимых решений

Эффективным движением к границе области допустимых решений является детерминированный итерационный подход, основанный на последовательном чередовании «пробных» и «рабочих» шагов в заданном, например, градиентном направлении целевой функции. При этом рационально используется накопленная информация в процессе испытаний модели. Под испытанием понимается полный или частичный анализ модели с вычислением значения целевой функции С(х) и значений функций ограничений gk(x). Допустим, что , но ,(D). Возникает задача организации движения на , где ГD – граница области допустимых решений: 
.					
Для определенности будем рассматривать данный процесс движения на при условии минимизации целевой функции С(Х). Сущность решения данной задачи состоит в определении расстояния любой точки Х до  в заданном направлении, проведенном из точки .
Рассмотрим итерационную процедуру движения к границе  по градиентному направлению целевой функции, т.е. по С(Х). При этом предполагаем, что по данному направлению целевая функция С(Х) монотонно изменяется. Это значит, что между точкой Х и   нет локальных экстремумов. В основу алгоритма движения по  положена итерационная процедура чередования «пробных» и «рабочих» шагов. Пусть мы находимся в точке .
 «Пробный» шаг в направлении антиградиента состоит в определении точки Х(1) (рис. 5.2.1). Через точку «0» проходит уровень С(Х) = С(0) = const , а через точку «1» проходит соответственно уровень С(Х) = С(1) = const. 

С учетом заданной точности с точка Х(1) должна принадлежать уровню ,  где С(Х0) – значение целевой функции в точке «0». Знак минус в формуле перед с означает, что «пробный» шаг выполняется в направлении антиградиента функции С(Х).
Каждая i-я координата пространства поиска в точке Х(1) будет определяться зависимостью
.				
Сделав испытание (анализ) изучаемой системы по данной математической модели в точках Х(1) и обработав информацию об изменениях целевой функции и функций ограничений, можно определить точку Х(2), которая будет ближе расположена к границе (рабочий шаг):
,			
где  – параметр, характеризующий кратность «пробных» шагов из точки Х(0) в точку Х(2) в направлении границы (по градиентному направлению) с учетом нелинейного характера изменения функции . Для определения параметра m вводят понятие критерия удаленности Lk точки от границы по отношению к k-му ограничению .
Для точки Х(0) критерий Lk(0) запишется в следующем виде:
										Точка Х(0) в общем случае может занимать произвольное положение в области поиска П. При произвольном положении точки Х возможны следующие значения Lk:
Lk>0, если х D, х ГD,  так как  gk(х)<0;
Ln = 0 , если х  ГD D, так как gk(х) = 0;
Lk< 0, если х D, так как  gk(х) >0. 

За «пробный» шаг критерий удаленности изменится и получит приращение
								
Тогда параметр mk, характеризующий приближенно кратность «пробных» шагов, до k-го ограничения  вычисляется
									
Параметр m, характеризующий необходимое число «пробных» шагов до «активного» ограничения, то есть до границы области допустимых решений, определяется формулой 
								
Параметр α учитывает нелинейный характер «активного» ограничения и влияет на скорость сходимости итерационной процедуры при движении из точки Х(0) к границе. Задача коррекции параметра α требует специального исследования и решения с целью обеспечения наилучшей сходимости итерационного процесса спуска на границу за счет последовательного чередования «пробных» и «рабочих» шагов.
Спуск на границу прекращается, если выполнены условия:
1.	;
2.	.
Условие (1) означает, что «рабочий» шаг лежит в пределах пробного шага и обеспечена точность  βс . Условие (2) означает, что в точках «0», «1» или «2» выполняется k-е ограничение в пределах заданной точности β0 .

2. Движение по границе

После определения допустимой точки в задаче при поиске условного локального минимума может возникнуть две ситуации: точка локального экстремума Х* является внутренней точкой допустимых решений D или точка Х* является граничной. 
Рассмотрим методику движения в условный локальный минимум, лежащий на границе . Рассмотрим вариант одного ограничения типа .
Выделим для движения область , где δ – заданная величина, .
Допустим, начальная точка Х0D, , где 0 – заданный параметр точности удовлетворения ограничениям 0>0, >0.
Рассмотрим касательный вектор P0, определяемый проекцией антиградиента C(Х) на гиперплоскость к уравнению  из фиксированной точки Х0. Это направление P0 определяет наискорейшее убывание С(Х) вдоль ограничения.
Применительно к рассматриваемой задаче минимизации функции имеем
.			
Получим выражение для P0
.			
Процесс движения вдоль направления P0 начинается с «пробного» шага, то есть с определения точки Х(1):
,							
где - параметр величины пробного шага(>0),
,		
.							
«Рабочий» шаг будет определяться точкой Х(2)  координаты которой определяются зависимостью
,						
где m –число, характеризующее число «пробных» шагов с учетом линейного или нелинейного характера изменения функции g(Х) в направлении P0. На Рис.5.3.1. буквой а обозначено ограничение , а буквой b – уровень g(Х)==const.

Если функция g(Х) линейна, то =1. Параметр m кратности «пробных» шагов определяется по формуле
.							

После определения точки Х2 осуществляется передвижение на границу  в точку X3 с заданной точностью 0. Схема движения к условному минимуму показана на рисунке

Полученная точка Х3 принимается за снова за точку «0» и процедура повторяется. Последовательное получение точек  продолжается до тех пор, пока выполняется условие монотонного убывания С(Х)
						
Нарушение этого условия определяет участок ограничения , который содержит точку Х* условного минимума С(Х). При нарушении условия параметр  можно уменьшать. Процесс движения к условному минимуму прекращается, если выполняется условие
,							
где c – заданная величина.
В случае нескольких переменных (m > 1) следует рассматривать участки «активного» ограничения, образующего :
.		
Если  представляет собой линейную функцию g(Х), то m= и точка Х2 неопределенна.
Если учитывать ограниченную область поиска, то алгоритм поиска условного локального минимума с использованием «пробных» и «рабочих» шагов является работоспособным независимо от свойств функции gk(Х). При этом необходимо учитывать все ограничения образующих область D допустимых решений и области поиска П. Параметр m следует вычислять по формуле:
,								
,							
где i – номера тех ограничений, для которых выполняется условия:
      .				                                    

ЛИТЕРАТУРА
1.	Моисееев Н.Н. Математические методы системного анализа. М.:Наука,1981.
2.	Гермейер Ю.Б. Введение в теорию исследования операций. М.: Наука, 1971.
3.	Химмельблау Д. Прикладное нелинейное программирование. М.: Мир, 1975.
4.	Малков В.П., Угодчиков А.Г. Оптимизация упругих систем. М.: Наука.1981.
5.	Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. М.: Мир, 1985.
6.	Батищев Д.И. Поисковые методы оптимального проектирования. 
М.: Советское радио, 1975.
7.	Соболь И.М., Статников Р.Б. Выбор оптимальных параметров в задачах со многими критериями. М.: Наука, 1981. 110с.
8.	Стронгин Р.Г. Численные методы в экстремальных задачах. 
М.: Наука, 1978.
9.	Стронгин Р.Г. Поиск глобального оптимума. М.: Знание, 1990.
10.	Кони Р., Райфа Х. Принятие решений при многих критериях: предпочтения и замечания. – М: Радио и связь, 1981. 
11.	Подиновский В.В., Ногин В.Д. Парето-оптимальные решения многокритериальных задач. М.: Наука, 1982. 254 с.
12.	Strongin R.G., Markin D.L., Markina M.V. Reduction of Multi-extremum Multi-criterion Problems with Constraints to Unconstrainted Optimization Problems: Theory and Algorithms. Computational and Mathematical Modelling, V. 6.  № 4. 1995, P.242-248. Plenum Publishing Corporation.
13.	Стронгин Р.Г., Гергель В.П., Городецкий С.Ю., Гришагин В.А., Маркина М.В. Современные методы принятия оптимальных решений. Учебник. Н. Новгород. Изд-во ННГУ. 2002.
14.	Малков В.П., Маркина М.В. Поэтапная параметрическая оптимизация. Учебное пособие. Н. Новгород. Изд-во Нижегородского университета. 1998. 
15.	Пиявский С.А. Один алгоритм отыскания абсолютного минимума функции.-ЖВМ и МФ, №4, 1972, с.888-896.
16.	Strongin R.G., Markin D.L. Minimization of multiextremal functions with nonconvex constraints. Cybernetics 22(4), 1986, p.486-493.
17.	Уайлд Д.Дж. Методы поиска экстремума. –М.: Наука, 1967. –267 с.