The sensor network localization (SNL) problem in embedding dimension r consists of locating the positions of wireless sensors, given only the distances between sensors that are within radio range and ...the positions of a subset of the sensors (called anchors). Current solution techniques relax this problem to a weighted, nearest, (positive) semidefinite programming (SDP) completion problem by using the linear mapping between Euclidean distance matrices (EDM) and semidefinite matrices. The resulting SDP is solved using primal-dual interior point solvers, yielding an expensive and inexact solution. This relaxation is highly degenerate in the sense that the feasible set is restricted to a low dimensional face of the SDP cone, implying that the Slater constraint qualification fails. Cliques in the graph of the SNL problem give rise to this degeneracy in the SDP relaxation. In this paper, we take advantage of the absence of the Slater constraint qualification and derive a technique for the SNL problem, with exact data, that explicitly solves the corresponding rank restricted SDP problem. No SDP solvers are used. For randomly generated instances, we are able to efficiently solve many huge instances of this NP-hard problem to high accuracy by finding a representation of the minimal face of the SDP cone that contains the SDP matrix representation of the EDM. The main work of our algorithm consists in repeatedly finding the intersection of subspaces that represent the faces of the SDP cone that correspond to cliques of the SNL problem PUBLICATION ABSTRACT
Celotno besedilo
Dostopno za:
CEKLJ, DOBA, IZUM, KILJ, NUK, PILJ, PNG, SAZU, UILJ, UKNU, UL, UM, UPUK
This article presents
BiqCrunch
, an exact solver for binary quadratic optimization problems.
BiqCrunch
is a branch-and-bound method that uses an original, efficient semidefinite-optimization-based ...bounding procedure. It has been successfully tested on a variety of well-known combinatorial optimization problems, such as Max-Cut, Max-
k
-Cluster, and Max-Independent-Set. The code is publicly available online; a web interface and many conversion tools are also provided.
We present an improved algorithm for finding exact solutions to Max-Cut and the related binary quadratic programming problem, both classic problems of combinatorial optimization. The algorithm uses a ...branch-(and-cut-)and-bound paradigm, using standard valid inequalities and nonstandard semidefinite bounds. More specifically, we add a quadratic regularization term to the strengthened semidefinite relaxation in order to use a quasi-Newton method to compute the bounds. The ratio of the tightness of the bounds to the time required to compute them depends on two real parameters; we show how adjusting these parameters and the set of strengthening inequalities gives us a very efficient bounding procedure. Embedding our bounding procedure in a generic branch-and-bound platform, we get a competitive algorithm: extensive experiments show that our algorithm dominates the best existing method.
On FISTA with a relative error rule Bello-Cruz, Yunier; Gonçalves, Max L. N.; Krislock, Nathan
Computational optimization and applications,
03/2023, Letnik:
84, Številka:
2
Journal Article
Recenzirano
The fast iterative shrinkage/thresholding algorithm (FISTA) is one of the most popular first-order iterations for minimizing the sum of two convex functions. FISTA is known to improve the complexity ...of the classical proximal gradient method (PGM) from
O
(
k
-
1
)
to the optimal complexity
O
(
k
-
2
)
in terms of the sequence of the functional values. When the evaluation of the proximal operator is hard, inexact versions of FISTA might be used to solve the problem. In this paper, we proposed an inexact version of FISTA by solving the proximal subproblem inexactly using a relative error criterion instead of exogenous and diminishing error rules. The introduced relative error rule in the FISTA iteration is related to the progress of the algorithm at each step and does not increase the computational burden per iteration. Moreover, the proposed algorithm recovers the same optimal convergence rate as FISTA. Some numerical experiments are also reported to illustrate the numerical behavior of the relative inexact method when compared with FISTA under an absolute error criterion.
This computational paper presents a method to solve k-cluster problems exactly by intersecting semidefinite and polyhedral relaxations. Our algorithm uses a generic branch-and-bound method featuring ...an improved semidefinite bounding procedure. Extensive numerical experiments show that this algorithm outperforms the best known methods both in time and ability to solve large instances. For the first time, numerical results are reported for k-cluster problems on unstructured graphs with 160 vertices.
•Semidefinite-based method to solve k-cluster problems to optimality.•Extensive numerical experiments and theoretical analysis.•Compared favorably with best existing methods.•For the first time, k-cluster instances on graphs with 160 nodes solved to optimality.
This preface introduces the special issue of the Journal of Global Optimization dedicated to the workshop “Distance Geometry Theory and Applications” (DGTA16) which took place at the DIMACS Center, ...Rutgers University, Piscataway NJ, USA.
Contemporary practical methods for protein nuclear magnetic resonance (NMR) structure determination use molecular dynamics coupled with a simulated annealing schedule. The objective of these methods ...is to minimize the error of deviating from the nuclear overhauser effect (NOE) distance constraints. However, the corresponding objective function is highly nonconvex and, consequently, difficult to optimize. Euclidean distance matrix (EDM) methods based on semidefinite programming (SDP) provide a natural framework for these problems. However, the high complexity of SDP solvers and the often noisy distance constraints provide major challenges to this approach. The main contribution of this article is a new SDP formulation for the EDM approach that overcomes these two difficulties. We model the protein as a set of intersecting two- and three-dimensional cliques. Then, we adapt and extend a technique called semidefinite facial reduction to reduce the SDP problem size to approximately one quarter of the size of the original problem. The reduced SDP problem can be solved approximately 100 times faster, and it is also more resistant to numerical problems from erroneous and inexact distance bounds.
We study Semidefinite Programming,
SDP
, relaxations for Sensor Network Localization,
SNL
, with anchors and with noisy distance information. The main point of the paper is to view
SNL
as a (nearest) ...Euclidean Distance Matrix,
EDM
, completion problem that does not distinguish between the anchors and the sensors. We show that there are advantages for using the well studied
EDM
model. In fact, the set of anchors simply corresponds to a given fixed clique for the graph of the
EDM
problem.
We next propose a method of projection when large cliques or dense subgraphs are identified. This projection reduces the size, and improves the stability, of the relaxation. In addition, by viewing the problem as an
EDM
completion problem, we are able to derive a new approximation scheme for the sensors from the
SDP
approximation. This yields, on average, better low rank approximations for the low dimensional realizations. This further emphasizes the theme that
SNL
is in fact just an
EDM
problem.
We solve the
SDP
relaxations using a primal-dual interior/exterior-point algorithm based on the Gauss-Newton search direction. By not restricting iterations to the interior, we usually get lower rank optimal solutions and thus, better approximations for the
SNL
problem. We discuss the relative stability and strength of two formulations and the corresponding algorithms that are used. In particular, we show that the quadratic formulation arising from the
SDP
relaxation is better conditioned than the linearized form that is used in the literature.
PDF
