We analyze the semidefinite programming (SDP) based model and method for the position estimation problem in sensor network localization and other Euclidean distance geometry applications. We use SDP duality and interior–point algorithm theories to prove that the SDP localizes any network or graph that has unique sensor positions to fit given distance measures. Therefore, we … Read more
We consider the problem of computing the outer-radii of point sets. In this problem, we are given integers $n, d, k$ where $k \le d$, and a set $P$ of $n$ points in $R^d$. The goal is to compute the {\em outer $k$-radius} of $P$, denoted by $\kflatr(P)$, which is the minimum, over all $(d-k)$-dimensional … Read more
We prove that if two smooth manifolds intersect transversally, then the method of alternating projections converges locally at a linear rate. We bound the speed of convergence in terms of the angle between the manifolds, which in turn we relate to the modulus of metric regularity for the intersection problem, a natural measure of conditioning. … Read more
The traffic assignment problem with elastic demands can be formulated as an optimization problem, whose objective is sum of a congestion function and a disutility function. We propose to use a variant of the Analytic Center Cutting Plane Method to solve this problem. We test the method on instances with different congestion functions (linear with … Read more
The paper deals with an optimal control problem with a scalar first-order state constraint and a scalar control. In presence of (nonessential) touch points, the arc structure of the trajectory is not stable. We show how to perform a sensitivity analysis that predicts which touch points will, under a small perturbation, become inactive, remain touch … Read more
We use the proximal point method with the phi-divergence given by phi(t) = t – log t – 1 for the minimization of quasiconvex functions subject to nonnegativity constraints. We establish that the sequence generated by our algorithm is well-defined in the sense that it exists and it is not cyclical. Without any assumption of … Read more
We show that the problem of computing sharp upper and lower static-arbitrage bounds on the price of a European basket option, given the prices of other similar options, can be cast as a linear program (LP). The LP formulations readily yield super-replicating (sub-replicating) strategies for the upper (lower) bound problem. The dual counterparts of the … Read more
The Lipschitz Global Optimizer (LGO) software integrates global and local scope search methods, to handle nonlinear optimization models. Here we discuss the LGO implementation linked to the General Algebraic Modeling System (GAMS). First we review the key features and basic usage of the GAMS /LGO solver option, then present reproducible numerical results to illustrate its … Read more
It has been known since the early 1970s that the Hessian matrices in quasi-Newton methods can be updated by variational means, in several different ways. The usual formulation of these variational problems uses a coordinate system, and the symmetry of the Hessian matrices are enforced as explicit constraints. As a result, the variational problems seem … Read more
Wavelet decomposition problems have been modeled as linear programs – but only as extremely dense problems. Both revised simplex and interior point methods have difficulty with dense linear programs. The question then is how to get around that issue. In our experiments the standard method outperforms a revised implementation for these problems. Moreover, the standard … Read more