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

на основании последовательных вычислений целевой
функции f(x).
При решении задач нелинейного

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

функции и существования производных.
Голоморфная функция, также называемая регулярной функцией — функция комплексного

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

то, что при использовании методов
оптимизации, основанных на вычислении первых

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

раз
одной переменной, тогда как другие остаются постоянными, пока не будет

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

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.

поиска,
использующую априорные сведения и в то же время отвергающую

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

одна) на выбранные величины приращений, пока все параметры не
будут

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

Если значение не улучшают ни ,
ни , то оставляют без изменений.

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

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

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

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

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

приблизительно пропорциональна числу удачных шагов, имевших место
ранее в этом

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

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

использует метод
Хука - Дживса для решения задачи минимизации функции многих
переменных

без вычисления производных при наличии двухсторонних
ограничений на переменные методом покоординатного спуска с
построением аппроксимирующей параболы.
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.

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

, 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

,

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 ;

. 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.

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.}

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.}