2. Лекции Практические и лабораторные занятия
жүктеу/скачать 0,77 Mb.
|
- Бұл бет үшін навигация:
- Лекция 11 . Методы безусловной оптимизации Содержание лекционного занятия
| Вопросы для самоконтроля:
1.Понятия и сущность о выпуклом программировании. 2.Теорема Куна - Таккера. 3.Метод множителей Лагранжа. Рекомендуемая литература: 1.Ашманов С.А. Линейное программирование. —М.: Наука, 1981. 2.Айсагалиев А.С., Айсагалиева С.С. Лекции по методам оптмизации.-Алматы:Гылым,1996
Градиентные методы Метод параллельных касательных Метод сопряженных градиентов Метод покоординатного спуска О методах второго порядка О методах прямого поиска Методы одномерной минимизации Это методы поиска минимума функции многих переменных при отсутствии ограничений. Итерационные методы минимизации функции F(x) состоят в построении последовательности векторов, т.е. точек х0, х1,..., хkтаких что F(x0) > F(x1) > ... > F(xk) > ... Любой такой метод называется методом спуска. Естественно, должна быть обеспечена сходимость получаемой последовательности точек к точке минимума, т.е. рассматриваются методы, позволяющие получить точку минимума за конечное число шагов или приблизиться к ней достаточно близко при соответствующем числе шагов. К сожалению, здесь нельзя употребить слова «сколь угодно близко при неограниченном увеличении числа шагов». Дело в том, что теоретически все сходящиеся методы этим свойством обладают, но практически близость к минимуму в задачах большой размерности ограничивается ошибками вычислений, которые обусловлены погрешностью представления чисел в компьютере. Поэтому необходимо вести вычисления с удвоенной точностью, выбирая соответствующие типы данных при разработке конкретных компьютерных программ. Для построения итерационной последовательности необходимо выбрать начальное приближение х0. В задачах с ограничениями это должна быть допустимая точка, а в задачах без ограничений— теоретически любая точка. Однако целесообразно использовать всю имеющуюся информацию о поведении целевой функции F(x), чтобы выбрать х0 поближе к точке минимума. После того как начальное приближение получено, прежде чем перейти к следующей точке, нужно принять два решения: Выбрать направление, по которому пойдем из х0 в точку с меньшим значением целевой функции (направление спуска); Определить величину шага по направлению спуска. При любом методе спуска итерационная последовательность точек{хк} может быть записана в виде: хк+'=хк + λкpк,(к = 0, 1,...), где вектор рк — это направление, а λк||рк|| — величина шага. Если ||рк|| =1, т.е. длина вектора спуска равна единице, то величина шага равна λк. Отметим, что иногда λк называют шагом независимо от длины вектора рк. Здесь — длина вектора рк. Методы спуска отличаются процедурами построения вектора рк и вычисления λк. При этом могут использоваться одна (последняя) или две последние (или более) из уже полученных точек. Для задач безусловной минимизации любое направление является возможным (никакие ограничения не мешают), но далеко не все направления приемлемы. Нас могут интересовать только направления, обеспечивающие убывание целевой функции, хотя бы при достаточно малом шаге. Предполагая непрерывность первых частных производных целевой функции и используя ее разложение в ряд Тэйлора в произвольной точке х, получим F(x + λр) ≈ F(x) + λ(g, p). Здесь g— градиент функции, вычисленный в точке х. Отсюда следует, что приращение функции F(x + λр) - F(x) < 0 при отрицательном скалярном произведении (g, p). Итак, направление спуска должно составлять острый угол с антиградиентом. Этот вывод справедлив и для задач с ограничениями, но там еще дополнительно требуется, чтобы при достаточно малом шаге не нарушалось ни одно из ограничений. Все такие направления называются подходящими (приемлемыми). Методы спуска, позволяющие получать последовательно подходящие направления, Зойтендейк (Zoutendijk G.) назвал методами возможных направлений. жүктеу/скачать 0,77 Mb. Достарыңызбен бөлісу:
|