Non-Linear Programming Via Penalty Functions

Abstract

The non-linear programming problem seeks to maximize a function f(x) where the n component vector x must satisfy certain constraints g i(x) = 0, i = 1, …, m 1 and g i(z) ≧ 0, i = m 1 + 1, …, m. The algorithm presented in this paper solves the non-linear programming problem by transforming it into a sequence of unconstrained maximization problems. Essentially, a penalty is imposed whenever x does not satisfy the constraints. Although the algorithm appears most useful in the concave case, the convergence proof holds for non-concave functions as well. The algorithm is especially interesting in the concave case because the programming problem reduces to a single unconstrained maximization problem or, at most, to a finite sequence of unconstrained maximization problems. In addition, the paper presents a new class of dual problems, and the algorithm is shown to be a dual feasible method. Another property of the algorithm is that it appears particularly well suited for large-scale problems with a sizable number of constraints.