Реферат: Нелинейное программирование

З. Я. Тьмеладзе

Земля! Земля!

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

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

– На острове должна быть вода. Утром мы займёмся её поисками.

– Боюсь, кое для кого к утру будет уже поздно, – через силу произнес Зейдель. – Искать нужно сейчас. В низине должен быть ручей.

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

– Воздушный шар? – хрипло воскликнул Растригин. – Прожекторы?! Зачем предаваться грёзам? Нам нужно подумать, как обойтись фонарями. Что скажете вы, Ферма?

– Господа судьи, – начал Ферма, но тут же поправился. – Простите – галлюцинации! Мне показалось, что я снова в суде – ведь я юрист. По моему разумению, нам поможет обычный плотницкий уровень. Есть ли он среди корабельных приборов?

– Да, их несколько. Но какое отноше...

– Погодите. Мы должны двигаться в направлении низины, прикладывая к земле уровень. Как только уровень покажет, что поверхность горизонтальна, – мы в низине. Вот как я здесь представил на рисунке.

И он изобразил на листке из судового журнала рисунок 1.

Рис. 1

– Но позвольте, – как можно вежливее остановил его измученный Гаусс, – ведь так мы найдем лишь самую низкую точку по выбранному направлению. А как его выбрать, если ни зги не видно? Что думаете вы, Зейдель?

– Спасибо, господин Гаусс, что вы сочли возможным обратиться ко мне. Я думаю, что в этой ситуации нам не помешал бы компас, – ага, вот и он. Давайте действовать так: сначала установим уровень, ориентируя его с запада на восток, – он показывает снижение местности к востоку, видите? Пойдём на восток до тех пор, пока местность будет понижаться, как нам любезно подсказал господин Ферма. А дойдя до этой точки, снова приложим уровень к земле, но уже в направлении с юга на север. Допустим он укажет на понижение местности к северу. Тогда отправимся на север и будем идти, пока местность будет понижаться. Так мы будем сворачивать до тех пор, пока не придем в низшую точку. В ней уровень будет горизонтален, как его ни поверни. Не так ли?

– Я думаю, сын мой, вы правы, и через час мы уже будем здесь с полными фляжками, – ответил Гаусс, и оба побрели к востоку, захватив с собой компас и один из уровней. Ферма отправился за ними.

– Они правы, правы, – приговаривал деятельный Коши, нетерпеливо поглядывая на другой уровень, – но не во всём. Гаусс и Зейдель отправились на восток. И действительно, местность понижается к востоку. Но понижается слабо. Смотрите, сильнее всего снижение происходит в направлении на северо-восток. Может, туда и стоит отправиться? Пожалуй, я так и сделаю. Пройду несколько шагов и снова проверю, в каком направлении нужно спускаться, и снова сделаю несколько шагов. Где моя фляжка? Ах, вот она. Минут через сорок она уже будет полна!

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

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

– Ну как? Догнал он его? – зачем-то спросил Иномата.

– Куда там! – возразил ему со вздохом Кумада, который в этот момент возился с глобусом, снимая его с оси. – Им уже не встретиться. Они могли бы уже здесь сказать друг другу «до свидания». Ну что, двинулись и мы, Иномата-сан?

– Конечно! Зачем нам уровень, а тем паче компас? Вот этот шар доведёт нас до цели. Пусть он свободно катится, а мы просто пойдём вслед. Ведь шар скатится в самую низкую точку.

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

Цетлин утомленно смотрел вслед людям, растаявшим в ночи.

– О чём вы думаете? – спросил его Гельфанд, с трудом поднимаясь с земли. – Не о том ли, что Гаусс и Зейдель придут не туда, куда направлялись?

– Вы угадали. Они собирались найти самую низкую точку, представляя себе местность в виде впадины с гладкими стенками (рис. 2). Но судьба может сыграть с ними злую шутку: им может встретиться на пути овраг. И он быстро начертил на листке из судового журнала рисунок 3.

– Их счастье, если по дну оврага протекает ручей. А если родник в самой низкой точке?

– Да, тогда судьбе Гаусса и Зейделя не позавидуешь: идя на восток, они придут в точку A – это самое низкое место на их пути. А в направлении север-юг самая низкая точка – это снова точка A. Таким образом, бедняги придут к выводу, что A – самая низкая точка на местности и умрут в ней от жажды.

