A practical approach to decomposable nonlinear programming problems

Nonlinear programming problems often contain two types of variables; one appears linearly, while the other nonlinearly. The purpose of this paper is to propose a practical decomposition approach for solving nonlinear programming problems in which the number of linear variables is presumably much larger than that of nonlinar variables. Using quadratic penalty and quadratic perturbation techniques, the authors first formulate a parametric approximate problem for the given problem. By reformulating the approximate problem, they then obtain a differentiable nonlinear programming problem containing the nonlinear variables only. The main advantage of this approach is that any available nonlinear programming code may be used to solve the last problem, of which variables are presumably much fewer than the original problem. The authors may thus avoid solving the given problem directly or developing a specialized algorithm like Benders’ algorithm that essentially deals with a nonsmooth optimization problem equivalent to the original problem. They give error bounds for the approximate problem and mention a possibility of parallel decomposition for a class of structured problems. Some computational results indicate that the proposed approach is practically useful.