Search

The simplex method, as proposed by Dantzig in 1947, is a widely-used practical algorithm for solving Linear Programs (LPs)—systems of linear inequalities headed by a single linear objective function. We examine the difficulty of implementing quantum subroutines outlined by Nannicini in Fast quantum subroutines for the simplex method. Classically, choosing an entering variable in an LP with n optimization variables, m constraints, and at most d c non-zero entries per column requires $O\left({d_c^{0.7}{m^{1.9}} + {m^{2 + o(1) + {d_c}n}}}\right)$ time using the fastest known algorithm for sparse matrix multiplication. By using quantum subroutines Nannicini’s approach results in $O\left({\frac{1}{\varepsilon }\kappa d\sqrt n \left({{d_c}n + dm}\right)}\right)$ time, where O hides polylogarithmic factors. We examine the implementation of subroutine FindColumn (A,B,ϵ) that selects a valid entering variable (if any) using quantum search and quantum phase estimation algorithms; here, A is the constraint matrix, B is the basis and ϵ is optimality tolerance. We focus on challenges presented by transforming the matrices and vectors given by an LP into quantum states and the preparation of the oracle. We discuss our implementation and encountered challenges when implementing the algorithm using IBM’s Quantum Experience.

Construction of tight confidence sets and intervals is central to statistical inference and decision making. This paper develops new theory showing minimum average volume confidence sets for categorical data. More precisely, consider an empirical distribution $\widehat{p}$ generated from $n$ iid realizations of a random variable that takes one of $k$ possible values according to an unknown distribution $p$ . This is analogous to a single draw from a multinomial distribution. A confidence set is a subset of the probability simplex that depends on $\widehat{p}$ and contains the unknown $p$ with a specified confidence. This paper shows how one can construct minimum average volume confidence sets. The optimality of the sets translates to improved sample complexity for adaptive machine learning algorithms that rely on confidence sets, regions and intervals.

Z 2 $s$ -additive codes are subgroups of Zn 2 s, and can be seen as a generalization of linear codes over Z 2 and Z 4 . A Z 2 $s$ -linear code is a binary code (not necessarily linear) which is the Gray map image of a Z 2 $s$ -additive code. We consider Z 2 s- additive simplex codes of type a and β, which are a generalization over $Z$ 2 $s$ of the binary simplex codes. These codes are related to the Z 2 $s$ -additive Hadamard codes. In this paper, we use this relationship to find a linear subcode of the corresponding $Z$ 2 s-linear codes, called kernel, and a representation of these codes as cosets of this kernel. In particular, this also gives the linearity of these codes. Similarly, Z 2 $s$ -additive MacDonald codes are defined for $s$ > 2, and equivalent results are obtained.

Consider the problem of representing a distribution $\pi$ on a large alphabet of size $k$ up to fidelity $\varepsilon$ in Kullback-Leibler (KL) divergence. Heuristically, arguing as for quadratic loss in high dimension, one expects that about $(k/2)\log(1/\varepsilon)$ bits would be required. We show this intuition is correct by proving explicit non-asymptotic bounds for the minimal average distortion when $\pi$ is randomly sampled from a symmetric Dirichlet prior on the simplex. Our method is to reduce the single-sample problem to the traditional setting of iid samples, but for a non-standard rate distortion question with the novel distortion measure $d(x, y)= x\log(x/y)$ , which we call divergence distortion. Practically, our results advocate using a $x\mapsto x^{2/3}$ compander (for small $x$ ) followed by a uniform scalar quantizer for storing large-alphabet distributions.

Sparse manifold learning algorithms combine techniques in manifold learning and sparse optimization to learn features that could be utilized for downstream tasks. The standard setting of compressive sensing can not be immediately applied to this setup. Due to the intrinsic geometric structure of data, dictionary atoms might be redundant and do not satisfy the restricted isometry property or coherence condition. In addition, manifold learning emphasizes learning local geometry which is not reflected in a standard l 1 minimization problem. We propose weighted l 0 and weighted l 1 regularizations that encourage representation via neighborhood atoms suited for dictionary based manifold learning. Assuming that the data is generated from Delaunay triangulation, we show the equivalence of weighted l 1 and weighted l 0 . We discuss an optimization program that learns the dictionaries and sparse co-efficients and demonstrate the utility of our regularization on synthetic and real datasets.