– Но может быть, их спасёт фляжка Коши?

– Боюсь, что и фляга Коши останется пустой, если он встретится с оврагом. Оказавшись у дна оврага, он будет искать направление самого крутого спуска, и оно неизбежно приведёт его в точку по другую сторону оврага. Из этой точки он вернётся на прежнюю сторону и дальше пойдёт небольшими шажками до тех пор, пока жажда не свалит его. Ведь весь овраг он увидеть не может – его фонарь способен осветить местность лишь у самых ног. Надо придумать что-нибудь другое...

– А что если Канторович достигнет цели? Хотя не думаю: если овраг искривлён, а овраги редко бывают прямыми, то он начнёт метаться по дну оврага, почти не приближаясь к цели. Надо стараться двигаться по дну оврага.

– Разумеется, но как? Впрочем... кажется, придумал. Посмотрите на рисунок 4. Давайте мы оба, вы и я, пойдём из двух разных точек методом Канторовича. Скажем, я отсюда, а вы – отойдя шагов на сто в любом направлении.

Рис. 4

– Понятно, а дальше? Ага, дальше мы оба спустимся на дно оврага и постараемся увидеть фонари друг друга. Допустим, нам это удастся. Тот из нас, чей фонарь выше, двинется по направлению к тому, чей фонарь ниже.

– Но встретившись, не остановится, а пройдет дальше в том же направлении до точки D. Из этой точки он снова спустится на дно оврага, и мы опять попытаемся увидеть друг друга. И так до тех пор, пока уровень на дне оврага не укажет горизонтальный участок.

И, выбрав фонари поприметнее, оба отправились каждый своим путём.

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

– У всех этих способов один недостаток – слишком много приходится возиться с уровнем, пока найдёшь нужное направление. А что если пойти по какому-либо направлению наугад, пока оно ведёт на спуск? Потом изменить направление и снова спускаться по нему. Изменить, разумеется, тоже наугад. Разве таким образом я не приду к цели? Стоит ли терять время на отыскание направления наискорейшего спуска, если уже через несколько шагов оно перестает им быть?

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

Методы спуска

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

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

Великий француз П.Ферма (1601–1665) первым ясно осознал и сумел описать аналитически свойство экстремума гладкой непрерывной функции: касательная в этом месте должна быть горизонтальна. К.Гаусс (1777–1855) и А.Зейдель (1821–1896), следуя своему методу покоординатного спуска, по очереди спускались то вдоль одной, то вдоль другой координаты. Спускались до тех пор, пока касательная к направлению движения не станет горизонтальной. А положение уровня естественно определяет направление касательной.

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

А потому нетрудно понять наших современников, японцев С.Иномату и М.Кумаду, которые попытались придать процессу спуска по антиградиенту вышеописанный физический смысл. Между прочим, их метод так и назвали «методом тяжёлого шарика». Только разумеется, при его использовании не катают глобус по макету функции, а лишь решают дифференциальные уравнения движения.

Немало трудностей ждёт того, кто ищет экстремум функции, но одна из самых коварных – это овраги. Любой из методов, даже наиболее совершенный в вычислительном отношении метод наискорейшего спуска Л.В.Канторовича, известного советского математика, приводит к беспомощному метанию по дну оврага. Поэтому советские математики И.М.Гельфанд и М.Л.Цетлин и предложили «овражный поиск», который позволяет выследить дно оврага. Итак, как мы видим, почти все численные методы поиска наилучшего направления спуска так или иначе связаны с антиградиентом. Правда, оказалось, что труды по отысканию антиградиента не всегда вознаграждаются качеством найденного направления спуска, и советский учёный Л.А.Растригин предложил вообще не тратить сил и машинного времени на поиск антиградиента, а шагать куда себе вздумается, то бишь по случайному направлению. И представьте, результаты такого образа действий оказались ничуть не хуже в вычислительном отношении, чем поиски наилучших путей. Иначе говоря, не настолько эти наилучшие пути превосходят по качеству случайный, чтобы стоило тратить время на их поиск. Разумеется, чтобы выбрать направление спуска случайным образом, не крутятся на месте с закрытыми глазами – для этого в машине используют датчики случайных чисел. И вообще численную сторону методов нелинейного программирования трудно продемонстрировать на бумаге – это существенно машинные методы.

Но вернёмся к потерпевшим кораблекрушение и узнаем, кому из них сопутствовал успех в поиске воды.

