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

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

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

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

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

Карьера[2][3]

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

В 1964 году, после получения докторской степени в Беркли, он работал в Bell Telephone Laboratories в Холмделе, штат Нью-Джерси . В 1965 году его пригласили посетить программу OR Стэнфорда, а в 1966 году он стал исполняющим обязанности доцента кафедры промышленной инженерии в Стэнфорде. В следующем году он стал доцентом новой кафедры исследования операций Стэнфорда. В 1969 году он стал доцентом, а в 1973 году — полным профессором. Он возглавлял кафедру с 1990 по 1996 год. За 39 лет работы в качестве действующего преподавателя в Стэнфорде он занимал более 30 руководящих должностей на национальных и международных конференциях. Он входил в редколлегию 8 научных журналов и был главным редактором журнала Mathematical Programming. Он занимал должность заместителя председателя кафедры исследования инженерно-экономических систем и операций (EES & OR) после слияния двух кафедр. В 2000 году EES & OR снова объединились, на этот раз с Industrial Engineering & Engineering Management Department, чтобы сформировать Management Science and Engineering (MS&E). Во время своего академического отпуска в Гарварде и MIT (1970-1971) он написал «Manifestations of the Schur Complement», одну из своих самых цитируемых статей. В 1974 году он начал работать над «The Linear Complementarity Problem», одной из своих самых известных публикаций. В середине 1980-х годов двое его бывших студентов, Джонг-Ши Панг и Ричард Э. Стоун, присоединились к нему в качестве соавторов этой книги, которая была опубликована в 1992 году. «Проблема линейной дополнительности» получила премию Фредерика У. Ланчестера Института исследования операций и управленческих наук (INFORMS) в 1994 году. «Проблема линейной дополнительности» была переиздана Обществом промышленной и прикладной математики в серии «Classics in Applied Mathematics series» в 2009 году. В 1978–1979 годах он провел годичный академический отпуск в Боннском и Кельнском университетах. Там он написал статью «Наблюдения над классом проблем коварной линейной комплементарности», в которой связывает знаменитый результат Клее-Минти об экспоненциальном поведении времени симплексного метода линейного программирования с таким же поведением в алгоритме Лемке для LCP и гамильтоновых путей на n-кубе с представлением двоичным кодом Грея целых чисел от 0 до 2^n - 1. Также в это время он решил задачу минимальной триангуляции n-куба для n = 4 и работал с Марком Броди над решением ограниченного случая для n = 5. В 2006 году он был назначен членом INFORMS [5] , а в 2018 году получил премию Сола И. Гэсса за письменные пояснения.

Вклады

Линейная комплементарностьПроблема

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

Определения

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

f : R n → R n ␣ f ( x ) = q + M x {\displaystyle f:R^{n}\rightarrow R^{n}\mathrm {\textvisiblespace} f(x)=q+Mx} (1)

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

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

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

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

Публикации и прочее

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

