Matrix optimization based Euclidean embedding with outliers

Euclidean embedding from noisy observations containing outlier errors is an important and challenging problem in statistics and machine learning. Many existing methods would struggle with outliers due to a lack of detection ability. In this paper, we propose a matrix optimization based embedding model that can produce reliable embeddings and identify the outliers jointly. We show that the estimators obtained by the proposed method satisfy a non-asymptotic risk bound, implying that the model provides a high accuracy estimator with high probability when the order of the sample size is roughly the degree of freedom up to a logarithmic factor. Moreover, we show that under some mild conditions, the proposed model also can identify the outliers without any prior information with high probability. Finally, numerical experiments demonstrate that the matrix optimization-based model can produce configurations of high quality and successfully identify outliers even for large networks.

     

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.     

The K -discretization and K -incident graphs for discretizable Distance Geometry

The Distance Geometry Problem (DGP) is the problem of determining whether a realization for a simple weighted undirected graph $$G=(V,E,d)$$ in a given Euclidean space exists so that the distances between pairs of realized vertices u, $$v \in V$$ correspond to the weights $$d_{uv}$$, for each $$\{u,v\} \in E$$. We focus on a special class of DGP instances, referred to as the Discretizable DGP (DDGP), and we introduce the K-discretization and the K-incident graphs for the DDGP class. The K-discretization graph is independent on the vertex order that can be assigned to V, and can be useful for discovering whether one of such orders actually exists so that the DDGP assumptions are satisfied. The use of a given vertex order allows the definition of another important graph, the K-incident graph, which is potentially useful for performing pre-processing analysis on the solution set of DDGP instances.     

The problem of finding a subset of vectors with the maximum total weight

The NP-hardness is proved for the discrete optimization problems connected with maximizing the total weight of a subset of a finite set of vectors in Euclidean space, i.e., the Euclidean norm of the sum of the members. Two approximation algorithms are suggested, and the bounds for the relative error and time complexity are obtained. We give a polynomial approximation scheme in the case of a fixed dimension and distinguished a subclass of problems solvable in pseudopolynomial time. The results obtained are useful for solving the problem of choice of a fixed number of subsequences from a numerical sequence with a given number of quasiperiodical repetitions of the subsequence.     

Nonsmooth optimization reformulations characterizing all solutions of jointly convex generalized Nash equilibrium problems

Generalized Nash equilibrium problems (GNEPs) allow, in contrast to standard Nash equilibrium problems, a dependence of the strategy space of one player from the decisions of the other players. In this paper, we consider jointly convex GNEPs which form an important subclass of the general GNEPs. Based on a regularized Nikaido-Isoda function, we present two (nonsmooth) reformulations of this class of GNEPs, one reformulation being a constrained optimization problem and the other one being an unconstrained optimization problem. While most approaches in the literature compute only a so-called normalized Nash equilibrium, which is a subset of all solutions, our two approaches have the property that their minima characterize the set of all solutions of a GNEP. We also investigate the smoothness properties of our two optimization problems and show that both problems are continuous under a Slater-type condition and, in fact, piecewise continuously differentiable under the constant rank constraint qualification. Finally, we present some numerical results based on our unconstrained optimization reformulation.     

Distance Matrix Completion by Numerical Optimization

Consider the problem of determining whether or not a partial dissimilarity matrix can be completed to a Euclidean distance matrix. The dimension of the distance matrix may be restricted and the known dissimilarities may be permitted to vary subject to bound constraints. This problem can be formulated as an optimization problem for which the global minimum is zero if and only if completion is possible. The optimization problem is derived in a very natural way from an embedding theorem in classical distance geometry and from the classical approach to multidimensional scaling. It belongs to a general family of problems studied by Trosset (Technical Report 97-3, Department of Computational & Applied Mathematics—MS 134, Rice University, Houston, TX 77005-1892, 1997) and can be formulated as a nonlinear programming problem with simple bound constraints. Thus, this approach provides a constructive technique for obtaining approximate solutions to a general class of distance matrix completion problems.     

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.     

An iterative method of solution for equilibrium and optimization problems

In this paper, we introduce an iterative scheme for finding a common element of the set of fixed points of a nonexpansive mapping, the set of solutions of the variational inequality for an inverse-strongly monotone mapping and the set of solutions of an equilibrium problem in a Hilbert space. We show that the iterative sequence converges strongly to a common element of the three sets. The results of this paper extended and improved the results of H. Iiduka and W. Takahashi [Strong convergence theorems for nonexpansive mappings and inverse-strongly monotone mappings, Nonlinear Anal. 61 (2005) 341–350] and S. Takahashi and W. Takahashi [Viscosity approximation methods for equilibrium problems and fixed point problems in Hilbert spaces, J. Math. Anal. Appl. 331 (2007) 506–515]. Therefore, by using the above result, an iterative algorithm for the solution of a optimization problem was obtained.     

