Nonlinear Programs with Positively Bounded Jacobians

Abstract

In [3], it is constructively demonstrated that if M is a square (not necessarily symmetric) matrix all of whose principal minors are positive, the quadratic program\[ (A1) \qquad {\text{minimize}}\quad z^T ( {Mz + q} )\quad {\text{subject to}}\quad Mz + q\geqq 0,\quad z\geqq 0, \] has an optimal solution satisfying the equation\[ ({\text{A2}})\qquad z^T ( {Mz + q} ) = 0. \]A different prooff is offered here. The analysis is then extended to programs of the form \[ ({\text{A3}})\qquad {\text{minimize}}\quad z^T W( z )\quad {\text{subject to}}\quad W( z )\geqq 0,\quad z\geqq 0, \] where W is a continuously differentiable mapping of real N-space into itself. The condition used to insure the existence of an optimal solution to (A3) is positive boundedness of the Jacobian matrix of the mapping W. Definition: A differentiable mapping $W:R^N \to R^N $ has a positively bounded Jacobian matrix, $J_w ( z )$, if there exists a real number $\delta $ such that $0 < \delta < 1$ and such that for every $z \in R^N $ each principal minor of $J_W ( z )$ lies between $\delta $ and $\delta ^{ - 1} $. Mappings of the form $W( z ) = Mz + q$ have positively bounded Jacobian matrices if and only if M has positive principal minors, hence the programs (Al) are subsumed by (A3). Elementary examples show that it is not enough to assume in the general case, (A3), that $J_W ( z )$ has positive principal minors for all z. A consequence of the main result is the Minimax Theorem: If $K( {x,y} )$ is a twice continuously differentiable real-valued function on $R^n \times R^m $, and if $[ {\nabla _x K( {x,y} ), - \nabla _y K( {x,y} )} ]$ has a positively bounded Jacobian matrix, then\[ \mathop {\max }\limits_{y\geqq 0} \mathop {\min }\limits_{x\geqq 0} K( {x,y} ) = \mathop {\min }\limits_{x\geqq 0} \mathop {\max }\limits_{y\geqq 0} K( {x,y} ). \]