A comparative study of primal and dual approaches for solving separable and partially-separable nonlinear optimization problems
Tóm tắt
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.
Tài liệu tham khảo
Avriel, M. 1976:Nonlinear programming. Englewood Cliffs, New Jersey: Prentice Hall
Bitran, G.R.; Hax, A.C. 1979: On the solution of convex knapsack problems with bounded variables. In: Prekopa, A. (ed.)Survey of mathematical programming, pp. 357–367. Amsterdam: North-Holland
van den Bosch, P.P.J.; Lootsma, F.A. 1987: Scheduling of power generation via large-scale nonlinear optimization.J. Optimiz. Theory and Appl. 55, 313–326
Buys, J.D. 1972:Dual algorithms for constrained optimization problems. Thesis, Univ. of Leiden, The Netherlands
Dayde, M. 1986:Parallélisation d'algorithmes d'optimisation pour des problémes d'optimum design. Thèse, Institut National Polytechnique de Toulouse, France
Lescrenier, M.; Toint, Ph.L. 1987:Large-scale nonlinear optimization on the FPS164 and CRAY X-MP vector processors. Rep. CSS 205, Harwell Laboratory, Oxfordshire OX11 ORA, England
Lootsma, F.A.; Ragsdell, K.M. 1988: State-of-the-art in parallel nonlinear optimization.Parallel Computing 6, 133–155
Roode, J.D. 1968:Generalized Lagrangian functions in mathematical programming. Thesis, Univ. of Leiden, The Netherlands
Rosen, J.D.; Suzuki, S. 1965: Construction of nonlinear programming test problems.Communications of the ACM 8, 113
Schmit, L.A.; Fleury, C. 1980: Structural synthesis by combining approximation concepts and dual methods.J. Amer. Inst. Aeronaut. Astronaut. 18, 1252–1260
Zenios, S.A.; Lasken, R.A. 1987: Nonlinear network optimization on a massively parallel connection machine. Rep. 87-08-03, The Wharton School, Univ. of Pennsylvania, Philadelphia, PA 19104. Also:Annals Oper. Res. (to appear)