Robust optimization with applications to game theory

In this article, we investigate robust optimization equilibria with two players, in which each player can neither evaluate his opponent's strategy nor his own cost matrix accurately while may estimate a bounded set of the strategy or cost matrix. We obtain a result that solving this equilibria can be formulated as solving a second-order cone complementarity problem under an ellipsoid uncertainty set or a mixed complementarity problem under a box uncertainty set. We present some numerical results to illustrate the behaviour of robust optimization equilibria.     

An application-based characterization of dynamical distance geometry problems

The dynamical distance geometry problem (dynDGP) is the problem of finding a realization in a Euclidean space of a weighted undirected graph G representing an animation by relative distances, so that the distances between realized vertices are as close as possible to the edge weights. In the dynDGP, the vertex set of the graph G is the set product of V, representing certain objects, and T, representing time as a sequence of discrete steps. We suppose moreover that distance information is given together with the priority of every distance value. The dynDGP is a special class of the DGP where the dynamics of the problem comes to play an important role. In this work, we propose an application-based characterization of dynDGP instances, where the main criteria are the presence or absence of a skeletal structure, and the rigidity of such a skeletal structure. Examples of considered applications include: multi-robot coordination, crowd simulations, and human motion retargeting.     

A linearly convergent iterative method for identifying H-matrices

ABSTRACT

H-matrices play an important role in applied sciences such as numerical analysis and optimization theory. An attractive question is to identify whether a given matrix is an H-matrix. In this paper, we propose a new iterative algorithm for identifying H-matrices. We show that the proposed algorithm has linear convergence and can determine the H-matrix characterization for any given matrix. Its performance is illustrated in a set of numerical tests.     

Bi-criteria evolution strategy in estimating weights from the AHP ratio-scale matrices

The problem of deriving weights from ratio-scale matrices in an analytic hierarchy process (AHP) is addressed by researchers worldwide. There are various ways to solve the problem that are generally grouped into simple matrix and optimization methods. All methods have received criticism regarding the accuracy of derived weights, and different criteria are in use to compare the weights obtained from different methods. Because the set of Pareto non-dominated solutions (weights) is unknown and for inconsistent matrices is indefinite, a bi-criterion optimization approach is proposed for manipulating such matrices. The problem-specific evolution strategy algorithm (ESA) is implemented for a robust stochastic search over a feasible indefinite solution space. The fitness function is defined as a scalar vector function composed of the common error measure, i.e. the Euclidean distance and a minimum violation error that accounts for no violation of the rank ordering. The encoding scheme and other components of the search engine are adjusted to preserve the imposed constraints related to the required normalized values of the weights. The solutions generated by the proposed approach are compared with solutions obtained by five well-known prioritization techniques for three judgment matrices taken from the literature. In these and other test applications, the prioritization method that uses the entitled weights estimation by evolution strategy algorithm (WEESA) appears to be superior to other methods if only two, the most commonly used methods, are applied: the Euclidean distance and minimum violation exclusion criteria.     

On the convexity of integrals of multivalued mappings: Applications in control theory

Using the notion of the local convexity index, we characterize in a quantitative way the local convexity of a set in then-dimensional Euclidean space, defined by an integral of a multivalued mapping. We estimate the rate of convergence of the conditional gradient method for solving an abstract optimization problem by means of the convexity index of the constraining set at the solution point. These results are applied to the qualitative analysis of the solutions of time-optimal and Mayer problems for linear control systems, as well as for estimating the convergence rate of algorithms solving these problems.     

Reducing the bandwidth of a sparse matrix with a genetic algorithm

Abstract

The matrix bandwidth minimization problem (MBMP) consists in finding a permutation of the lines and columns of a given sparse matrix in order to keep the non-zero elements in a band that is as close as possible to the main diagonal. Equivalently in terms of graph theory, MBMP is defined as the problem of finding a labelling of the vertices of a given graph G such that its bandwidth is minimized. In this paper, we propose an improved genetic algorithm (GA)-based heuristic for solving the matrix bandwidth minimization problem, motivated by its robustness and efficiency in a wide area of optimization problems. Extensively computational results are reported for an often used set of benchmark instances. The obtained results on the different instances investigated show improvement of the quality of the solutions and demonstrate the efficiency of our GA compared to the existing methods in the literature.     

Primal and dual algorithms for optimization over the efficient set

ABSTRACT

