Алан Джером Хоффман (30 мая 1924 — 18 января 2021) — американский математик и почётный научный сотрудник IBM в Исследовательском центре имени Т. Дж. Уотсона , IBM, в Йорктаун-Хайтс, штат Нью-Йорк . Он был одним из редакторов-основателей журнала « Линейная алгебра и ее приложения» и имел несколько патентов. Он внес вклад в комбинаторную оптимизацию и теорию собственных значений графов. Хоффман и Роберт Синглтон построили граф Хоффмана-Синглтона , который является уникальным графом Мура степени 7 и диаметра 2. [2]
Хоффман умер 18 января 2021 года в возрасте 96 лет. [3] [4]
Алан Хоффман родился и вырос в Нью-Йорке, проживая сначала в Бенсонхерсте , Бруклин, а затем в Верхнем Вест-Сайде Манхэттена, со своей сестрой Милдред и его родителями Мюриэл и Джесси. Алан с раннего возраста знал, что хочет сделать карьеру в области математики. Он хорошо учился во всех дисциплинах, находя вдохновение как в гуманитарных, так и в естественных науках. Но он был очарован строгостью дедуктивных рассуждений, присущих математике. Он окончил среднюю школу Джорджа Вашингтона в 1940 году и той осенью поступил в Колумбийский университет по Пулитцеровской стипендии в 1940 году в возрасте 16 лет.
В Колумбии Хоффман присоединился к Дебатному совету, отчасти для того, чтобы преодолеть свой страх перед публичными выступлениями, и принимал активное участие в обоих движениях, направленных на увеличение американской поддержки союзников в растущей войне против стран Оси, а также в движении за прямое вступление Америки в коалицию. война. Хотя его курсовая работа состояла в основном из математики, включая небольшие занятия со знаменитостями в этой области, он также изучал философию, литературу и историю правительств.
Вторая мировая война прервала учебу Хоффмана, но не его интерес к математике. Он был призван на службу в феврале 1943 года и служил в армии США с 1943 по 1946 год, проводя время как в Европе, так и на Тихом океане. Хоффман красноречиво называет эти три года «кульминационным событием в моей жизни, наполненным приключениями, усиленными чувствами юности».
Во время начальной подготовки в зенитно-артиллерийском училище он рассматривал возможность разработки аксиом геометрии окружностей. Не умея рисовать, он носил в голове видение конфигураций пространства – точек, кругов и сфер – изображающих явления, аналогичные геометрии линий. Эти идеи позже легли в основу его докторской диссертации по основам инверсионной геометрии. Опыт разработки идей в уме, а не на бумаге или на доске, оставался практикой на протяжении всей его карьеры – практикой, которую он не рекомендовал другим, но которая удивительно хорошо послужила его уникальному уму.
После дополнительной армейской подготовки Хоффман стал инструктором в школе зенитной метрологии [IL1] [2], преподавая основы тригонометрии, используемой для отслеживания воздушных шаров и построения графиков определения ветра на высоте. После дополнительного обучения электротехнике в Университете штата Мэн и освоению азов междугородной телефонной связи Хоффман был направлен в 3186-й батальон службы связи и отправлен на европейский театр военных действий в декабре 1944 года, когда война там приближалась к концу. Он провел короткое время на Тихоокеанском театре военных действий, прежде чем вернуться домой в феврале 1946 года. Во время своего пребывания за границей он и другие преподавали математику на небольших самостоятельно организованных курсах, и он записывал свои набеги на круговую геометрию, чтобы поделиться ими с преподавателями Колумбийского университета.
По возвращении в Колумбию осенью 1946 года Хоффману поручили вести курс математических исследований в Колумбийском фармацевтическом колледже. Он рассматривал это как возможность улучшить свои педагогические[3] навыки и определить, будет ли запланированная карьера преподавателя в университете наиболее подходящим выбором. В течение этого учебного года он приобрел уверенность и навыки преподавания, кристаллизовал свои идеи об аксиомах круговой геометрии и сделал предложение Эстер Уокер, сестре своего армейского друга. Осенью 1947 года Хоффман поступил в аспирантуру Колумбийского университета, «полный уверенности».
После успешной сдачи экзаменов и защиты докторской диссертации по основам инверсионной геометрии в 1950 году Хоффман провел постдокторантский год в Институте перспективных исследований в Принстоне, спонсируемом Управлением военно-морских исследований. В течение этого года он установил ритм своей работы, основанный на мантре «Ты математик, ты занимаешься математикой». [5]
В конце постдокторского года, не получив академической должности там, где он хотел бы жить, Хоффман присоединился к отделу прикладной математики Национального бюро стандартов (NBS, ныне Национальный институт стандартов и технологий) в Вашингтоне, округ Колумбия. Этот выбор, против которого выступали друзья и коллеги, был случайным. «Вся моя карьера основана на опыте пяти лет, которые я провел в Вашингтоне, в NBS». Хоффман был нанят для выполнения контракта (Проект SCOOP) с Управлением авиадиспетчера ВВС США по реализации программы исследований и вычислений в области, о которой он никогда не слышал: линейном программировании. Хоффман нашел новый (как для себя, так и для всего мира) предмет «восхитительным сочетанием сложности и веселья».
Хоффман научился линейному программированию у Джорджа Данцига, который считал, что их работа поможет организациям работать более эффективно за счет использования математики – концепция, которая сейчас, 70 лет спустя, продолжает реализовываться[IL4]. Благодаря этой работе Хоффман познакомился с бизнес-концепциями в сфере управленческого консалтинга, производства и финансов — областей, которые ему нравились, но в которых он никогда не чувствовал себя полностью как дома. Благодаря проекту SCOOP Хоффман познакомился с другими выдающимися деятелями исследования операций, такими как Ричард Беллман и Гарольд Кун. Хотя код, который он написал в 1951 году, «просто не работал», опыт был настолько обескураживающим, что он так и не написал ни одной программы. Хоффман и соавторы опубликовали статью, показывающую на основе экспериментов, что симплексный метод превосходит своих современных конкурентов в вычислительном отношении. Эта статья содержит первые вычислительные эксперименты с симплекс-методом и служит моделью для проведения вычислительных экспериментов по математическому программированию.
В эти первые годы работы в NBS Хоффман разработал первый пример велосипедного движения по симплексному методу, пример, который появляется во многих учебниках по этому предмету. Краткий технический документ NBS, по-видимому, не получивший широкого распространения, показал, что точка, которая «почти» удовлетворяет набору линейных неравенств, является «близкой: к некоторой другой точке, которая удовлетворяет при любых разумных определениях «почти» и «близко». заслуживают внимания последствия для алгоритмов линейного программирования, которые учитывают «ленивые» или «мягкие» ограничения или для которых данные ограничений (коэффициенты матрицы и правая часть) подвержены шуму.
Хоффман был ключевым организатором влиятельного Второго симпозиума по линейному программированию , проходившего в Бюро в январе 1955 года. Статья NBS о симплексном методе («Как решить задачу линейного программирования », Proc. Второй симпозиум по линейному программированию, 1955 г.) была широко распространен среди других групп, работающих над собственными кодами симплексного алгоритма. В 2020 году эта статья представляет собой увлекательный взгляд на проблемы решения линейных программ на крошечных (по сегодняшним меркам) компьютерах. Работа Хоффмана в NBS включала в себя неудачные попытки использовать линейное программирование для решения задачи комбинаторного аукциона по закупкам. Комбинаторные аукционы по сей день остаются сложной задачей из-за огромной вычислительной нагрузки, связанной с вычислением оптимальных решений [IL5]. В проекте NBS использовался подход, напоминающий метод ветвей и границ, который сейчас является стандартным методом решения задач целочисленного программирования.
Вместе с немецким математиком Гельмутом Виландтом Хоффман использовал линейное программирование, чтобы оценить, насколько далеки собственные значения одной нормальной матрицы от собственных значений другой нормальной матрицы с точки зрения того, насколько далеки эти две матрицы друг от друга. Результат основан на наблюдении, что каждая дважды стохастическая матрица является выпуклой оболочкой матриц перестановок. Для сообщества исследования операций этот результат означает, что для подкласса задач линейного программирования, которые называются транспортными задачами, если данные (правая часть или значения спроса и предложения) состоят из целых чисел, то существует оптимальное решение, принимающее только целые числа. ценности. Общий результат известен как теорема Хоффмана-Виланда , и есть математики, которые знают Хоффмана только благодаря этому результату.
В NBS Хоффман исследовал связь между двойственностью линейного программирования и другими комбинаторными задачами. Это привело к простому, но элегантному доказательству теоремы Кенига-Эгервари, которая гласит, что для матрицы 0–1 максимальное количество единиц, появляющихся в разных строках и столбцах, равно минимальному количеству строк и столбцов, которые в комбинации включают все единицы в матрице. Эта ранняя работа в NBS и постоянный интерес Хоффмана к использованию линейных равенств для доказательства комбинаторных теорем привели к сотрудничеству с Гарольдом Куном, Дэвидом Гейлом и Элом Такером и к рождению подполя, которое позже стало известно как полиэдральная комбинаторика. Хоффман оказал влияние на то, что позже привел Джека Эдмондса в NBS (1959–1969), где эта тема процветала.
Находясь в NBS, Джо Краскал и Хоффман показали, что полная унимодулярность (концепция, а не название) объясняет, почему некоторые линейные программы с целочисленными данными имеют целочисленные решения, а некоторые нет. Они также определили некоторые достаточные условия, при которых матрица обладает требуемым свойством.
Хоффман также писал об условиях Липшица для систем линейных неравенств, границах собственных значений нормальных матриц и свойствах гладких моделей производства. В 1956 году Хоффман покинул Бюро и переехал в Англию с Эстер и двумя маленькими дочерьми, Элеонорой (тогда ей было 2 года) и Элизабет (тогда ей было менее 6 месяцев) на блестящую роль сотрудника по научным связям (математика) в лондонском филиале Бюро. Военно-морских исследований с миссией восстановить связи между американскими и европейскими математиками. Это был год слушания и обучения, установления и возобновления дружеских отношений и, конечно же, занятий математикой. Он занимался математикой по всей Европе, обнаружив в поезде во Франкфурт прекрасную теорему (но ошибочное доказательство, позже исправленное Джеффом Каном), связывающую тему алгебры с его ранними работами по геометрии кругов. Другая статья, написанная в этот период, дополнительно исследует последствия полной унимодулярности и вводит концепцию циркуляции в ориентированном графе как обобщение концепции st-потока, в котором два узла графа играют особую роль.
Когда год за границей подошел к концу, Хоффман исследовал две должности в промышленности в Нью-Йорке: одну в крошечной группе математических исследований в зарождающейся исследовательской лаборатории IBM в северном округе Вестчестер, а другую преподавал и обеспечивал общую поддержку исследований операций для сотрудников GE в Манхэттене. штаб-квартира компании. Хоффман выбрал роль в более крупной и авторитетной организации из-за ее местоположения, зарплаты и возможности увидеть, сможет ли он и область исследования операций добиться успеха в бизнесе. Хоффман нашел эту работу увлекательной и во многих отношениях приносящей удовлетворение. Руководство разрешило ему заниматься математикой, если это не мешало ему выполнять возложенные на него обязанности. Хоффман продолжил свои исследования, большая часть которых была параллельна миссии группы управленческого консалтинга, в элегантном офисе в самом центре Манхэттена.
Летом 1960 года Хоффман принял участие в летнем семинаре по комбинаторике, организованном математическим факультетом IBM Research. Он был ослеплен атмосферой и «людьми вокруг, занимающимися математикой». В 1961 году он принял приглашение Германа Голдстайна, Херба Гринберга и Ральфа Гомори присоединиться к IBM Research, думая, что это будет отличное место для работы, но, вероятно, оно продлится недолго, и через несколько лет он получит «настоящая работа» в академических кругах. Хотя Хоффман работал приглашенным или адъюнкт-профессором в Израильском технологическом институте Технион (который присвоил ему степень почетного доктора), Йельском университете, Стэнфорде (где он провел холодные зимы почти десять лет), Рутгерсе, Технологическом институте Джорджии, Университете Иешива, Новой школы и Городского университета Нью-Йорка и руководил докторской диссертацией. диссертации в Городских университетах Нью-Йорка, Стэнфорда, Йеля и Принстона, он оставался членом математического факультета IBM Research до выхода на пенсию с должности сотрудника IBM в 2002 году.
Придя в IBM, Хоффман был одним из старейших сотрудников отдела, который состоял в основном из новых докторов наук. Несмотря на то, что Хоффман получил докторскую степень всего через 11 лет, он быстро взял на себя роль наставника для этих молодых исследователей, обсуждая их работу и интересы и давая рекомендации. Некоторое время он занимал должность директора отдела, а в 1977 году был назначен научным сотрудником IBM. За свою карьеру он опубликовал более 200 научных статей, более трети из которых — в соавторстве. Его математический диапазон охватывал множество областей как алгебры, так и исследования операций. Он был соавтором статей со многими своими коллегами из IBM, эффективно сотрудничая со всеми, от своих коллег-стипендиатов IBM) до летних стажеров и постдоков. Юмор Гофмана, увлечение математикой, музыкой и игрой слов, доброта и щедрость ценились всеми, кто с ним сталкивался.
Краткое изложение математических вкладов (из его заметок в «Избранных статьях Алана Хоффмана») [6]
Работа Хоффмана по геометрии, начиная с диссертации «Об основах геометрии обращения», включала в себя доказательства свойств аффинных плоскостей, исследование точек корреляции конечных проективных плоскостей, условий на закономерности объединения и пересечения конусов (выведенные во многом благодаря обобщению своих более ранних результатов о ранге вещественных матриц). Он представил альтернативное доказательство, основанное на аксиомах для некоторых абстрактных систем выпуклых множеств, результата (Скарфа и других) о количестве неравенств, необходимых для определения решения задачи целочисленного программирования. Теорема об этой абстрактной системе, по-видимому, тесно связана с антиматроидами (также известными как выпуклые геометрии), хотя эта связь еще не полностью исследована.
Работы Хоффмана в области комбинаторики расширили наше понимание некоторых классов графов. Лекция Г. Хайоса по интервальным графам в 1956 году привела к характеристике Хоффманом графов сравнимости, а позже, благодаря сотрудничеству с Полом Гилмором, к теореме GH (также приписываемой А. Гуйя-Ури). Вдохновленный алгоритмом сопоставления Эдмонда, Хоффман сотрудничал с Рэем Фулкерсоном и М. МакЭндрю Хоффманом, чтобы охарактеризовать наборы целых чисел, которые могли бы соответствовать степеням и границам количества ребер каждой пары вершин такого графа. Далее они рассмотрели, какие графы в классе всех графов, имеющих заданный набор степеней и границ числа ребер, могут быть преобразованы с помощью определенного набора обменов в любой другой набор в классе. Доказательства тесно связаны с важной концепцией базиса Гильберта. Статья о самоортогональных латинских квадратах, написанная соавторами IBM Доном Копперсмитом и Р. Брайтоном, была вдохновлена просьбой запланировать, чтобы супруга избегала турнира смешанного парного разряда в местном ракетном клубе. Это единственная статья, которую Хоффман обсуждал за пределами математического сообщества.
Частично упорядоченные множества были частой темой исследований Хоффмана. В статье 1977 года, написанной совместно с Д.Е. Шварцем, двойственность линейного программирования используется для обобщения обобщения Грина и Клейтмана 1976 года теоремы Дилворта о разложении частично упорядоченных множеств, что является еще одним примером объединяющей роли, которую двойственность играет во многих комбинаторных результатах.
На протяжении всей своей карьеры Хоффман искал простые элегантные альтернативные доказательства доказанным теоремам. Эти альтернативные доказательства часто приводили к обобщениям и расширениям. В конце 1990-х он сотрудничал с Цао, Хваталом и Винсом, чтобы разработать альтернативное доказательство, используя элементарные методы, а не линейную алгебру или теорему Райзера о квадратных матрицах 0–1.
Работы Хоффмана по матричным неравенствам и собственным значениям являются основой любого курса теории матриц. Особое очарование и в соответствии с его любовью к унификации подходов представляет его статья 1975 года о линейных G-функциях. Хотя доказательство указанного варианта Гершгорина длиннее и сложнее, чем другие, оно охватывает все варианты Островского и многие дополнительные варианты как частные случаи.
Хоффман был обнадеживающим старейшиной, но не принимал активного участия в разработке IBM серии продуктов для линейного и целочисленного программирования. Однако он продолжил исследования комбинаторных и алгебраических аспектов линейного программирования и линейных неравенств, включая восхитительную абстракцию двойственности линейного программирования (1963). Он также продолжал использовать свойства линейных неравенств для доказательства (или более элегантного передоказательства) результатов о выпуклости.
В сотрудничестве со Шмуэлем Виноградом, также научным сотрудником IBM в отделе математики, был создан эффективный алгоритм для поиска всех кратчайших расстояний в направленной сети с использованием псевдоумножения матриц. В серии статей о решетчатых многогранниках (некоторые совместно с Доном Швартсом) была введена концепция решетчатых многогранников, что привело к еще одному примеру комбинаторной двойственности.
После сотрудничества с Рэем Фулкерсоном и Розой Оппенгейм над сбалансированными матрицами Хоффман обобщил результат Форда-Фалкерсона «Максимальный поток – минимальный разрез» на другие случаи (поток в узлах, ненаправленные дуги и т. д.), предоставив доказательство того, что все ранее известные случаи были Особые случаи. В этой статье также была представлена концепция (но опять же не название) полной двойственной целостности, идея, лежащая в основе большинства применений линейного программирования для доказательства экстремальных комбинаторных теорем.
За свою карьеру Хоффман изучал класс задач целочисленного программирования, которые можно было решить путем последовательной максимизации переменных в некотором порядке. Одним из таких примеров является полная транспортная задача в случае, когда коэффициент стоимости демонстрирует особое свойство, открытое более века назад французским математиком Гаспаром Монжем. Этот подход, названный в статье Хоффмана просто «простым», позже Эдмондс и Фулкерсон сочли его «жадным». Свойство Монжа порождает антиматроид, и с помощью этого антиматроида результат Хоффмана легко распространить на случай неполных транспортных задач. Хоффман повторно использовал термин «жадный» для описания подкласса матриц 0–1, для которых двойственная линейная программа может быть решена с помощью жадного алгоритма для всех правых частей и всех целевых функций с убывающими (в переменном индексе) коэффициентами. . Вместе с Коленом и Сакаровичем он показал, что для этих матриц соответствующая целочисленная программа имеет целочисленное оптимальное решение для целочисленных данных. Элегантная и краткая статья 1992 года дает характеристику матриц 0-1, для которых проблемы упаковки и покрытия могут быть решены с помощью жадного подхода. Он обеспечивает унификацию результатов для задач о кратчайшем пути и минимальном остовном дереве. Его последняя статья на эту тему «О жадных алгоритмах, частично упорядоченных множествах и субмодулярных функциях», написанная в соавторстве с Дитрихом, появилась в 2003 году.
Хоффман посетил и вновь вернулся к теме «Спектры графов», обращаясь к уникальности схемы треугольных ассоциаций в статье 1959 года «Графы Мура с диаметрами 2 и 3» в 1960 году (совместно с Р. Синглтоном), полиномом графа в 1963 году, линейным графиком симметричный сбалансированный дизайн неполных блоков (совместно с Рэем-Чаудхури) в 1965 году, связи между собственными значениями и раскрасками графа (в 1970 году), связи между собственными значениями и разбиениями ребер в графе в 1972 году и многое другое, включая исследование свойств матрица инцидентности ребер и путей серий параллельных графов (связанная с жадными упаковками) с Шибером в 2002 году.
Хоффман был избран в Национальную академию наук в 1982 году, в Американскую академию искусств и наук в 1987 году и в первый класс стипендиатов INFORMS в 2002 году. За свою долгую карьеру Хоффман входил в редакционную коллегию одиннадцати журналов и редактор-основатель журнала «Линейная алгебра и ее приложения». В 1992 году вместе с Филипом Вулфом (также из IBM) он был удостоен премии Джона фон Неймана по теории от ORSA и TIMS[6], предшественников INFORMS[7]. Вручая награду, Джордж Немхаузер признал Хоффмана и Вульфа интеллектуальными лидерами группы математического программирования в IBM. Он процитировал Хоффмана за его работу в области комбинаторики и линейного программирования, а также за его раннюю работу по вычислительной эффективности симплексного метода во время его пребывания в NBS. В августе 2000 года Хоффман был отмечен Обществом математического программирования как один из 10 лауреатов (3 от IBM) премии Founders Award.
В биографии, опубликованной в выпуске « Линейной алгебры и ее приложений», посвященной Хоффману по случаю его шестидесятипятилетия, Уриэль Ротблюм написал: «Помимо его научного и профессионального вклада, Хоффман обладает беспрецедентной способностью получать удовольствие от всего, что он делает. Ему нравится петь, играть в настольный теннис, каламбуры, остроумные истории и — возможно, не меньше, чем что-либо еще — заниматься математикой».
Эстер Хоффман умерла от заболевания крови летом 1988 года. Алан женился на Элинор Хершафт, дизайнере интерьеров, в 1990 году. Они развелись в 2014 году. Элинор умерла в октябре 2020 года. Хоффман провел свои последние годы в пенсионном сообществе Осборн в городе Рай, штат Нью-Йорк. . У него остались дочери Элеонора и Элизабет.
Алан Хоффман был лауреатом ряда наград. [7]
{{cite book}}: CS1 maint: multiple names: authors list (link) CS1 maint: numeric names: authors list (link)