Current performance indicators for assessing the diversity of many-objective optimisation approximations are often underperforming as the number of objectives increases, particularly for complex optimisation problems. In this article, a new pure unary diversity indicator is proposed, Inverse Ratio of Net Avertence angle (IRNA), which is formulated by minimising the sum of the included angles between approximation set and a set of reference vectors. It is achieved by effectively rotating the reference vectors system in all dimensions simultaneously with an optimised spatial angle. Any potential systematic bias in included angles is removed, and the highest possible diversity score of a solution set is obtained. Numerical results from evaluating performance on synthetic solutions on a unit simplex plane and benchmark functions of MaF show that the proposed performance indicator IRNA is more sensitive to capturing diversity changes as the number of objectives increases compared to other popular indicators.

Reference sets are widely used by many multi-objective evolutionary algorithms (MOEAs) to decompose the objective space, define search directions, or calculate quality indicators (QIs) embedded into the selection mechanisms. Well-known MOEAs adopt the generation of uniformly distributed points on a unit simplex to construct such reference sets. Although these mechanisms are useful for approximating Pareto fronts with regular shapes, i.e., simplex-like shapes, they have difficulties representing Pareto fronts with irregular geometries. To overcome this drawback, many reference set adaptation methods have been proposed so far. However, some adaptation methods present a degraded performance on regular Pareto front shapes, while others promote a balanced performance. Nevertheless, an extensive assessment has not been made. In this paper, a MOEA based on the inverted generational distance plus indicator, using an adaptive reference set, is used to study the performance of well-known adaptation methods. Although an adaptation method promotes a balanced performance on both regular and irregular Pareto front shapes, results show some difficulties related to the distribution of solutions in complex Pareto front shapes. The results of this study allow detecting the main drawbacks of adaptation methods, which can be addressed by using diversity-oriented selection mechanisms in the generation of reference sets. Hence, these could impact the generation of reference set-based MOEAs achieving good coverage, convergence, and diversity regardless of the Pareto front shape.

Fingerprint liveness detection is an effective way to ensure the security and reliability of fingerprint recognition algorithms against spoof fingerprint attacks. Local descriptors are one of the most widely studied fingerprint liveness detection algorithms. However, the performance of simplex local descriptors or simple voting models among multiple descriptors still can-not achieve satisfactory accuracy, robustness, and applicability. This paper proposes a 2-layer parallel Support Vector Machine (SVM) network to improve the classification performance of local descriptors and achieve 95.32% accuracy on the LivDet datasets (2009, 2011, 2013, and 2015). The experimental results and theoretical analysis indicate that the proposed 2-layer parallel SVM network based on aggregated local descriptors shows better detection accuracy and model robustness against adversarial attacks compared with simplex descriptors and state-of-the-art neural network structures. Besides, the 2-layer parallel SVM network can save training time through parallel computing, and achieve extremely high accuracy and reliability through ultra-high-dimensional descriptor classification.

Spatial graph embedding is a technique for placing graphs in space used for visualization and graph analytics. The general goal is to place connected nodes close together while spreading apart all others. Previous work has looked at spatial graph embedding in 2 or 3 dimensions. These used high performance libraries and fast algorithms for N-body simulation. We expand into higher dimensions to find what it can be useful for. Using an arbitrary number of dimensions allows all unweighted graph to have exact edge lengths, as n nodes can all be one distance part in a n − 1 dimensional simplex. This increases the complexity of the simulation, so we provide an efficient GPU implementation in high dimensions. Although high dimensional embeddings cannot be easily visualized they find a consistent structure which can be used for graph analytics. Problems this has been used to solve are graph isomorphism and graph coloring.

This article is devoted to some results of research on improving the multiparameter multiextremal optimization algorithm in proposed author”s evolutionary algorithm version Simplex Evolution program. The research was conducted in the Visual Studio software environment using the C# programming language and its multithreaded method. For this solution, the “main” thread is the user interface for setting and processing results, and all other threads are parallel interacting elements groups that move in the search space to the best multi-extreme function solution. At each evolutionary algorithm step, elimination is performed for each stream. The essence of which is to remove the worst solutions results, which are replaced by new, randomly selected starting points. The target function acts as a measure of fitness for the environment. The probability of finding a global extreme depends on both the number of search points in the groups (population size) and the number of streams. The results obtained show a significant increase in the probability of finding a global extremum and an increase in the algorithm's performance in parallel multithreaded calculations compared to single-threaded ones. The Simplex Evolution algorithm shell is intended for implementation in MATLAB and SimInTech libraries as a built-in function.