Там, за перевалом

Итак, все разбрелись в поисках воды, кроме кучки Скептиков.

– Дьявольская жажда! – промолвил один из них. – Неужели вас она не мучит?

– Не меньше, чем вас, – ответил Винер от имени остальных. – И я охотно двинулся бы на поиски воды, если бы меня убедил какой-то из предложенных способов. Но увы! Если мы начнём таким способом искать высшую точку Земли, то вместо Эвереста окажемся на вершине соседнего холмика. И самое ужасное то, что у нас нет никакого средства отличить этот холмик от Эвереста. Если, конечно, не привлечь на помощь математике обыкновенную географию.

– Как это нет? Почему? – поинтересовался молодой Скептик, которого скептицизм не отучил ещё задавать вопросы.

– Очень просто. С помощью фонарика мы способны лишь убедиться, что из данной точки пути ведут вниз. А что там, дальше? Вот тут наши друзья предложили ряд способов, – он снисходительно показал на оставшиеся листки из судового журнала. – Они исходили из того, что на острове только одна низина. А если их много, и вода лишь в самой низкой из этих низин (рис. 5)? Спуск приведёт нас в точку A, а вода в точке B – там гуще горизонтали и, следовательно, ниже отметка. Задумайтесь над этим.

Рис. 5

– Я уже задумывался, – сказал первый Скептик. – И решил действовать так. Сначала пойду куда глаза глядят. Потом спущусь в ближайшую низину и замерю её высоту высотомером. Запомню её расположение и перейду в новую случайную точку. Из нее снова спущусь в низину и снова взгляну на высотомер. Допустим, он покажет на сей раз меньшую высоту. Это значит, что вторая низина ниже первой, и там больше шансов найти воду. Затем...

– Что будет затем, ясно, – прервали его. – Но уверены ли вы, что найдёте воду прежде, чем свалитесь с ног?

– Могу ли я быть в этом уверен? Ведь я же Скептик! Просто это лучше, чем стоять сложа руки.

И первый Скептик скрылся в темноте.

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

– Уж не собираетесь ли вы по следам Кумады? – спросил его Винер, одновременно к чему-то прислушиваясь.

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

– Но так можно обнаружить лишь недалёкий перевал.

– Что вы! У меня сильный удар. Меня обычно просят ударить от ворот.

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

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

– Что ж, я желаю вам успеха. Если наградой вам и не послужит вода, то во всяком случае вы повысите свою спортивную форму.

– А я поступлю иначе, – обратился третий Скептик к Винеру. – Я отправлюсь просто бродить по острову, не стараясь найти наилучшее направление, и буду поглядывать на высотомер. Побродив, замечу, где самая низкая точка, и уже там начну поиски воды. Все эти разговоры убедили меня, что если у нас нет карты острова, то никакой разумной стратегии движения быть не может. Так зачем же тогда тратить время на возню с приборами? Но вы, кажется, не слушаете меня?

Где кончается асфальт

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

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

Одни пробовали выскакивать из экстремума, если уже попали в него, и по успешности или неуспешности этих попыток судить о достижении глобального экстремума. Другие пытались спускаться из нескольких случайно выбранных точек. Наконец, третьи (верх скептицизма!) пришли в выводу, что разумнее всего не напрягать разума, а просто бродить по острову, поглядывая на высотомер.

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

Существуют весьма изощрённые способы объединения разных методов. Например, всех трёх скептиков можно было объединить в один коллектив. Вы скажете, между ними мало родства? А много и не требуется. Достаточно того, что они мало верят в свои собственные методы. Можно отправить их на поиск низины общей группой из трёх человек, порешив, что на каждом шаге поиска будет действовать тот из них, на которого падёт жребий. Скажем, все трое будут тянуть из шапки свёрнутые бумажки, на одной из которых стоит крестик. И, представьте себе, в пользу такого образа действий есть свои доводы.

Эпилог

– Простите, что вы сказали? – переспросил Винер.

– Я говорю, вы, кажется, не слышите меня? Разве мой метод не разумен?

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

– Нет... впрочем, да. Кажется, это журчание. Но почему здесь, а не в низине?

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

– Как видите, в нашем случае решить проблему отыскания воды было весьма просто, – сказал Винер, светя фонарём своему спутнику. – Достаточно было всем замолчать на минуту.