Minimization of a Non-Separable Objective Function Subject to Disjoint Constraints

We consider an important class of mathematical programs, in which the vector variable can be partitioned into two subvectors corresponding to independent constraint sets. Necessary and sufficient conditions for optimal solutions are developed, and two approaches for obtaining solutions are reviewed. We present an enumeration approach, reducing the problem to a finite number of subproblems, and show that duality makes the solution of many of the subproblems unnecessary. Next, we develop an alternating approach, wherein the problem is solved for one of the subvectors while the other is held constant, and then the subvector roles are reversed. This procedure is observed to converge to partial optimum solutions. A widely applicable subclass of problems includes a linear program in one of the subvectors. For this subclass a sufficient condition for local optimality is determined. The condition is easily testable and fails to hold, in many cases, only if a better solution is obtained. Also, this condition shows that partial optimum solutions are almost always local optima.