Richard W. Cottle

Richard W. Cottle (29 June 1934) is an American mathematician. He was a professor of Management Science and Engineering at Stanford University, starting as an Acting Assistant Professor of Industrial Engineering in 1966 and retiring in 2005. He is notable for his work on mathematical programming/optimization, “Nonlinear programs”, the proposal of the linear complementarity problem, and the general field of operations research.

Richard W. Cottle
Born	29 June 1934 Chicago, Illinois
Nationality	American
Alma mater	Harvard College, University of California at Berkeley

Life and career

Early life and family

Cottle was born in Chicago on 29 June 1934 to Charles and Rachel Cottle. He started his elementary education in the neighboring village of Oak Park, Illinois, and graduated from Oak Park-River Forest High School. After that, admitted to Harvard, Cottle began by studying government (political science) and taking premedical courses. After the first semester, he changed his major to mathematics in which he earned his bachelor's (cum laude) and master's degrees. Around 1958, he became interested in teaching secondary-level mathematics. He joined the Mathematics Department at the Middlesex School in Concord, Massachusetts, where he spent two years. Midway through the latter period, he married his wife, Suzanne.

Career

While teaching at Middlesex School, he applied and was admitted to the PhD program in mathematics at the University of California at Berkeley, with the intention of focusing on geometry. Meanwhile, he also received an offer from the Radiation Laboratory at Berkeley as a part-time computer programmer. Through that work, some of which involved linear and quadratic programming, he became aware of the work of George Dantzig and Philip Wolfe. Soon thereafter he became a member of Dantzig's team at UC Berkeley Operations Research Center (ORC). There he had the opportunity to investigate quadratic and convex programming. This developed into his doctoral dissertation under the guidance of Dantzig and Edmund Eisenberg. Cottle's first research contribution, "Symmetric Dual Quadratic Programs," was published in 1963. This was soon generalized in the joint paper "Symmetric Dual Nonlinear Programs," co-authored with Dantzig and Eisenberg. This led to the consideration of what is called a "composite problem," the first-order optimality conditions for symmetric dual programs. This in turn, was named "the fundamental problem" and still later (in a more general context) "the complementarity problem." A special case of this, called "the linear complementarity problem", is a major part of Cottle's research output. Also in 1963, he was a summer consultant at the RAND Corporation working under the supervision of Philip Wolfe. This resulted in the RAND Memo, RM-3858-PR, "A Theorem of Fritz John in Mathematical Programming."

In 1964, upon completion of his doctorate at Berkeley, he worked for Bell Telephone Laboratories in Holmdel, New Jersey. In 1965, he was invited to visit Stanford's OR Program, and in 1966, he became an Acting Assistant Professor of Industrial Engineering at Stanford. The next year he became an Assistant Professor in Stanford's new Department of Operations Research. He became an Associate Professor in 1969 and Full Professor in 1973. He chaired the department from 1990 to 1996. During 39 years on the active faculty at Stanford he had over 30 leadership roles in national and international conferences. He served on the editorial board of 8 scholarly journals, and was Editor-in-Chief of the journal, Mathematical Programming. He served as the associate chair of the Engineering-Economic Systems & Operations Research Department (EES & OR) after the merger of the two departments. In 2000, EES & OR merged again, this time with the Industrial Engineering & Engineering Management Department to form Management Science and Engineering (MS&E). During his sabbatical year at Harvard and MIT (1970-1971), he wrote “Manifestations of the Schur Complement’’, one of his most cited papers. In 1974, he started working on “The Linear Complementarity Problem,” one his most noted publications. In the mid 1980s, two of his former students, Jong-Shi Pang and Richard E. Stone, joined him as co-authors of this book which was published in 1992. “The Linear Complementarity Problem” won the Frederick W. Lanchester Prize of the Institute for Operations Research and the Management Sciences (INFORMS) in 1994. “The Linear Complementarity Problem” was republished by the Society for Industrial and Applied Mathematics in the series “Classics in Applied Mathematics series” in 2009. During 1978–1979, he spent a sabbatical year at the University of Bonn and the University of Cologne. There he wrote the paper “Observations on a Class of Nasty Linear Complementarity Problems’’ which relates the celebrated Klee-Minty result on the exponential time behavior of the simplex method of linear programming with the same sort of behavior in Lemke's algorithm for the LCP and hamiltonian paths on the n-cube with the binary Gray code representation of the integers from 0 to 2^n - 1. Also during this time he solved the problem of minimally triangulating the n-cube for n = 4 and worked with Mark Broadie to solve a restricted case for n = 5. In 2006 he was appointed a fellow of INFORMS and in 2018 received the Saul I. Gass Expository Writing Award.

Contributions

Linear complementarity Problem

Cottle is best known for his extensive publications on the Linear Complementarity Problem (LCP). This work includes analytical studies, algorithms, and the interaction of matrix theory and linear inequality theory with the LCP. Much of this is an outgrowth of his doctoral dissertation supervised by George Dantzig, with whom he collaborated in some of his earliest papers. The leading example is "Complementary pivot theory of mathematical programming," published in 1968.

Definitions

The standard form of the LCP is a mapping:

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

Given $f$, find a vector $x\in R^{n}$ , such that $x_{i}\geq 0$, $f_{i}(x)\geq 0$ and $x_{i}f_{i}(x)=0$, for $i=1,2,...,n$

