Численные методы оптимизации

Сентябрь 3, 2022

Главная
Алгебра
Численные методы оптимизации

Содержание

2. Методы прямого поиска В типичном методе поиска направления минимизации полностью определяются на основании последовательных вычислений целевой
3. Методы прямого поиска Методы поиска не требуют регулярности и непрерывности целевой функции и существования производных. Голоморфная
4. Методы прямого поиска Вторым обстоятельством, правда, связанным с предыдущей проблемой, является то, что при использовании методов
5. Методы прямого поиска Методы поиска простейшего типа заключаются в изменении каждый раз одной переменной, тогда как
6. Hooke, R.; Jeeves, T.A. (1961). "'Direct search' solution of numerical and statistical problems". Journal of the
7. Алгоритм Хука и Дживса Хук и Дживс предложили логически простую стратегию поиска, использующую априорные сведения и
8. Затем в циклическом порядке изменяется каждая переменная (каждый раз только одна) на выбранные величины приращений, пока
9. На каждом шаге или сдвиге по независимой переменной значение целевой функции сравнивается с ее значением в
10. Длина шага при поиске по образцу в данном координатном направлении приблизительно пропорциональна числу удачных шагов, имевших
11. Алгоритм Хука и Дживса Один из алгоритмов минимизации (библиотека МГУ) использует метод Хука - Дживса для
12. Assume we are searching for the minimizer of f starting from a given initial point x(0)
13. If , then a success is recorded and the starting point is moved in , from
14. Алгоритм Хука и Дживса -II , To achieve a certain accuracy, the step lengths must be
15. Алгоритм Хука и Дживса -II , 2. . If then the method terminates yielding as an
16. Алгоритм Хука и Дживса , function [x,minf,iter]=hookejeeves(f,n,h,x0,tol) {HOOKEJEEVES HOOKE and JEEVES method for function minimization. [X,
17. Алгоритм Хука и Дживса , function [x]=explore(f,n,h,x0) { EXPLORE Exploration step for function minimization. [X] =
18. Hooke and Jeeves -I
19. Hooke and Jeeves -II
20. Example – Tests for Simplex and Hooke and Jeeves methods
22. Скачать презентацию

Слайд 2

Методы прямого поиска
В типичном методе поиска направления минимизации полностью
определяются на

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

Слайд 3

Методы прямого поиска
Методы поиска не требуют регулярности и непрерывности целевой
функции

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

Слайд 4

Методы прямого поиска
Вторым обстоятельством, правда, связанным с предыдущей
проблемой, является то,

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

Слайд 5

Методы прямого поиска
Методы поиска простейшего типа заключаются в изменении каждый раз
одной

переменной, тогда как другие остаются постоянными, пока не будет
достигнут минимум. Например, в одном из таких методов переменная
устанавливается постоянной, а изменяют до тех пор, пока не будет
получен минимум.
Затем, сохраняя новое значение постоянным, изменяют пока
не будет достигнут оптимум при выбранном значении и т. д.
Однако такой алгоритм работает плохо, если имеет место взаимодействие
между и , т. е., например, если в выражение для целевой функции
входят члены, содержащие произведение .

Слайд 6

Hooke, R.; Jeeves, T.A. (1961). "'Direct search' solution of numerical and

statistical problems". Journal of the Association for
Computing Machinery (ACM) 8 (2): 212–229.

Алгоритм Хука и Дживса

Pattern search (PS) refers to a family of numerical optimization methods that do not require the gradient of the problem to be optimized and PS can hence be used on functions that are not continuous or differentiable. Such optimization methods are also known as direct-search, derivative-free, or black-box methods

The name, pattern search, was coined by Hooke and Jeeves [1]. An early and simple PS variant is attributed to Fermi and Metropolis when they worked at the Los Alamos National Laboratory as described by Davidon [2] who summarized the algorithm as follows:

They varied one theoretical parameter at a time by steps of the same magnitude, and when no such increase or decrease in any one parameter further improved the fit to the experimental data, they halved the step size and repeated the process until the steps were deemed sufficiently small.

Слайд 7

Алгоритм Хука и Дживса
Хук и Дживс предложили логически простую стратегию поиска,

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

Слайд 8

Затем в циклическом порядке изменяется каждая переменная (каждый раз
только одна)

на выбранные величины приращений, пока все параметры не
будут таким образом изменены.
В частности, изменяется на величину , так что
Если приращение не улучшает целевую функцию, изменяется
на и значение проверяется, как и ранее.
Если значение не улучшают ни ,
ни , то оставляют без изменений.
Затем изменяют на величину и т, д., пока не будут изменены
все независимые переменные, что завершает один исследующий поиск.

Алгоритм Хука и Дживса

Слайд 9

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

сравнивается с ее значением в предыдущей точке. Если целевая
функция улучшается на данном шаге, то ее старое значение заменяется на
новое при последующих сравнениях. Однако если проведенное возмущение
по неудачно, то сохраняется прежнее значение .
После проведения (exploration step) исследующего поиска применяется
стратегия поиска по образцу. Удачные изменения переменных в
исследующем поиске [т. е, те изменения переменных,
которые уменьшили ] определяют вектор в , указывающий
некоторое направление минимизации, которое может привести к успеху. Серия ускоряющихся шагов (advancing steps), или поиск по образцу,
проводится вдоль этого вектора до тех пор, пока уменьшается при
каждом таком поиске.

Исследующий поиск

Слайд 10

Длина шага при поиске по образцу в данном координатном направлении
приблизительно

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

Исследующий поиск и поиск по образцу

Слайд 11

Алгоритм Хука и Дживса
Один из алгоритмов минимизации (библиотека МГУ) использует

метод
Хука - Дживса для решения задачи минимизации функции многих
переменных без вычисления производных при наличии двухсторонних
ограничений на переменные методом покоординатного спуска с
построением аппроксимирующей параболы.
http://www.srcc.msu.su/num_anal/lib_na/cat/mn/mnn1r.htm

Тексты программ приводятся на фортране, Си и паскале.
Немного отличный от этого метод приводится в книге:
Alfio Quarteroni, Riccardo Sacco, Fausto Saleri. Numerical Mathematics.
Springer, 2nd ed., 2007.

Слайд 12

Assume we are searching for the minimizer of f starting from

a given initial point x(0) and requiring that the error on the residual is less than a certain fixed tolerance . The Hooke and Jeeves method computes a new point x(1) using the values of f at suitable points along the orthogonal coordinate directions around x(0).
The method consists of two steps: an exploration step and an advancing step.
The exploration step starts by evaluating , where is the first vector of the canonical basis of and is a positive real number to be suitably chosen.

Алгоритм Хука и Дживса -II

Слайд 13

If , then a success is recorded and
the starting point is

moved in , from which an
analogous check is carried out at point
with .
If, instead, , then a failure is recorded and
a similar check is performed at . If a success is
registered, the method explores, as previously, the behavior
of f in the direction starting from this new point, while,
in case of a failure, the method passes directly to examining
direction , keeping as starting point for the
exploration step.

Алгоритм Хука и Дживса -II

Слайд 14

Алгоритм Хука и Дживса -II
,
To achieve a certain accuracy,

the step lengths must be selected in such
a way that the quantities
have comparable sizes.
The exploration step terminates as soon as all the n Cartesian directions
have been examined. Therefore, the method generates a new point, ,
after at most 2n + 1 functional evaluations.
Only two possibilities may arise:
. In such a case, if the method terminates and yields the
approximate solution .
Otherwise, the step lengths are halved and another exploration step is
performed starting from ;

Слайд 15

Алгоритм Хука и Дживса -II
,
2. . If then the

method terminates yielding as
an approximate solution, otherwise the advancing step starts.
The advancing step consists of moving further from along the direction , (which is the direction that recorded the maximum decrease of f during the exploration step), rather then simply setting as a new starting point .
This new starting point is instead set equal to . From this point
a new series of exploration moves is started. If this exploration leads to a
point such that , then a new starting point
for the next exploration step has been found, otherwise the initial guess
for further explorations is set equal to .
The method is now ready to restart from the point just computed.

Слайд 16

Алгоритм Хука и Дживса
,
function [x,minf,iter]=hookejeeves(f,n,h,x0,tol)
{HOOKEJEEVES HOOKE and JEEVES method

for function minimization.
[X, MINF, ITER] = HOOKEJEEVES(F, N, H, X0, TOL) attempts to compute the minimizer of a function of N variables with the Hooke and Jeeves method. F is a string variable containing the functional expression of f. H is an initial step. X0 specifies the initial guess. TOL specifies the tolerance of the method. ITER is the iteration number at which X is computed. MINF is the value of F at the mimimizer X.}

Слайд 17

Алгоритм Хука и Дживса
,
function [x]=explore(f,n,h,x0)
{ EXPLORE Exploration step for

function minimization.
[X] = EXPLORE(F, N, H, X0) executes one exploration step of size H in the Hooke
and Jeeves method for function minimization.}

Слайд 18

Hooke and Jeeves -I

Слайд 19

Hooke and Jeeves -II

Слайд 20

Численные методы оптимизации

Содержание

Методы прямого поискаВ типичном методе поиска направления минимизации полностью определяются на

Методы прямого поиска Методы поиска не требуют регулярности и непрерывности целевой функции

Методы прямого поиска Вторым обстоятельством, правда, связанным с предыдущей проблемой, является то,

Методы прямого поискаМетоды поиска простейшего типа заключаются в изменении каждый разодной

Hooke, R.; Jeeves, T.A. (1961). "'Direct search' solution of numerical and

Алгоритм Хука и ДживсаХук и Дживс предложили логически простую стратегию поиска,

Затем в циклическом порядке изменяется каждая переменная (каждый раз только одна)

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

Длина шага при поиске по образцу в данном координатном направлении приблизительно

Алгоритм Хука и Дживса Один из алгоритмов минимизации (библиотека МГУ) использует