Richarda W. Cottle'a

Richarda W. Cottle'a
Urodzić się	29 czerwca 1934 r Chicago, Illinois
Narodowość	amerykański
Alma Mater	Harvard College, Uniwersytet Kalifornijski w Berkeley

Richard W. Cottle (29 czerwca 1934) to amerykański matematyk . Był profesorem Nauk o Zarządzaniu i Inżynierii na Uniwersytecie Stanforda, zaczynając jako Adiunkt Inżynierii Przemysłowej w 1966 i przechodząc na emeryturę w 2005. Znany jest ze swojej pracy nad programowaniem/optymalizacją matematyczną, „Programami nieliniowymi” , propozycją problem komplementarności liniowej i ogólny obszar badań operacyjnych.

życie i kariera

Wczesne życie i rodzina

Richard W. Cottle urodził się w Chicago 29 czerwca 1934 r. Jako syn Charlesa i Rachel Cottle. Rozpoczął swoją podstawową edukację w sąsiedniej wiosce Oak Park w stanie Illinois i ukończył Oak Park-River Forest High School . Po tym, przyjęty na Harvard, Cottle zaczął studiować rząd (nauki polityczne) i brać udział w kursach przedmedycznych. Po pierwszym semestrze zmienił specjalizację na matematykę , na której uzyskał tytuł licencjata (cum laude) i magistra . Około 1958 roku zainteresował się nauczaniem matematyki na poziomie średnim. Wstąpił do Wydziału Matematyki w Szkole Middlesex w Concord, Massachusetts , gdzie spędził dwa lata. W połowie tego ostatniego okresu poślubił swoją żonę Suzanne.

Kariera

Podczas nauczania w Middlesex School złożył podanie i został przyjęty na studia doktoranckie z matematyki na Uniwersytecie Kalifornijskim w Berkeley z zamiarem skupienia się na geometrii. W międzyczasie otrzymał również ofertę z Radiation Laboratory w Berkeley jako programista komputerowy w niepełnym wymiarze godzin. Dzięki tej pracy, z których część obejmowała programowanie liniowe i kwadratowe, dowiedział się o pracach George'a Dantziga i Philipa Wolfe'a . Wkrótce potem został członkiem zespołu Dantziga w UC Berkeley Operations Research Center (ORC). Tam miał okazję zbadać programowanie kwadratowe i wypukłe. To przekształciło się w jego rozprawę doktorską pod kierunkiem Dantziga i Edmunda Eisenberga. Pierwszy wkład badawczy Cottle'a, „Symetryczne podwójne programy kwadratowe”, został opublikowany w 1963 r. Zostało to wkrótce uogólnione we wspólnym artykule „Symetryczne podwójne programy nieliniowe”, którego współautorem byli Dantzig i Eisenberg. Doprowadziło to do rozważenia tak zwanego „problemu złożonego”, warunków optymalności pierwszego rzędu dla symetrycznych programów dualnych. To z kolei nazwano „problemem podstawowym”, a jeszcze później (w bardziej ogólnym kontekście) „problemem komplementarności”. Szczególny przypadek tego, zwany „problemem liniowej komplementarności”, stanowi znaczną część dorobku badawczego Cottle'a. Również w 1963 roku był letnim konsultantem w RAND Corporation pracującym pod nadzorem Philipa Wolfe'a. Doprowadziło to do powstania notatki RAND, RM-3858-PR, „Twierdzenie Fritza Johna w programowaniu matematycznym”.

