Abstract:
The following complementarity problem is considered: to find $x\in R^n$, $y\in R^n$, satisfying the conditions $x\ge0$, $y\ge0$, $y=Ax-b$, $(x,y)=0$. A problem of linear programming is reducible to this statement, but not vice versa. The complementarity problem is shown to be reducible to a problem of concave programming with linear constraints and a piecewise linear target function.