A QP-free constrained Newton-type method for variational inequality problems

Received January 5, 1997 / Revised version received November 19, 1997 Published online November 24, 1998     

Convex optimization learning of faithful Euclidean distance representations in nonlinear dimensionality reduction

Classical multidimensional scaling only works well when the noisy distances observed in a high dimensional space can be faithfully represented by Euclidean distances in a low dimensional space. Advanced models such as Maximum Variance Unfolding (MVU) and Minimum Volume Embedding (MVE) use Semi-Definite Programming (SDP) to reconstruct such faithful representations. While those SDP models are capable of producing high quality configuration numerically, they suffer two major drawbacks. One is that there exist no theoretically guaranteed bounds on the quality of the configuration. The other is that they are slow in computation when the data points are beyond moderate size. In this paper, we propose a convex optimization model of Euclidean distance matrices. We establish a non-asymptotic error bound for the random graph model with sub-Gaussian noise, and prove that our model produces a matrix estimator of high accuracy when the order of the uniform sample size is roughly the degree of freedom of a low-rank matrix up to a logarithmic factor. Our results partially explain why MVU and MVE often work well. Moreover, the convex optimization model can be efficiently solved by a recently proposed 3-block alternating direction method of multipliers. Numerical experiments show that the model can produce configurations of high quality on large data points that the SDP approach would struggle to cope with.

     

Convex Euclidean distance embedding for collaborative position localization with NLOS mitigation

One of the challenging problems in collaborative position localization arises when the distance measurements contain non-line-of-sight (NLOS) biases. Convex optimization has played a major role in modelling such problems and numerical algorithm developments. One of the successful examples is the semi-definite programming (SDP), which translates Euclidean distances into the constraints of positive semidefinite matrices, leading to a large number of constraints in the case of NLOS biases. In this paper, we propose a new convex optimization model that is built upon the concept of Euclidean distance matrix (EDM). The resulting EDM optimization has an advantage that its Lagrangian dual problem is well structured and hence is conducive to algorithm developments. We apply a recently proposed 3-block alternating direction method of multipliers to the dual problem and tested the algorithm on some real as well as simulated data of large scale. In particular, the EDM model significantly outperforms the existing SDP model and several others.     

A Smoothing Newton Method for General Nonlinear Complementarity Problems

Smoothing Newton methods for nonlinear complementarity problems NCP(F) often require F to be at least a P ₀-function in order to guarantee that the underlying Newton equation is solvable. Based on a special equation reformulation of NCP(F), we propose a new smoothing Newton method for general nonlinear complementarity problems. The introduction of Kanzow and Pieper's gradient step makes our algorithm to be globally convergent. Under certain conditions, our method achieves fast local convergence rate. Extensive numerical results are also reported for all complementarity problems in MCPLIB and GAMSLIB libraries with all available starting points.     

Optimal portfolio selections via $$\ell _{1, 2}$$ ℓ 1 , 2 -norm regularization

Computational Optimization and Applications - There has been much research about regularizing optimal portfolio selections through $$\ell _1$$ norm and/or $$\ell _2$$ -norm squared. The common...     

Computing the nearest Euclidean distance matrix with low embedding dimensions

Euclidean distance embedding appears in many high-profile applications including wireless sensor network localization, where not all pairwise distances among sensors are known or accurate. The classical Multi-Dimensional Scaling (cMDS) generally works well when the partial or contaminated Euclidean Distance Matrix (EDM) is close to the true EDM, but otherwise performs poorly. A natural step preceding cMDS would be to calculate the nearest EDM to the known matrix. A crucial condition on the desired nearest EDM is for it to have a low embedding dimension and this makes the problem nonconvex. There exists a large body of publications that deal with this problem. Some try to solve the problem directly and some are the type of convex relaxations of it. In this paper, we propose a numerical method that aims to solve this problem directly. Our method is strongly motivated by the majorized penalty method of Gao and Sun for low-rank positive semi-definite matrix optimization problems. The basic geometric object in our study is the set of EDMs having a low embedding dimension. We establish a zero duality gap result between the problem and its Lagrangian dual problem, which also motivates the majorization approach adopted. Numerical results show that the method works well for the Euclidean embedding of Network coordinate systems and for a class of problems in large scale sensor network localization and molecular conformation.