W 1964 roku, po ukończeniu doktoratu w Berkeley, pracował dla Bell Telephone Laboratories w Holmdel, New Jersey . W 1965 roku został zaproszony do odwiedzenia Stanford's OR Program, aw 1966 został Aktorem na Wydziale Inżynierii Przemysłowej na Uniwersytecie Stanforda. W następnym roku został adiunktem w nowym Wydziale Badań Operacyjnych Stanforda. Został profesorem nadzwyczajnym w 1969 r., a profesorem zwyczajnym w 1973 r. Kierował katedrą od 1990 do 1996 r. W ciągu 39 lat aktywnego wydziału w Stanford pełnił ponad 30 funkcji kierowniczych na konferencjach krajowych i międzynarodowych. Zasiadał w radach redakcyjnych 8 czasopism naukowych i był redaktorem naczelnym czasopisma Mathematical Programming. Pełnił funkcję zastępcy przewodniczącego Wydziału Inżynierii-Ekonomicznych Systemów i Badań Operacyjnych (EES & OR) po połączeniu obu wydziałów. W 2000 roku EES & OR ponownie połączyło się, tym razem z Wydziałem Inżynierii Przemysłowej i Zarządzania Inżynierią, tworząc Management Science and Engineering (MS&E). Podczas swojego roku urlopowego na Harvardzie i MIT (1970-1971), napisał „Manifestations of the Schur Complement”, jeden z najczęściej cytowanych artykułów. W 1974 roku rozpoczął pracę nad „Problemem liniowej komplementarności”, jedną z jego najbardziej znanych publikacji. W połowie lat 80. dwóch jego byłych uczniów, Jong-Shi Pang i Richard E. Stone, dołączyło do niego jako współautorzy tej książki, która została opublikowana w 1992 r. „Problem liniowej komplementarności” zdobył nagrodę im. Fredericka W. Lanchestera Instytutu Badań Operacyjnych i Nauk o Zarządzaniu (INFORMS) w 1994 r. „The Linear Complementarity Problem” został ponownie opublikowany przez Society for Industrial and Applied Mathematics w serii „Classics in Applied Mathematics” w 2009 r. W latach 1978–1979 spędził rok naukowy na Uniwersytecie w Bonn i Uniwersytecie w Kolonii. Tam napisał artykuł „Observations on a Class of Nasty Linear Complementarity Problems”, w którym powiązał słynny wynik Klee-Minty'ego dotyczący wykładniczego zachowania metody simplex programowania liniowego z tym samym rodzajem zachowania w algorytmie Lemkego dla LCP i ścieżki hamiltonowskie na n-sześcianie z reprezentacją liczb całkowitych w kodzie binarnym Graya od 0 do 2^n - 1. Również w tym czasie rozwiązał problem minimalnej triangulacji n-sześcianu dla n = 4 i pracował z Markiem Broadiem nad rozwiązać ograniczony przypadek dla n = 5. W 2006 roku został mianowany członkiem INFORMS, aw 2018 roku otrzymał nagrodę Saul I. Gass Expository Writing Award.

Składki

Problem komplementarności liniowej

Cottle jest najbardziej znany ze swoich obszernych publikacji na temat problemu liniowej komplementarności (LCP). Ta praca obejmuje badania analityczne, algorytmy i interakcje teorii macierzy i teorii nierówności liniowych z LCP. Wiele z tego jest następstwem jego rozprawy doktorskiej, której promotorem był George Dantzig, z którym współpracował przy niektórych ze swoich najwcześniejszych prac. Wiodącym przykładem jest „Komplementarna teoria obrotu w programowaniu matematycznym”, opublikowana w 1968 roku.

Definicje

Standardową formą LCP jest mapowanie:

${\ Displaystyle f: R ^ {n} \ strzałka w prawo R ^ {n} \ operatorname {\ textvisiblespace} f (x) = q + Mx}$ ( 1)

