28
- Тымеладзе
Нелинейное программрование
Земля! Земля!
Густая мгла тропического почи обволокла островов, но люди, почувствовав под ногами твердую почву, поверили в спасение. Поверили впервые за неделю, прошедшую с тех пор, как смыло за борт бочонки с водой, впервые за те тринадцать суток, что прошли после кораблекрушения.
— Пить! — бормотали переохшие губы, когда група отошла подальше от моря вглубь острова. Никаких припасов не осталось — только бесполезные судовые приборы ташили они с собой, словно не решаясь расстаться с этой последней реликвей с затонувшего судна.
— На острове должа была вода. Утром мы зайемся ее понским.
— Боюсь,кое для кого к утру будет уже поздно,— через силу произнес Зейдель. — Искать нужно сейчас. Внизне должен быть ручей.
— Но как мы доберемся до низины? У нас нет ничего, кроме нескольких слабых фонарей, которые хватит ненадолго, а тьма такая, что я не вижу собственной руки, — устало возразил Коши. — Вот если мы можно было подняться над местностью на воздушном шаре и осветить ее…
— Воздуший шар? — хрипло воскликнул Растригин. — Проjekто-
Рис. 1.
29
bot и он. Давайте действовать так: сначала установим уровень, ориентируя его с запада на восток, — он показывает снижение местности к востоку, видите? Пойдем на восток до тех пор, пока местность будет понжаться, как нам любезно подсказал господин Ферма. А doitя до этой точки, снова приложим уровень к земле, но уже в направлении с юга на север. Допустим он указыва на снижение местности к северу. Тогда отправимся на север и будем идти, пока местность будет понжаться. Так мы будем сворчивать до тех пор, пока не придет в низую точку. В ней уровень будет горизонтален, как его ни поверни. Не так ли?
— Я думаю, сын мой, вы правы, и через час мы уже будем здесь с полнымми фляжками,—ответил Гауссс, и она побрел к востоку, захватив с собой компас и один из уровней. Ферма отправился за ним.
— Они правы, правы, — приготовивал деятельности Коши, нетерпеливо поглядывая на другой уровень, — но не во всем. Гауссс и Зейдель отправились на восток. И действительно, местность понжается к востоку. Но понжается слабо. Смотите, сльнее всего снижение проискодит в направлении на северовосток. Может, туда и стоит отпавиться? Пожалуйста, я так и сделаю. Пройду несколько шагов и снова проверю, в каком направлении нужно спускаться, и снова сделаю несколько шагов. Где моя фляжка? Ах, вот она. Минут через сорок она уже будет полна!
— Месь! Кажется, можно прийти к цели и проше! — крикнул ему всед Канторович, с трудом раскрывая пересохшие губы. — Вам не следует оставываться через несколько шагов. Последуйте лучшие советы господина Ферма и идите до тех пор по выбранному направлению, пока местность снижения. На уменьшении числа промеров вы изрядно экономите время!
No энергичного Коши уже поглощила мгла, и Канторович был вынужден поспешить с фляжкой за ним.
— Ну как? Догнал он его? — зачем-то спросил Иномата.
— Куда там! — возразил ему со вздохом Кумада, который в этот момент возникся с глобусом, снимая его с оси. — Им уже не встретиться. Они могли бы уже здесь сказыть друг другу «до свидания». Ну что, двинулись и мы, Иномата-сан?
— Конечно! Зачем нам уровень, а тем паче компас? Вот этот шар доведет нас до цели. Пусть он свободно катится, а мы просто поддем вслед. Ведь шар сканится в самую низкую точку.
И оба скрылись в темноте, стараясь не упустить шар из виду.
Цетлин утомленно смотрел всед людям, растаяшим в ночи.
— О чем вы думаете? — спросил его Гельфанд, с трудом поднимаясь с земли. — Не о том ли, что Гауссс и Зейдель придут не туда, куда направлялись?
— Вы уgradали. Они собирались найти самую низкую точку, представляя себе местность в виде впадины с гладкими стенками (рис. 2). Но судьба может сыграть с ним злую шутку: им может встретиться
30
на пути овраг. И он быстро начертил на листке из судового журнала ricсунок 3.
— Их счастье, если по дну оврага протекает ручей. А если родник в самой низкой точке?
— Да, тогда судьбе Гаусса и Зейделя не позавидешь: идея на восток, они придут в точку А — это самое низкое место на их пути. А в направлении север — юг самая низкая точка — это снова точка А. Таким образом, бедняги придут к выводу, что А — самая низкая точка на местности и умугт в ней от жажды.
— Но может быть, их спасет фляжка Коши?
— Боюсь, что и фляга Коши останется пустой, если он встретился с оврагом. Оказавшись у дня оврага, он будет искать направление самого кругого спуска, и оно неизбежно приведет его в точку по другую сторону оврага. Из этой точки он вернется на прежнюю сторону и дальше пойдет небольшими шажками до тех пор, пока жажда не свалит его. Ведь весь овраг он увидеть не может — его фонарь способен осветить местность лишь у самых ног. Нado придуть что-нибудь другое…
— А что если Канторович достигнет целли? Хотя не думало: если овраг искривлен, а овраги редко бывают прямыми, то он начинает metastасу по дну оврага, почти не приближаясь к целли. Нado страться дивигаться по дну оврага.
— Разумеется, но как? Впрочем… каждется, придумал. Посмотрит на рисунок 4. Давайте мы оба, вы и я, подем из двух разных точек методом Канторовича. Скажем, я отсюда, а вы — отойдя шагов на стою в любом направлении.
— Понятно, а дальше? Ага, дальше мы оба спустимся на дно оврага и поставаемся увидеть фонари друг друга. Допустим, нам это удостся. Тот из нас, чей фонарь выше, дивнется по направлению к тому, чей фонарь ниже.
— Но встретились, не останоится, аройдет дальше в том же направлении до точки D. Из этой точки он снова спустимся на дно оврага, и мы опять попытаемся увидеть друг друга. И так до тех пор, пока уровень на дне оврага не указывает горизонтальной участок.
И, выбрав фонари поприметнее, оба отправились каждый своим путем.
— А вы, я вижу, не торопитесь к влаге? — спросил Растригина Винер. — Иначе почему бы вам не воспользоваться одним из весыма ра-
Рис. 3.
Рис. 4.
31
зумных способов, которые предложили наши друзья по несчастью?
— У всех этих способов один недостаток — слишком много приходится возиться с уровнем, пока найдешь нужное направление. А что если почти по какому-либо направлению научад, пока оно ведет на спуск? Потом изменить направление и снова спускаться по нему. Изменить, разумется, тоже научад. Разве таким образом я не приду к целю? Стоит ли терять время на отыскание направления наскорейшего спуска, если уже через несколько шагов оно перестает им быть?
И не успел Винер возразить или согласиться, как Растригин закрыл глаза, повернулся несколько раз на месте, как делают при игре в жмурки, и отправился в темноту.
Методы спуска
Необходимость найти максимум или минимум (объединяемых названем «экстремум» — «крайнее значение») некоторой функции возникает во многих задачах экономики и техники. А местность можно считать макетом функции двух переменных, скажем широты и долготы. Значение функции — это высота местности (над уровнем моря) в данной точке, горизонтали — линни уровня, вдоль них функция постоянна. И ситуация, возникающая при поиске экстремума, во многом сходна с той, в которой оказывается неудачливые путешественики. Поиск экстремума производит как бы в темноте, единственным средством ориентации служебная минимизируемой (максимизируемой) функции в какой-то точке, а также направления ее наскорейшего убывания или возрастания.
Придумано уже немало методов отыскания экстремума. Не случайно, как заметил читатель, фамилии потеревших кораблекрушение совпадют с фамилиями ряда математиков прошло и настоящего, которые решали эту проблему. А путь, который они отправились, показывает сущесть их методов отыскания экстремума.
Великий француз П. Ферма (1601—1665) первый ясно осознал и сумел описать аналитические свойства экстремума гладкой непрерывной функции: касательная в этом месте должна быть горизонтальна. К. Гаусс (1777—1855) и А. Зейдель (1821—1896), следуя своему методу покоординатного спуска, по очереди спускались то вдоль одной, то вдоль другой координаты. Спускались до тех пор, пока касательная к направлению движения не станет горизонтальной. А положение уровня естественно определяет направление касательной.
Обратите внимание на то, что Гаусс и Зейдель не стремились спускаться по тому направлению, где кругизна больше всего. К этой идеерывым приSEL О. Коши (1789—1857). Вектор, указывающий направление (вверх) с наиболее крупизной, называется граденом, а сам метод Коши — граденным методом. Именно по градиенту стал бы прокладывать свой путь Коши, если бы его цель была смая высокая точка местности, чтобы осмотреть. Но вспомним, что на острове стояла мгла кромешная и целью Коши была вода. Поэтому он отправился по направлению наскорейшего убывания высоты местности, или по направлению антиградиента. Для определения антиградиента функции существенно и приближенные методы, но нам достаточно представить себе уровень, который мы прикладываем к земле и разыскиваем то направление, при котором воздушный пузырек быстрое всего убегает к краю шкалы. Конечно, способ этот весыма неточен, да и морки с ним немало. Но и для определения градиента с помощью упомянутых аналитических методов тоже приходится повозиться.
А потому нетрудно понять наших современников, японцев
32
С. Иномату и М. Кумаду, которые попытались придать процессу спуска по антиградиенту вышеописанный физический смысл. Между прочим, их метод так и называют «метод мягкого шарика». Только размещется, при его использовании некатают глобус по макету функции, а лишь решают дифференциальные уравнения движения.
Немало трудностей ждет того, кто цветет экстремум функции, но одна из самых коварных — это овраги. Любой из методов, даже наиболее совершенный в вычислительной отчислении метод наскорейшего спуска Л. В. Канторовича, известного советского математика, приводит к беспомощному метанию по дну оврага. Поэтому советские математики И. М. Гельфанд и М. Л. Цетлин и предложили «овражный поиск», который позволяет выследить дну оврага. Итак, как мы видим, почти все численные методы поиска наличищего направления спуска так или иначе связаны с антиградиентом. Правда, оказалось, что труды по отысканию антиградиента не всегда вознаграждаются качеством найденного направления спуска, и советский ученый Л. А. Растригин предложил вообще не траитить сил и машинного времени на поиск антиградиента, а шагать куда себе вздумается, то быш по случайному направлению. И представьте, результаты такого образа действия оказалисьничут не хуже в вычислительной отношении, чем поиск наличиших путей. Иначе говоря, не настоящее эти наличищие пути превоходят по качеству случайный, чтобы стонло траитить время на их понск. Разумеется, чтобы выбрать направление спуска случайным образом, не кругтятся на месте с закрытыми глазами — для этого в машине использовут датчики случайных чисел. И вообще численную сторону методов непленного программирования трудно продемонстрировать на бумаге — это существенно машинные методы.
Но вернемся к потерпевшим кораблекрушение и узнаем, кому из них сопутствовал успех в понске воды.
Там, за перевалом
Итак, все разбрелись в понсках воды, кроме кучки Скелтников.
— Дьявольская жажда! — промолвил один из них. — Нeyжели вас она не мучит?
— Не меняше, чем вас, — ответил Винер от имени остальных. И я охотно движился бы на понски воды, если бы меня убедил какой-то из предложенных способов. Но увы! Если мы начнем таким способом искать высшую точку Земли, то вместе Эвереста окажемся на вершине соседнего холмика. И самое ужасное то, что у нас нет никакого средства отличить этот холмик от Эвереста. Если, конечно, не привлечь на помощь математике обыкновенную географию.
— Как это нет? Почему? —pointerсовался молодой Скелтник, которое скелтрицзм не отучил еще задавать вопросы.
— Очень просто. С помощью фонарика мы способны лишь убедиться, что из данной точки пути ведут визз. А что там, дальше? Вот тут наши
Рис. 5.
33
друзья предложили ряд способов, — сн сисходительно показал на оставшиеся листки из судового журнала. — Они исходили из того, что на острове только одна низина. А если их много, и вода лишь в самой низкой из этих низин (рис. 5)? Спуск приведет нас в точку А, а вода в точке B — там гуше горизонтали и, следовательно, ниже отметка. Задумайтесь над этим.
— Я уже задумывался, — сказал первый Скелтик. — И решил действовать так. Сначала пойдут куда глаза глазят. Потом спушут в близкойшую низину и затем ее высоту высотомером. Запомню ее расположение и перейду в новую случайную точку. Из нее снова спушут в низину и снова взгляну на высотомер. Допустим, он показет на себя раз меньше высоты. Это значит, что вторая низина ниже первой, и там больше шанссов найти воду. Затем…
— Что будет затем, ясно, — перевалил его. — Но уверены ли еще, что найдете воду прежде, чем свалиесь с ног?
— Могу ли я быть в этом уверен? Ведь я же Скелтик! Просто это лучше, чем стоять сложа руки.
И первый Скелтик скрылся в темноте.
Второй Скелтик привязвал в это время шлагат к футбольному мячу, невесты как оказавшемся среди приборов.
— Уж не собирается ли вы по следам Кумады? — спросил его Винер, одновременно к чем-то прислушиваясь.
— Вы почти угадали. Но я поступло несколько иначе. Спустившись в низину, я замерю ее высоту, а затем буду быть по мячу ногой в разных стороны. Если мяч будет каждой раз скатывать назад, значит, пользовости нет перевала, за которым новая низина. Если мяч не скатится ко мне, я отправюсь по шлагату за ним, приду в низину, в которой он застрял, и замерю ее высоту. И так далее…
— Но так можно обнаружить лишь недалекий перевал.
— Что вы! У меня сильный удар. Меня обещно просит ударить отворот.
— В таком случае может произойти еще худшее: вы перебете мяч через низину, которое ищите. Мяч не вернется к вам, но уведет вас от цели.
— Вы правы… Тогда, пожалуйста, я не буду статься каждой раз ударить посильнее. Я буду чередовать сильные и слабые удары. Или, скажем, буду постепенно усиливать их, начав со слабых.
— Что же, я желаю вам успеха. Если наградой вам и не послужит вода, то во всяком случае вы повышитесь ссно спортивную форму.
— А я поступлю иначе, — обратился третий Скелтик к Винеру. — Я отправлюсь просто бродить по строву, не стаясь найти наличище направление, и буду поглядывать на высотомер. Побродив, замечу, где самая низкая точка, и уже там начну понски воды. Все эти разговоры убедили меня, что если у нас нет карты острова, то никакой разумной стратегии движения быть не может. Так зачем же тогда tratить время на возню с приборами? Но вы, кажется, не случайете меня?
Где кончается acфальт
Когда приходится определять экстремум функции, у которой их много, задча намного условиями. В этом случае обычно требуется не только найти экстремум (скажем, минимум), но и определить «лобальный» экстремум, или «minimum минимум». К великомому созалению, большинство реализых математических задач, для которых ищется минимум, многоэкстремальный. Точно так же трудно найти местность, на которой одна вершина господствовала бы безразделно на очень большом пространстве. Obviously выслуших вершин имеются вершины
34
поменьше, но есть и относительно небольшая область, из которой подъем безусловно приведет к высочайшей вершине. Эта область называется oblastью приятиения глобального экстремума. Достаточно выйти за границы этой области или оказаться за ним в начале понска, как достижение глобального экстремума уже становится трудно гарантировать. Увеличиваются шансы попасть в местный (локальный) экстремум.
Существует много способов борьбы с многоэкстремальнымностью, однако ни один из них не гарантирует успеха. Эти методы носят нестрогий, как говоря математики, эвристический характер. Сторонники трех разных многоэкстремальных методов встретились в группе Скептиков. Мы не приводим их именно: фронт научных исследований в этой области за последнее время настолько расширился и столбнее вступил в борьбу с многоэкстремальнымностью, что указываемые методы трудно связать с чьими-то конкретными именами.
Одни пробовали выскакивать из экстремума, если уже попали в него, и по успешности или неспешности этих попыток судить о достижении глобального экстремума. Другие пытались спускаться из нескольких случайно выбранных точек. Наконец, третьи (верх скептиизма!) пришли в выводу, что разумнее всего не направлять разума, а просто борить по острову, поглядывая на высотомер.
Все эти три образа действий находят приверженцев среди ученых, хотя третьий — все же реже. Составлены специальные программы для вычислительных машин, которые реализуют каждой из этих способов и еще многое другие. Тем не менее не только завзятые скептики, но и неунывающие оптимизиты не рискуют сегдня считать проблуему решенной. И первое побужение при анализе какой-либо функции на экстремум — это попытка доказать ее однознакство. Нередко это достижение почтиется не ниже, чем правильность математической модели вообще. Так, например, отсутствие локальных экстреммов в задачах линейного программирования — важный довод в попытку линейных моделей, перевышивающий многое их недостатки.
Существуют всема изошренные способы обедининия разных методов. Например, всех трех скептиков можно было обединить в один коллектив. Вы скажете, между ними мало родства? А много и не требуется. Достаточно того, что они мало верят в свои собственные методы. Можно отправить их на поиск низины общей группой из трех человек, порешив, что на каждом шаге попска будет действовать тот из них, на которой падет жребий. Скажем, все трое будут тянут из шапки свернутьые бумажки, на одной из которых стоит крестик. И, представьте себе, в попытку такого образа действий есть свои доводы.
Эпилог
— Простите, что вы сказали? — переспросил Винер.
— Я говорю, вы, какется, не слышите меня? Разве мои метод не разумен?
— Прошу прощения, быть может, ваш метод и хороший, хотячно я поострегся бы назвать его методом. Но меня отвлекиной звук. Слушите?
— Нет… впрочем, да. Кажется, это журчание. Но почему здесь, а не в низине?
Обаbrosлись на слабый звук, который раньше заглушали голова, и припали к роднику, было ему изскалы. Хрустальные стружки, истекая, тут же терялись среди камней.
— Как видите, в нашем случае решить проблуему отыскания воды было веса просто — сказал Винер, света фонарем своего спутника. — Достаточно было всем замолчать на минуту.