Этот список был получен с веб-сайта. [8]

  • Ричард В. Коттл: О «доисторическом» линейном программировании и фигуре Земли. J. Optimization Theory and Applications 175(1): 255-277 (2017)
  • Илан Адлер, Ричард В. Коттл, Джонг-Ши Пан: Некоторые LCP, решаемые за сильно полиномиальное время с помощью алгоритма Лемке. Математическая программа. 160(1-2): 477-493 (2016)
  • Ричард В. Коттл: Полевое руководство по классам матриц, встречающимся в литературе по проблеме линейной дополнительности. J. Global Optimization 46(4): 571-580 (2010)
  • Ричард В. Коттл: Краткая история международных симпозиумов по математическому программированию. Математическая программа. 125(2): 207-233 (2010)
  • Ричард В. Коттл: Проблема линейной дополнительности. Энциклопедия оптимизации 2009: 1873-1878
  • Ричард В. Коттл, Ингрэм Олкин: Замкнутое решение задачи максимизации. J. Global Optimization 42(4): 609-617 (2008)
  • Ричард В. Коттл: Рецензия на книгу «Методы оптимизации и программное обеспечение» 23(5): 821-825 (2008)
  • Ричард В. Коттл: Джордж Б. Данциг: легендарная жизнь в математическом программировании. Математическая программа. 105(1): 1-8 (2006)
  • Илан Адлер, Ричард В. Коттл, Сушил Верма: Достаточные матрицы принадлежат L. Math. Program. 106(2): 391-401 (2006)
  • Ричард В. Коттл: Джордж Б. Данциг: Икона исследования операций. Исследование операций 53(6): 892-898 (2005)
  • Ричард В. Коттл: Quartic Barriers. Comp. Opt. and Appl. 12(1-3): 81-105 (1999)
  • Ричард В. Коттл: Линейные программы и смежные проблемы (Эвар Д. Неринг и Альберт В. Такер). SIAM Review 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)
  • Ричард В. Коттл: Наблюдения над классом неприятных линейных проблем дополнительности. Discrete Applied Mathematics 2(2): 89-111 (1980)
  • Yow-Yieh Chang, Richard W. Cottle: Разрешение вырождения в квадратичном программировании с наименьшим индексом. Math. Program. 18(1): 127-137 (1980)
  • Ричард В. Коттл: Журнал. Математическая программа. 19(1): 1-2 (1980)
  • Ричард В. Коттл: Полностью-матрицы. Математическая программа. 19(1): 347-351 (1980)
  • Мухамед Аганагич, Ричард В. Коттл: Заметка о Q-матрицах. Математическая программа. 16(1): 374-377 (1979)
  • Ричард В. Коттл, Джонг-Ши Пан: Теория наименьшего числа элементов для решения линейных задач дополнительности как линейных программ. Math. Oper. Res. 3(2): 155-170 (1978)
  • Ричард В. Коттл: Три замечания о двух статьях о квадратичных формах. Zeitschr. für OR 19(3): 123-124 (1975)
  • Ричард В. Коттл: Обзоры книг. Математическая программа. 4(3): 349-350 (1973)
  • Ричард В. Коттл: Монотонные решения параметрической линейной проблемы дополнительности. Математическая программа. 3(1): 210-224 (1972)
  • Ричард В. Коттл, Жак А. Ферланд: О псевдовыпуклых функциях неотрицательных переменных. Математическая программа. 1(1): 95-101 (1971)
  • Ричард В. Коттл: Письмо редактору - О выпуклости квадратичных форм над выпуклыми множествами. Operations Research 15(1): 170-172 (1967)

Членство

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

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

RW Cottle и GB Dantzig . Дополнительная теория стержня математического программирования. Линейная алгебра и ее приложения , 1:103-125, 1968

Ссылки

  1. ^ "Cottle, Richard W." purl.stanford.edu . Получено 2018-11-09 .
  2. ^ "Cottle, Richard W." purl.stanford.edu . Получено 2018-11-09 .
  3. ^ ИНФОРМИРУЕТ. "Cottle, Richard W." ИНФОРМИРУЕТ . Получено 2018-11-09 .
  4. ^ Коттл, Ричард У. (2008), «Проблема линейной дополнительности», Энциклопедия оптимизации , Springer US, стр.  1873–1878 , doi :10.1007/978-0-387-74759-0_333, ISBN 9780387747583
  5. ^ Стипендиаты: Алфавитный список, Институт исследований операций и управленческих наук , получено 09.10.2019
  6. ^ Коттл, Ричард У. (2008), «Проблема линейной дополнительности», Энциклопедия оптимизации , Springer US, стр.  1873–1878 , doi :10.1007/978-0-387-74759-0_333, ISBN 9780387747583
  7. ^ Коттл, Ричард У.; Вейнотт, Артур Ф. (декабрь 1972 г.). «Многогранные множества, имеющие наименьший элемент». Математическое программирование . 3– 3 (1): 238– 249. doi :10.1007/bf01584992. ISSN  0025-5610. S2CID  34876749.
  8. ^ "dblp: Richard W. Cottle". dblp.uni-trier.de . Получено 19 октября 2018 г. .
Retrieved from "https://en.wikipedia.org/w/index.php?title=Richard_W._Cottle&oldid=1177204375"