{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/72536"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/72536","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Least Square Methods for Solving Systems of Inequalities With Application to an Assignment Problem","abstract":"This research addresses algorithmic approaches for solving two different, but related, types of optimization problems. Firstly, the research considers the solution of a specific type of assignment problem using continuous methods. Secondly, the research addresses solving systems of inequalities (and equalities) in a least square sense. The specific assignment problem has piece-wise linear additive separable server cost functions, which are continuous everywhere except at zero, the point of discontinuity for the $\\{0,1\\}$ assignment condition. Continuous relaxation of the $\\{0,1\\}$ constraints yields a linear programming problem. Solving the dual of the linear programming problem yields the complementarity conditions for a primal solution, a system of linear inequalities and equalities. Adding equations to this system to enforce a $\\{0,1\\}$ solution in the relaxed solution set yields an augmented system, not necessarily linear. Methods to solve this system, a system of linear inequalities and non-linear equations, in a least square sense are developed, extending Han's method for solving linear systems of inequalities. Generalizations of these methods to solve general systems of inequalities in a least square sense are developed. The specific assignment problem is a variation of problems which are amenable to strong continuous relaxation, in that the solution set of the relaxed problem has been shown, experimentally, to often contain a $\\{0,1\\}$ solution. However, if there are a large number of variables, efficient continuous (non-combinatoric) methods are needed to locate $\\{0,1\\}$ solutions, if such exist. This work addresses methods to find $\\{0,1\\}$ solutions using a least square formulation for solving systems of inequalities.","abstract_html":"This research addresses algorithmic approaches for solving two different, but related, types of optimization problems. Firstly, the research considers the solution of a specific type of assignment problem using continuous methods. Secondly, the research addresses solving systems of inequalities (and equalities) in a least square sense. The specific assignment problem has piece-wise linear additive separable server cost functions, which are continuous everywhere except at zero, the point of discontinuity for the $\\{0,1\\}$ assignment condition. Continuous relaxation of the $\\{0,1\\}$ constraints yields a linear programming problem. Solving the dual of the linear programming problem yields the complementarity conditions for a primal solution, a system of linear inequalities and equalities. Adding equations to this system to enforce a $\\{0,1\\}$ solution in the relaxed solution set yields an augmented system, not necessarily linear. Methods to solve this system, a system of linear inequalities and non-linear equations, in a least square sense are developed, extending Han's method for solving linear systems of inequalities. Generalizations of these methods to solve general systems of inequalities in a least square sense are developed. The specific assignment problem is a variation of problems which are amenable to strong continuous relaxation, in that the solution set of the relaxed problem has been shown, experimentally, to often contain a $\\{0,1\\}$ solution. However, if there are a large number of variables, efficient continuous (non-combinatoric) methods are needed to locate $\\{0,1\\}$ solutions, if such exist. This work addresses methods to find $\\{0,1\\}$ solutions using a least square formulation for solving systems of inequalities.","abstract_has_math":true,"creators":["Spoonamore, Janet Hurst"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Mathematics","degree_department":null,"school":null,"contributors":["Bramley, R.,"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2014,"date_issued":"2014-12-17T23:17:45Z","date_published":"2014-12-17T23:17:45Z","updated_at":"2026-07-22T22:26:07Z","subjects":["Mathematics","Computer Science"],"languages":[],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["(UMI)AAI9305702"],"render_values":[{"text":"(UMI)AAI9305702","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/2142/72536","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Bramley, R.,"]},{"key":"dc:creator","label":"Author","values":["Spoonamore, Janet Hurst"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2014-12-17T23:17:45Z","10000-01-01","1992"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Mathematics"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Mathematics","Computer Science"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/72536","(UMI)AAI9305702"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["This research addresses algorithmic approaches for solving two different, but related, types of optimization problems. Firstly, the research considers the solution of a specific type of assignment problem using continuous methods. Secondly, the research addresses solving systems of inequalities (and equalities) in a least square sense. The specific assignment problem has piece-wise linear additive separable server cost functions, which are continuous everywhere except at zero, the point of discontinuity for the $\\{0,1\\}$ assignment condition. Continuous relaxation of the $\\{0,1\\}$ constraints yields a linear programming problem. Solving the dual of the linear programming problem yields the complementarity conditions for a primal solution, a system of linear inequalities and equalities. Adding equations to this system to enforce a $\\{0,1\\}$ solution in the relaxed solution set yields an augmented system, not necessarily linear. Methods to solve this system, a system of linear inequalities and non-linear equations, in a least square sense are developed, extending Han's method for solving linear systems of inequalities. Generalizations of these methods to solve general systems of inequalities in a least square sense are developed. The specific assignment problem is a variation of problems which are amenable to strong continuous relaxation, in that the solution set of the relaxed problem has been shown, experimentally, to often contain a $\\{0,1\\}$ solution. However, if there are a large number of variables, efficient continuous (non-combinatoric) methods are needed to locate $\\{0,1\\}$ solutions, if such exist. This work addresses methods to find $\\{0,1\\}$ solutions using a least square formulation for solving systems of inequalities.","Common algorithmic approaches to solve nonlinear least square problems are adapted to solve systems of inequalities. Local and global convergence results are developed, using properties of the Clarke generalized subdifferential and Jacobian. Rates of convergence are analyzed. Applications of the algorithms for solving the piece-wise linear assignment subproblem are developed and analyzed. Application of the algorithms for solving linear programming problems, and linear and convex complementarity problems are described.","Made available in DSpace on 2014-12-17T23:17:45Z (GMT). No. of bitstreams: 1 9305702.pdf: 3440708 bytes, checksum: 9fc1e9c8159b5c058e604bf775d581e9 (MD5) Previous issue date: 1992","Embargo set by: Seth Robbins for item 72704 Lift date: Forever Reason: Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","U of I Only","83 p.","Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1992."]},{"key":"dc:title","label":"Title","values":["Least Square Methods for Solving Systems of Inequalities With Application to an Assignment Problem"]}]}],"canonical_facts":{"dc:contributor":["Bramley, R.,"],"dc:creator":["Spoonamore, Janet Hurst"],"dc:date":["2014-12-17T23:17:45Z","10000-01-01","1992"],"dc:description":["This research addresses algorithmic approaches for solving two different, but related, types of optimization problems. Firstly, the research considers the solution of a specific type of assignment problem using continuous methods. Secondly, the research addresses solving systems of inequalities (and equalities) in a least square sense. The specific assignment problem has piece-wise linear additive separable server cost functions, which are continuous everywhere except at zero, the point of discontinuity for the $\\{0,1\\}$ assignment condition. Continuous relaxation of the $\\{0,1\\}$ constraints yields a linear programming problem. Solving the dual of the linear programming problem yields the complementarity conditions for a primal solution, a system of linear inequalities and equalities. Adding equations to this system to enforce a $\\{0,1\\}$ solution in the relaxed solution set yields an augmented system, not necessarily linear. Methods to solve this system, a system of linear inequalities and non-linear equations, in a least square sense are developed, extending Han's method for solving linear systems of inequalities. Generalizations of these methods to solve general systems of inequalities in a least square sense are developed. The specific assignment problem is a variation of problems which are amenable to strong continuous relaxation, in that the solution set of the relaxed problem has been shown, experimentally, to often contain a $\\{0,1\\}$ solution. However, if there are a large number of variables, efficient continuous (non-combinatoric) methods are needed to locate $\\{0,1\\}$ solutions, if such exist. This work addresses methods to find $\\{0,1\\}$ solutions using a least square formulation for solving systems of inequalities.","Common algorithmic approaches to solve nonlinear least square problems are adapted to solve systems of inequalities. Local and global convergence results are developed, using properties of the Clarke generalized subdifferential and Jacobian. Rates of convergence are analyzed. Applications of the algorithms for solving the piece-wise linear assignment subproblem are developed and analyzed. Application of the algorithms for solving linear programming problems, and linear and convex complementarity problems are described.","Made available in DSpace on 2014-12-17T23:17:45Z (GMT). No. of bitstreams: 1 9305702.pdf: 3440708 bytes, checksum: 9fc1e9c8159b5c058e604bf775d581e9 (MD5) Previous issue date: 1992","Embargo set by: Seth Robbins for item 72704 Lift date: Forever Reason: Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","U of I Only","83 p.","Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1992."],"dc:identifier":["http://hdl.handle.net/2142/72536","(UMI)AAI9305702"],"dc:subject":["Mathematics","Computer Science"],"dc:title":["Least Square Methods for Solving Systems of Inequalities With Application to an Assignment Problem"],"dc:type":["text"],"thesis:degree_discipline":["Mathematics"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:26:07Z"}