An Algorithm to Solve Finite Separable Single-Constrained Optimization Problems

This paper presents an iterative algorithm that allows the solution of the following problem to be obtained to any desired degree of accuracy: choose s_i ϵ A_i for i = 1, …, n to minimize ∑_i=1ⁱ⁼ⁿc_i(s_i) subject to ∑_i=1ⁱ⁼ⁿe_i(s_i) ≧ ε for arbitrary given real ε, c_i, e_i, and finite A_i, i = 1, …, n. In particular, the sets {(C_i(γ), e_i(γ)): γ ϵ A_i} need not be convex. The procedure offers considerable computational advantage over alternative means of obtaining the desired solution. The technique uses a pair of Lagrange multipliers for the single constraint. This pair of Lagrangians induces a partial ordering among the set of all (s₁, …, s_n). The desired solution is found among the maximal elements under this ordering for appropriate choices of the multipliers, and possible improvement in the solution is bounded in terms of other maximal elements. The set of all maximal elements, under the partial ordering, is generated by dynamic programming.