We report on the experimental results of the combination of unique auto-correlation properties of Golay complementary code and Hadamard matrix properties of standard simplex code. The combination of the two coding techniques results in improvement of the signal-to-noise ratio (SNR) of time domain multiplexed fiber Bragg grating (TDM-FBG) sensor for temperature measurement. Previously, we have analyzed the properties of both coding techniques when deployed separately in the TDM-FBG sensor. In this case, both coding techniques result in the same amount of SNR improvement for code length longer than 31 bits. In this paper, we demonstrate the combination and simultaneous deployment of the two techniques to measure multiple FBGs under room condition (25 °C) and 50 °C temperature. The two schemes combination results in remarkable improvement of SNR and still retains the original spatial property of the decoded FBG signals, confirming the successful deployment of the hybrid codes. From the measurement of two FBG sensors located after 16 km of fiber, the combination of 31 bits of simplex- and 64 bits of Golay codes has resulted in a total of 10.5 dB improvement of SNR.

This paper presents a proposal of a faster Wasserstein $k$-means algorithm for histogram data by reducing Wasserstein distance computations and exploiting sparse simplex projection. We shrink data samples, centroids, and the ground cost matrix, which leads to considerable reduction of the computations used to solve optimal transport problems without loss of clustering quality. Furthermore, we dynamically reduced the computational complexity by removing lower-valued data samples and harnessing sparse simplex projection while keeping the degradation of clustering quality lower. We designate this proposed algorithm as sparse simplex projection based Wasserstein $k$-means, or SSPW $k$-means. Numerical evaluations conducted with comparison to results obtained using Wasserstein $k$-means algorithm demonstrate the effectiveness of the proposed SSPW $k$-means for real-world datasets, Comment: Accepted in ICPR2020

A more stationary and discriminative embedding is necessary for robust classification of images. We focus our attention on the newel CapsNet model and we propose the angular margin loss function in composition with margin loss. We define a fixed classifier implemented with fixed weights vectors obtained by the vertex coordinates of a simplex polytope. The advantage of using simplex polytope is that we obtain the maximal symmetry for stationary features angularly centred. Each weight vector is to be considered as the centroid of a class in the dataset. The embedding of an image is obtained through the capsule network encoding phase, that is identified as digitcaps matrix. Based on the centroids from the simplex coordinates and the embedding from the model, we compute the angular distance between the image embedding and the centroid of the correspondent class of the image. We take this angular distance as angular margin loss. We keep the computation proposed for margin loss in the original architecture of CapsNet. We train the model to minimise the angular between the embedding and the centroid of the class and maximise the magnitude of the embedding for the predicted class. The experiments on different datasets demonstrate that the angular margin loss improves the capability of capsule networks with complex datasets.

In deep learning, hyperparameters can severely affect the learning model performance. The Nelder-Mead (NM) method is known for showing a superior performance for hyperparameter optimization in deep learning. An initial simplex, one of the initial NM method's values, is usually determined randomly while the search performance strongly depends on the shape of the initial simplex. Therefore, it is necessary to determine a proper initial simplex as previous researchers have proposed methods to construct an initial simplex from one starting point in the bounded search space. In this study, we verified how these methods for constructing an initial simplex contribute to improving the result of hyperparameter optimization in deep learning, by using a simple model and a complicated model. A smaller initial simplex may fail to optimization by bad local minima because there are some bad local minima in both learning models. We concluded that the starting point is not necessarily located close to the origin, and that a larger initial simplex contributes to improving the result of hyperparameter optimization in deep learning.

