On alternative solution methods for solving approximate subproblems in SAO (Sequential Approximate Optimization)
Date
2015-12
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Stellenbosch : Stellenbosch University
Abstract
ENGLISH ABSTRACT: In this study, we focus our attention on sequential approximate optimization
(SAO) techniques for large scale nonlinear constrained simulation based optimization
problems, and aim to add to the efficiency and robustness of the SAOi
algorithm, developed by Groenwold and Etman (2012). The SAOi algorithm
construct diagonal quadratic subproblems using an intermediate variable (reciprocal
and/or exponential) approach, which may be solved via a quadratic
program (QP), or in the dual space.
In the first part of this study, we propose the use of a limited memory implementation
of the Broyden, Fletcher, Goldfarb and Shanno updating formula for
unconstrained optimization (l-BFGS) to approximate Hessian (second-order) information
in an attempt to solve the quadratic approximate subproblems using
a QP solver. Although the use of exact second-order information leads to more
accurate quadratic approximation functions, the evaluation and storage of the
generally fully populated Hessian matrix is not practical for large scale simulation
based optimization. We then focus our attention on solving the approximate
subproblems in the dual space, and consider the use of a projected adaptive
cyclic Barzalai-Borwein (PACBB) method for bound constrained optimization to
solve the approximate dual subproblems. Currently, the limited memory bound
constrained l-BFGS-b solver is the only dual solver available in the SAOi algorithm.
As a practical application, we attempt the topology optimization of the
Messerschmitt-Bölkow-Blohm (MBB) beam.
Even though the proposed memoryless l-BFGS implementation does not retain
the diagonal and separable nature of the approximate subproblems, the numerical
results indicate that (although more expensive in terms of computational
requirements) it is more efficient and robust than both the intermediate variable
approach and the CPLEX solver. When compared to the implementation using
exact Hessian information, only a slight increase in the number of iterations
is noticed. A drawback of the current implementation is that (for very large
scale optimization problems) the QP solver ’struggles’ to return a solution to the
quadratic subproblem when the Hessian approximation is dense and ill conditioned.
It is worth exploring different choices of initial matrix and of the number of previous iterations used in the construction of the Hessian approximation.
The use of other QP solvers should also be investigated.
The numerical results for the PACBB method (unfortunately) indicate that the
l-BFGS-b dual solver is more efficient and robust than the proposed alternative.
However, further investigation shows that the implemented PACBB method
delivers a fast initial rate of convergence for the majority of test problems. The
PACBB implementation quickly converges to within a neighbourhood of the
local or global minimum, but then slows down and sometimes even ’struggles’
to converge to the optimal solution. We propose that the PACBB implementation
is used for the initial iterations and that an alternative method is then used
to achieve a faster rate of convergence to the final solution. The use of other
linesearch methods should also be explored.
A feasible solution is found in the application of the proposed PACBB method on
the MBB beam problem. However, the l-BFGS implementation does not retain
the conservative nature of the convex and separable approximate subproblem,
and does not find an acceptable optimal solution to the MBB beam topology
application.
Keywords: sequential approximate optimization (SAO); large scale optimization;
simulation based optimization; quadratic program (QP); dual space; limited
memory Broyden, Fletcher, Goldfarb and Shanno (l-BFGS); projected adaptive
cyclic Barzalai-Borwein (PACBB); approximate subproblems.
AFRIKAANSE OPSOMMING: In hierdie studie fokus ons ons aandag op opeenvolgende benaderde optimering (sequential approximate optimization (SAO)) tegnieke vir grootskaalse lineêre beperkte simulasie gebaseerde optimeringsprobleme. Ons poog om die doeltreffendheid en robuustheid van die SAOi algoritme, ontwikkel deur Groenwold en Etman (2012), verder te verbeter. Die SAOi algoritme konstrueer diagonale kwadratiese subprobleme met behulp van ’n intermediêre veranderlike (resiproke en/of eksponensiële) benadering. Die subprobleme kan dan opgelos word deur middel van ’n kwadratiese program (quadratic program (QP)), of in die duale ruimte. In die eerste deel van hierdie studie, maak ons gebruik van ’n beperkte geheue implementering van die Broyden, Fletcher, Goldfarb en Shanno opdaterings formule vir onbeperkte optimeringsprobleme (l-BFGS) om Hessiaan (tweede-orde) inligting te benader in ’n poging om die kwadratiese benaderde subprobleme op te los met behulp van ’n QP oplosser. Alhoewel die gebruik van presiese tweede-orde inligting tot meer akkurate kwadratiese benaderingsfunksies lei, is die evaluering en storing van die algemeen ten volle bevolkde Hessiaan matriks nie prakties vir grootskaalse simulasie gebaseerde optimeringsprobleme nie. Ons fokus hierna ons aandag op die oplossing van die benaderde subprobleme in die duale ruimte. Ons oorweeg die gebruik van ’n geprojekteerde aanpasbare sikliese Barzalai-Borwein (projected adaptive cyclic Barzalai-Borwein (PACBB)) metode vir begrensde optimering om die benaderde duale subprobleme op te los. Tans is die beperkte geheue l-BFGS-b oplosser die enigste duale oplosser beskikbaar in die SAOi algoritme. As ’n praktiese toepassing, poog ons dan die topologie optimering van die Messerschmitt-Bölkow-Blohm (MBB) balk. Alhoewel die voorgestelde l-BFGS metode nie die diagonale en skeibare aard van die benaderde subprobleme behou nie (en dit duurder is in terme van die berekenings vereistes), dui die numeriese resultate daarop dat dit meer doeltreffend en robuust is as beide die intermediêre veranderlike benadering en die CPLEX oplosser. Wanneer ons dit vergelyk met die gebruik van presiese (ware) Hessiaan inligting, word net ’n effense toename in die aantal iterasies opgemerk. ’n Nadeel van die huidige implementering is dat (vir baie grootskaalse optimeringsprobleme) die QP oplosser ’sukkel’om’n oplossing vir die kwadratiese subprobleme te vind wanneer die Hessiaan benadering dig en sleg gekondisioneerd is. Dit sal die moeite werd wees om verskillende keuses van aanvangsmatriks en van die aantal vorige iterasies wat gebruik word in die konstruksie van die Hessiaan benadering te verken. Die gebruik van ander QP oplossers moet ook ondersoek word. Die numeriese resultate vir die PACBB implementering dui (ongelukkig) daarop dat die l-BFGS-b duale oplosser meer doeltreffend en robuust is as die voorgestelde alternatief. Verdere ondersoek wys egter dat die PACBB metode ’n vinniger aanvanklike tempo van konvergensie vir die meerderheid van die toets probleme lewer. Dit konvergeer vinnig tot binne ’n area van die plaaslike of globale minimum, maar word dan stadiger en ’sukkel’ soms dan selfs om die optimale oplossing te vind. Ons stel voor dat die PACBB implementering gebruik word vir die aanvanklike iterasies en dat ’n alternatiewe metode dan ingespan word om ’n vinniger tempo van konvergensie tot die finale oplossing te verkry. Die gebruik van ander lynsoek metodes moet ook ondersoek word. Die toepassing van die voorgestelde PACBB metode op die MBB balk probleem lewer ’n aanvaarbare oplossing. Die l-BFGS implementering behou egter nie die konserwatiewe aard van die konvekse en skeibare benaderde subprobleme nie en vind nie ’n aanvaarbare optimale oplossing vir die MBB balk topologie toepassing nie. Sleutelwoorde: opeenvolgende benaderde optimering (sequential approximate optimization (SAO)); grootskaalse optimering; simulasie gebaseerde optimering; kwadratiese program (quadratic program (QP)); duale ruimte; beperkte geheue Broyden, Fletcher, Goldfarb en Shanno (l-BFGS); geprojekteerde aanpasbare sikliese Barzalai-Borwein (projected adaptive cyclic Barzalai-Borwein (PACBB)); benaderde subprobleme.
AFRIKAANSE OPSOMMING: In hierdie studie fokus ons ons aandag op opeenvolgende benaderde optimering (sequential approximate optimization (SAO)) tegnieke vir grootskaalse lineêre beperkte simulasie gebaseerde optimeringsprobleme. Ons poog om die doeltreffendheid en robuustheid van die SAOi algoritme, ontwikkel deur Groenwold en Etman (2012), verder te verbeter. Die SAOi algoritme konstrueer diagonale kwadratiese subprobleme met behulp van ’n intermediêre veranderlike (resiproke en/of eksponensiële) benadering. Die subprobleme kan dan opgelos word deur middel van ’n kwadratiese program (quadratic program (QP)), of in die duale ruimte. In die eerste deel van hierdie studie, maak ons gebruik van ’n beperkte geheue implementering van die Broyden, Fletcher, Goldfarb en Shanno opdaterings formule vir onbeperkte optimeringsprobleme (l-BFGS) om Hessiaan (tweede-orde) inligting te benader in ’n poging om die kwadratiese benaderde subprobleme op te los met behulp van ’n QP oplosser. Alhoewel die gebruik van presiese tweede-orde inligting tot meer akkurate kwadratiese benaderingsfunksies lei, is die evaluering en storing van die algemeen ten volle bevolkde Hessiaan matriks nie prakties vir grootskaalse simulasie gebaseerde optimeringsprobleme nie. Ons fokus hierna ons aandag op die oplossing van die benaderde subprobleme in die duale ruimte. Ons oorweeg die gebruik van ’n geprojekteerde aanpasbare sikliese Barzalai-Borwein (projected adaptive cyclic Barzalai-Borwein (PACBB)) metode vir begrensde optimering om die benaderde duale subprobleme op te los. Tans is die beperkte geheue l-BFGS-b oplosser die enigste duale oplosser beskikbaar in die SAOi algoritme. As ’n praktiese toepassing, poog ons dan die topologie optimering van die Messerschmitt-Bölkow-Blohm (MBB) balk. Alhoewel die voorgestelde l-BFGS metode nie die diagonale en skeibare aard van die benaderde subprobleme behou nie (en dit duurder is in terme van die berekenings vereistes), dui die numeriese resultate daarop dat dit meer doeltreffend en robuust is as beide die intermediêre veranderlike benadering en die CPLEX oplosser. Wanneer ons dit vergelyk met die gebruik van presiese (ware) Hessiaan inligting, word net ’n effense toename in die aantal iterasies opgemerk. ’n Nadeel van die huidige implementering is dat (vir baie grootskaalse optimeringsprobleme) die QP oplosser ’sukkel’om’n oplossing vir die kwadratiese subprobleme te vind wanneer die Hessiaan benadering dig en sleg gekondisioneerd is. Dit sal die moeite werd wees om verskillende keuses van aanvangsmatriks en van die aantal vorige iterasies wat gebruik word in die konstruksie van die Hessiaan benadering te verken. Die gebruik van ander QP oplossers moet ook ondersoek word. Die numeriese resultate vir die PACBB implementering dui (ongelukkig) daarop dat die l-BFGS-b duale oplosser meer doeltreffend en robuust is as die voorgestelde alternatief. Verdere ondersoek wys egter dat die PACBB metode ’n vinniger aanvanklike tempo van konvergensie vir die meerderheid van die toets probleme lewer. Dit konvergeer vinnig tot binne ’n area van die plaaslike of globale minimum, maar word dan stadiger en ’sukkel’ soms dan selfs om die optimale oplossing te vind. Ons stel voor dat die PACBB implementering gebruik word vir die aanvanklike iterasies en dat ’n alternatiewe metode dan ingespan word om ’n vinniger tempo van konvergensie tot die finale oplossing te verkry. Die gebruik van ander lynsoek metodes moet ook ondersoek word. Die toepassing van die voorgestelde PACBB metode op die MBB balk probleem lewer ’n aanvaarbare oplossing. Die l-BFGS implementering behou egter nie die konserwatiewe aard van die konvekse en skeibare benaderde subprobleme nie en vind nie ’n aanvaarbare optimale oplossing vir die MBB balk topologie toepassing nie. Sleutelwoorde: opeenvolgende benaderde optimering (sequential approximate optimization (SAO)); grootskaalse optimering; simulasie gebaseerde optimering; kwadratiese program (quadratic program (QP)); duale ruimte; beperkte geheue Broyden, Fletcher, Goldfarb en Shanno (l-BFGS); geprojekteerde aanpasbare sikliese Barzalai-Borwein (projected adaptive cyclic Barzalai-Borwein (PACBB)); benaderde subprobleme.
Description
Thesis (MSc)--Stellenbosch University, 2015.
Keywords
Dual space, Sequential approximate optimization (SAO) techniques, Aquadratic program (QP), Large scale optimization, UCTD