Ричард В. Коттл

Ричард В. Коттл
Рожденный	29 июня 1934 г. Чикаго, Иллинойс
Национальность	Американский
Альма-матер	Гарвардский колледж, Калифорнийский университет в Беркли

Ричард Коттл (29 июня 1934 г.) — американский математик . Он был профессором управления и инженерии в Стэнфордском университете, начиная с должности исполняющего обязанности доцента кафедры промышленной инженерии в 1966 году и выйдя на пенсию в 2005 году. Он известен своими работами по математическому программированию/оптимизации, « Нелинейным программам », предложению проблема линейной дополнительности и общая область исследования операций.

Жизнь и карьера

Ранняя жизнь и семья

Коттл родился в Чикаго 29 июня 1934 года в семье Чарльза и Рэйчел Коттл. Он начал свое начальное образование в соседней деревне Оук-Парк, штат Иллинойс , и окончил среднюю школу Оук-Парк-Ривер-Форест . После этого, поступив в Гарвард, Коттл начал с изучения государственного управления (политологии) и прохождения домедицинских курсов. После первого семестра он сменил специальность на математику , по которой получил степени бакалавра (с отличием) и магистра . Примерно в 1958 году он заинтересовался преподаванием математики на среднем уровне. Он поступил на математический факультет школы Миддлсекс в Конкорде, штат Массачусетс , где провёл два года. В середине последнего периода он женился на своей жене Сюзанне.

Карьера

Во время преподавания в школе Миддлсекс он подал заявку и был принят в докторантуру по математике в Калифорнийском университете в Беркли с намерением сосредоточиться на геометрии. Тем временем он также получил предложение от Радиационной лаборатории в Беркли в качестве программиста на неполный рабочий день. Благодаря этой работе, некоторые из которых включали линейное и квадратичное программирование, он узнал о работах Джорджа Данцига и Филипа Вульфа . Вскоре после этого он стал членом команды Данцига в Центре операционных исследований Калифорнийского университета в Беркли (ORC). Там у него была возможность исследовать квадратичное и выпуклое программирование. Это переросло в его докторскую диссертацию под руководством Данцига и Эдмунда Айзенбергов. Первый исследовательский вклад Коттла «Симметричные двойственные квадратичные программы» был опубликован в 1963 году. Вскоре он был обобщен в совместной статье «Симметричные двойные нелинейные программы», написанной в соавторстве с Данцигом и Айзенбергом. Это привело к рассмотрению так называемой «составной задачи» — условий оптимальности первого порядка для симметричных двойственных программ. Это, в свою очередь, было названо «фундаментальной проблемой», а еще позже (в более общем контексте) «проблемой дополнительности». Частный случай этого, называемый «проблемой линейной дополнительности». является основной частью результатов исследований Коттла. Также в 1963 году он был летним консультантом в корпорации RAND, работая под руководством Филипа Вулфа. Результатом этого стал меморандум RAND, RM-3858-PR, «Теорема Фрица Джона в математическом программировании».

