Research Reports from the Department of Operations
Document Type
Dissertation
Publication Date
5-1-1981
Abstract
This research develops a nonlinear programming approach for solving a convex system of equations. Two applications of interest are also studied, namely, computation of a Brouwer fixed point of a convex function, and the Linear Complementarity Problem (LCP). Our approach to finding a zero of a function is to try to solve the optimization problem of minimizing the sum of the coordinate functions subject to each one being nonnegative. An optimal solution with objective function value of zero yields a zero of the function. The principal advantages of our approach are: (1) Global convergence of our algorithms under reasonable conditions. (2) Finite nature of our algorithm for solving piecewise linear equations and the Linear Complementarity Problem. (3) The 'descent' nature of our algorithms. By (3) we mean that with each problem we can associate a function which strictly and monotonically changes at each iteration toward its value at the solution point. This implies that at each iteration we are strictly 'improving' toward the solution. In the first part of this work we propose a finite algorithm for solving piecewise linear convex equations. We show that our algorithm finds a solution if the function satisfies a regularity condition. In the second part we transform the Linear Complementarity Problem into one of solving piecewise linear convex equations. We then show that, if the LCP has a P-matrix, then the resulting system of convex equations satisfies the needed regularity conditions. Such LCP's are therefore solved finitely by our algorithm. We also provide computational results to compare our algorithm with that of Lemke. Our algorithm seems to require greater overall computational effort than Lemke's, but it visits fewer pieces of linearity. We have identified some directions of future research which show promise for substantially improving the computational performance of our algorithm. In the third part, we use a similar approach to the problem of finding a Brouwer fixed point of a convex function mapping an n-simplex into itself. Under reasonable conditions on the function, we prove that our algorithm is globally convergent.
Keywords
Operations research, Nonlinear programming, Convex functions, Mathematical optimization, Linear complementarity problem, Mathematical analysis, Piecewise linear topology
Publication Title
Dissertation/Technical Memorandums from the Department of Operations, School of Management, Case Western Reserve University
Issue
Technical memorandum no. 493 ; Submitted in partial fulfillment of the requirements for the Degree of Doctor of Philosophy.
Rights
This work is in the public domain and may be freely downloaded for personal or academic use
Recommended Citation
Sengupta, Partha, "A Constrained Optimization Approach to Solving Convex Equations with Applications to the Linear Complementarity and Brouwer Fixed Point Problems" (1981). Research Reports from the Department of Operations. 98.
https://commons.case.edu/wsom-ops-reports/98