![]() | This article has multiple issues. Please help improve it or discuss these issues on the talk page . (Learn how and when to remove these template messages)
|
Richard W. Cottle | |
---|---|
![]() | |
Born | 29 June 1934 Chicago, Illinois |
Nationality | American |
Alma mater | Harvard College, University of California at Berkeley |
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.
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. [1]
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", [4] 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 [5] and in 2018 received the Saul I. Gass Expository Writing Award.
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.
The standard form of the LCP is a mapping:
(1)
Given , find a vector , such that , and , for
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(). The notation CP() is meant to cover both cases." [6]
According to a paper by Cottle and Veinott: "For a fixed mn matrix A, we consider the family of polyhedral sets , 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 n identity matrix, the conditions are equivalent to A^T being Leontief. [7]
This list has been retrieved from the website. [8]
R. W. Cottle and G. B. Dantzig. Complementary pivot theory of mathematical programming. Linear Algebra and its Applications, 1:103-125, 1968
George Bernard Dantzig was an American mathematical scientist who made contributions to industrial engineering, operations research, computer science, economics, and statistics.
Linear algebra is the branch of mathematics concerning linear equations such as:
Quadratic programming (QP) is the process of solving certain mathematical optimization problems involving quadratic functions. Specifically, one seeks to optimize a multivariate quadratic function subject to linear constraints on the variables. Quadratic programming is a type of nonlinear programming.
Linear programming (LP), also called linear optimization, is a method to achieve the best outcome in a mathematical model whose requirements are represented by linear relationships. Linear programming is a special case of mathematical programming.
Mathematical optimization or mathematical programming is the selection of a best element, with regard to some criterion, from some set of available alternatives. It is generally divided into two subfields: discrete optimization and continuous optimization. Optimization problems arise in all quantitative disciplines from computer science and engineering to operations research and economics, and the development of solution methods has been of interest in mathematics for centuries.
In mathematical optimization, Dantzig's simplex algorithm is a popular algorithm for linear programming.
In mathematics, a unimodular matrixM is a square integer matrix having determinant +1 or −1. Equivalently, it is an integer matrix that is invertible over the integers: there is an integer matrix N that is its inverse. Thus every equation Mx = b, where M and b both have integer components and M is unimodular, has an integer solution. The n × n unimodular matrices form a group called the n × n general linear group over , which is denoted .
Basic Linear Algebra Subprograms (BLAS) is a specification that prescribes a set of low-level routines for performing common linear algebra operations such as vector addition, scalar multiplication, dot products, linear combinations, and matrix multiplication. They are the de facto standard low-level routines for linear algebra libraries; the routines have bindings for both C and Fortran. Although the BLAS specification is general, BLAS implementations are often optimized for speed on a particular machine, so using them can bring substantial performance benefits. BLAS implementations will take advantage of special floating point hardware such as vector registers or SIMD instructions.
In mathematical optimization theory, the linear complementarity problem (LCP) arises frequently in computational mechanics and encompasses the well-known quadratic programming as a special case. It was proposed by Cottle and Dantzig in 1968.
The quadratic assignment problem (QAP) is one of the fundamental combinatorial optimization problems in the branch of optimization or operations research in mathematics, from the category of the facilities location problems first introduced by Koopmans and Beckmann.
In mathematics, a Q-matrix is a square matrix whose associated linear complementarity problem LCP(M,q) has a solution for every vector q.
Semidefinite programming (SDP) is a subfield of convex optimization concerned with the optimization of a linear objective function over the intersection of the cone of positive semidefinite matrices with an affine space, i.e., a spectrahedron.
A second-order cone program (SOCP) is a convex optimization problem of the form
In mathematics, a P-matrix is a complex square matrix with every principal minor is positive. A closely related class is that of -matrices, which are the closure of the class of P-matrices, with every principal minor 0.
A complementarity problem is a type of mathematical optimization problem. It is the problem of optimizing (minimizing or maximizing) a function of two vector variables subject to certain requirements (constraints) which include: that the inner product of the two vectors must equal zero, i.e. they are orthogonal. In particular for finite-dimensional real vector spaces this means that, if one has vectors X and Y with all nonnegative components (xi ≥ 0 and yi ≥ 0 for all : in the first quadrant if 2-dimensional, in the first octant if 3-dimensional), then for each pair of components xi and yi one of the pair must be zero, hence the name complementarity. e.g. X = (1, 0) and Y = (0, 2) are complementary, but X = (1, 1) and Y = (2, 0) are not. A complementarity problem is a special case of a variational inequality.
In mathematics, a matrix is a rectangular array or table of numbers, symbols, or expressions, arranged in rows and columns, which is used to represent a mathematical object or a property of such an object.
In mathematical optimization, Lemke's algorithm is a procedure for solving linear complementarity problems, and more generally mixed linear complementarity problems. It is named after Carlton E. Lemke.
In mathematical optimization, the criss-cross algorithm is any of a family of algorithms for linear programming. Variants of the criss-cross algorithm also solve more general problems with linear inequality constraints and nonlinear objective functions; there are criss-cross algorithms for linear-fractional programming problems, quadratic-programming problems, and linear complementarity problems.
The quadratic knapsack problem (QKP), first introduced in 19th century, is an extension of knapsack problem that allows for quadratic terms in the objective function: Given a set of items, each with a weight, a value, and an extra profit that can be earned if two items are selected, determine the number of items to include in a collection without exceeding capacity of the knapsack, so as to maximize the overall profit. Usually, quadratic knapsack problems come with a restriction on the number of copies of each kind of item: either 0, or 1. This special type of QKP forms the 0-1 quadratic knapsack problem, which was first discussed by Gallo et al. The 0-1 quadratic knapsack problem is a variation of knapsack problems, combining the features of unbounded knapsack problem, 0-1 knapsack problem and quadratic knapsack problem.