В 1964 году, после получения докторской степени в Беркли, он работал в Bell Telephone Laboratories в Холмделе, штат Нью-Джерси . В 1965 году его пригласили посетить Стэнфордскую программу операционной, а в 1966 году он стал исполняющим обязанности доцента кафедры промышленной инженерии в Стэнфорде. В следующем году он стал доцентом нового факультета исследования операций Стэнфорда. Он стал доцентом в 1969 году и профессором в 1973 году. Он возглавлял кафедру с 1990 по 1996 год. За 39 лет работы на факультете Стэнфорда он сыграл более 30 руководящих должностей на национальных и международных конференциях. Он входил в редакционную коллегию 8 научных журналов и был главным редактором журнала «Математическое программирование». Он занимал должность заместителя председателя Департамента инженерно-экономических систем и исследований операций (EES & OR) после слияния двух отделов. В 2000 году EES & OR снова объединились, на этот раз с Департаментом промышленной инженерии и инженерного менеджмента, и образовали Management Science and Engineering (MS&E). Во время своего творческого отпуска в Гарварде и Массачусетский технологический институт (1970-1971) он написал «Проявления дополнения Шура», одну из его наиболее цитируемых статей. В 1974 году он начал работать над «Проблемой линейной дополнительности», одной из самых известных его публикаций. В середине 1980-х годов двое его бывших учеников, Чон-Ши Панг и Ричард Э. Стоун, присоединились к нему в качестве соавторов этой книги, которая была опубликована в 1992 году. «Проблема линейной дополнительности» получила Фредерика В. Ланчестера премию в Институте исследования операций и наук управления (ИНФОРМС) в 1994 году. «Проблема линейной дополнительности» была переиздана Обществом промышленной и прикладной математики в серии «Классика в серии прикладной математики» в 2009 году. В 1978–1979 годах он провел творческий год в Боннском и Кельнском университетах. Там он написал статью «Наблюдения над классом неприятных проблем линейной дополнительности», в которой связывает знаменитый результат Кли-Минти об экспоненциальном поведении во времени симплексного метода линейного программирования с таким же поведением в алгоритме Лемке для LCP и гамильтоновы пути на n-кубе с двоичным кодом Грея, представляющим целые числа от 0 до 2^n - 1. Также в это время он решил проблему минимальной триангуляции n-куба для n = 4 и работал с Марком Броди над решить ограниченный случай для n = 5. В 2006 году он был назначен научным сотрудником ИНФОРМСА. а в 2018 году получил премию Сола И. Гасса за разъяснительные работы.

Взносы

линейной дополнительности Проблема

Коттл наиболее известен своими обширными публикациями по проблеме линейной дополнительности (LCP). Эта работа включает в себя аналитические исследования, алгоритмы и взаимодействие теории матриц и теории линейного неравенства с LCP. Во многом это результат его докторской диссертации под руководством Джорджа Данцига, с которым он сотрудничал в некоторых из своих первых статей. Ярким примером является «Дополнительная теория поворотов математического программирования», опубликованная в 1968 году.

Определения

Стандартной формой LCP является отображение:

$f:R^{n}\rightarrow R^{n}\mathrm {\textvisiblespace} f(x)=q+Mx$ (1)

Данный $f$, найдите вектор $x\in R^{n}$ , такой, что $x_{i}\geq 0$, $f_{i}(x)\geq 0$ и $x_{i}f_{i}(x)=0$, для $i=1,2,...,n$

Поскольку аффинное отображение f задается вектором и матрицей, проблема обычно обозначается LCP( q , M ) или иногда просто ( q , M ). Система вида (1), в которой f не аффинна, называется нелинейной задачей дополнительности и обозначается NCP( $f$). Обозначение CP( $f$) предназначен для охвата обоих случаев».

Многогранные множества, имеющие наименьший элемент

Согласно статье Коттла и Вейнотта: «Для фиксированного m $\times$ n матрицы A , рассмотрим семейство многогранных множеств $X_{b}=\{x|Ax\geq b\},\mathrm {\textvisiblespace} b\in R_{m}$ и докажите теорему, характеризующую в терминах A обстоятельства, при которых каждый непустой X_b имеет наименьший элемент. В особом случае, когда A содержит все строки n $\times$ n единичная матрица, условия эквивалентны тому, что A^T является Леонтьевым.

Публикации и другое

Публикации и профессиональная деятельность

Этот список был получен с сайта.

