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

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

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

За фразой "а — небольшая константа" скрывается огромное разнообразие методов определения значения а. Основная проблема состоит в том, что если значение а слишком мало, то требуется слишком много этапов поиска, а если слишком велико, то в поиске можно проскочить максимум. Попытка преодолеть эту дилемму предпринимается в методе линейного поиска, который предусматривает продолжение поиска в направлении текущего градиента (обычно путем повторного удвоения а) до тех пор, пока f не начнет снова уменьшаться. Точка, в которой это происходит, становится новым текущим состоянием. Сформировалось несколько научных школ, в которых доминируют разные взгляды на то, каким образом в этой точке следует выбирать новое направление.