Biorąc $)$ , znajdź wektor taki, że ${\ Displaystyle x \ w R ^ {n}} ,$$f_{i}(x)\geq 0$${\ Displaystyle x_ {i} \ geq$, and $x_{i}f_{i}(x)=0$, for ${\ Displaystyle i = 1,2, ..., n$

Ponieważ odwzorowanie afiniczne f jest określone przez wektor i macierz, problem jest zwykle oznaczany jako LCP( q , M ) lub czasami po prostu ( q , M ). Układ o postaci (1), w którym f nie jest afiniczny, nazywany jest nieliniowym problemem komplementarności i oznaczany jako NCP ( ${\ displaystyle f}$ ). Notacja CP ( $ma$ obejmować oba przypadki”.

Zestawy wielościenne mające najmniejszy element

Według artykułu Cottle'a i Veinotta: „Dla ustalonej macierzy $A$ , rozważamy rodzinę $zbiorów$ { których każdy niepusty X_b ma najmniejszy element. W szczególnym przypadku, gdy A zawiera wszystkie wiersze $macierzy identyczności$ n A , warunki są równoważne temu, że ^ T to .

Publikacje i inne

Publikacje i działalność zawodowa

Ta lista została pobrana ze strony internetowej.

• Richard W. Cottle: O „prehistorycznym” programowaniu liniowym i kształcie Ziemi. J. Teoria optymalizacji i zastosowania 175(1): 255-277 (2017)
• Ilan Adler, Richard W. Cottle, Jong-Shi Pang: Niektóre LCP rozwiązywalne w silnie wielomianowym czasie za pomocą algorytmu Lemkego. Matematyka Program. 160(1-2): 477-493 (2016)
• Richard W. Cottle: Przewodnik po klasach macierzy występujących w literaturze dotyczącej problemu liniowej komplementarności. J. Globalna optymalizacja 46 (4): 571-580 (2010)
• Richard W. Cottle: Krótka historia Międzynarodowych Sympozjów Programowania Matematycznego. Matematyka Program. 125(2): 207-233 (2010)
• Richard W. Cottle: Problem liniowej komplementarności. Encyklopedia optymalizacji 2009: 1873-1878
• Richard W. Cottle, Ingram Olkin: Zamknięte rozwiązanie problemu maksymalizacji. J. Globalna optymalizacja 42 (4): 609-617 (2008)
• Richard W. Cottle: Recenzja książki. Metody optymalizacji i oprogramowanie 23(5): 821-825 (2008)
• Richard W. Cottle: George B. Dantzig: legendarne życie w programowaniu matematycznym. Matematyka Program. 105(1): 1-8 (2006)
• Ilan Adler, Richard W. Cottle, Sushil Verma: Wystarczające macierze należą do L. Math. Program. 106(2): 391-401 (2006)
• Richard W. Cottle: George B. Dantzig: ikona badań operacyjnych. Badania operacyjne 53(6): 892-898 (2005)
• Richard W. Cottle: Bariery kwarcowe. Komp. Optować. i Appl. 12(1-3): 81-105 (1999)
• Richard W. Cottle: programy liniowe i powiązane problemy (Evar D. Nering i Albert W. Tucker). Przegląd SIAM 36 (4): 666-668 (1994)
• Richard W. Cottle: powrót do głównej metody obracania. Matematyka Program. 48: 369-385 (1990)
• Muhamed Aganagic, Richard W. Cottle: Konstruktywna charakterystyka macierzy Qo _z nieujemnymi głównymi nieletnimi. Matematyka Program. 37(2): 223-231 (1987)
• Mark Broadie, Richard W. Cottle: Uwaga na temat triangulacji kostki 5. Matematyka dyskretna 52(1): 39-49 (1984)
• Richard W. Cottle, Richard E. Stone: O wyjątkowości rozwiązań problemów liniowej komplementarności. Matematyka Program. 27(2): 191-213 (1983)
• Richard W. Cottle: Minimalna triangulacja 4-sześcianu. Matematyka dyskretna 40(1): 25-29 (1982)
• Richard W. Cottle: Obserwacje klasy paskudnych problemów z liniową komplementarnością. Dyskretna matematyka stosowana 2 (2): 89-111 (1980)
• Yow-Yieh Chang, Richard W. Cottle: rozdzielczość najmniejszego indeksu degeneracji w programowaniu kwadratowym. Matematyka Program. 18(1): 127-137 (1980)
• Richard W. Cottle: Dziennik. Matematyka Program. 19(1): 1-2 (1980)
• Richard W. Cottle: Całkowicie – macierze. Matematyka Program. 19(1): 347-351 (1980)
• Muhamed Aganagic, Richard W. Cottle: Uwaga na temat macierzy Q. Matematyka Program. 16(1): 374-377 (1979)
• Richard W. Cottle, Jong-Shi Pang: najmniej elementowa teoria rozwiązywania problemów liniowej komplementarności jako programy liniowe. Matematyka Oper. Rez. 3(2): 155-170 (1978)
• Richard W. Cottle: Trzy uwagi na temat dwóch artykułów na temat form kwadratowych. Zeitschr. für OR 19(3): 123-124 (1975)
• Richard W. Cottle: recenzje książek. Matematyka Program. 4(3): 349-350 (1973)
• Richard W. Cottle: Monotoniczne rozwiązania problemu parametrycznej komplementarności liniowej. Matematyka Program. 3(1): 210-224 (1972)
• Richard W. Cottle, Jacques A. Ferland: O funkcjach pseudowypukłych zmiennych nieujemnych. Matematyka Program. 1(1): 95-101 (1971)
• Richard W. Cottle: List do redakcji - O wypukłości form kwadratowych nad zbiorami wypukłymi. Badania operacyjne 15 (1): 170-172 (1967)

Członkostwo

1. Międzynarodowe Towarzystwo Algebry Liniowej 1989–2005.
2. Gesellschaft für Mathematik, Ökonomie, und Operations Research 1984–1998
3. Towarzystwo Programowania Matematycznego 1970
4. INFORMUJE 1995
5. Instytut Nauk o Zarządzaniu 1967-1995
6. Towarzystwo Badań Operacyjnych Ameryki 1962–1995
7. Towarzystwo Matematyki Przemysłowej i Stosowanej 1966
8. Amerykańskie Stowarzyszenie Matematyczne 1958-2017
9. Amerykańskie Towarzystwo Matematyczne 1958

Dalsza lektura

RW Cottle i GB Dantzig . Uzupełniająca teoria przestawna programowania matematycznego. Algebra liniowa i jej zastosowania , 1:103-125, 1968