Generalized Descent Methods for Asymmetric Systems of Equations and Variational Inequalities
We consider generalizations of the steepest descent algorithm for solving asymmetric systems of equations. We first show that if the system is linear and is defined by a matrix M, then the method converges if M2 is positive definite. We also establish easy to verify conditions on the matrix M that e...
| Main Authors: | , |
|---|---|
| Format: | Working Paper |
| Language: | en_US |
| Published: |
Massachusetts Institute of Technology, Operations Research Center
2004
|
| Online Access: | http://hdl.handle.net/1721.1/5331 |
| _version_ | 1811096053402828800 |
|---|---|
| author | Hammond, Janice H. Magnanti, Thomas L. |
| author_facet | Hammond, Janice H. Magnanti, Thomas L. |
| author_sort | Hammond, Janice H. |
| collection | MIT |
| description | We consider generalizations of the steepest descent algorithm for solving asymmetric systems of equations. We first show that if the system is linear and is defined by a matrix M, then the method converges if M2 is positive definite. We also establish easy to verify conditions on the matrix M that ensure that M is positive definite, and develop a scaling procedure that extends the class of matrices that satisfy the convergence conditions. In addition, we establish a local convergence result for nonlinear systems defined by uniformly monotone maps, and discuss a class of general descent methods. Finally, we show that a variant of the Frank-Wolfe method will solve a certain class of variational inequality problems. All of the methods that we consider reduce to standard nonlinear programming algorithms for equivalent optimization problems when the Jacobian of the underlying problem map is symmetric. We interpret the convergence conditions for the generalized steepest descent algorithms as restricting the degree of asymmetry of the problem map. |
| first_indexed | 2024-09-23T16:37:15Z |
| format | Working Paper |
| id | mit-1721.1/5331 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T16:37:15Z |
| publishDate | 2004 |
| publisher | Massachusetts Institute of Technology, Operations Research Center |
| record_format | dspace |
| spelling | mit-1721.1/53312019-04-12T08:16:24Z Generalized Descent Methods for Asymmetric Systems of Equations and Variational Inequalities Hammond, Janice H. Magnanti, Thomas L. We consider generalizations of the steepest descent algorithm for solving asymmetric systems of equations. We first show that if the system is linear and is defined by a matrix M, then the method converges if M2 is positive definite. We also establish easy to verify conditions on the matrix M that ensure that M is positive definite, and develop a scaling procedure that extends the class of matrices that satisfy the convergence conditions. In addition, we establish a local convergence result for nonlinear systems defined by uniformly monotone maps, and discuss a class of general descent methods. Finally, we show that a variant of the Frank-Wolfe method will solve a certain class of variational inequality problems. All of the methods that we consider reduce to standard nonlinear programming algorithms for equivalent optimization problems when the Jacobian of the underlying problem map is symmetric. We interpret the convergence conditions for the generalized steepest descent algorithms as restricting the degree of asymmetry of the problem map. 2004-05-28T19:34:07Z 2004-05-28T19:34:07Z 1985-08 Working Paper http://hdl.handle.net/1721.1/5331 en_US Operations Research Center Working Paper;OR 137-85 2490237 bytes application/pdf application/pdf Massachusetts Institute of Technology, Operations Research Center |
| spellingShingle | Hammond, Janice H. Magnanti, Thomas L. Generalized Descent Methods for Asymmetric Systems of Equations and Variational Inequalities |
| title | Generalized Descent Methods for Asymmetric Systems of Equations and Variational Inequalities |
| title_full | Generalized Descent Methods for Asymmetric Systems of Equations and Variational Inequalities |
| title_fullStr | Generalized Descent Methods for Asymmetric Systems of Equations and Variational Inequalities |
| title_full_unstemmed | Generalized Descent Methods for Asymmetric Systems of Equations and Variational Inequalities |
| title_short | Generalized Descent Methods for Asymmetric Systems of Equations and Variational Inequalities |
| title_sort | generalized descent methods for asymmetric systems of equations and variational inequalities |
| url | http://hdl.handle.net/1721.1/5331 |
| work_keys_str_mv | AT hammondjaniceh generalizeddescentmethodsforasymmetricsystemsofequationsandvariationalinequalities AT magnantithomasl generalizeddescentmethodsforasymmetricsystemsofequationsandvariationalinequalities |