|
|
Cluster :
|
Nonsmooth and Convex Optimization
|
|
|
Session Information
|
: Tuesday Aug 25, 13:15 - 14:45
|
|
|
Title:
|
Applications of Cone Optimization
|
| Chair: | Henry Wolkowicz,Professor
of Math., University of Waterloo, Dept of Combinatorics &
Optimization, University of Waterloo, Waterloo ON N2L 3G1, Canada,
hwolkowicz@uwaterloo.ca
|
|
|
Abstract Details
|
|
| Title: | Explicit Sensor Network Localization using Semidefinite Programming and Clique Reductions |
| | Presenting Author: | Nathan Krislock,University
of Waterloo, Dept. of Combinatorics & Optimization, University of
Waterloo, Waterloo ON N2L 3G1, Canada, ngbkrisl@math.uwaterloo.ca
|
| | Co-Author: | Henry Wolkowicz,Professor
of Math., University of Waterloo, Dept of Combinatorics &
Optimization, University of Waterloo, Waterloo ON N2L 3G1, Canada,
hwolkowicz@uwaterloo.ca
|
| |
| Abstract: | The
sensor network localization, SNL, problem consists of locating the
positions of sensors, given only the distances between sensors that are
within radio range and the positions of some fixed sensors (called
anchors). Using the theory of Euclidean Distance Matrices, EDMs, we
relax SNL to a semidefinite programming, SDP, problem. The feasible set
of this SDP is restricted to a low dimensional face of the SDP cone,
causing the Slater constraint qualification to fail. By finding
explicit representations of the faces of the SDP cone corresponding to
intersections of cliques of the SNL problem, we derive a preprocessing
technique that solves the SNL problem, with exact data, by explicitly
solving the corresponding SDP problem. |
| | |
| Title: | SDP Representation of Rational and Singular Convex Sets |
| | Presenting Author: | Jiawang Nie,Assistant
Professor, University of California at San Diego, UCSD, Mathematics
Department, 9500 Gilman Drive, La Jolla CA 92093, United States of
America, njw@math.ucsd.edu
|
| | Co-Author: | J. William Helton,UCSD, 9500 Gilman Drive, Mathematics Department, La Jolla CA 92093, United States of America, helton@math.ucsd.edu
|
| |
| Abstract: | A
set is called SDP representable if it is expressible by some linear
matrix inequality via lifting variables. First, we will present a
general result: A set S defined by polynomial inequalities is SDP
representable if its boundary pieces are nonsingular and positively
curved. Second, we will present conditions for SDP representability
when S is defined by multivariate rational polynomial functions or its
boundary pieces have singularities. Specific examples will also be
shown.
|
| | |
| Title: | Graph Realizations Corresponding to Optimized Extremal Eigenvalues of the Laplacian |
| | Presenting Author: | Christoph Helmberg,Technische Universität Chemnitz, Fakultät für Mathematik, Chemnitz D-09107, Germany, helmberg@mathematik.tu-chemnitz.de
|
| | Co-Author: | Frank Goering,Technische Universitaet Chemnitz, Strasse der Nationen 62, Chemnitz 09107, Germany, frank.goering@mathematik.tu-chemnitz.de
|
| | | Susanna Reiss,Technische Universität Chemnitz, Fakultät für Mathematik, Chemnitz 09107, Germany, susanna.reiss@mathematik.tu-chemnitz.de
|
| | | Markus Wappler,Technische Universität Chemnitz, Fakultät für Mathematik, Chemnitz, Germany, markus.wappler@mathematik.tu-chemnitz.de
|
| |
| Abstract: | We
study graph realizations in Euclidean space obtained from optimal
solutions of semidefinite programs for optimizing the maximal and
minimal eigenvalue of the Laplace matrix of a graph by redistributing
the mass on the edges of the graph. We show that the geometric
structure of optimal graph realizations is tightly linked to the
separator structure of the graph and that in both cases there exist
optimal realizations whose dimension is bounded by the tree width of
the graph plus one.
|
| | |
|