Optimization over the efficient set of a multi-objective optimization problem is a mathematical model for the problem of selecting a most preferred solution that arises in multiple criteria decision-making to account for trade-offs between objectives within the set of efficient solutions. In this paper, we consider a particular case of this problem, namely that of optimizing a linear function over the image of the efficient set in objective space of a convex multi-objective optimization problem. We present both primal and dual algorithms for this task. The algorithms are based on recent algorithms for solving convex multi-objective optimization problems in objective space with suitable modifications to exploit specific properties of the problem of optimization over the efficient set. We first present the algorithms for the case that the underlying problem is a multi-objective linear programme. We then extend them to be able to solve problems with an underlying convex multi-objective optimization problem. We compare the new algorithms with several state of the art algorithms from the literature on a set of randomly generated instances to demonstrate that they are considerably faster than the competitors.     

Smoothing method in multi-criteria transportation network equilibrium problem

ABSTRACT

This paper is aimed to study a single-product multi-criteria transportation network with capacity constraints. We use a vector version of the Heaviside Step function to construct an optimization problem, the solutions of which form the set of equilibria of our model. We propose two methods to solve this problem. The first one is based on a modified Frank-Wolfe gradient algorithm, and the second one is based on smoothing the objective function, the optimal solutions of which can be obtained by optimization tools. Numerical examples are also given to illustrate our approaches.     

Pareto Solutions of Polyhedral-valued Vector Optimization Problems in Banach Spaces

In general Banach spaces, we consider a vector optimization problem (SVOP) in which the objective is a set-valued mapping whose graph is the union of finitely many polyhedra. We establish some results on structure and connectedness of the weak Pareto solution set, Pareto solution set, weak Pareto optimal value set and Pareto optimal value set of (SVOP). In particular, we improve and generalize Arrow, Barankin and Blackwell’s classical results on linear vector optimization problems in Euclidean spaces.     

Axiomatizations of the Euclidean compromise solution

A multicriteria optimization problem is one of choosing an alternative that optimizes several—possibly conflicting—objective functions simultaneously. The utopia point of a multicriteria optimization problem is the vector that specifies for each objective function the most favorable feasible value. The Euclidean compromise solution in multicriteria optimization is a solution that selects from a feasible set the alternative such that its vector of criteria values has minimal Euclidean distance to the utopia point. This paper provides several axiomatic characterizations of the Euclidean compromise solution that are based on consistency properties.     

A distributed genetic algorithm for deterministic and stochastic labor scheduling problems

A recurring operational decision in many service organizations is determining the number of employees, and their work schedules, that minimize labor expenses and expected opportunity costs. These decisions have been modeled as generalized set covering (GSC) problems, deterministic goal programs (DGP), and stochastic goal programs (SGP); each a challenging optimization problem. The pervasiveness and economic significance of these three problems has motivated ongoing development and refinement of heuristic solution procedures. In this paper we present a unified formulation for these three labor scheduling problems and introduce a distributed genetic algorithm (DGA) that solves each of them.Our distributed genetic algorithm operates in parallel on a network of message-passing workstations. Separate subpopulations of solutions evolve independently on each processor but occasionally, the fittest solutions migrate over the network to join neighboring subpopulations. With its standard genetic operators, DGA frequently produces infeasible offspring. A few of these are repaired before they enter the population. However, most enter the population as-is, carrying an appropriate fitness penalty. This allows DGA to exploit potentially favorable adaptations that might be present in infeasible solutions while orienting the locus of the search near the feasible region.We applied the DGA to suites of published test problems for GSC, DGP, and SGP formulations and compared its performance with alternative solution procedures, including other metaheuristics such as simulated annealing and tabu search. We found that DGA outperformed the competing alternatives in terms of mean error, maximum error, and percentage of least cost solutions. While DGA is computationally intensive, the quality of its solutions is commensurate with the effort expended. In plots of solution quality versus CPU time for the various algorithms evaluated in our study, DGA consistently appeared on the efficient frontier.     

Sensitivity Analysis of Merit Function in Solving Nonlinear Equations by Optimization

To solve nonlinear equations by an optimization method, scaling is very important. Two types of poor scaling where: (a) the variables differ greatly in magnitude; (b) the merit function of system is highly sensitive to small changes in certain variables and relatively insensitive to changes in other variables. If poor scaling is ignored, the algorithm may produce solutions with poor quality. To solve (a), we can change units of variables. A numerical solution of the nonlinear equations produced by the finite volume method in the forced convective heat transfer of a nanofluid, as a case study, indicates that the poor scaling (b) is solved by using the Euclidean norm of columns of the Jacobian matrix as scaling data, while some researchers proposed diagonal elements of the Hessian matrix as scaling data.