Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA Robust Numerical Path Tracking Algorithm for Polynomial Homotopy Continuation
313
0
0.0
(
0
)
Added by
Simon Telen
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We propose a new algorithm for numerical path tracking in polynomial homotopy continuation. The algorithm is `robust in the sense that it is designed to prevent path jumping and in many cases, it can be used in (only) double precision arithmetic. It is based on an adaptive stepsize predictor that uses Pade techniques to detect local difficulties for function approximation and danger for path jumping. We show the potential of the new path tracking algorithm through several numerical examples and compare with existing implementations.
rate research
Read More
We develop the Littlewood-Richardson homotopy algorithm, which uses numerical continuation to compute solutions to Schubert problems on Grassmannians and is based on the geometric Littlewood-Richardson rule. One key ingredient of this algorithm is our new optimal formulation of Schubert problems in local Stiefel coordinates as systems of equations. Our implementation can solve problem instances with tens of thousands of solutions.
In this paper we propose a primal-dual homotopy method for $ell_1$-minimization problems with infinity norm constraints in the context of sparse reconstruction. The natural homotopy parameter is the value of the bound for the constraints and we show that there exists a piecewise linear solution path with finitely many break points for the primal problem and a respective piecewise constant path for the dual problem. We show that by solving a small linear program, one can jump to the next primal break point and then, solving another small linear program, a new optimal dual solution is calculated which enables the next such jump in the subsequent iteration. Using a theorem of the alternative, we show that the method never gets stuck and indeed calculates the whole path in a finite number of steps. Numerical experiments demonstrate the effectiveness of our algorithm. In many cases, our method significantly outperforms commercial LP solvers; this is possible since our approach employs a sequence of considerably simpler auxiliary linear programs that can be solved efficiently with specialized active-set strategies.
An efficient contour integral technique to approximate a cluster of nonlinear eigenvalues of a polynomial eigenproblem, circumventing certain large
In support vector machine (SVM) applications with unreliable data that contains a portion of outliers, non-robustness of SVMs often causes considerable performance deterioration. Although many approaches for improving the robustness of SVMs have been studied, two major challenges remain in robust SVM learning. First, robust learning algorithms are essentially formulated as non-convex optimization problems. It is thus important to develop a non-convex optimization method for robust SVM that can find a good local optimal solution. The second practical issue is how one can tune the hyperparameter that controls the balance between robustness and efficiency. Unfortunately, due to the non-convexity, robust SVM solutions with slightly different hyper-parameter values can be significantly different, which makes model selection highly unstable. In this paper, we address these two issues simultaneously by introducing a novel homotopy approach to non-convex robust SVM learning. Our basic idea is to introduce parametrized formulations of robust SVM which bridge the standard SVM and fully robust SVM via the parameter that represents the influence of outliers. We characterize the necessary and sufficient conditions of the local optimal solutions of robust SVM, and develop an algorithm that can trace a path of local optimal solutions when the influence of outliers is gradually decreased. An advantage of our homotopy approach is that it can be interpreted as simulated annealing, a common approach for finding a good local optimal solution in non-convex optimization problems. In addition, our homotopy method allows stable and efficient model selection based on the path of local optimal solutions. Empirical performances of the proposed approach are demonstrated through intensive numerical experiments both on robust classification and regression problems.
We consider the propagation of acoustic waves at a given wavenumber in a waveguide which is unbounded in one direction. We explain how to construct penetrable obstacles characterized by a physical coefficient $rho$ which are invisible in various ways. In particular, we focus our attention on invisibility in reflection (the reflection matrix is zero), invisibility in reflection and transmission (the scattering matrix is the same as if there were no obstacle) and relative invisibility (two different obstacles have the same scattering matrix). To study these problems, we use a continuation method which requires to compute the scattering matrix $mathbb{S}(rho)$ as well as its differential with respect to the material index $dmathbb{S}(rho)$. The justification of the method also needs for the proof of abstract results of ontoness of well-chosen functionals constructed from the terms of $dmathbb{S}(rho)$. We provide a complete proof of the results in monomode regime when the wavenumber is such that only one mode can propagate. And we give all the ingredients to implement the method in multimode regime. We end the article by presenting numerical results to illustrate the analysis.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