As a bridge linking propagating waves and surface waves, reflective metasurfaces play a significant role to manipulate electromagnetic (EM) waves. Without transmission coefficients, however, the effective constitutive parameters (e eff , μ eff , n eff , z eff ) of reflective metasurfaces cannot be retrieved by conventional theory. In this work, an innovative method using single S-parameters (only S 11 ) is proposed to retrieve the effective EM parameters for reflective metasurfaces. The validity of the method is demonstrated by imping TE-polarized EM waves normally and obliquely on the single- and multiple-layer unit cells. The retrieved results match well with each other corresponding to the assumption of passive homogeneous mediums. This method is beneficial for the design of reflective metasurfaces and other applications of anomalous reflection.

The project is intended to cover main issues pertaining to the area of a signal processing inside the fiberwire Raman sensors. The target of the proposed system is increasing the signal to noise ratio, by means of the simplex coding. The emphasis here is not based on perfecting the Raman sensors scheme, but rather on refining the digital signal processing. The paper will be arranged as follows: analyzing literature, revealed the regularities between the growth of temperature resolution and the simplex coding, computer simulation of the Raman sensors. As a result, the output signal-processing algorithm, which is strengthening the output signal amplitude will be obtained. The question posed will help to understand the simplex coding nature for various scholars.

In materials handling activities, finding the best route for vehicles is a key factor for the improvement of productivity and efficiency and, reduction of costs. The shortest path is the most common criterion adopted in a routing problem. The difficulty in solving this problem is due to a large number of nonoptimal solutions. The best path is not always found if the quantity of maneuvers is not taken into account in the route. This paper reports a comparison of Dijkstra and Network Simplex Algorithms, and propose a modified version of Dijkstra's Algorithm to reduce the number of vehicle maneuvers. In the results, as the environment complexity increased, the differences in the algorithm performances were highlighted.

In this work, aiming at reflective metasurfaces, an innovative method based on a one-port network model is proposed to retrieve the constitutive effective parameters (CEPs) only using S 11 . The theory is demonstrated by calculating the CEPs for different incident angles and multiple-layer metasurfaces. The results match well with each other.

Through Simplex LP the optimized results of our optimization are projected. Setting our goal by finding the best way where to increase the time interval rate through transportation modeling. The total waiting time before the manipulation of intervals was at the peak total time through minimization, and by confirming that the constraints give us a minimized value. Hence, the transportation method also showed us the critically affected stations that contribute delay to the interval time of trains in LRT 2.

Endmember determination is a key step of spectral unmixing, which decomposes a mixed pixel into endmembers and corresponding fractional abundances for hyperspectral imagery. So far, convex geometry-based endmember determination methods have attracted much attention due to their clear physical meaning and light computational burden. Recently, a Fast Gram Determinant-based Algorithm (FGDA) has been proposed as an efficient endmember determination method for hyperspectral imagery. In this letter, we further implement the derivation of endmember score index (ESI) defined in FGDA. From the algebra and geometric view, we find interestingly that the ESI is actually the height of a new vertex to the hyperplane or simplex linear spanned by previously found endmembers (base), and essentially the FGDA is equivalent to the Automatic Target Generation Process (ATGP) when their initial condition is the same.

The three-dimensional (3D) simplex interpolation method, which only uses the same shape and size of tetrahedrons for all points, is proposed. The maximum and root-means-square (RMS) errors are analyzed for the proposed simplex, traditional simplex and Lagrange interpolations. The interpolation regions are chosen basing on the smallest interpolation error or simpler numerical implementation. Numerical results verified that the proposed simplex interpolation makes the interpolation simple, easy to be implemented, and more efficient.

As members of a network share more information with each other and network providers, sensitive data leakage raises privacy concerns. To address this need for a class of problems, we introduce a novel mechanism that privatizes vectors belonging to the unit simplex. Such vectors can be seen in many applications, such as privatizing a decision-making policy in a Markov decision process. We use differential privacy as the underlying mathematical framework for these developments. The introduced mechanism is a probabilistic mapping that maps a vector within the unit simplex to the same domain according to a Dirichlet distribution. We find the mechanism well-suited for inputs within the unit simplex because it always returns a privatized output that is also in the unit simplex. Therefore, no further projection back onto the unit simplex is required. We verify the privacy guarantees of the mechanism for two cases, namely, identity queries and average queries. In the former case, we derive expressions for the differential privacy level of privatizing a single vector within the unit simplex. In the latter case, we study the mechanism for privatizing the average of a collection of vectors, each of which is in the unit simplex. We establish a trade-off between the strength of privacy and the variance of the mechanism output, and we introduce a parameter to balance the trade-off between them. Numerical results illustrate these developments., Comment: Submitted to ACC 2020

