В области
Имеются несколько подходов при разработке методов решения задач
Основная идея
z=f(x)
с соответствующими ограничениями, наложенными на x,
в задачу поиска минимума без ограничений функции
Z=f(x)+P(x).
Функция Р(х) является штрафной. Необходимо, чтобы
при нарушении ограничений она "штрафовала" функцию Z, т.е. увеличивала ее значение. В этом случае минимум Z будет находиться внутри области ограничений. Функция Р(х), удовлетворяющая этому условию, может быть не
единственной. Задачу минимизации можно сформулировать следующим
образом:$$\text{минимизировать функцию } z=f(x)$$
$$\text{при ограничениях } c_j(x) > 0, \; j=1,2,\ldots,m.$$
Замечание. Ограничение вида "меньше или равно", $$h(х) \le 0$$, всегда может быть записано как $$-h(x) \ge 0$$, поэтому в приведенной выше формулировке нет потери общности.
Функцию Р(х) удобно записать следующим образом:$$P(x) = r \sum_{j=1}^m \frac{1}{c_j(x)} .$$
где r - положительная величина. Тогда функция $$Z = \varphi(х,r)$$ принимает вид$$Z = \varphi (x, r) = f(x) + \sum_{j=1}^m \frac{1}{c_j(x)} .$$
Если x принимает допустимые значения, т.е. значения,
для которых $$c_j(х) \ge 0$$, то Z принимает
значения, которые больше соответствующих значений f(х)
(истинной r может быть очень малой величиной.
Но если x принимает значения, которые хотя и являются
допустимыми, но близки к границе области ограничений, и по крайней
мере одна из функций cj(x) близка к нулю,
тогда значения функции Р(х) и, следовательно, значения
функции Z станут очень велики. Таким образом, влияние
функции Р(х) состоит в создании "гребня с крутыми
краями" вдоль каждой границы области ограничений. Следовательно,
если поиск начинается из допустимой точки и осуществляется поиск
минимума функции $$\varphi(х,r)$$ без ограничений, то минимум,
конечно, будет достигаться внутри r достаточно малой величиной,
для того чтобы влияние Р(х) было малым в точке минимума,
мы можем сделать точку минимума функции $$\varphi(х,r)$$ без
ограничений совпадающей с точкой минимума функции f(х)
с ограничениями.
В общем случае невозможно аналитически определить положение
минимума функции $$\varphi (x,r)$$, рассматривая ее как
обычную функцию от r. Для его определения необходимо
обратиться к численным методам.
Следует отметить, что если f(х)
выпукла, а функция сj(х) вогнута, то
функция $$\varphi (х, r)$$, заданная уравнением (1.4),
также является выпуклой функцией в области ограничений, которая
сама является выпуклой. Следовательно, $$\varphi (х, r)$$
имеет для данного значения r единственный минимум.
Если x1 и x2 -
точки, принадлежащие j = 1,2,...,m, то при $$0 < \Theta < 1$$
справедливо неравенство$$c_j (\Theta x_2 + (1 - \Theta)x) \ge \Theta c_j (x_2) + (1 - \Theta) c_j (x_1) \ge 0 ,$$
так как функция сj(х) выпукла.
Следовательно,
Таким образом, точка $$х_2 + (1 - \Theta) x_1$$ при $$0 < \Theta < 1$$ также является допустимой.
Кроме того, функция 1/сj(х) является
выпуклой для всех x, которые удовлетворяют
неравенству $$c_j(х) \ge 0$$. Если h(х) = 1/сj(х), то$$\nabla h (x) = \frac{-\nabla c_j (x)}{[c_j(x)]^2} .$$
где $$c(х)_{ik} = \partial^2 с_j(x)/\partial x_i \partial x_k$$
есть сj(х). Тогда, если p - произвольный вектор, то справедливо равенство$$p^T \mathbf{H} (x) p =
-\frac{p^T C(x)p}{[c_j (x)]^2} +
\frac{2[p^T \nabla c_j (x)]^2}{[c_j (x)]^3} ,$$
где всегда рTН(х)р > 0, так как С(х) - отрицательно определенная матрица ввиду того,
что сj(х) - выпуклая функция и $$c_j(х) \ge 0$$. Тогда матрица Н(х)
положительно определена и 1/сj(х) выпукла
во вcей области. Eсли r > 0, то функция Р(х), заданная уравнением (1.3), и функция $$\varphi (х, r)$$, заданная уравнением (1.4), также выпуклы.
Предположим, что $$x^*_1, х^*_2, \ldots , х^*_k$$ -
минимальные точки функции $$\varphi (х, r)$$ для убывающей
последовательности значений r1, r2, ..., rk, ...,
стремящейся к нулю. Тогда последовательность точек $$x^*_1, х^*_2, \ldots , х^*_k$$, сходится к
Полученный результат можно доказать следующим образом.
Поскольку f(х) непрерывная функция и $$f(х^*) \le f(х)$$ для всех допустимых точек,
то, задав произвольное достаточно малое значение $$\varepsilon$$, можно найти допустимую точку х', такую, что$$f(x') < f(x^*) + \varepsilon / 2 .$$
Поскольку rk - убывающая
последовательность, стремящаяся к нулю, можно найти
такое значение K, что для $$k \ge K$$
справедливо неравенство$$r_k \leqslant
\left\{ \frac{\varepsilon}{2m} \min_j
\left[ \frac{1}{c_j (x')}
\right] \right\}.$$
Поскольку P(x) > 0 из определения функции $$\varphi(x, r)$$, имеем$$f(x^*) \leqslant \min \varphi (x, r_k) = \varphi (x_k^*, r_k) .$$
где $$х^*_k$$ - минимальная точка функции $$\varphi(х, r_k)$$ для задачи без ограничений. Кроме
того, если k > К, то rk < rK и справедливо
неравенство$$\varphi(x_k^*, r_k) \leqslant \varphi(x_K^*, r_k).$$
Это следует из того, что, поскольку $$х^*_k$$
минимизирует функцию $$\varphi(х, r_k)$$ в любой
другой точке области x, в частности в точке $$х^*_k$$, функция будет принимать значение,
большее чем $$\varphi(х_k^*, r_k)$$. Поэтому$$\begin{aligned}
\varphi(x_K^*, r_K) = f(x_K^*) + r_K \sum_{j=1}^m \frac{1}{c_j(x_K^*)} > \\
> f(x_K^*) + r_k \sum_{j=1}^m \frac{c_j}{x_K^*} ,
\end{aligned}$$
поскольку rk<rK.
Следовательно,$$\varphi(x_K^*,r_K) > \varphi(x_K^*,r_k)$$
Тогда$$f(x^*) \leqslant \varphi(x_k^*,r_k) \leqslant \varphi(x_K^*,r_k) < \varphi(x_K^*,r_K).$$
Но так как значение $$x^*_K$$ минимизирует функцию $$\varphi(x, r_K)$$, то$$\varphi(x_K^*,r_K) \leqslant \varphi(x',r_K) = f(x') + r_K \sum_{j=1}^m \frac{1}{c_j(x')} .$$
Следовательно, из уравнений (1.11) и (1.12) получим$$f(x^*) \leqslant \varphi (x_k^*,r_k) \leqslant f(x') +r_K \sum_{j=1}^m \frac{1}{c_j(x')}$$
Из уравнения (1.8) следует, что$$f(x') + r_K \sum_{j=1}^m \frac{1}{c_j(x')} \leqslant f(x') + \frac{\varepsilon}{2} .$$
Тогда из уравнения (1.7) следует, что$$f(x^*) \leqslant \varphi (x_k^*, r_k) < f(x^*) + \frac{\varepsilon}{2} + \frac{\varepsilon}{2} .$$ и$$\varphi (x_k^*, t_k) - f(x^*) < \varepsilon .$$
Поскольку $$\varepsilon$$ может быть выбрано произвольно
малым, всегда можно найти такое значение k, при котором$$f(x^*) < \varphi (x_k^*,r_k) < f(x^*) + \varepsilon$$
Таким образом, при $$k \rightarrow \infty \; (r_k \rightarrow 0)$$$$\lim_{r_k \rightarrow 0} \varphi(x_k^*,r_k)=f(x^*).$$
Из приведенного выше доказательства следует, что при $$r_k \rightarrow 0$$$$f(x_k^*) \rightarrow f(x^*) \quad \text{и} \quad r_k \sum_{j=1}^m \frac{1}{c_j(x_k^*)} \rightarrow 0.$$
В качестве упражнения оставлено доказательство того, что $$f(х^*_1), f(х^*_2), \ldots, f(x^*_3)$$ образуют убывающую последовательность, такую, что$$f(x_{k+1}^*) < f(x_k^*).$$
Очевидно, что если функция f(х) выпукла, а
функция cj(х) при j = 1,...,n вогнута, то функция f(х) при наличии ограничении имеет единственный
минимум.
Результаты предыдущего раздела показывают, что можно решить
задачу минимизации с ограничениями (минимизировать функцию f(х) при ограничениях $$c_j(x) \ge 0$$, решая для последовательности значений r, стремящейся к нулю, задач без ограничений
следующего вида:$$\text{минимизировать функцию} \quad
\varphi(x,r) = f(x) + к \sum_{j=1}^m \frac{1}{c_j(x)} .$$
х*(r),
предел которой при $$r \rightarrow 0$$ можно исследовать.
Поэтому для того, чтобы можно было применить настоящий метод на
практике, необходимо построить вычислительный метод, использующий
теоретическое свойство сходимости, рассмотренное в предыдущем разделе.
Теоретически здесь не возникает трудностей. Для заданных функцией f(х) ограничениях $$с_j(х) \ge 0, j = 1,\ldots, n$$,
необходимо выбрать начальное значение r = r0,
чтобы сформировать функцию $$\varphi(х, r_0)$$, которая
минимизируется без ограничений методом ДФП. Найдя минимум функции $$\varphi(х, r_0)$$, необходимо уменьшить значение r. Это можно сделать эффективно и просто, если найти r1 = r0/c, где константа с > 1. Затем необходимо минимизировать функцию $$\varphi(х, r_k)$$, снова используя метод ДФП. Таким
образом, будет разработана итерационная процедура.
На k -м шаге минимизируется функция $$\varphi(х, r_k)$$, минимум которой находится в точке $$х^*_k$$. Важно, что ее можно использовать в дальнейшем
в качестве первой точки в итерационной процедуре минимизации функции $$\varphi(х, г_{k-1})$$, где rk+1 = гk/с. Теперь ясно, что
последовательность rk убывает и стремится к
нулю, следовательно, последовательность точек минимумов будет
сходиться к решению задачи с ограничениями.
Ниже приведена блок-схема (рис. 13.1)
Предполагается, что в начале процедуры имеется допустимая точка.
Важно, чтобы в процессе последующих вычислений получаемые точки
принадлежали x к
границе внутри x к границе снаружи
Таким образом, если поиск осуществляется вдоль прямой,
соединяющей две точки, одна из которых лежит внутри, а другая
вне области ограничений, то кубическая интерполяция оказывается
неприемлемой, поскольку функция разрывна вдоль данной прямой.
Действительно, если минимум будет найден вне
(рис 13.1) Выбор начального значения r может оказаться важным
с точки зрения сокращения числа итераций при минимизации функции $$\varphi (х, r)$$. Если сначала r выбрано очень
малым, для того чтобы функция $$\varphi (х, r)$$ мало
отличалась от функции f(x), то метод будет сходиться
очень быстро. Однако такой выбор может привести к серьезным
осложнениям при вычислениях. Для малых r функция $$\varphi (х, r)$$ будет быстро меняться в окрестности
минимума, что может вызвать затруднения при использовании градиентного
метода. Слишком же большое значение r может привести к
тому, что штрафная функция Р(х) в уравнении (1.4) станет
доминирующей. Поэтому "разумный" выбор начальной точки очень
важен. Для многих задач "разумным" значением для начальной
точки является значение r0 = 1. Более
рациональный подход состоит в том, чтобы понять, что если начальная
точка x будет лежать вблизи минимума функции$$\varphi(x,r)=f(x)+r \sum_{j=1}^m \frac{1}{c_j(x)} =f(x)+rP(x),$$
то
Это начальное значение r, как предполагает Фиакко
и Маккормик, должно давать хорошие результаты в общем случае.
Уменьшить значение r очень простo: rk+1 = rk/с, где с = 10.
Для минимизации функции $$\varphi (x,r_{k+})$$
используется метод ДФП. В качестве начальной точки используется
оптимальная точка функции $$\varphi (x,r_{r})$$, и это
оказывается очень эффективным. Oднако необходимо обратить внимание
на то, чтобы в процессе одномерного поиска не выйти за область
ограничений. Грубым, но вполне эффективным является следующий
метод. Пусть имеются точка p и направление поиска d=-Hg. Следующая точка $$q=р+\lambda d$$ необходима для осуществления
кубической интерполяции. Начнем со значения $$\lambda =2$$ (удвоенный шаг в q допустимой, т.е.
выполняется ли неравенство сj(q) > 0
для всех j. Если оно выполняется, то $$\lambda$$ не меняется, но если неравенство не
выполняется, то $$\lambda$$ заменяется на $$\lambda /\alpha$$ находится новая точка q и вновь производится проверка. В конце концов
допустимая точка q будет найдена, и тогда можно
осуществить интерполяцию. Выбор значения $$\alpha$$
не вполне очевиден. Выбор $$\alpha =2$$ был успешным,
при $$\alpha =1,05$$ длина шага становится близкой к
расстоянию до ближайшей границы области ограничений и поэтому
является "безопасной" для интерполяционной процедуры.
Важно не дать точкам выйти за область ограничений в процессе минимизации.
Функция $$\varphi (х,r)$$ минимизируется до тех пор,
пока два последовательных значения F1 и F2 не станут такими, что |(F1–F2)/F1|<0,000001.
Это условие, конечно, может быть изменено. В соответствии с
соотношением (1.17) процесс минимизации заканчивается, когда$$r \sum_{j=1}^m \frac{1}{c_j (x_k^*)} < 0,000001 .$$
Если ограничения в задаче имеют вид чистых неравенств, т.е.$$a_i < g_i (\overline{X}) < b_i , \quad i=\overline{1,m} ,$$ то присоединенная функция может быть построена в виде так называемого барьера:$$G(\overline{X}) = \sum_{i=1}^m \frac{1}{(b_i - g_i (\overline{X}))(g_i(\overline{X})-a_i)} .$$
Как только одна из функций $$g_i(\overline{X})$$ достигнет
своего предела ( ai или bi ),
штраф $$G(\overline{X})) \rightarrow \infty$$, т.е.
возникнет т.н. "барьер".
Метод был предложен Кэрролом, и получил название
При этом 10-5 ).
Рассмотрим действие данного метода на примере задачи оптимального проектирования контейнера.
Пусть требуется спроектировать контейнер в форме прямоугольного
параллелепипеда объемом V=1м3. Желательно,
чтобы при изготовлении контейнеров затрачивалось как можно меньше
материалов. Чтобы его было удобно брать автопогрузчиком, ширина
должна быть не менее 1,5 м.
Строим математическую модель контейнера.
1) Формируем вектор переменных $$\overline{X}$$.
Параметрами вектора переменных являются: длина x1, ширина x2
и высота x3 контейнера, т.е.$$\overline{X} = [x_1,x_2,x_3].$$
Размерность задачи n=3.
2) Строим
Тогда$$F(\overline{X}) = S(\overline{X}) = 2(x_1 x_2 + x_2 x_3 + x_1 x_3).$$
3) Формируем ограничения.
Ограничение-равенство:$$\text{Объем } V = x_1 \cdot x_2 \cdot x_3 = 1\text{м}^2 .$$ Ограничение-неравенство:$$\text{Ширина } x_2 \ge 1,5 \text{м}.$$
Упростим математическую модель контейнера. Ограничение – равенство (3.3) в задаче, благодаря своей простоте, позволяет уменьшить размерность задачи, т.е.
x3 = 1/x1x2 .
В результате параметр x3 можно исключить
из вектора проектных параметров, и из трехмерной задачи мы получим
двумерную. Тогда вектор $$\overline{X}$$ будет иметь вид:$$\overline{X}=[x_1,x_2].$$
В результате, задача проектирования контейнера может быть сформулирована следующим образом:
Найти вектор $$\overline{X} = [x_1, x_2]$$, доставляющий
минимум
В данной задаче
Как только один из параметров x1 или x2 достигнет своего предела, штраф $$G(\overline{X}) \rightarrow \infty$$, т.е. возникнет
т.н. "барьер".
Штрафная функция в задаче проектирования контейнера будет иметь вид:$$P(\overline{X},RC)=F(\overline{X})+RC \cdot G(\overline{X}) = 2 \left( x_1 \cdot x_2 + \frac{1}{x_1} + \frac{1}{x_2} \right) + RC \left( \frac{1}{x_1 - 1,5} + \frac{1}{x_2} \right).$$
Для нахождения минимума этой штрафной функции (задача двумерная) может быть использован метод многомерной оптимизации.
Задачи
Пример.
Найти вектор $$\overline{X}=[x_1,x_2]$$, доставляющий минимум$$F(\overline{X}) = x_1^2 + x_2 ,$$ при ограничениях$$\begin{gathered} g_1(\overline{X}) \rightarrow -(x_1^2 + x_2^2) + 9 \ge 0, \\ g_2(\overline{X}) \rightarrow -x_1 - x_2 + 1 \ge 0. \end{gathered}$$
Строим область допустимых решений $$G$$. Для этого преобразуем ограничения.
Ограничение $$g_1(\overline{X})$$ будет иметь вид:$$x_1^2 + x_2^2 \le 9.$$
Тогда ограничение $$g_1(\overline{X})$$ отсекает на
плоскости круг радиусом r=3.
Ограничение $$g_2(\overline{X})$$ будет иметь вид:$$x_1 + x_2 \le 1 .$$
Тогда ограничение $$g_2(\overline{X})$$ отсекает на
плоскости полуплоскость, ограниченную уравнением x1+x2=1.
В результате область допустимых решений G будет
иметь вид, представленный на
рис 13.2.
Строим [x1,x2] для которых
Меняя значения C, получим различные линии уровня.$$\begin{aligned}
\text{Если } C=\phantom{-}0, \; \text{то} \; x_2 = -x_1^2, \\
C=-1, \; \text{то} \; x_2 = -1 -x_1^2, \\
C=-2, \; \text{то} \; x_2 = -2 -x_1^2, \\
C=-3, \; \text{то} \; x_2 = -3 -x_1^2.
\end{aligned}$$
Как видно, x2.
Положение каждой параболы зависит от значения константы C (рис 13.2.).
Исследуя полученные линии уровня получим что G, в точке с координатами [0,-3].
(рис 13.2)
В области
Имеются несколько подходов при разработке методов решения задач
Основная идея
z=f(x)
с соответствующими ограничениями, наложенными на x,
в задачу поиска минимума без ограничений функции
Z=f(x)+P(x).
Функция Р(х) является штрафной. Необходимо, чтобы
при нарушении ограничений она "штрафовала" функцию Z, т.е. увеличивала ее значение. В этом случае минимум Z будет находиться внутри области ограничений. Функция Р(х), удовлетворяющая этому условию, может быть не
единственной. Задачу минимизации можно сформулировать следующим
образом:$$\text{минимизировать функцию } z=f(x)$$
$$\text{при ограничениях } c_j(x) > 0, \; j=1,2,\ldots,m.$$
Замечание. Ограничение вида "меньше или равно", $$h(х) \le 0$$, всегда может быть записано как $$-h(x) \ge 0$$, поэтому в приведенной выше формулировке нет потери общности.
Функцию Р(х) удобно записать следующим образом:$$P(x) = r \sum_{j=1}^m \frac{1}{c_j(x)} .$$
где r - положительная величина. Тогда функция $$Z = \varphi(х,r)$$ принимает вид$$Z = \varphi (x, r) = f(x) + \sum_{j=1}^m \frac{1}{c_j(x)} .$$
Если x принимает допустимые значения, т.е. значения,
для которых $$c_j(х) \ge 0$$, то Z принимает
значения, которые больше соответствующих значений f(х)
(истинной r может быть очень малой величиной.
Но если x принимает значения, которые хотя и являются
допустимыми, но близки к границе области ограничений, и по крайней
мере одна из функций cj(x) близка к нулю,
тогда значения функции Р(х) и, следовательно, значения
функции Z станут очень велики. Таким образом, влияние
функции Р(х) состоит в создании "гребня с крутыми
краями" вдоль каждой границы области ограничений. Следовательно,
если поиск начинается из допустимой точки и осуществляется поиск
минимума функции $$\varphi(х,r)$$ без ограничений, то минимум,
конечно, будет достигаться внутри r достаточно малой величиной,
для того чтобы влияние Р(х) было малым в точке минимума,
мы можем сделать точку минимума функции $$\varphi(х,r)$$ без
ограничений совпадающей с точкой минимума функции f(х)
с ограничениями.
В общем случае невозможно аналитически определить положение
минимума функции $$\varphi (x,r)$$, рассматривая ее как
обычную функцию от r. Для его определения необходимо
обратиться к численным методам.
Следует отметить, что если f(х)
выпукла, а функция сj(х) вогнута, то
функция $$\varphi (х, r)$$, заданная уравнением (1.4),
также является выпуклой функцией в области ограничений, которая
сама является выпуклой. Следовательно, $$\varphi (х, r)$$
имеет для данного значения r единственный минимум.
Если x1 и x2 -
точки, принадлежащие j = 1,2,...,m, то при $$0 < \Theta < 1$$
справедливо неравенство$$c_j (\Theta x_2 + (1 - \Theta)x) \ge \Theta c_j (x_2) + (1 - \Theta) c_j (x_1) \ge 0 ,$$
так как функция сj(х) выпукла.
Следовательно,
Таким образом, точка $$х_2 + (1 - \Theta) x_1$$ при $$0 < \Theta < 1$$ также является допустимой.
Кроме того, функция 1/сj(х) является
выпуклой для всех x, которые удовлетворяют
неравенству $$c_j(х) \ge 0$$. Если h(х) = 1/сj(х), то$$\nabla h (x) = \frac{-\nabla c_j (x)}{[c_j(x)]^2} .$$
где $$c(х)_{ik} = \partial^2 с_j(x)/\partial x_i \partial x_k$$
есть сj(х). Тогда, если p - произвольный вектор, то справедливо равенство$$p^T \mathbf{H} (x) p =
-\frac{p^T C(x)p}{[c_j (x)]^2} +
\frac{2[p^T \nabla c_j (x)]^2}{[c_j (x)]^3} ,$$
где всегда рTН(х)р > 0, так как С(х) - отрицательно определенная матрица ввиду того,
что сj(х) - выпуклая функция и $$c_j(х) \ge 0$$. Тогда матрица Н(х)
положительно определена и 1/сj(х) выпукла
во вcей области. Eсли r > 0, то функция Р(х), заданная уравнением (1.3), и функция $$\varphi (х, r)$$, заданная уравнением (1.4), также выпуклы.
Предположим, что $$x^*_1, х^*_2, \ldots , х^*_k$$ -
минимальные точки функции $$\varphi (х, r)$$ для убывающей
последовательности значений r1, r2, ..., rk, ...,
стремящейся к нулю. Тогда последовательность точек $$x^*_1, х^*_2, \ldots , х^*_k$$, сходится к
Полученный результат можно доказать следующим образом.
Поскольку f(х) непрерывная функция и $$f(х^*) \le f(х)$$ для всех допустимых точек,
то, задав произвольное достаточно малое значение $$\varepsilon$$, можно найти допустимую точку х', такую, что$$f(x') < f(x^*) + \varepsilon / 2 .$$
Поскольку rk - убывающая
последовательность, стремящаяся к нулю, можно найти
такое значение K, что для $$k \ge K$$
справедливо неравенство$$r_k \leqslant
\left\{ \frac{\varepsilon}{2m} \min_j
\left[ \frac{1}{c_j (x')}
\right] \right\}.$$
Поскольку P(x) > 0 из определения функции $$\varphi(x, r)$$, имеем$$f(x^*) \leqslant \min \varphi (x, r_k) = \varphi (x_k^*, r_k) .$$
где $$х^*_k$$ - минимальная точка функции $$\varphi(х, r_k)$$ для задачи без ограничений. Кроме
того, если k > К, то rk < rK и справедливо
неравенство$$\varphi(x_k^*, r_k) \leqslant \varphi(x_K^*, r_k).$$
Это следует из того, что, поскольку $$х^*_k$$
минимизирует функцию $$\varphi(х, r_k)$$ в любой
другой точке области x, в частности в точке $$х^*_k$$, функция будет принимать значение,
большее чем $$\varphi(х_k^*, r_k)$$. Поэтому$$\begin{aligned}
\varphi(x_K^*, r_K) = f(x_K^*) + r_K \sum_{j=1}^m \frac{1}{c_j(x_K^*)} > \\
> f(x_K^*) + r_k \sum_{j=1}^m \frac{c_j}{x_K^*} ,
\end{aligned}$$
поскольку rk<rK.
Следовательно,$$\varphi(x_K^*,r_K) > \varphi(x_K^*,r_k)$$
Тогда$$f(x^*) \leqslant \varphi(x_k^*,r_k) \leqslant \varphi(x_K^*,r_k) < \varphi(x_K^*,r_K).$$
Но так как значение $$x^*_K$$ минимизирует функцию $$\varphi(x, r_K)$$, то$$\varphi(x_K^*,r_K) \leqslant \varphi(x',r_K) = f(x') + r_K \sum_{j=1}^m \frac{1}{c_j(x')} .$$
Следовательно, из уравнений (1.11) и (1.12) получим$$f(x^*) \leqslant \varphi (x_k^*,r_k) \leqslant f(x') +r_K \sum_{j=1}^m \frac{1}{c_j(x')}$$
Из уравнения (1.8) следует, что$$f(x') + r_K \sum_{j=1}^m \frac{1}{c_j(x')} \leqslant f(x') + \frac{\varepsilon}{2} .$$
Тогда из уравнения (1.7) следует, что$$f(x^*) \leqslant \varphi (x_k^*, r_k) < f(x^*) + \frac{\varepsilon}{2} + \frac{\varepsilon}{2} .$$ и$$\varphi (x_k^*, t_k) - f(x^*) < \varepsilon .$$
Поскольку $$\varepsilon$$ может быть выбрано произвольно
малым, всегда можно найти такое значение k, при котором$$f(x^*) < \varphi (x_k^*,r_k) < f(x^*) + \varepsilon$$
Таким образом, при $$k \rightarrow \infty \; (r_k \rightarrow 0)$$$$\lim_{r_k \rightarrow 0} \varphi(x_k^*,r_k)=f(x^*).$$
Из приведенного выше доказательства следует, что при $$r_k \rightarrow 0$$$$f(x_k^*) \rightarrow f(x^*) \quad \text{и} \quad r_k \sum_{j=1}^m \frac{1}{c_j(x_k^*)} \rightarrow 0.$$
В качестве упражнения оставлено доказательство того, что $$f(х^*_1), f(х^*_2), \ldots, f(x^*_3)$$ образуют убывающую последовательность, такую, что$$f(x_{k+1}^*) < f(x_k^*).$$
Очевидно, что если функция f(х) выпукла, а
функция cj(х) при j = 1,...,n вогнута, то функция f(х) при наличии ограничении имеет единственный
минимум.
Результаты предыдущего раздела показывают, что можно решить
задачу минимизации с ограничениями (минимизировать функцию f(х) при ограничениях $$c_j(x) \ge 0$$, решая для последовательности значений r, стремящейся к нулю, задач без ограничений
следующего вида:$$\text{минимизировать функцию} \quad
\varphi(x,r) = f(x) + к \sum_{j=1}^m \frac{1}{c_j(x)} .$$
х*(r),
предел которой при $$r \rightarrow 0$$ можно исследовать.
Поэтому для того, чтобы можно было применить настоящий метод на
практике, необходимо построить вычислительный метод, использующий
теоретическое свойство сходимости, рассмотренное в предыдущем разделе.
Теоретически здесь не возникает трудностей. Для заданных функцией f(х) ограничениях $$с_j(х) \ge 0, j = 1,\ldots, n$$,
необходимо выбрать начальное значение r = r0,
чтобы сформировать функцию $$\varphi(х, r_0)$$, которая
минимизируется без ограничений методом ДФП. Найдя минимум функции $$\varphi(х, r_0)$$, необходимо уменьшить значение r. Это можно сделать эффективно и просто, если найти r1 = r0/c, где константа с > 1. Затем необходимо минимизировать функцию $$\varphi(х, r_k)$$, снова используя метод ДФП. Таким
образом, будет разработана итерационная процедура.
На k -м шаге минимизируется функция $$\varphi(х, r_k)$$, минимум которой находится в точке $$х^*_k$$. Важно, что ее можно использовать в дальнейшем
в качестве первой точки в итерационной процедуре минимизации функции $$\varphi(х, г_{k-1})$$, где rk+1 = гk/с. Теперь ясно, что
последовательность rk убывает и стремится к
нулю, следовательно, последовательность точек минимумов будет
сходиться к решению задачи с ограничениями.
Ниже приведена блок-схема (рис. 13.1)
Предполагается, что в начале процедуры имеется допустимая точка.
Важно, чтобы в процессе последующих вычислений получаемые точки
принадлежали x к
границе внутри x к границе снаружи
Таким образом, если поиск осуществляется вдоль прямой,
соединяющей две точки, одна из которых лежит внутри, а другая
вне области ограничений, то кубическая интерполяция оказывается
неприемлемой, поскольку функция разрывна вдоль данной прямой.
Действительно, если минимум будет найден вне
(рис 13.1) Выбор начального значения r может оказаться важным
с точки зрения сокращения числа итераций при минимизации функции $$\varphi (х, r)$$. Если сначала r выбрано очень
малым, для того чтобы функция $$\varphi (х, r)$$ мало
отличалась от функции f(x), то метод будет сходиться
очень быстро. Однако такой выбор может привести к серьезным
осложнениям при вычислениях. Для малых r функция $$\varphi (х, r)$$ будет быстро меняться в окрестности
минимума, что может вызвать затруднения при использовании градиентного
метода. Слишком же большое значение r может привести к
тому, что штрафная функция Р(х) в уравнении (1.4) станет
доминирующей. Поэтому "разумный" выбор начальной точки очень
важен. Для многих задач "разумным" значением для начальной
точки является значение r0 = 1. Более
рациональный подход состоит в том, чтобы понять, что если начальная
точка x будет лежать вблизи минимума функции$$\varphi(x,r)=f(x)+r \sum_{j=1}^m \frac{1}{c_j(x)} =f(x)+rP(x),$$
то
Это начальное значение r, как предполагает Фиакко
и Маккормик, должно давать хорошие результаты в общем случае.
Уменьшить значение r очень простo: rk+1 = rk/с, где с = 10.
Для минимизации функции $$\varphi (x,r_{k+})$$
используется метод ДФП. В качестве начальной точки используется
оптимальная точка функции $$\varphi (x,r_{r})$$, и это
оказывается очень эффективным. Oднако необходимо обратить внимание
на то, чтобы в процессе одномерного поиска не выйти за область
ограничений. Грубым, но вполне эффективным является следующий
метод. Пусть имеются точка p и направление поиска d=-Hg. Следующая точка $$q=р+\lambda d$$ необходима для осуществления
кубической интерполяции. Начнем со значения $$\lambda =2$$ (удвоенный шаг в q допустимой, т.е.
выполняется ли неравенство сj(q) > 0
для всех j. Если оно выполняется, то $$\lambda$$ не меняется, но если неравенство не
выполняется, то $$\lambda$$ заменяется на $$\lambda /\alpha$$ находится новая точка q и вновь производится проверка. В конце концов
допустимая точка q будет найдена, и тогда можно
осуществить интерполяцию. Выбор значения $$\alpha$$
не вполне очевиден. Выбор $$\alpha =2$$ был успешным,
при $$\alpha =1,05$$ длина шага становится близкой к
расстоянию до ближайшей границы области ограничений и поэтому
является "безопасной" для интерполяционной процедуры.
Важно не дать точкам выйти за область ограничений в процессе минимизации.
Функция $$\varphi (х,r)$$ минимизируется до тех пор,
пока два последовательных значения F1 и F2 не станут такими, что |(F1–F2)/F1|<0,000001.
Это условие, конечно, может быть изменено. В соответствии с
соотношением (1.17) процесс минимизации заканчивается, когда$$r \sum_{j=1}^m \frac{1}{c_j (x_k^*)} < 0,000001 .$$
Если ограничения в задаче имеют вид чистых неравенств, т.е.$$a_i < g_i (\overline{X}) < b_i , \quad i=\overline{1,m} ,$$ то присоединенная функция может быть построена в виде так называемого барьера:$$G(\overline{X}) = \sum_{i=1}^m \frac{1}{(b_i - g_i (\overline{X}))(g_i(\overline{X})-a_i)} .$$
Как только одна из функций $$g_i(\overline{X})$$ достигнет
своего предела ( ai или bi ),
штраф $$G(\overline{X})) \rightarrow \infty$$, т.е.
возникнет т.н. "барьер".
Метод был предложен Кэрролом, и получил название
При этом 10-5 ).
Рассмотрим действие данного метода на примере задачи оптимального проектирования контейнера.
Пусть требуется спроектировать контейнер в форме прямоугольного
параллелепипеда объемом V=1м3. Желательно,
чтобы при изготовлении контейнеров затрачивалось как можно меньше
материалов. Чтобы его было удобно брать автопогрузчиком, ширина
должна быть не менее 1,5 м.
Строим математическую модель контейнера.
1) Формируем вектор переменных $$\overline{X}$$.
Параметрами вектора переменных являются: длина x1, ширина x2
и высота x3 контейнера, т.е.$$\overline{X} = [x_1,x_2,x_3].$$
Размерность задачи n=3.
2) Строим
Тогда$$F(\overline{X}) = S(\overline{X}) = 2(x_1 x_2 + x_2 x_3 + x_1 x_3).$$
3) Формируем ограничения.
Ограничение-равенство:$$\text{Объем } V = x_1 \cdot x_2 \cdot x_3 = 1\text{м}^2 .$$ Ограничение-неравенство:$$\text{Ширина } x_2 \ge 1,5 \text{м}.$$
Упростим математическую модель контейнера. Ограничение – равенство (3.3) в задаче, благодаря своей простоте, позволяет уменьшить размерность задачи, т.е.
x3 = 1/x1x2 .
В результате параметр x3 можно исключить
из вектора проектных параметров, и из трехмерной задачи мы получим
двумерную. Тогда вектор $$\overline{X}$$ будет иметь вид:$$\overline{X}=[x_1,x_2].$$
В результате, задача проектирования контейнера может быть сформулирована следующим образом:
Найти вектор $$\overline{X} = [x_1, x_2]$$, доставляющий
минимум
В данной задаче
Как только один из параметров x1 или x2 достигнет своего предела, штраф $$G(\overline{X}) \rightarrow \infty$$, т.е. возникнет
т.н. "барьер".
Штрафная функция в задаче проектирования контейнера будет иметь вид:$$P(\overline{X},RC)=F(\overline{X})+RC \cdot G(\overline{X}) = 2 \left( x_1 \cdot x_2 + \frac{1}{x_1} + \frac{1}{x_2} \right) + RC \left( \frac{1}{x_1 - 1,5} + \frac{1}{x_2} \right).$$
Для нахождения минимума этой штрафной функции (задача двумерная) может быть использован метод многомерной оптимизации.
Задачи
Пример.
Найти вектор $$\overline{X}=[x_1,x_2]$$, доставляющий минимум$$F(\overline{X}) = x_1^2 + x_2 ,$$ при ограничениях$$\begin{gathered} g_1(\overline{X}) \rightarrow -(x_1^2 + x_2^2) + 9 \ge 0, \\ g_2(\overline{X}) \rightarrow -x_1 - x_2 + 1 \ge 0. \end{gathered}$$
Строим область допустимых решений $$G$$. Для этого преобразуем ограничения.
Ограничение $$g_1(\overline{X})$$ будет иметь вид:$$x_1^2 + x_2^2 \le 9.$$
Тогда ограничение $$g_1(\overline{X})$$ отсекает на
плоскости круг радиусом r=3.
Ограничение $$g_2(\overline{X})$$ будет иметь вид:$$x_1 + x_2 \le 1 .$$
Тогда ограничение $$g_2(\overline{X})$$ отсекает на
плоскости полуплоскость, ограниченную уравнением x1+x2=1.
В результате область допустимых решений G будет
иметь вид, представленный на
рис 13.2.
Строим [x1,x2] для которых
Меняя значения C, получим различные линии уровня.$$\begin{aligned}
\text{Если } C=\phantom{-}0, \; \text{то} \; x_2 = -x_1^2, \\
C=-1, \; \text{то} \; x_2 = -1 -x_1^2, \\
C=-2, \; \text{то} \; x_2 = -2 -x_1^2, \\
C=-3, \; \text{то} \; x_2 = -3 -x_1^2.
\end{aligned}$$
Как видно, x2.
Положение каждой параболы зависит от значения константы C (рис 13.2.).
Исследуя полученные линии уровня получим что G, в точке с координатами [0,-3].
(рис 13.2)
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.