Go to  Advanced Search

Convex relaxations of the maximin dispersion problem

Show simple item record

dc.contributor.author Haines, Sheena Ayla
dc.date.accessioned 2011-10-25T18:37:21Z
dc.date.available 2011-10-25T18:37:21Z
dc.date.copyright 2011 en
dc.date.issued 2011-10-25
dc.identifier.uri http://hdl.handle.net/2429/38242
dc.description.abstract Recently, convex relaxations have achieved notable success in solving NP-hard optimization problems. This thesis studies semidefinite and second-order cone programming convex relaxations of the maximin dispersion problem. Providing nontrivial approximation bounds, we believe that our SDP and SOCP relaxation methods are useful in large-scale optimization. The thesis is organized as follows. We begin by recalling some basic concepts from convex analysis, nonsmooth analysis, and optimization. We then introduce the weighted maximin dispersion optimization problem; locating point(s) in a given region X ⊆ R^{n} that is/are furthest from a given set of m points. Also given are several reformulations of the original problem, including a convex relaxation problem and semidefinite and second order cone programming relaxations. Using well known results on Lipschitz functions and subdifferentials of Lipschitz functions we then derive a theoretical characterization of the optimal solutions for a given convex region X and equal weights. Next, we provide a proof that the weighted maximin dispersion problem is NP-hard even in the case where X is a box and the weights are equal. We then propose an algorithm for finding an approximate solution using the SDP relaxation, and derive an approximation bound that depends on the subset X. In the case that X is a box or a product of low-dimensional spheres, we show that the convex relaxation reduces to a second-order cone program, and provide further results on the bound provided. Lastly, we provide numerical examples using the SDP and SOCP relaxations, and suggest future work. en
dc.language.iso eng en
dc.publisher University of British Columbia en
dc.relation.ispartof Electronic Theses and Dissertations (ETDs) 2008+ en
dc.title Convex relaxations of the maximin dispersion problem en
dc.type Text en
dc.degree.name Master of Science - MSc en
dc.degree.discipline Mathematics en
dc.degree.grantor University of British Columbia en
dc.date.graduation 2012-05
dc.type.text Thesis/Dissertation en
dc.description.affiliation Science, Faculty of en
dc.degree.campus UBCO en
dc.description.scholarlevel Graduate en

Files in this item

Files Size Format Description   View
ubc_2012_spring_haines_sheena.pdf 907.1Kb Adobe Portable Document Format   View/Open

This item appears in the following Collection(s)

Show simple item record

UBC Library
1961 East Mall
Vancouver, B.C.
Canada V6T 1Z1
Tel: 604-822-6375
Fax: 604-822-3893