Определение длины шага в методе возможных направлений

Лекция №14

Определение длины шага в методе возможных направлений

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

Эту задачу удобно решать в два этапа:

1. На первом этапе определим число . То есть определим значение , при котором луч пересекает границу допустимой области R. Это достигается нахождением корней уравнений

и выбором из них наименьшего положительного.

2. Далее выбираем число .

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

Таким образом, длина шага, выполняемого из точки в выбранном направлении , устанавливается по правилу .

Оценка погрешности приближенного решения

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

Как оценить близость полученной точки к неизвестному решению исходной задачи

,

где .

Алгоритм такого оценивания вытекает из следующей теоремы.

Теорема 14.1. Для любой точки и любой функциивыпуклой на выпуклом множестве R справедливо неравенство

, ( 14.1 )

где

.

Д о к а з а т е л ь с т в о. Воспользуемся теоремой (12.5), в силу которой для любой пары точек и выпуклой функции имеет место неравенство или . Таким образом, можно утверждать, что для любой точки справедлива цепочка соотношений :

.

С другой стороны, для любой точки выполняются условия :

, и

или . Тогда, если вместо ограничений исходной задачи использовать в качестве ограничений только что полученные неравенства, то мы будем иметь «более пухлое множество», содержащее в себе. Но тогда

.

Обозначая , получим

.

Теорема 14.1 доказана.

З а м е ч а н и е. Очевиден геометрический смысл доказанной теоремы. Её можно рассматривать как теорему об аппроксимации. А именно, на основании этой теоремы можно утверждать, что если мы начинаем итерационный процесс в допустимой точке , то наибольшее уменьшение минимизируемой функции не может быть больше уменьшения минимизируемой функции в линеаризованной задаче.

Линеаризованную задачу получаем заменой минимизации функции

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

В заключении проиллюстрируем описанный метод возможных направлений на примере.

Пример 14.1. Решить задачу выпуклого программирования

где

,

Выполним одну итерацию рассмотренного метода возможных направлений. В качестве начального приближения выберем точку =(2;0).

Определим индексные множества активных ограничений в точке :

=;

.

Поставим задачу выбора наилучшего подходящего направления в точке Х0 как задачу линейного программирования с нормализацией №3:

.

Здесь - искомый вектор; - вспомогательная переменная; - градиенты соответствующих функций в точке , то есть векторы

.

Итак, имеем задачу в виде

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

Далее, для приведения задачи к канонической форме, введём дополнительные переменные, заменяя величину с неопределённым знаком на разность двух неотрицательных переменных и преобразуем ограничения типа неравенств в ограничения- равенства. В результате этих действий наша ЗЛП запишется так:

Дальнейший процесс решения ЗЛП отражён в следующих симплекс-таблицах:

			С	0	0	1	-1	0	0
N	C	P	B	A1	A2	A3	A4	A5	A6	t
1	0	A5	12	6	6	1	-1	1	0	12
2	0	A6	1	0	1	1	-1	0	1	1
			0	0	0	-1	1	0	0
1	0	A5	11	6	5	0	0	1	-1
2	1	A3	1	0	1	1	-1	0	1
			1	0	1	0	0	0	1

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

Таким образом, в результате решения задачи выбора в точке Х0=(2;0) подходящего направления найден вектор S0=(1;1). Построим луч, исходящий из точки Х0 по направлению найденного вектора :

Определим длину шага в этом направлении.

Для этого найдём вначале то значение , при котором луч пересекает границу допустимой области R. То есть найдём положительные корни уравнений

,

а именно, уравнений

,

или . Отсюда найдутся корни

.

Таким образом, величина . Далее, определим значение , при котором функция достигает минимума по . Для этого приравняем к нулю производную этой функции по и найдём корень полученного уравнения:

Отсюда получим, что . Следовательно, искомое значение длины шага . Завершая итерацию, находим новую точку.

Первая итерация полностью выполнена.

Контрольные вопросы

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

2. Из какого условия вычисляется наибольшее значение длины шага?

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

4. Какое число окончательно выбирается в качестве длины шага?

5. С какой целью рассматривается задача оценивания погрешности приближённого решения ЗВП методом возможных направлений?

6. Какой алгоритм оценивания погрешности приближённого решения ЗВП можно предложить на основании доказанной аппроксимационной теоремы?

7. Поясните геометрический смысл аппроксимационной теоремы.

8. Как осуществляется линеаризация исходной задачи при формировании задачи оценивания погрешности приближённого решения ЗВП методом возможных направлений?

9. Остаётся ли справедливым неравенство ( 14.1) , если точка окажется точкой минимума функции в допустимой области R?

PAGE 151

Определение длины шага в методе возможных направлений