POSITIVE (SEMI-) DEFINITE MATRICES AND MATHEMATICAL PROGRAMMING
Abstract
A general mapping w of points z in RN into points w(z) in the same space is considered. It is shown that classical mathematical programming problems can all be restate as finding among those vectors z greater than or equal to 0 which map into w greater than or equal to 0, one which minimizes zTw. For a differentiable mapping w with a positive semi-definite Jacobian matrix the obviously sufficient (''complementary slackness'') condition zTw 0 for a minimum is shown to be necessary. Next considered is the case which in cludes quadratic and linear programming: w Mz q where q is a fixed vector and M is positive (semi-) definite with constant coefficients. It is noted that the definiteness property is pre served for any equivalent system generated by an interchange of a subset of corresponding comple ments of z and w or what is the same thing by a ''block'' pivot on a principal minor of M. Since this result is related to recent ones obtained by A. Tucker and P. Wolfe, it is planned to in corporate its proof in a separate joint paper. Finally, a simple constructive solution of quad ratic and linear programs is presented. In a sense the simplex method for linear programs and the results of Barankin, Dorfman, Wolfe, Beale, and Markowitz on quadratic programs reappear here but are curiously free of primal-dual structure. Complementary pairs of variables play a key role.
Document Details
- Document Type
- Technical Report
- Publication Date
- May 15, 1963
- Accession Number
- AD0415759
Entities
People
- George Bernard Dantzig
- Richard Cottle
Organizations
- University of California, Berkeley