An Algorithm for the Chebyshev Problem—With an Application to Concave Programming

The Chebyshev problem is to determine a point x α which solves max α min i = 1,…, N{g i (x)}. By exploiting generalized inverses an algorithm is developed for determining x α . It is also shown that in a certain sense the Chebyshev problem is equivalent to the concave programming problem. Moreover, for the programming problem generated by the Chebyshev problem, the Kuhn-Tucker conditions are proven to be sufficient even though the feasible region may not be convex.