Алан Джером Хоффман (30 мая 1924 г. — 18 января 2021 г.) — американский математик и почётный член IBM , Исследовательский центр TJ Watson , IBM, в Йорктаун-Хайтс, штат Нью-Йорк . Он был редактором-основателем журнала Linear Algebra and its Applications и имел несколько патентов. Он внёс вклад в комбинаторную оптимизацию и теорию собственных значений графов. Хоффман и Роберт Синглтон построили граф Хоффмана–Синглтона , который является уникальным графом Мура степени 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. Second Linear Programming Symposium, 1955) была широко распространена среди других групп, работающих над собственными кодами для симплексного алгоритма. В 2020 году эта статья представляет собой увлекательный взгляд на проблемы решения линейных программ на крошечных (по сегодняшним меркам) компьютерах. Работа Хоффмана в NBS включала неудачные попытки использовать линейное программирование для решения задачи комбинаторного аукциона по закупкам. Комбинаторные аукционы остаются сложными и по сей день из-за огромной вычислительной нагрузки, связанной с вычислением оптимальных решений [IL5]. Усилия NBS использовали подход, который напоминает метод ветвей и границ, который в настоящее время является стандартным методом решения задач целочисленного программирования.
Совместно с немецким математиком Хельмутом Виландтом Хоффман использовал линейное программирование для оценки того, насколько далеки собственные значения одной нормальной матрицы от собственных значений другой нормальной матрицы, с точки зрения того, насколько далеки две матрицы друг от друга. Результат основан на наблюдении, что каждая дважды стохастическая матрица является выпуклой оболочкой матриц перестановок. Для сообщества Operations Research этот результат подразумевает, что для подкласса задач линейного программирования, которые называются транспортными задачами, если данные (правая часть или значения спроса и предложения) состоят из целых чисел, то существует оптимальное решение, принимающее только целые значения. Общий результат известен как теорема Хоффмана-Виландта , и есть математики, которые знают Хоффмана только по этому результату.
В NBS Хоффман исследовал связь между дуальностью линейного программирования и другими комбинаторными проблемами. Это привело к простому, но элегантному доказательству теоремы Кёнига-Эгервари, которая гласит, что для матрицы 0-1 максимальное количество единиц, которые появляются в разных строках и столбцах, равно минимальному количеству строк и столбцов, которые в совокупности включают все единицы в матрице. Эта ранняя работа в NBS и постоянный интерес Хоффмана к использованию линейных равенств для доказательства комбинаторных теорем привели к сотрудничеству с Гарольдом Куном, Дэвидом Гейлом и Элом Такером и к рождению подотрасли, которая позже стала известна как полиэдральная комбинаторика. Хоффман оказал влияние на то, что позже Джек Эдмондс был привлечен в NBS (1959-1969), где эта тема процветала.
В то время как в NBS Джо Крускал и Хоффман показали, что полная унимодулярность (концепция, а не название) дает объяснение того, почему некоторые линейные программы с целочисленными данными имеют целочисленные решения, а некоторые — нет. Они также определили некоторые достаточные условия для того, чтобы матрица обладала требуемым свойством.
Хоффман также писал об условиях Липшица для систем линейных неравенств, границах собственных значений нормальных матриц и свойствах гладких моделей производства. В 1956 году Хоффман покинул Бюро и переехал в Англию с Эстер и двумя маленькими дочерьми, Элеанор (тогда ей было 2 года) и Элизабет (тогда ей было меньше 6 месяцев) на гламурную роль научного офицера по связям (математика) в лондонском отделении Управления военно-морских исследований с миссией восстановления связей между американскими и европейскими математиками. Это был год слушания и обучения, установления и возобновления дружеских отношений и, конечно, занятий математикой. Он занимался математикой по всей Европе, обнаружив в поезде во Франкфурт прекрасную теорему (но с несовершенным доказательством, позже исправленным Джеффом Каном), связывающую тему алгебры с его ранней работой по геометрии окружностей. В другой статье, написанной в этот период, более подробно изучаются последствия полной унимодулярности, а также вводится понятие циркуляции в ориентированном графе как обобщение понятия st-потока, в котором две вершины графа играют особую роль.
Когда год за границей подходил к концу, Хоффман исследовал две промышленные должности в Нью-Йорке: одну в небольшой математической исследовательской группе в зарождающейся исследовательской лаборатории IBM в северном округе Вестчестер, а другую — преподавание и предоставление общей поддержки в области исследования операций для сотрудников GE в штаб-квартире компании на Манхэттене. Хоффман выбрал роль в более крупной, более устоявшейся организации из-за местоположения, зарплаты и возможности увидеть, сможет ли он и область исследования операций добиться успеха в бизнесе. Хоффман нашел эту работу увлекательной и, во многих отношениях, удовлетворяющей. Руководство разрешило ему заниматься математикой, пока это не мешало его обязанностям. Хоффман продолжил свои исследования, большая часть которых была ортогональна миссии группы управленческого консалтинга, в элегантном офисе в самом сердце Манхэттена.
Летом 1960 года Хоффман принял участие в летнем семинаре по комбинаторике, организованном математическим отделом IBM Research. Он был ошеломлен атмосферой и «людьми, занимающимися математикой». В 1961 году он принял приглашение Германа Голдстайна, Херба Гринберга и Ральфа Гомори присоединиться к IBM Research, думая, что это будет отличное место для работы, но что это, вероятно, не продлится долго, и через несколько лет он получит «настоящую работу» в академической среде. Хотя Хоффман был приглашенным или внештатным профессором в Израильском технологическом институте Технион (который наградил его почетной докторской степенью), Йельском университете, Стэнфорде (где он проводил холодные зимы почти десять лет), Ратгерском университете, Технологическом институте Джорджии, Университете Йешива, Новой школе и Городском университете Нью-Йорка и руководил докторской диссертацией. Защитив диссертации в Городском университете Нью-Йорка, Стэнфорде, Йельском университете и Принстоне, он оставался членом математического факультета исследовательского центра IBM вплоть до выхода на пенсию в качестве научного сотрудника IBM в 2002 году.
Присоединившись к IBM, Хоффман был одним из старейших членов отдела, который в основном состоял из новых докторов наук. Несмотря на то, что он получил докторскую степень всего 11 лет назад, Хоффман быстро взял на себя роль наставника для этих молодых исследователей, обсуждая их работу и интересы и давая указания. Он недолгое время занимал должность директора отдела и был назначен IBM Fellow в 1977 году. За свою карьеру он опубликовал свыше 200 научных работ, более трети из них с соавторами. Его математический диапазон охватывал многочисленные области как алгебры, так и исследования операций. Он был соавтором статей со многими коллегами из IBM, эффективно сотрудничая со всеми, от своих коллег IBM Fellows) до летних стажеров и постдоков. Юмор Хоффмана, его энтузиазм к математике, музыке и каламбурам, доброта и щедрость ценились всеми, кто с ним сталкивался.
Резюме математических работ (из его заметок в Selected Papers of Alan Hoffman) [6]
Работа Хоффмана по геометрии, начавшаяся с его диссертации «Об основах инверсионной геометрии», включала доказательства свойств аффинных плоскостей и изучение точек корреляции конечных проективных плоскостей, условий на шаблоны объединения и пересечения конусов (выведенных в значительной степени из его обобщения его более ранних результатов о ранге действительных матриц). Он создал альтернативное доказательство, основанное на аксиомах для некоторых абстрактных систем выпуклых множеств, результата (Скарфа и других) о количестве неравенств, необходимых для указания решения задачи целочисленного программирования. Теорема об этой абстрактной системе, по-видимому, тесно связана с антиматроидами (также известными как выпуклые геометрии), хотя эта связь не была полностью исследована.
Работа Хоффмана в области комбинаторики расширила наше понимание нескольких классов графов. Лекция 1956 года Г. Хайоша об интервальных графах привела к характеристике Хоффманом графов сравнимости, а позднее, благодаря сотрудничеству с Полом Гилмором, к теореме GH (также приписываемой А. Гуйя-Хури). Мотивированный алгоритмом сопоставления Эдмондса, Хоффман сотрудничал с Рэем Фулкерсоном и М. МакЭндрю Хоффманом, чтобы охарактеризовать наборы целых чисел, которые могли бы соответствовать степеням и границам на каждом количестве ребер пары вершин такого графа. Они также рассмотрели, какие графы в классе всех графов, имеющие заданный набор степеней и границ количества ребер, могут быть преобразованы определенным набором замен в любой другой набор в этом классе. Доказательства тесно связаны с важной концепцией базиса Гильберта. Статья о самоортогональных латинских квадратах, написанная совместно с соавторами из IBM Доном Копперсмитом и Р. Брайтоном, была вдохновлена просьбой организовать для супруга, избегающего турнира по смешанным парам в местном клубе по игре в ракетку. Она отличается тем, что является единственной статьей, которую Хоффман обсудил за пределами математического сообщества.
Частично упорядоченные множества были частой темой для изучения Хоффманом. В статье 1977 года с Д. Э. Шварцем используется дуальность линейного программирования для обобщения обобщения Грином и Клейтманом 1976 года теоремы Дилворта о разложении частично упорядоченных множеств, что является еще одним примером объединяющей роли дуальности во многих комбинаторных результатах.
На протяжении всей своей карьеры Хоффман искал простые элегантные альтернативные доказательства устоявшимся теоремам. Эти альтернативные доказательства часто приводили к обобщениям и расширениям. В конце 1990-х годов он сотрудничал с Као, Хваталом и Винсом, чтобы разработать альтернативное доказательство, используя элементарные методы, а не линейную алгебру или теорему Райзера о квадратных матрицах 0-1.
Работы Хоффмана по матричным неравенствам и собственным значениям являются основными в любом курсе по теории матриц. Особое очарование и соответствие его пристрастию к унифицированным подходам представляет его работа 1975 года о линейных G-функциях. Хотя доказательство указанной вариации Гершгорина длиннее и сложнее других, оно охватывает все вариации Островского и многие дополнительные вариации как особые случаи.
Хоффман был вдохновляющим старейшиной, но не активным участником разработки IBM серии продуктов линейного и целочисленного программирования. Однако он продолжил исследования комбинаторных и алгебраических аспектов линейного программирования и линейных неравенств, включая восхитительную абстракцию двойственности линейного программирования (1963). Он также продолжал использовать свойства линейных неравенств для доказательства (или передоказательства, более элегантно) результатов в выпуклости.
Сотрудничество с Шмуэлем Виноградом, также сотрудником IBM на кафедре математики, привело к созданию эффективного алгоритма для поиска всех кратчайших расстояний в направленной сети с использованием псевдоумножения матриц. Серия статей о решетчатых многогранниках (некоторые с Доном Швартсом) ввела концепцию решетчатых многогранников, что дало начало еще одному примеру комбинаторной двойственности.
После сотрудничества с Рэем Фулкерсоном и Розой Оппенгейм по сбалансированным матрицам Хоффман обобщил результат Форда-Фулкерсона Max Flow – Min Cut на другие случаи (поток в узлах, ненаправленные дуги и т. д.), предоставив доказательство, согласно которому все ранее известные случаи были частными случаями. В этой статье также была введена концепция (но опять же не название) полной дуальной целочисленности, идея, лежащая в основе большинства применений линейного программирования для доказательства экстремальных комбинаторных теорем.
За свою карьеру Хоффман изучал класс задач целочисленного программирования, которые решались путем последовательной максимизации переменных в некотором порядке. Одним из таких примеров является полная транспортная задача в случае, когда коэффициент стоимости демонстрирует особое свойство, открытое более века назад французским математиком Гаспаром Монжем. Этот подход, названный просто «простым» в статье Хоффмана, позже был признан «жадным» Эдмондсом и Фулкерсоном. Свойство Монжа приводит к антиматроиду, и посредством использования этого антиматроида результат Хоффмана легко распространяется на случай неполных транспортных задач. Хоффман повторно использовал термин «жадный», чтобы описать подкласс матриц 0-1, для которых двойственная линейная программа может быть решена жадным алгоритмом для всех правых частей и всех целевых функций с убывающими (по индексу переменной) коэффициентами. Вместе с Коленом и Сакаровичем он показал, что для этих матриц соответствующая целочисленная программа имеет целочисленное оптимальное решение для целочисленных данных. Элегантная и краткая статья 1992 года дает характеристику матриц 0-1, для которых проблемы упаковки и покрытия могут быть решены с помощью жадного подхода. Она обеспечивает объединение результатов для задач кратчайшего пути и минимального остовного дерева. Его последняя статья по этой теме "О жадных алгоритмах, частично упорядоченных множествах и субмодулярных функциях", написанная в соавторстве с Дитрихом, появилась в 2003 году.
Хоффман вернулся к теме спектров графов и снова обратился к ней, рассмотрев уникальность треугольной схемы ассоциации в статье 1959 года, графы Мура с диаметрами 2 и 3 в 1960 году (совместно с Р. Синглтоном), многочлен графа в 1963 году, линейный граф симметричной сбалансированной неполной блочной конструкции (совместно с Рэем-Чоудхури) в 1965 году, связи между собственными значениями и раскрасками графа (в 1970 году), связи между собственными значениями и разбиениями ребер в графе в 1972 году и многое другое, включая исследование свойств матрицы инцидентности ребер и путей последовательно-параллельных графов (связанных с жадной упаковкой) с Шибером в 2002 году.
Хоффман был избран в Национальную академию наук в 1982 году, в Американскую академию искусств и наук в 1987 году и в первый класс стипендиатов INFORMS в 2002 году. За свою долгую карьеру Хоффман входил в редколлегию одиннадцати журналов и был редактором-основателем Linear Algebra and its Applications. В 1992 году вместе с Филиппом Вулфом (также из IBM) он был награжден премией Джона фон Неймана по теории ORSA и TIMS[6], предшественниками INFORMS[7]. Вручая награду, Джордж Немхаузер признал Хоффмана и Вулфа интеллектуальными лидерами группы математического программирования в IBM. Он упомянул Хоффмана за его работу в области комбинаторики и линейного программирования, а также за его раннюю работу по вычислительной эффективности симплексного метода во время его работы в NBS. В августе 2000 года Хоффман был удостоен награды Founders Award от Общества математического программирования и стал одним из 10 лауреатов (3 от IBM).
В биографии, опубликованной в выпуске журнала Linear Algebra and its Applications, посвященном Хоффману по случаю его шестидесятипятилетия, Уриэль Ротблюм написал, что «Помимо своих научных и профессиональных заслуг, Хоффман обладает непревзойденной способностью получать удовольствие от всего, что он делает. Он любит петь, играть в пинг-понг, каламбуры, остроумные истории и — возможно, больше всего на свете — заниматься математикой».
Эстер Хоффман умерла от болезни крови летом 1988 года. Алан женился на Элинор Хершафт, дизайнере интерьеров, в 1990 году. Они развелись в 2014 году. Элинор умерла в октябре 2020 года. Хоффман провел свои последние годы в доме престарелых The Osborn в городе Рай, штат Нью-Йорк. У него остались дочери, Элинор и Элизабет.
Алан Хоффман был удостоен ряда наград. [7]
{{cite book}}: CS1 maint: multiple names: authors list (link) CS1 maint: numeric names: authors list (link)