POSITIVE (SEMI-) DEFINITE MATRICES AND MATHEMATICAL PROGRAMMING
CALIFORNIA UNIV BERKELEY OPERATIONS RESEARCH CENTER
Pagination or Media Count:
A general mapping w of points z in RN into points wz 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.
- Operations Research