A new method for the creation of reference points is proposed, for use in reference point-based Many objective Optimisation Problems. Unlike the current common practice of generating reference points on a unit simplex plane by Dan and Dennis method, which leads to uneven distribution of reference points on actual Pareto Front (PF) that the generated reference points are projected onto, the reference points are more evenly generated on an m dimensional B-norm surface which is created adaptively by tracking the true PF. The method is thus named as B-norm based PF tracking method (Bn-PFt). To ease the work of algorithmic development, an indexing system of reference points is also proposed. Systematic numerical studies performed on B-norm surfaces of various B values show that reference points created by the proposed Bn-PFt method are more evenly distributed on the surfaces than those of the projected onto the same surfaces generated using Dan and Dennis method. Simulation results using NSGA III on benchmark problems MaF3 and MaF5 with 3, 5, and 7 objective functions, show that the candidate solution sets obtained, via adopting reference points with the proposed method, have better diversity.

Aiming at parameter identification for fractional-order chaotic systems, a Nelder-Mead simplex gravitational search algorithm (NMGSA) is proposed. The search and replacement mechanism in the simplex search method and the particles update method in gravitational search algorithm is combined together in the proposed algorithm. Simplex search method has powerful local searching capacity, which is helpful for particles to jump out from local optimum, thus avoiding the gravitational search algorithm plunging falling into local optimum. Standard test functions are used to test the NMGSA, and the test results show that the algorithm has good stability and global search capability. Then, NMGSA is applied in the parameter identification for fractional-order Lorenz system. The results prove the effectiveness and robustness of NMGSA, when solve the problem of parameter identification of fractional-order chaotic system.

For the production of medium-voltage insulators, the main technological parameters of the production settings have a significant impact on product quality. Determination of the optimal production process parameters, therefore, can effectively improve the quality of medium voltage insulators. In the industrial scene, engineers usually use the trial-and-error method and the design of experiments (DOE) method. Both of the methods, however, have significant deficiencies, such as cumbersome and time-consuming. To improve the efficiency of quality control for medium voltage insulators, a revised simplex search method, based on historical simplexes information, was proposed. By integrating the knowledge of the historical reflection points of the simplexes, the reflection point of each simplex can be reformulated differently from the traditional simplex search method. Due to this modification, the search directions of the simplex search method at each iteration can be more accurate to follow the descend directions. Thus the efficiency of the method can be improved. The efficacy and efficiency of the revised method have been verified on the quality control of a particular type of pillar insulators.

In this paper a new algorithm for multi-class classification is presented. The algorithm, that is named Vertex Feature Classification (VFC), maps input data sets into an ad-hoc built space, called "simplex space" in order to perform geometric classification. More precisely, each class is first associated to a specific vertex of the polytope computed in the feature space. Successively, pattern classification is performed according to the geometric arrangement of patterns in a higher dimensional feature space. The experimental results, carried out on datasets of the UCI Machine Learning Repository, demonstrate the accuracy of the new algorithm is comparable with KNN, VDA and SVM, without or with a little training phase. An important aspect of this algorithm is its training time, which takes often a few milliseconds. Furthermore, the algorithm is robust and computationally efficient.

A new Initial Orbit Determination (IOD) method for angles-only observations is presented. This method is based on an adaptive Nelder-Mead simplex optimization technique for fusion of multiple observations from one or more acquisition satellites. The resulting solution characterizes the target orbit as a standard state vector. The algorithm is tested under a variety of scenarios, including acquisition orbits in Low Earth Orbit (LEO) and Geostationary Orbit (GEO), targets in GEO, both coplanar and non-coplanar cases, number of observations varying from 3 to 8, and time between observations varying from 60 to 1800 seconds. Observation error is varied in all cases to characterize the performance of the algorithm given varying angular resolution error. The simplex fusion algorithm is shown to perform well in a variety of cases when multiple acquisition satellites are used. Special emphasis is placed on GEO to GEO observations where the acquisition and target are in coplanar orbits. This new IOD method supports Space Situational Awareness (SSA) capabilities by enhancing performance in scenarios with multiple observation satellites for challenging GEO to GEO IOD scenarios.