Because the affine mapping f is specified by vector and matrix, the problem is ordinarily denoted LCP(q, M) or sometimes just (q, M). A system of the form (1) in which f is not affine is called a nonlinear complementarity problem and is denoted NCP($f$). The notation CP($f$) is meant to cover both cases."

Polyhedral sets having a least element

According to a paper by Cottle and Veinott: "For a fixed m $\times$ n matrix A, we consider the family of polyhedral sets $X_{b}=\{x|Ax\geq b\},\mathrm {\textvisiblespace} b\in R_{m}$ , and prove a theorem characterizing, in terms of A, the circumstances under which every nonempty X_b has a least element. In the special case where A contains all the rows of an n $\times$ n identity matrix, the conditions are equivalent to A^T being Leontief.

Publications and others

Publications and Professional Activities

This list has been retrieved from the website.

• Richard W. Cottle: On "Pre-historic" Linear Programming and the Figure of the Earth. J. Optimization Theory and Applications 175(1): 255-277 (2017)
• Ilan Adler, Richard W. Cottle, Jong-Shi Pang: Some LCPs solvable in strongly polynomial time with Lemke's algorithm. Math. Program. 160(1-2): 477-493 (2016)
• Richard W. Cottle: A field guide to the matrix classes found in the literature of the linear complementarity problem. J. Global Optimization 46(4): 571-580 (2010)
• Richard W. Cottle: A brief history of the International Symposia on Mathematical Programming. Math. Program. 125(2): 207-233 (2010)
• Richard W. Cottle: Linear Complementarity Problem. Encyclopedia of Optimization 2009: 1873-1878
• Richard W. Cottle, Ingram Olkin: Closed-form solution of a maximization problem. J. Global Optimization 42(4): 609-617 (2008)
• Richard W. Cottle: Book Review. Optimization Methods and Software 23(5): 821-825 (2008)
• Richard W. Cottle: George B. Dantzig: a legendary life in mathematical programming. Math. Program. 105(1): 1-8 (2006)
• Ilan Adler, Richard W. Cottle, Sushil Verma: Sufficient matrices belong to L. Math. Program. 106(2): 391-401 (2006)
• Richard W. Cottle: George B. Dantzig: Operations Research Icon. Operations Research 53(6): 892-898 (2005)
• Richard W. Cottle: Quartic Barriers. Comp. Opt. and Appl. 12(1-3): 81-105 (1999)
• Richard W. Cottle: Linear Programs and Related Problems (Evar D. Nering and Albert W. Tucker). SIAM Review 36(4): 666-668 (1994)
• Richard W. Cottle: The Principal Pivoting Method Revisited. Math. Program. 48: 369-385 (1990)
• Muhamed Aganagic, Richard W. Cottle: A constructive characterization of Q_o-matrices with nonnegative principal minors. Math. Program. 37(2): 223-231 (1987)
• Mark Broadie, Richard W. Cottle: A note on triangulating the 5-cube. Discrete Mathematics 52(1): 39-49 (1984)
• Richard W. Cottle, Richard E. Stone: On the uniqueness of solutions to linear complementarity problems. Math. Program. 27(2): 191-213 (1983)
• Richard W. Cottle: Minimal triangulation of the 4-cube. Discrete Mathematics 40(1): 25-29 (1982)
• Richard W. Cottle: Observations on a class of nasty linear complementarity problems. Discrete Applied Mathematics 2(2): 89-111 (1980)
• Yow-Yieh Chang, Richard W. Cottle: Least-index resolution of degeneracy in quadratic programming. Math. Program. 18(1): 127-137 (1980)
• Richard W. Cottle: The journal. Math. Program. 19(1): 1-2 (1980)
• Richard W. Cottle: Completely- matrices. Math. Program. 19(1): 347-351 (1980)
• Muhamed Aganagic, Richard W. Cottle: A note on Q-matrices. Math. Program. 16(1): 374-377 (1979)
• Richard W. Cottle, Jong-Shi Pang: A Least-Element Theory of Solving Linear Complementarity Problems as Linear Programs. Math. Oper. Res. 3(2): 155-170 (1978)
• Richard W. Cottle: Three remarks about two papers on quadratic forms. Zeitschr. für OR 19(3): 123-124 (1975)
• Richard W. Cottle: Book reviews. Math. Program. 4(3): 349-350 (1973)
• Richard W. Cottle: Monotone solutions of the parametric linear complementarity problem. Math. Program. 3(1): 210-224 (1972)
• Richard W. Cottle, Jacques A. Ferland: On pseudo-convex functions of nonnegative variables. Math. Program. 1(1): 95-101 (1971)
• Richard W. Cottle: Letter to the Editor - On the Convexity of Quadratic Forms Over Convex Sets. Operations Research 15(1): 170-172 (1967)

Membership

1. International Linear Algebra Society 1989–2005.
2. Gesellschaft für Mathematik, Ökonomie, und Operations Research 1984–1998
3. Mathematical Programming Society 1970
4. INFORMS 1995
5. The Institute of Management Sciences 1967–1995
6. Operations Research Society of America 1962–1995
7. Society for Industrial and Applied Mathematics 1966
8. Mathematical Association of America 1958-2017
9. American Mathematical Society 1958

Further reading

R. W. Cottle and G. B. Dantzig. Complementary pivot theory of mathematical programming. Linear Algebra and its Applications, 1:103-125, 1968