Нелинейное программирование (стр. 1 из 2)

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

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

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

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

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

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

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

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

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

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

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

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

Рис. 1

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

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

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

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

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

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

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

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

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

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

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

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

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

Рис. 2

Рис. 3

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

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

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

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

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

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

Рис. 4

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

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

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

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

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

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

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

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

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

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

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