{"id":{"repo_id":"vt","oai_identifier":"oai:vtechworks.lib.vt.edu:10919/44856"},"canonical_url":"https://search.dev.ndltd.org/etd/vt/oai:vtechworks.lib.vt.edu:10919/44856","repository":{"repo_id":"vt","name":"Virginia Tech","base_url":"https://vtechworks.lib.vt.edu/oai/request"},"display":{"title":"Analysis of a nonhierarchical decomposition algorithm","abstract":"Large scale optimization problems are tractable only if they are somehow decomposed. Hierarchical decompositions are inappropriate for some types of problems and do not parallelize well. Sobieszczanski-Sobieski has proposed a nonhierarchical decomposition strategy for nonlinear constrained optimization that is naturally parallel. Despite some successes on engineering problems, the algorithm as originally proposed fails on simple two dimensional quadratic programs. Here, the algorithm is carefully analyzed by testing it on simple quadratic programs, thereby recognizing the problems with the algorithm. Different modifications are made to improve its robustness and the best version is tested on a larger dimensional example. Some of the changes made are very fundamental, affecting the updating of the various tuning parameters present in the original algorithm. The algorithm involves solving a given problem by dividing it into subproblems and a final coordination phase. The results indicate good success with small problems. On testing it with a larger dimensional example, it was discovered that there is a basic flaw in the coordination phase which needs to be rectified.","abstract_html":"Large scale optimization problems are tractable only if they are somehow decomposed. Hierarchical decompositions are inappropriate for some types of problems and do not parallelize well. Sobieszczanski-Sobieski has proposed a nonhierarchical decomposition strategy for nonlinear constrained optimization that is naturally parallel. Despite some successes on engineering problems, the algorithm as originally proposed fails on simple two dimensional quadratic programs. Here, the algorithm is carefully analyzed by testing it on simple quadratic programs, thereby recognizing the problems with the algorithm. Different modifications are made to improve its robustness and the best version is tested on a larger dimensional example. Some of the changes made are very fundamental, affecting the updating of the various tuning parameters present in the original algorithm. The algorithm involves solving a given problem by dividing it into subproblems and a final coordination phase. The results indicate good success with small problems. On testing it with a larger dimensional example, it was discovered that there is a basic flaw in the coordination phase which needs to be rectified.","abstract_has_math":false,"creators":["Shankar, Jayashree"],"institution":"Virginia Tech","degree_name":"Master of Science","degree_level":"masters","degree_discipline":"Computer Science and Applications","degree_department":"Computer Science and Applications","school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":1992,"date_issued":"1992","date_published":"1992","updated_at":"2026-07-22T22:19:41Z","subjects":[],"languages":["en"],"rights":["In Copyright"],"rights_urls":["http://rightsstatements.org/vocab/InC/1.0/"],"identifier_entries":[{"key":"dc:identifier.other","label":"Dc Identifier Other","values":["etd-09192009-040336"],"render_values":[{"text":"etd-09192009-040336","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/10919/44856","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.department","label":"Department","values":["Computer Science and Applications"]},{"key":"dc:creator","label":"Author","values":["Shankar, Jayashree"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2014-03-14T21:46:09Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2014-03-14T21:46:09Z","2009-09-19"]},{"key":"dc:date.issued","label":"Date","values":["1992"]},{"key":"dc:publisher","label":"Institution","values":["Virginia Tech"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]},{"key":"dc:type.dcmitype","label":"Dc Type Dcmitype","values":["Text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science and Applications"]},{"key":"thesis:degree_level","label":"Degree Level","values":["masters"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Master of Science"]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["Virginia Polytechnic Institute and State University"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["In Copyright"]},{"key":"dc:rights.uri","label":"Rights URI","values":["http://rightsstatements.org/vocab/InC/1.0/"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.other","label":"Dc Identifier Other","values":["etd-09192009-040336"]},{"key":"dc:identifier.uri","label":"Identifier URI","values":["http://hdl.handle.net/10919/44856"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["Large scale optimization problems are tractable only if they are somehow decomposed. Hierarchical decompositions are inappropriate for some types of problems and do not parallelize well. Sobieszczanski-Sobieski has proposed a nonhierarchical decomposition strategy for nonlinear constrained optimization that is naturally parallel. Despite some successes on engineering problems, the algorithm as originally proposed fails on simple two dimensional quadratic programs. Here, the algorithm is carefully analyzed by testing it on simple quadratic programs, thereby recognizing the problems with the algorithm. Different modifications are made to improve its robustness and the best version is tested on a larger dimensional example. Some of the changes made are very fundamental, affecting the updating of the various tuning parameters present in the original algorithm. The algorithm involves solving a given problem by dividing it into subproblems and a final coordination phase. The results indicate good success with small problems. On testing it with a larger dimensional example, it was discovered that there is a basic flaw in the coordination phase which needs to be rectified."]},{"key":"dc:description.degree","label":"Dc Description Degree","values":["Master of Science"]},{"key":"dc:format.medium","label":"Dc Format Medium","values":["BTD"]},{"key":"dc:format.mimetype","label":"Dc Format Mimetype","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Analysis of a nonhierarchical decomposition algorithm"]}]}],"canonical_facts":{"dc:contributor.department":["Computer Science and Applications"],"dc:creator":["Shankar, Jayashree"],"dc:date.accessioned":["2014-03-14T21:46:09Z"],"dc:date.available":["2014-03-14T21:46:09Z","2009-09-19"],"dc:date.issued":["1992"],"dc:description.abstract":["Large scale optimization problems are tractable only if they are somehow decomposed. Hierarchical decompositions are inappropriate for some types of problems and do not parallelize well. Sobieszczanski-Sobieski has proposed a nonhierarchical decomposition strategy for nonlinear constrained optimization that is naturally parallel. Despite some successes on engineering problems, the algorithm as originally proposed fails on simple two dimensional quadratic programs. Here, the algorithm is carefully analyzed by testing it on simple quadratic programs, thereby recognizing the problems with the algorithm. Different modifications are made to improve its robustness and the best version is tested on a larger dimensional example. Some of the changes made are very fundamental, affecting the updating of the various tuning parameters present in the original algorithm. The algorithm involves solving a given problem by dividing it into subproblems and a final coordination phase. The results indicate good success with small problems. On testing it with a larger dimensional example, it was discovered that there is a basic flaw in the coordination phase which needs to be rectified."],"dc:description.degree":["Master of Science"],"dc:format.medium":["BTD"],"dc:format.mimetype":["application/pdf"],"dc:identifier.other":["etd-09192009-040336"],"dc:identifier.uri":["http://hdl.handle.net/10919/44856"],"dc:language.iso":["en"],"dc:publisher":["Virginia Tech"],"dc:rights":["In Copyright"],"dc:rights.uri":["http://rightsstatements.org/vocab/InC/1.0/"],"dc:title":["Analysis of a nonhierarchical decomposition algorithm"],"dc:type":["Thesis"],"dc:type.dcmitype":["Text"],"thesis:degree_discipline":["Computer Science and Applications"],"thesis:degree_level":["masters"],"thesis:degree_name":["Master of Science"],"thesis:institution_name":["Virginia Polytechnic Institute and State University"]},"updated_at":"2026-07-22T22:19:41Z"}