Mathematical programming

The branch of mathematics concerned with the theory and methods for solving problems on finding the extrema of functions on sets defined by linear and non-linear constraints (equalities and inequalities) in a finite-dimensional vector space. Mathematical programming is a branch of operations research, which comprises a wide class of control problems the mathematical models of which are finite-dimensional extremum problems. The problems of mathematical programming find applications in various areas of human activity where it is necessary to choose one of the possible ways of action, e.g. in solving numerous problems of control and planning of production processes as well as in problems of design and long-term planning. The term "mathematical programming" is connected with the fact that the goal of solving various problems is choosing programs of action.

The mathematical formulation of the problem of mathematical programming is: To minimize a scalar function $/phi (x)$ of a vector argument on the set

where and are scalar functions. The function is called the objective function, and also the quality criterion, the set is called the feasible set, or the set of plans, a solution of the mathematical programming problem is an optimum point (or vector), a point of global minimum and also an optimal plan.

In mathematical programming one customarily distinguishes the following branches. Linear programming: The objective function and the constraints and are linear. Quadratic programming: The objective function is quadratic and convex, while the feasible set is defined by linear equalities and inequalities. Convex programming: The objective function and the constraints are convex. Discrete programming: The solution is sought only at discrete, say integer, points of . Stochastic programming: In contrast to deterministic problems, here the data contain an element of indeterminacy. For example, in stochastic problems of minimization of a linear function

under linear constraints

the parameters , or only some of them, are random. The problems of linear, quadratic and convex programming have a common property: Local optimality implies global optimality. The so-called multi-extremum problems, for which the indicated property does not hold, are both considerably more difficult and less investigated.

At the basis of the theory of convex, and, in particular, linear and quadratic, programming lies the Kuhn–Tucker theorem, which gives necessary and sufficient conditions for the existence of an optimum point : In order that be an optimum point, i.e.

it is necessary and sufficient that there exist a point such that the pair be a saddle point of the Lagrange function

The latter means that

for all and all . If the constraints are non-linear, the theorem is valid under some additional assumptions on the feasible set, for example, the existence of a point such that , (Slater's regularity condition).

If and are differentiable functions, then the following relations characterize a saddle point:

Thus, the problem of convex programming reduces to the solution of a system of equations and inequalities.

On the basis of the Kuhn–Tucker theorem various iterative minimization methods were developed, which amount to searching for a saddle point of Lagrange's function.

In mathematical programming one of the main directions concerns computational methods for solving extremum problems. One of the widest used among these methods is the method of feasible directions. In this method a sequence of points of the set is constructed by the formula . At each iteration, to calculate the point one has to choose a direction (a vector) and a step length (a number) . For one selects from among the feasible directions (i.e. directions at the point , a small displacement along which does not lead out of the set ) the one that makes an acute angle with the direction of steepest descent of the objective function (with the vector if is differentiable). Therefore, along the direction the function is decreasing. The number is determined from the conditions that and . To calculate at one defines the cone of feasible directions, given by a system of inequalities, and one formulates the problem (of linear programming) of finding the possible direction along which the objective function decreases most quickly. This problem is readily solved using, say, the standard simplex method. The step length is determined by solving the minimization problem for the function . Under rather general assumptions it has been shown that the distance from to the set of stationary points of the original problem (i.e. the set of points at which the conditions necessary for a local minimum of on are satisfied) tends to zero as . In the case when the original problem is a problem in convex programming, then, as , approaches the set of solutions (optimum points) of the original problem. The method of feasible directions admits an approximate solution of the indicated problems of determination of and , and in this sense it is stable with respect to computational errors.

For feasible sets of special structure (from the point of view of the simplicity of choosing ) one can apply minimization methods different from the method of feasible directions. Thus, in a gradient-projection method, as the descent direction at the point one takes , where is the projection of , , on the set .

If is given by linear constraints, one has the rather promising method of the conditional gradient: One linearizes the objective function at by constructing the function , and then, minimizing on the set , one finds a minimum point of it and one finally sets .

Minimization methods for non-smooth functions were successfully elaborated. One of the representatives of this class is the method of the generalized gradient. By definition, a generalized gradient at is any vector such that the inequality holds for all . This method differs from the projection-gradient method in that for the point that is projected one takes .

Stochastic methods of minimization are also widely used. In the simplest variant of the method of random descent one takes for a random point on the -dimensional unit sphere with centre at the coordinate origin, and if is a feasible direction and if, in addition, decreases along this direction, then a step is effected, i.e. one shifts to the point . In the opposite case, the procedure for selecting is carried out anew.

A characteristic feature of the computational aspect of the methods for solving the problems in mathematical programming is that the application of these methods is invariably connected with the utilization of electronic computers. The main reason for this is that the problems in mathematical programming that formalize situations of control of real systems involve a large amount of work which cannot be performed by manual computation.

One of the widespread methods for investigating problems in mathematical programming is the method of penalty functions (cf. Penalty functions, method of). This method essentially replaces the given mathematical programming problem by a sequence of parametric problems on unconditional minimization, such that when the parameter tends to infinity (in other cases, to zero) the solutions of these auxiliary problems converge to the solution of the original problem. Note that in an unconditional minimization problem every direction is feasible, and consequently the search for requires less effort in comparison with the solution of the same problem by the method of feasible directions. (For example, in the method of steepest descent one takes .) The same is true concerning the search for .

An important direction of investigation in mathematical programming is the problem of stability. Here essential importance is attached to the study of the class of stable problems, that is, problems for which small perturbations (errors) in the data result in perturbations of the solutions that are also small. In the case of unstable problems an important role is reserved for a procedure of approximating the unstable problem by a sequence of stable problems — this is known as the regularization process.

Along with finite-dimensional problems, problems of mathematical programming in infinite-dimensional spaces are considered as well. Among the latter there are various extremum problems in mathematical economics, technology, problems of optimization of physical characteristics of nuclear reactors, and others. In the terminology of mathematical programming one formulates the problems in the corresponding function space of variational calculus and optimal control.

Mathematical programming has crystallized as a science in the 1950-s until 1970-s. This is first of all connected with the development of electronic computers and, hence, the mathematical processing of large amounts of data. On this basis one solves problems of control and planning, in which the application of mathematical methods is connected mainly with the construction of mathematical models and related extremal problems, among them problems of mathematical programming.

References

[1]	Yu.P. Ivanov, "Methods of optimization" , Moscow (1978) (In Russian)
[2]	V.G. Karmanov, "Mathematical programming" , Moscow (1975) (In Russian)
[3]	E. Polak, "Computational methods in optimization: a unified approach" , Acad. Press (1971)
[4]	Yu.M. Ermol'ev, "Methods of stochastic programming" , Moscow (1976) (In Russian)

References

[a1]	M. Minoux, "Mathematical programming: theory and algorithms" , Wiley (1986)
[a2]	G. Zoutendijk, "Mathematical programming methods" , North-Holland (1976)
[a3]	A.R.G. Heesterman, "Matrices and simplex algorithms" , Reidel (1983)
[a4]	G.F. Hadley, "Nonlinear and dynamic programming" , Addison-Wesley (1964)
[a5]	W.I. Zangwill, "Nonlinear programming: a unified approach" , Prentice-Hall (1969)
[a6]	S. Zionts, "Linear and integer programming" , Prentice-Hall (1973)