A comparative study of primal and dual approaches for solving separable and partially-separable nonlinear optimization problems

In nonlinear optimization, the dual problem is in general not easier to solve than the primal problem. Convex separable optimization problems, frequently arising in electrical and mechanical engineering, constitute a notable exception to the above rule. The dual problem is to optimize the dual objective functionℓ over a non-negative orthant, and the evaluation ofℓ reduces to the execution of independentlinear searches only. To generalize the idea, we also consider partially-separable problems with objective and constraint functions such that the Hessian matrix of the Lagrange function is a block-diagonal matrix with 2*2 blocks. The evaluation of the dual objective function is accordingly reduced to a number of independentplanar searches. Obviously, 3*3 blocks would lead tospatial searches, etc. We compare the performance of a primal and a dual method on a graded set of artificial test problems with increasing size, increasing degree of degeneracy, and increasing ill-conditioning. The observed speed-up by the dual approach varies between 2 and 30. Finally, we consider the potential of the dual approach for execution on parallel computers.