No label defined (Q4401029)

Mathematical programming is concerned with minimizing a real-valued function of several variables, which may be either discrete or continuous, subject to equality and/or inequality constraints on other functions of the variables. Optimality conditions and computational schemes for such problems frequently rely on geometrical properties of the set of feasible solutions or subsidiary geometrical constructions. Here we consider these aspects of general nonlinear optimization problems, general convex programming (the ellipsoid method and its relatives); linear programming (the simplex algorithm and more recent interior-point methods); integer and combinatorial optimization; and special convex programming problems. The treatment here focuses mainly on methods involving geometric ideas, especially those for which global complexity estimates are known. For the entire collection see [Zbl 0890.52001].