Accession Number : ADA258682


Title :   Least Square Methods for Solving Systems of Inequalities with Application to an Assignment Problem


Descriptive Note : Final rept.


Corporate Author : CONSTRUCTION ENGINEERING RESEARCH LAB (ARMY) CHAMPAIGN IL


Personal Author(s) : Spoonamore, Janet H


Full Text : https://apps.dtic.mil/dtic/tr/fulltext/u2/a258682.pdf


Report Date : Nov 1992


Pagination or Media Count : 81


Abstract : This research addresses algorithmic approaches for solving two related types of optimization problems: (1) solving a specific type of assignment problem using continuous methods and (2) 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 assignment condition. Continuous relaxation of the consults 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 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. Common algorithmic approaches to solve nonlinear least square problems are adapted to solve systems of inequalities Local and global convergence results are developed. 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.


Descriptors :   *PROBLEM SOLVING , *LEAST SQUARES METHOD , *INEQUALITIES , *STATISTICAL ANALYSIS , ALGORITHMS , FUNCTIONS , STABILITY , CONVERGENCE , EQUATIONS , DISCONTINUITIES , RELAXATION , ALLOCATIONS , COSTS , OPTIMIZATION , COMPUTER PROGRAMMING , LINEAR PROGRAMMING


Subject Categories : Statistics and Probability
      Operations Research


Distribution Statement : APPROVED FOR PUBLIC RELEASE