Математические основы 3D оптимизации трасс линейных сооружений

Разложение проекции градиента на нуль - пространство матрицы активных ограничений по специально подобранному базису, что многократно использовалось при проектировании продольного профиля, имеет простой геометрический смысл. Любое изменение проектной линии, сохраняющее предельные значения уклонов и разностей уклонов смежных элементов на некотором участке независимого построения проекции, можно представить как комбинацию элементарных движений: сдвиг вдоль оси ординат и повороты участков проектной линии как единого целого с центрами в нужных точках. Особенно удачным оказывается выбор в качестве центров вращения точек, на ординаты которых наложены высотные ограничения, если эти ограничения выполнены как равенства.

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

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

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

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

Рассмотрим ограничения на план трассы при его представлении в виде ломаной линии, составленной из коротких элементов (см. разд. 3.2.2).

Ограничения на координаты отдельных точек плана трассы на поперечниках вида Cj

Пусть на некоторой итерации точки с i-ой по (i+m)-yio лежат на кривой предельного радиуса (рис. 11.1). Её начальное положение АВ. Необходимо найти такие изменения переменных щ , ui+) , ..., ui+m, при которых радиус остаётся предельным. Это означает, что окружность смещается как единое целое и любое её смещение можно представить как комбинацию двух смещений, например, сдвиг вдоль некоторой прямой и поворот в плоскости вокруг некоторого центра. В качестве прямой можно взять любой поперечник с номером i < k < i+m, а за центр вращения принять точку пересечения плана трассы и выбранного поперечника. На рис. 11.1 это точка М на поперечнике с номером г. Пусть а - величина смещения окружности вдоль поперечника, а ср-угол поворота. Если величины а и ср известны, то приращения Auk (i < k < i+m) вычисляются через a, tp, углы поперечников с осью ОХ и исходные значения Uk(i < k < i+m).

Если на окружности оказалась одна точка, у которой координата Uj имеет минимальное или максимальное значение (далее такие точки называются фиксированными), то её следует принять за центр вращения, а соответствующий j-ый поперечник за линию сдвига. В этом случае а=0, и все искомые смещения по поперечникам определяются углом поворота.

Пример базисного смещения (сдвиг + поворот)

Рис. 11.1. Пример базисного смещения (сдвиг + поворот).

Если на окружности предельного радиуса оказалось две или более фиксированных точек, то искомые смещения или приращения координат Аш (i < k < i+m) равны нулю.

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

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

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

Примеры базисных смещений при отсутствии фиксированных точек

Рис. 11.2. Примеры базисных смещений при отсутствии фиксированных точек

Общее число «степеней свободы», а, следовательно, и базисных смещений равно П1-п2+1,где щ-число кривых (дуг окружностей), которые нельзя рассматривать независимо, п2- число фиксированных точек, причём на каждой кривой не более одной фиксированной точки.

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

1. При отсутствии фиксированных точек. На первой кривой предельного радиуса (рис. 11.2 а) смещается первая точка вдоль соответствующего поперечника, а смещения остальных точек определяются так, чтобы в конечной точке кривой и за её пределами смещение было равно нулю. Фактически это поворот первой кривой с центром в её конечной точке.

На второй и всех следующих кривых, кроме последней, смещается начальная точка вдоль соответствующего поперечника, а смещения остальных точек определяются так, чтобы в крайних точках двух смежных кривых и за их пределами они были равны нулю (рис. 11.2 б, в). Это соответствует поворотам двух смежных кривых при условии равенства смещения точки их сопряжения по поперечнику в каждом из поворотов.

Базисные смещения при наличии фиксированных точек

Рис. 11.3 Базисные смещения при наличии фиксированных точек

На последней кривой смещается конечная точка вдоль поперечника, а смещения всех остальных точек определяются так, чтобы начальная точка кривой и все точки за её пределами были неподвижны (рис. 11.2 г).

168

