2. Лекции Практические и лабораторные занятия



бет27/46
Дата06.01.2022
өлшемі0,77 Mb.
#11583
1   ...   23   24   25   26   27   28   29   30   ...   46
Байланысты:
УМКД метод матер МО и Исл опер

Вопросы для самоконтроля:

1.Понятия и сущность о выпуклом программировании.

2.Теорема Куна - Таккера.

3.Метод множителей Лагранжа.


Рекомендуемая литература:

1.Ашманов С.А. Линейное программирование. —М.: Наука, 1981.

2.Айсагалиев А.С., Айсагалиева С.С. Лекции по методам оптмизации.-Алматы:Гылым,1996
Лекция 11 . Методы безусловной оптимизации

Содержание лекционного занятия:


Это методы поиска минимума функции многих пере­менных при отсутствии ограничений.

Итерационные методы минимизации функции F(x) со­стоят в построении последовательности векторов, т.е. точек х0, х1,..., хkтаких что F(x0) > F(x1) > ... > F(xk) > ... Любой такой метод называется методом спуска. Естественно, должна быть обеспечена сходимость получаемой последо­вательности точек к точке минимума, т.е. рассматриваются методы, позволяющие получить точку минимума за конеч­ное число шагов или приблизиться к ней достаточно близко при соответствующем числе шагов. К сожалению, здесь нельзя употребить слова «сколь угодно близко при неогра­ниченном увеличении числа шагов». Дело в том, что тео­ретически все сходящиеся методы этим свойством облада­ют, но практически близость к минимуму в задачах боль­шой размерности ограничивается ошибками вычислений, которые обусловлены погрешностью представления чисел в компьютере. Поэтому необходимо вести вычисления с удвоенной точностью, выбирая соответствующие типы дан­ных при разработке конкретных компьютерных программ.



Для построения итерационной последовательности необхо­димо выбрать начальное приближение х0. В задачах с ограниче­ниями это должна быть допустимая точка, а в задачах без огра­ничений— теоретически любая точка. Однако целесообразно использовать всю имеющуюся информацию о поведении целе­вой функции F(x), чтобы выбрать х0 поближе к точке минимума.

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



  1. Выбрать направление, по которому пойдем из х0 в точку с меньшим значением целевой функции (направление спуска);

  2. Определить величину шага по направлению спуска. При любом методе спуска итерационная последователь­ность точек{хк} может быть записана в виде: хк+'=хк + λкpк,(к = 0, 1,...),

где вектор рк — это направление, а λк||рк|| — величина шага. Если ||рк|| =1, т.е. длина вектора спуска равна единице, то величина шага равна λк. Отметим, что иногда λк называ­ют шагом независимо от длины вектора рк. Здесь — длина вектора рк.

Методы спуска отличаются процедурами построения вектора рк и вычисления λк. При этом могут использоваться одна (последняя) или две последние (или более) из уже по­лученных точек.

Для задач безусловной минимизации любое направление является возможным (никакие ограничения не мешают), но далеко не все направления приемлемы. Нас могут интересо­вать только направления, обеспечивающие убывание целе­вой функции, хотя бы при достаточно малом шаге. Предпо­лагая непрерывность первых частных производных целевой функции и используя ее разложение в ряд Тэйлора в произ­вольной точке х, получим F(x + λр) ≈ F(x) + λ(g, p). Здесь g— градиент функции, вычисленный в точке х. Отсюда следует, что приращение функции F(x + λр) - F(x) < 0 при отрицательном скалярном произведении (g, p). Итак, направление спуска должно составлять острый угол с ан­тиградиентом. Этот вывод справедлив и для задач с огра­ничениями, но там еще дополнительно требуется, чтобы при достаточно малом шаге не нарушалось ни одно из огра­ничений.

Все такие направления называются подходящими (приемлемыми). Методы спуска, позволяющие получать последовательно подходящие направления, Зойтендейк (Zoutendijk G.) назвал методами возможных направлений.



Достарыңызбен бөлісу:
1   ...   23   24   25   26   27   28   29   30   ...   46




©emirsaba.org 2024
әкімшілігінің қараңыз

    Басты бет