Studies integrating geometry, probability, and optimization under convexity
Thesis (Ph. D.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2006.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2007
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/36227 |
| _version_ | 1826200335581970432 |
|---|---|
| author | Nogueira, Alexandre Belloni |
| author2 | Robert M. Freund. |
| author_facet | Robert M. Freund. Nogueira, Alexandre Belloni |
| author_sort | Nogueira, Alexandre Belloni |
| collection | MIT |
| description | Thesis (Ph. D.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2006. |
| first_indexed | 2024-09-23T11:34:53Z |
| format | Thesis |
| id | mit-1721.1/36227 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T11:34:53Z |
| publishDate | 2007 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/362272019-04-11T09:13:09Z Studies integrating geometry, probability, and optimization under convexity Nogueira, Alexandre Belloni Robert M. Freund. Massachusetts Institute of Technology. Operations Research Center. Massachusetts Institute of Technology. Operations Research Center. Operations Research Center. Thesis (Ph. D.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2006. Includes bibliographical references (p. 197-202). Convexity has played a major role in a variety of fields over the past decades. Nevertheless, the convexity assumption continues to reveal new theoretical paradigms and applications. This dissertation explores convexity in the intersection of three fields, namely, geometry, probability, and optimization. We study in depth a variety of geometric quantities. These quantities are used to describe the behavior of different algorithms. In addition, we investigate how to algorithmically manipulate these geometric quantities. This leads to algorithms capable of transforming ill-behaved instances into well-behaved ones. In particular, we provide probabilistic methods that carry out such task efficiently by exploiting the geometry of the problem. More specific contributions of this dissertation are as follows. (i) We conduct a broad exploration of the symmetry function of convex sets and propose efficient methods for its computation in the polyhedral case. (ii) We also relate the symmetry function with the computational complexity of an interior-point method to solve a homogeneous conic system. (iii) Moreover, we develop a family of pre-conditioners based on the symmetry function and projective transformations for such interior-point method. (cont.) The implementation of the pre-conditioners relies on geometric random walks. (iv) We developed the analysis of the re-scaled perceptron algorithm for a linear conic system. In this method a sequence of linear transformations is used to increase a condition measure associated with the problem. (v) Finally, we establish properties relating a probability density induced by an arbitrary norm and the geometry of its support. This is used to construct an efficient simulating annealing algorithm to test whether a convex set is bounded, where the set is represented only by a membership oracle. by Alexandre Belloni Nogueira. Ph.D. 2007-02-21T13:10:11Z 2007-02-21T13:10:11Z 2006 2006 Thesis http://hdl.handle.net/1721.1/36227 76954539 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 202 p. application/pdf Massachusetts Institute of Technology |
| spellingShingle | Operations Research Center. Nogueira, Alexandre Belloni Studies integrating geometry, probability, and optimization under convexity |
| title | Studies integrating geometry, probability, and optimization under convexity |
| title_full | Studies integrating geometry, probability, and optimization under convexity |
| title_fullStr | Studies integrating geometry, probability, and optimization under convexity |
| title_full_unstemmed | Studies integrating geometry, probability, and optimization under convexity |
| title_short | Studies integrating geometry, probability, and optimization under convexity |
| title_sort | studies integrating geometry probability and optimization under convexity |
| topic | Operations Research Center. |
| url | http://hdl.handle.net/1721.1/36227 |
| work_keys_str_mv | AT nogueiraalexandrebelloni studiesintegratinggeometryprobabilityandoptimizationunderconvexity |