Full Text Available
Note: Clicking the button above will open the full text document at the original institutional repository in a new window.
On alternative solution methods for solving approximate subproblems in SAO (Sequential Approximate Optimization)
Thesis (MSc)--Stellenbosch University, 2015.
Saved in:
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | en_ZA |
| Published: |
Stellenbosch : Stellenbosch University
2015
|
| Subjects: | |
| Tags: |
No Tags, Be the first to tag this record!
|
| _version_ | 1867613862920978432 |
|---|---|
| access_status_str | Open Access |
| author | Cronje, Marlize |
| author2 | Groenwold, Albert A. |
| author_browse | Cronje, Marlize Groenwold, Albert A. |
| author_facet | Groenwold, Albert A. Cronje, Marlize |
| author_sort | Cronje, Marlize |
| collection | Thesis |
| dc_rights_str_mv | Sellenbosch University |
| description | Thesis (MSc)--Stellenbosch University, 2015. |
| format | Thesis |
| id | oai:scholar.sun.ac.za:10019.1/98109 |
| institution | Stellenbosch University (South Africa) |
| language | en_ZA |
| last_indexed | 2026-06-10T12:42:53.367Z |
| license_str | Other — see source repository |
| provenance_str_mv | Harvested via OAI-PMH from SUNScholar — Stellenbosch University Repository |
| publishDate | 2015 |
| publishDateRange | 2015 |
| publishDateSort | 2015 |
| publisher | Stellenbosch : Stellenbosch University |
| publisherStr | Stellenbosch : Stellenbosch University |
| record_format | dspace |
| source_str | SUNScholar — Stellenbosch University Repository |
| spelling | oai:scholar.sun.ac.za:10019.1/98109 On alternative solution methods for solving approximate subproblems in SAO (Sequential Approximate Optimization) Cronje, Marlize Groenwold, Albert A. Stellenbosch University. Faculty of Engineering. Dept. Mechanical and Mechatronic Engineering. Dual space Sequential approximate optimization (SAO) techniques Aquadratic program (QP) Large scale optimization UCTD Thesis (MSc)--Stellenbosch University, 2015. 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. 2015-12-14T07:44:17Z 2015-12-14T07:44:17Z 2015-12 Thesis http://hdl.handle.net/10019.1/98109 en_ZA Sellenbosch University 108 pages : illustrations application/pdf Stellenbosch : Stellenbosch University |
| spellingShingle | Dual space Sequential approximate optimization (SAO) techniques Aquadratic program (QP) Large scale optimization UCTD Cronje, Marlize On alternative solution methods for solving approximate subproblems in SAO (Sequential Approximate Optimization) |
| title | On alternative solution methods for solving approximate subproblems in SAO (Sequential Approximate Optimization) |
| title_full | On alternative solution methods for solving approximate subproblems in SAO (Sequential Approximate Optimization) |
| title_fullStr | On alternative solution methods for solving approximate subproblems in SAO (Sequential Approximate Optimization) |
| title_full_unstemmed | On alternative solution methods for solving approximate subproblems in SAO (Sequential Approximate Optimization) |
| title_short | On alternative solution methods for solving approximate subproblems in SAO (Sequential Approximate Optimization) |
| title_sort | on alternative solution methods for solving approximate subproblems in sao sequential approximate optimization |
| topic | Dual space Sequential approximate optimization (SAO) techniques Aquadratic program (QP) Large scale optimization UCTD |
| url | http://hdl.handle.net/10019.1/98109 |
| work_keys_str_mv | AT cronjemarlize onalternativesolutionmethodsforsolvingapproximatesubproblemsinsaosequentialapproximateoptimization |