2. При наличии фиксированных точек. На первой из кривых, содержащей фиксированную точку, смещается первая нефиксированная граничная точка, а остальные точки смещаются так, чтобы фиксированная точка имела нулевое смещение (рис. 11.3). Если на смежных (с двух сторон) кривых нет фиксированных точек, то смещения их концов равны нулю, а если есть фиксированная точка, то её смещение равно нулю и процесс продолжается (в обе стороны) пока не встретится кривая, на которой нет фиксированной точки (рис.11.3 а), или конец участка (рис. 11.3 б, в).

При отсутствии фиксированных точек базисное смещение захватывает не более двух смежных кривых. А при наличии фиксированных точек базисное смещение может захватывать много кривых. В любом случае построение базисного смещения начинается со смещения одной точки по “своему” поперечнику; такие точки будем называть порождающими, так как смещения всех остальных вычисляются через это начальное смещение. В примерах на рис. 11.3 во всех случаях порождающей точкой было начало первой кривой, но базисные смещения были различны из-за фиксированных точек. Вообще порождающими точками являются концы участков предельной кривизны, но каждая фиксированная точка “убивает” одну порождающую точку. Число базисных смещений равно числу порождающих точек, и все эти смещения независимы в том смысле, что ни одно из них нельзя представить как комбинацию остальных. Действительно, если точка порождает базисное смещение, то при смещениях, порождаемых остальными точками, её смещение равно нулю. Зная смещения порождающих точек, можно вычислить и смещения всех остальных точек, так как в пределах каждой окружности предельного радиуса оказываются известными координаты двух точек:

  • - первая точка неподвижна. Это фиксированная точка (если она есть на данной окружности) или одна из крайних точек, если фиксированной точки нет;
  • - вторая точка имеет заданное смещение. Это порождающая точка, либо начальная (конечная), если смещение передаётся от смежной окружности, содержащей фиксированную точку.

Сначала определяются координаты этих двух точек на поперечниках (“плановые” координаты щ), а затем с использованием координат начала поперечника и его ориентации вычисляются их декартовы координаты. По координатам двух точек и радиусу определяются координаты центра окружности и далее координаты её пересечения с поперечниками. Так вычисляются базисные смещения, которые являются аналогами базисных векторов в случае линейных ограничений.

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

Если взять линейную часть приращения координаты щ каждой точки на соответствующем поперечнике как функцию от смещения порождающей точки, то получим базисное смещение (вектор) в касательной плоскости. Таких векторов будет столько, сколько порождающих точек. Фактически каждый базисный вектор имеет своими компонентами частные производные соответствующего смещения по смещению порождающей точки. Учитывая, что смещение порождающей точки равно нулю при смещениях других порождающих точек, получаем систему линейно независимых векторов. Поэтому их можно принять за базис в подпространстве параллельном касательной плоскости. Таким образом получаем базисную матрицу С, столбцы которой есть базисные векторы. Каждый вектор - это “линеаризованное ” базисное смещение и его j-ая компонента есть частная производная смещения j-ой точки по смещению соответствующей порождающей точки. Количество столбцов равно числу порождающих точек. Если из матрицы С вычеркнуть строки, соответствующие непорождающим точкам, то получится единичная матрица.

Формально описанные действия можно выразить следующим образом:

  • 1. Имеем граничную поверхность М, определяемую набором активных ограничений, которые должны рассматриваться совместно (предполагается, что дальнейшая декомпозиция невозможна).
  • 2. Координаты точки ueМ обозначим ub и2,..., um. Здесь ш- число поперечников, включённых в рассматриваемый участок, смещения которого можно определять независимо от других участков. Другими словами, вместо исходного пространства Rn рассматривается подпространство RmcRn ив нём поверхность М с Rm.
  • 3. Определяем число «степеней свободы» к и соответственно к порождающих точек. Их смещения (приращения координат на поперечниках) образуют вектор up (upi, up2, .. .,uPk).
  • 4. Для всех lT с компонентами

г = dsiJ I »

UlJ QUjP |u;p =0, где Sjj - функция, определяющая смещение вдоль

