Enhancements and computational evaluation of the hit-and-run random walk on polyhedra
Thesis (S.M.)--Massachusetts Institute of Technology, Computation for Design and Optimization Program, 2006.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2007
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/39216 |
| _version_ | 1811085657847627776 |
|---|---|
| author | Liang, Jiajie, S.M. Massachusetts Institute of Technology |
| author2 | Robert M. Freund. |
| author_facet | Robert M. Freund. Liang, Jiajie, S.M. Massachusetts Institute of Technology |
| author_sort | Liang, Jiajie, S.M. Massachusetts Institute of Technology |
| collection | MIT |
| description | Thesis (S.M.)--Massachusetts Institute of Technology, Computation for Design and Optimization Program, 2006. |
| first_indexed | 2024-09-23T13:13:13Z |
| format | Thesis |
| id | mit-1721.1/39216 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T13:13:13Z |
| publishDate | 2007 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/392162019-04-10T13:49:36Z Enhancements and computational evaluation of the hit-and-run random walk on polyhedra Liang, Jiajie, S.M. Massachusetts Institute of Technology Robert M. Freund. Massachusetts Institute of Technology. Computation for Design and Optimization Program. Massachusetts Institute of Technology. Computation for Design and Optimization Program. Computation for Design and Optimization Program. Thesis (S.M.)--Massachusetts Institute of Technology, Computation for Design and Optimization Program, 2006. Includes bibliographical references (p. 55). The symmetry function of a convex set offers us numerous useful information about the set in relation to probabilistic theory and geometric properties. The symmetry function is a measure of how symmetric the convex set is, and for a point, intuitively it measures how symmetric the set is with respect to that point. We call a point of high symmetry value a deep point. A random walk is a procedure that starts from a particular point in Rn and at each iteration, moves to a "neighboring" point according to some probability distribution that depends solely on the current point. The Hit-and-Run random walk on a convex set S picks a random line e through the point, and at next iteration goes to a new point that is chosen uniformly on the chord ℓ [intersection] S. In this thesis, we analyze and investigate the effectiveness of the Hit-and-Run random walk to compute a deep point in a convex body, given a randomly generated convex set. The effectiveness is evaluated in terms of the role of the starting point and the likelihood that the random walk will enter the zone of high symmetry. Additionally, some known probabilistic properties of the symmetry function are tested using the random walk, from which the integrity of the code is also verified. (cont.) The final portion of this thesis analyzes the behavioral properties of convex sets that have non-Euclidean rounding, which renders the random walk less efficient. Therefore the pre-conditioned Hit-and-Run random walk is performed, and the performance is quantitatively presented in a power law equation that predicts the preconditioning iterations required, given the dimension of the convex set, a starting point near a corner and the width of that corner. by Jiajie Liang. S.M. 2007-10-19T20:32:19Z 2007-10-19T20:32:19Z 2006 2006 Thesis http://hdl.handle.net/1721.1/39216 85844266 eng M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission. http://dspace.mit.edu/handle/1721.1/7582 55 p. application/pdf Massachusetts Institute of Technology |
| spellingShingle | Computation for Design and Optimization Program. Liang, Jiajie, S.M. Massachusetts Institute of Technology Enhancements and computational evaluation of the hit-and-run random walk on polyhedra |
| title | Enhancements and computational evaluation of the hit-and-run random walk on polyhedra |
| title_full | Enhancements and computational evaluation of the hit-and-run random walk on polyhedra |
| title_fullStr | Enhancements and computational evaluation of the hit-and-run random walk on polyhedra |
| title_full_unstemmed | Enhancements and computational evaluation of the hit-and-run random walk on polyhedra |
| title_short | Enhancements and computational evaluation of the hit-and-run random walk on polyhedra |
| title_sort | enhancements and computational evaluation of the hit and run random walk on polyhedra |
| topic | Computation for Design and Optimization Program. |
| url | http://hdl.handle.net/1721.1/39216 |
| work_keys_str_mv | AT liangjiajiesmmassachusettsinstituteoftechnology enhancementsandcomputationalevaluationofthehitandrunrandomwalkonpolyhedra |