• Ричард В. Коттл: О «доисторическом» линейном программировании и фигуре Земли. J. Теория оптимизации и приложения 175 (1): 255-277 (2017)
• Илан Адлер, Ричард В. Коттл, Чон-Ши Панг: Некоторые LCP, решаемые за сильно полиномиальное время с помощью алгоритма Лемке. Математика. Программа. 160(1-2): 477-493 (2016)
• Ричард В. Коттл: Полевое руководство по матричным классам, найденным в литературе по проблеме линейной дополнительности. Дж. Глобальная оптимизация 46(4): 571-580 (2010).
• Ричард В. Коттл: Краткая история международных симпозиумов по математическому программированию. Математика. Программа. 125(2): 207-233 (2010)
• Ричард В. Коттл: Проблема линейной дополнительности. Энциклопедия оптимизации 2009: 1873–1878 гг.
• Ричард В. Коттл, Ингрэм Олкин: Решение задачи максимизации в закрытой форме. Дж. Глобальная оптимизация 42(4): 609-617 (2008).
• Ричард В. Коттл: Рецензия на книгу. Методы оптимизации и программное обеспечение 23(5): 821-825 (2008).
• Ричард В. Коттл: Джордж Б. Данциг: легендарная жизнь в области математического программирования. Математика. Программа. 105(1): 1-8 (2006)
• Илан Адлер, Ричард В. Коттл, Сушил Верма: Достаточно матриц принадлежат Л. Математику. Программа. 106(2): 391-401 (2006).
• Ричард В. Коттл: Джордж Б. Данциг: символ исследования операций. Исследование операций 53(6): 892-898 (2005).
• Ричард В. Коттл: Четвертичные барьеры. Комп. Опция и прил. 12(1-3): 81-105 (1999)
• Ричард В. Коттл: Линейные программы и связанные с ними проблемы (Эвар Д. Неринг и Альберт В. Такер). Обзор SIAM 36 (4): 666-668 (1994).
• Ричард В. Коттл: новый взгляд на основной метод поворота. Математика. Программа. 48: 369-385 (1990)
• Мухамед Аганагич, Ричард В. Коттл: Конструктивная характеристика Q _o -матриц с неотрицательными главными минорами. Математика. Программа. 37(2): 223-231 (1987).
• Марк Броуди, Ричард В. Коттл: Примечание о триангуляции 5-куба. Дискретная математика 52 (1): 39-49 (1984)
• Ричард В. Коттл, Ричард Э. Стоун: О единственности решений задач линейной дополнительности. Математика. Программа. 27(2): 191-213 (1983)
• Ричард В. Коттл: Минимальная триангуляция 4-куба. Дискретная математика 40 (1): 25-29 (1982)
• Ричард В. Коттл: Наблюдения над классом неприятных проблем линейной дополнительности. Дискретная прикладная математика 2 (2): 89-111 (1980).
• Йоу-Йе Чанг, Ричард В. Коттл: Разрешение вырождения по методу наименьшего индекса в квадратичном программировании. Математика. Программа. 18(1): 127-137 (1980)
• Ричард В. Коттл: Журнал. Математика. Программа. 19(1): 1-2 (1980)
• Ричард В. Коттл: Полностью матрицы. Математика. Программа. 19(1): 347-351 (1980).
• Мухамед Аганагич, Ричард В. Коттл: Примечание о Q-матрицах. Математика. Программа. 16(1): 374-377 (1979)
• Ричард В. Коттл, Чон-Ши Панг: Теория наименьших элементов решения проблем линейной дополнительности с помощью линейных программ. Математика. Опер. Рез. 3 (2): 155–170 (1978)
• Ричард В. Коттл: Три замечания о двух статьях о квадратичных формах. Цайтшр. для OR 19(3): 123-124 (1975)
• Ричард В. Коттл: Рецензии на книги. Математика. Программа. 4 (3): 349–350 (1973)
• Ричард В. Коттл: Монотонные решения параметрической проблемы линейной дополнительности. Математика. Программа. 3 (1): 210–224 (1972)
• Ричард В. Коттл, Жак А. Ферланд: О псевдовыпуклых функциях неотрицательных переменных. Математика. Программа. 1(1): 95-101 (1971)
• Ричард В. Коттл: Письмо в редакцию - О выпуклости квадратичных форм над выпуклыми множествами. Исследование операций 15 (1): 170–172 (1967).

Членство

1. Международное общество линейной алгебры 1989–2005.
2. Общество математики, экономики и исследования операций 1984–1998 гг.
3. Общество математического программирования 1970 г.
4. ИНФОРМ 1995 г.
5. Институт управленческих наук 1967–1995 гг.
6. Американское общество исследования операций, 1962–1995 гг.
7. Общество промышленной и прикладной математики 1966 г.
8. Математическая ассоциация Америки 1958-2017 гг.
9. Американское математическое общество, 1958 г.

Дальнейшее чтение

Р.В. Коттл и Г.Б. Данциг . Дополнительная теория математического программирования. Линейная алгебра и ее приложения , 1: 103–125, 1968.