Triple modular redundancy (TMR) is commonly employed to increase the reliability and mean time to failure (MTTF) of a system. This improvement can be shown by using a continuous time Markov chain. However, typical Markov chain models do not model common cause failures (CCF), which is a singular event that simultaneously causes failure in multiple redundant modules. This paper introduces a new Markov chain to model CCF in TMR with repair systems. This new model is compared to the idealized models of TMR with repair without CCF. The fundamental limitations that CCF imposes on the system are shown and discussed. In a motivating example, it is seen that CCF imposes a limitation of $51\times$ on the reliability improvement in a system with TMR and repair compared to a simplex system, (i.e., without TMR). A case study is also presented where the likelihood of CCF is reduced by a factor of $18\times$ using various mitigation techniques. Reducing the CCF compounds the reliability improvement of TMR with repair and leads to a overall system reliability improvement of $10,000\times$ compared to the simplex system as supported by the proposed model.

A new method for image denoising was presented，which colligated the strong point of wave atoms transform and Cycle Spinning. Due to lack of translation invariance of wave atoms transform，image denoising by coefficient thresholding would lead to Pseudo-Gibbs phenomena. Cycle Spinning was employed to avoid the artifacts. Experimental results show that the method can remove noisy and remain edges, while Pseudo-Gibbs phenomena are controlled efficiently, and can get better visual effect and PSNR gains compared with the methods like simplex wave atoms or wavelet denoising using Cycle Spinning.And in heavy background noise, this advantage is significant.

Convex optimization is a well-established research area with applications in almost all fields. Over the decades, multiple approaches have been proposed to solve convex programs. The development of interior-point methods allowed solving a more general set of convex programs known as semi-definite programs and second-order cone programs. However, it has been established that these methods are excessively slow for high dimensions, i.e., they suffer from the curse of dimensionality. On the other hand, optimization algorithms on manifold have shown great ability in finding solutions to nonconvex problems in reasonable time. This paper is interested in solving a subset of convex optimization using a different approach. The main idea behind Riemannian optimization is to view the constrained optimization problem as an unconstrained one over a restricted search space. The paper introduces three manifolds to solve convex programs under particular box constraints. The manifolds, called the doubly stochastic, symmetric and the definite multinomial manifolds, generalize the simplex also known as the multinomial manifold. The proposed manifolds and algorithms are well-adapted to solving convex programs in which the variable of interest is a multidimensional probability distribution function. Theoretical analysis and simulation results testify the efficiency of the proposed method over state of the art methods. In particular, they reveal that the proposed framework outperforms conventional generic and specialized solvers, especially in high dimensions.

We propose a differentiable nonparametric algorithm, the Delaunay triangulation learner (DTL), to solve the functional approximation problem on the basis of a p-dimensional feature space. By conducting the Delaunay triangulation algorithm on the data points, the DTL partitions the feature space into a series of p-dimensional simplices in a geometrically optimal way, and fits a linear model within each simplex. We study its theoretical properties by exploring the geometric properties of the Delaunay triangulation, and compare its performance with other statistical learners in numerical studies.

We propose a free selective simplex for the downhill Nelder Mead simplex algorithm (1965), rather than the determinant simplex that forces its elements to perform a single operation, such as reflection. Unlike the Nelder-Mead algorithm, the elements of the proposed simplex select various operations of the algorithm to form the next simplex. In this way, we allow non-isometric reflections similar to that of the Nelder Mead, triangle simplex, but with rotation through an angle, permitting the proposed algorithm to have more control over the simplex, to change its size and direction for better performance. As a consequence, the solution that comes from the proposed simplex is always dynamic adaptive in size and orientation to different landscapes of mathematical functions. The proposed algorithm is examined in a large collection of different structures and classes of optimization problems. Additionally, comparisons are made with two enhanced, up-to-date versions of the Nelder-Mead algorithm. The numerical results show that Hassan Nelder Mead is stable due to non-dependence on the number of parameters processed. It also performs a higher accuracy for high dimensions compared with the other algorithms and a faster convergence rate toward global minima with respect to the number of simplex gradient estimates.