j-ro поперечника (j=l,2,...,m) при смещении i-ой порождающей точки (i=l,2,...,k) равном единице. Производные вычисляются в текущей итерационной точке Q, то есть при нулевом смещении порождающей точке. Касательную плоскость к граничной поверхности М в точке Q обозначим через Р. Если взять параллельную ей плоскость Р, проходящую через нуль, то в плоскости Р векторы с; образуют базис и соответственно базисную матрицу С размерностью mxk.

Соответственно р - вектор смещения в Р, представляет собой линейную комбинацию базисных векторов с коэффициентами ир.

Другими словами, вектор смещения р представлен координатами щр в базисе С; (i=l,2,...,k).

Если исходной точке QeM соответствует вектор и0, то новой итерационной точке (после смещения) будет соответствовать вектор u1= и°+Хр в касательной плоскости. Здесь Х>0- шаг по направлению р. Но если мы используем коэффициенты при смещениях порождающих точек для реализации базисных смещений, то есть будем вычислять приращения координат на поперечниках без линеаризации соответствующих функций, то получим новую точку на граничной поверхности М.

Если мы хотим, чтобы вектор смещения р был улучшающим направлением, то в качестве такого вектора можно взять проекцию антиградиента - f целевой функции на плоскость Р. Это означает, что вектор - f - р ортогонален любому вектору v € Р. Этот любой вектор представляется координатами Vi (i=l,2,...,k) в базисе Cj, то есть

Условие ортогональности есть равенство нулю скалярного произведения (-f-p,v)=0. Подставляя в это равенство представление векторов р и v (11.1 и 11.2), получим

Это равенство должно выполняться при произвольных v; (i=l,2,...,k), что даёт систему линейных уравнений для определения up(i=l,2,...,k).

Иначе.

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

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

Определив смещения порождающих точек ир, находим смещения всех

остальных точек, порождённые смещениями UjP (i=l,2,___,k). Для этого

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

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

Итак, вернёмся к старой замене и -и0 = Су +Вх, где и0- текущая итерационная точка, и- новая точка, так что и -и0 - смещение. С и В- базисные матрицы соответственно в подпространстве, которому принадлежит направление спуска, и в его дополнении. Число переменных на участке независимого определения направления спуска обозначаем через п, а число активных ограничений через ш. При этом предполагается, что поиск улучшающих смещений нельзя вести по отдельным группам переменных. Другими словами, возможная декомпозиция предполагается выполненной. Активные ограничения определяют многообразие (поверхность) М с Rn. Предположим, как и ранее, что любое смещение в М из и0 можно представить как комбинацию п-m независимых смещений. Это означает, что в подпространстве, соответствующем касательной плоскости к поверхности М в точке с координатами u°(u°i, u°2, ...,u°n) мы умеем строить базис, то есть матрицу С, которая использовалась ранее.

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

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

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

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

Если исследуется возможность исключения активного ограничения по фиксированной точке, то она объявляется свободной. При этом появляется новая порождающая точка и соответственно новое базисное смещение. Порождающая точка смещается по своему поперечнику в сторону нарушения ограничения в фиксированной точке.

Таким образом, предполагаем, что у нас есть полный набор базисных смещений, в котором первая группа (n-m) смещений сохраняет все активные ограничения, a j-oe смещение из второй группы соответствует движению в многообразии, определяемом оставшимися активными ограничениями, плюс движение по внешней нормали в точке и = и0 к граничной поверхности, соответствующей нарушаемому ограничению. Первой группе смещений соответствует матрица С (n х n-m). А второй группе смещений соответствует матрица В(п х ш). Наше предположение и состоит в том, что соответствующие матрицы С и В известны, то есть в исходном пространстве построен новый базис с заданными свойствами относительно системы активных ограничений.

Градиент в новых переменных (у,х) имеет вид

Здесь f- градиент в исходных переменных. Вектор р, у которого первые n-m компонент образуют вектор Fy, а следующие m компонент нулевые, задаёт движение в касательной плоскости.

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

Тем самым и при наличии нелинейных ограничений знание базисной матрицы С позволяет осуществить улучшающее смещение без решения системы линейных уравнений.

