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.