Scanning procedures for nonlinear mathematical programming: low-dimensional non-convex problems

Abstract

A convex programming algorithm for linear constraints is developed which essentially involves the solution of a sequence of subproblems of the original problem, each of which is formed by constructing the largest possible hypersphere inside the feasible region, i.e. every point of the hypersphere is a feasible point. The objective function is then maximized, restricted only by the hypersphere. By using the method, it is possible to generate a sequence of increasing values of the objective function. If the usual convexity conditions hold, the sequence of subproblem solutions converges to the maximum feasible value of the objective function. Some advantages of the new method are: (i) Every point at which the objective function is maximized in a subproblem is usable since it is a feasible point; (ii) no simplex-type operations are required to solve the subproblems; and, finally, (iii) at no time is it necessary to move along the boundary of the feasible region. The new algorithm is especially useful for solving problems of high dimensionality, but the convergence of the iterative process is slow in a narrow feasible space. A scanning procedure is developed for the special case of separable programming with linear constraints. The method of scanning is based on criteria for excluding from investigation a portion of the scanning region. The new spherical programming algorithm is incorporated into the scanning procedure to generate an increasing sequence of relative optima. Finally, a scanning procedure similar to the first is developed for concave programming with unrestricted constraints.