Посмотрим теперь, как решается вопрос об исключении ограничений из активного набора.

Систему активных ограничений запишем в виде Si(u)0)=Si°.

После линеаризации всех нелинейных ограничений в точке и°, то есть разложением функций Sj(u) в ряд Тейлора, в котором оставлен только линейный член, получим линейную систему

В матричном представлении она имеет вид A(u-u°)<0. После замены переменных и -и° = Су +Вх получим АСу +АВх<0. Если матрицы С и В выбраны так, что АС=0 и AB=D, где D- диагональная матрица, то далее поступаем как и в линейном случае (см. разд. 5).

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

Рассмотрим теперь случай дополнительных нелинейных ограничений, которые мы не можем учесть при построении базиса. Пусть эти ограничения имеют вид ti(u)

Теперь уже вектор, у которого первые n-m компонент образуют вектор -Fy, а следующие m компонент нулевые, нельзя использовать для построения базисных смещений, так как могут нарушаться дополнительные ограничения. Необходимо спроектировать его на плоскость AiCy +AiBx=0 , без нарушения ограничений.

Далее можно полностью повторить рассуждения разд. 5 , как при поиске направления спуска, так и при исключении ограничений из активного набора (основных и дополнительных).

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

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

В линейном случае шаг до границы вычислялся аналитически путём подстановки координат вектора спуска в соответствующие равенства и решения линейного уравнения для каждого неактивного ограничения, которое могло быть нарушено при использовании данного направления спуска. Из найденных величин шага выбиралась наименьшая Х^щ. Затем на интервале (О, Х,™) определялась величина шага, при которой целевая функция принимала минимальное значение. Для этого решалась одномерная задача оптимизации.

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

Имеется несколько возможностей преодоления возникающих трудностей.

1.Для поиска шага до границы действовать аналогично линейному случаю, но с учётом нелинейности неактивных ограничений. Для этого осуществляем все базисные смещения, принимая компоненты вектора Fy за смещения порождающих точек. Это соответствует шагу Х)=1. Заметим, что необходимо исследовать все базисные смещения, а не только те базисные смещения, которые могут нарушить рассматриваемое неактивное ограничение, так как может происходить компенсация нарушений при различных смещениях. Например, при ограничениях по фиксированным точкам базисные смещения на конкретном поперечнике могут давать сдвиги в разных направлениях. Очевидно, имеет смысл рассматривать не все активные ограничения, а только те, которые могут быть нарушены при базисных смещениях. Так, при ограничениях по кривизне и по фиксированным точкам достаточно рассматривать фиксированные точки в пределах участка, смещения которых по поперечникам ещё не приняли предельных значений, ограничения по кривизне на смещаемых концах кривых, в том числе в начальной и конечной точках участка, а также в точках, в которых активные ограничения по кривизне исключены при построении базисных смещений. Последние точки необходимо рассматривать, так как не исключено, что кривизна в них может получить новое предельное значение с обратным знаком.

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

Если ни одно из активных ограничений не нарушено, то можно увеличить шаг. Например, взять A,2=2Xi, умножить смещения всех порождающих точек на новое значение X, и повторить этот пункт заново. И так до тех пор пока не получим нарушение неактивных ограничений.

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

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

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

2. Вторая возможность состоит в том, чтобы действовать по базисным направлениям отдельно, не вычисляя общего значения шага по направлению. Это является аналогом покоординатного спуска [1].

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

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

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

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

В общем случае это утверждать нельзя, поскольку скорость сходимости соответствующих итерационных алгоритмов существенно зависит от особенностей целевой функции. Используя новый базис, мы существенно проще получаем направление спуска, чем при поиске проекции градиента, и объём вычислений на каждой итерации существенно снижается, особенно при наличии ограничений, не учтённых при построении базиса. Это направление спуска составляет острый угол с проекцией антиградиента, но весь вопрос состоит в том, улучшает ли сходимость алгоритма наличие этого угла. Здесь всё зависит от свойств целевой функции. Более того, в сложных случаях приходится применять комбинацию различных алгоритмов [21].

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >