Comparison of two kinds of approximate proximal point algorithms for monotone variational inequalities

This paper proposes two kinds of approximate proximal point algorithms （APPA） for monotone variational inequalities, both of which can be viewed as two extended versions of Solodov and Svaiter＇s APPA in the paper ＂Error bounds for proximal point subproblems and associated inexact proximal point algorithms＂ published in 2000. They are both prediction- correction methods which use the same inexactness restriction; the only difference is that they use different search directions in the correction steps. This paper also chooses an optimal step size in the two versions of the APPA to improve the profit at each iteration. Analysis also shows that the two APPAs are globally convergent under appropriate assumptions, and we can expect algorithm 2 to get more progress in every iteration than algorithm 1. Numerical experiments indicate that algorithm 2 is more efficient than algorithm 1 with the same correction step size,

A study on the dynamic tie points ASI algorithm in the Arctic Ocean

Sea ice concentration is an important parameter for polar sea ice monitoring. Based on 89 GHz AMSR-E （Advanced Microwave Scanning Radiometer for Earth Observing System） data, a gridded high-resolution passive microwave sea ice concentration product can be obtained using the ASI （the Arctic Radiation And Turbulence Interaction Study （ARTIST） Sea Ice） retrieval algorithm. Instead of using fixed-point values, we developed ASi algorithm based on daily changed tie points, called as the dynamic tie point ASI algorithm in this study. Here the tie points are expressed as the brightness temperature polarization difference of open water and 100% sea ice. In 2010, the yearly-averaged tie points of open water and sea ice in Arctic are estimated to be 50.8 K and 7.8 K, respectively. It is confirmed that the sea ice concentrations retrieved by the dynamic tie point ASI algorithm can increase （decrease） the sea ice concentrations in low-value （high-value） areas. This improved the sea ice concentrations by present retrieval algorithm from microwave data to some extent. Comparing with the products using fixed tie points, the sea ice concentrations retrieved from AMSR-E data by using the dynamic tie point ASI algorithm are closer to those obtained from MODIS （Moderate-resolution Imaging Spectroradiometer） data. In 40 selected cloud-free sample regions, 95% of our results have smaller mean differences and 75% of our results have lower root mean square （RMS） differences compare with those by the fixed tie points.

A Correntropy-based Affine Iterative Closest Point Algorithm for Robust Point Set Registration

The iterative closest point(ICP)algorithm has the advantages of high accuracy and fast speed for point set registration,but it performs poorly when the point set has a large number of noisy outliers.To solve this problem,we propose a new affine registration algorithm based on correntropy which works well in the affine registration of point sets with outliers.Firstly,we substitute the traditional measure of least squares with a maximum correntropy criterion to build a new registration model,which can avoid the influence of outliers.To maximize the objective function,we then propose a robust affine ICP algorithm.At each iteration of this new algorithm,we set up the index mapping of two point sets according to the known transformation,and then compute the closed-form solution of the new transformation according to the known index mapping.Similar to the traditional ICP algorithm,our algorithm converges to a local maximum monotonously for any given initial value.Finally,the robustness and high efficiency of affine ICP algorithm based on correntropy are demonstrated by 2D and 3D point set registration experiments.

A predictor-corrector interior-point algorithmfor monotone variational inequality problems

Mehrotra's recent suggestion of a predictor corrector variant of primal dual interior point method for linear programming is currently the interior point method of choice for linear programming. In this work the authors give a predictor corrector interior point algorithm for monotone variational inequality problems. The algorithm was proved to be equivalent to a level 1 perturbed composite Newton method. Computations in the algorithm do not require the initial iteration to be feasible. Numerical results of experiments are presented.

Comparison of two approximal proximal point algorithms for monotone variational inequalities

Proximal point algorithms （PPA） are attractive methods for solving monotone variational inequalities （MVI）. Since solving the sub-problem exactly in each iteration is costly or sometimes impossible, various approximate versions ofPPA （APPA） are developed for practical applications. In this paper, we compare two APPA methods, both of which can be viewed as prediction-correction methods. The only difference is that they use different search directions in the correction-step. By extending the general forward-backward splitting methods, we obtain Algorithm Ⅰ; in the same way, Algorithm Ⅱ is proposed by spreading the general extra-gradient methods. Our analysis explains theoretically why Algorithm Ⅱ usually outperforms Algorithm Ⅰ. For computation practice, we consider a class of MVI with a special structure, and choose the extending Algorithm Ⅱ to implement, which is inspired by the idea of Gauss-Seidel iteration method making full use of information about the latest iteration. And in particular, self-adaptive techniques are adopted to adjust relevant parameters for faster convergence. Finally, some numerical experiments are reported on the separated MVI. Numerical results showed that the extending Algorithm II is feasible and easy to implement with relatively low computation load.

PROXIMAL POINT ALGORITHM WITH ERRORS FOR GENERALIZED STRONGLY NONLINEARQUASIVARIATIONAL INCLUSIONS

In this paper, a class of generalized strongly nonlinear quasivariational inclusions are studied. By using the properties of the resolvent operator associated with a maximal monotone; mapping in Hilbert space, an existence theorem of solutions for generalized strongly nonlinear quasivariational inclusion is established and a new proximal point algorithm with errors is suggested for finding approximate solutions which strongly converge to the exact solution of the generalized strongly, nonlinear quasivariational inclusion. As special cases, some known results in this field are also discussed.

Digitalized Accurate Modeling of SPCB with Multi-spiral Surface Based on CPC Algorithm

The main methods of the existing multi-spiral surface geometry modeling include spatial analytic geometry algorithms, graphical method, interpolation and approximation algorithms. However, there are some shortcomings in these modeling methods, such as large amount of calculation, complex process, visible errors, and so on. The above methods have, to some extent, restricted the design and manufacture of the premium and high-precision products with spiral surface considerably. This paper introduces the concepts of the spatially parallel coupling with multi-spiral surface and spatially parallel coupling body. The typical geometry and topological features of each spiral surface forming the multi-spiral surface body are determined, by using the extraction principle of datum point cluster, the algorithm of coupling point cluster by removing singular point, and the ＂spatially parallel coupling＂ principle based on the non-uniform B-spline for each spiral surface. The orientation and quantitative relationships of datum point cluster and coupling point cluster in Euclidean space are determined accurately and in digital description and expression, coupling coalescence of the surfaces with multi-coupling point clusters under the Pro/E environment. The digitally accurate modeling of spatially parallel coupling body with multi-spiral surface is realized. The smooth and fairing processing is done to the three-blade end-milling cutter＇s end section area by applying the principle of spatially parallel coupling with multi-spiral surface, and the alternative entity model is processed in the four axis machining center after the end mill is disposed. And the algorithm is verified and then applied effectively to the transition area among the multi-spiral surface. The proposed model and algorithms may be used in design and manufacture of the multi-spiral surface body products, as well as in solving essentially the problems of considerable modeling errors in computer graphics and engineering in multi-spiral surface＇s connection available with approximate methods or graphical methods.

Predictor-corrector interior-point algorithm for linearly constrained convex programming

Active set method and gradient projection method are curre nt ly the main approaches for linearly constrained convex programming. Interior-po int method is one of the most effective choices for linear programming. In the p aper a predictor-corrector interior-point algorithm for linearly constrained c onvex programming under the predictor-corrector motivation was proposed. In eac h iteration, the algorithm first performs a predictor-step to reduce the dualit y gap and then a corrector-step to keep the points close to the central traject ory. Computations in the algorithm only require that the initial iterate be nonn egative while feasibility or strict feasibility is not required. It is proved th at the algorithm is equivalent to a level-1 perturbed composite Newton method. Numerical experiments on twenty-six standard test problems are made. The result s show that the proposed algorithm is stable and robust.

A Primal-Dual Infeasible-Interior-Point Algorithm for Multiple Objective Linear Programming Problems

A primal-dual infeasible interior point algorithm for multiple objective linear programming (MOLP) problems was presented. In contrast to the current MOLP algorithm. moving through the interior of polytope but not confining the iterates within the feasible region in our proposed algorithm result in a solution approach that is quite different and less sensitive to problem size, so providing the potential to dramatically improve the practical computation effectiveness.

Proximal point algorithm for a new class of fuzzy set-valued variational inclusions with (H,η)-monotone mappings

We introduced a new class of fuzzy set-valued variational inclusions with (H,η)-monotone mappings. Using the resolvent operator method in Hilbert spaces, we suggested a new proximal point algorithm for finding approximate solutions, which strongly converge to the exact solution of a fuzzy set-valued variational inclusion with (H,η)-monotone. The results improved and generalized the general quasi-variational inclusions with fuzzy set-valued mappings proposed by Jin and Tian Jin MM, Perturbed proximal point algorithm for general quasi-variational inclusions with fuzzy set-valued mappings, OR Transactions, 2005, 9(3): 31-38, (In Chinese); Tian YX, Generalized nonlinear implicit quasi-variational inclusions with fuzzy mappings, Computers & Mathematics with Applications, 2001, 42: 101-108.

MODIFIED APPROXIMATE PROXIMAL POINT ALGORITHMS FOR FINDING ROOTS OF MAXIMAL MONOTONE OPERATORS

In order to find roots of maximal monotone operators, this paper introduces and studies the modified approximate proximal point algorithm with an error sequence {e k} such that || ek || \leqslant hk || xk - [(x)\tilde]k ||\left\| { e^k } \right\| \leqslant \eta _k \left\| { x^k - \tilde x^k } \right\| with ?k = 0￥ ( hk - 1 ) < + ￥\sum\limits_{k = 0}^\infty {\left( {\eta _k - 1} \right)} and infk \geqslant 0 hk = m\geqslant 1\mathop {\inf }\limits_{k \geqslant 0} \eta _k = \mu \geqslant 1 . Here, the restrictions on {η k} are very different from the ones on {η k}, given by He et al (Science in China Ser. A, 2002, 32 (11): 1026–1032.) that supk \geqslant 0 hk = v < 1\mathop {\sup }\limits_{k \geqslant 0} \eta _k = v . Moreover, the characteristic conditions of the convergence of the modified approximate proximal point algorithm are presented by virtue of the new technique very different from the ones given by He et al.

Surface registration algorithm for rapid detection of surface thermal deformation of paraboloid antennas

In order to obtain and master the surface thermal deformation of paraboloid antennas,a fast iterative closest point( FICP) algorithm based on design coordinate guidance is proposed,which can satisfy the demands of rapid detection for surface thermal deformation. Firstly,the basic principle of the ICP algorithm for registration of a free surface is given,and the shortcomings of the ICP algorithm in the registration of surface are analysed,such as its complex computation,long calculation time,low efficiency,and relatively strict initial registration position. Then an improved FICP algorithm based on design coordinate guidance is proposed. Finally,the FICP algorithm is applied to the fast registration test for the surface thermal deformation of a paraboloid antenna. Results indicate that the approach offers better performance with regard to fast surface registration and the algorithm is more simple,efficient,and easily realized in practical engineering application.

Optimization of volume to point conduction problem based on a novel thermal conductivity discretization algorithm

A conduction heat transfer process is enhanced by filling prescribed quantity and optimized-shaped high thermal conductivity materials to the substrate. Numerical simulations and analyses are performed on a volume to point conduction problem based on the principle of minimum entropy generation. In the optimization, the arrangement of high thermal conductivity materials is variable, the quantity of high thermal-conductivity material is constrained, and the objective is to obtain the maximum heat conduction rate as the entropy is the minimum.A novel algorithm of thermal conductivity discretization is proposed based on large quantity of calculations.Compared with other algorithms in literature, the average temperature in the substrate by the new algorithm is lower, while the highest temperature in the substrate is in a reasonable range. Thus the new algorithm is feasible. The optimization of volume to point heat conduction is carried out in a rectangular model with radiation boundary condition and constant surface temperature boundary condition. The results demonstrate that the algorithm of thermal conductivity discretization is applicable for volume to point heat conduction problems.

Natural forest ALS-TLS point cloud data registration without control points

Airborne laser scanning(ALS)and terrestrial laser scanning(TLS)has attracted attention due to their forest parameter investigation and research applications.ALS is limited to obtaining fi ne structure information below the forest canopy due to the occlusion of trees in natural forests.In contrast,TLS is unable to gather fi ne structure information about the upper canopy.To address the problem of incomplete acquisition of natural forest point cloud data by ALS and TLS on a single platform,this study proposes data registration without control points.The ALS and TLS original data were cropped according to sample plot size,and the ALS point cloud data was converted into relative coordinates with the center of the cropped data as the origin.The same feature point pairs of the ALS and TLS point cloud data were then selected to register the point cloud data.The initial registered point cloud data was fi nely and optimally registered via the iterative closest point(ICP)algorithm.The results show that the proposed method achieved highprecision registration of ALS and TLS point cloud data from two natural forest plots of Pinus yunnanensis Franch.and Picea asperata Mast.which included diff erent species and environments.An average registration accuracy of 0.06 m and 0.09 m were obtained for P.yunnanensis and P.asperata,respectively.

A Primal-dual Interior Point Method for Nonlinear Programming

In this paper, we propose a primal-dual interior point method for solving general constrained nonlinear programming problems. To avoid the situation that the algorithm we use may converge to a saddle point or a local maximum, we utilize a merit function to guide the iterates toward a local minimum. Especially, we add the parameter ε to the Newton system when calculating the decrease directions. The global convergence is achieved by the decrease of a merit function. Furthermore, the numerical results confirm that the algorithm can solve this kind of problems in an efficient way.

A Novel Analytical Model of Brain Tumor Based on Swarm Robotics

A tumor is referred to as“intracranial hard neoplasm”if it grows near the brain or central spinal vessel(neoplasm).In certain cases,it is possible that the responsible cells are neurons situated deep inside the brain’s structure.This article discusses a strategy for halting the progression of brain tumor.A precise and accurate analytical model of brain tumors is the foundation of this strategy.It is based on an algorithm known as kill chain interior point(KCIP),which is the result of a merger of kill chain and interior point algorithms,as well as a precise and accurate analytical model of brain tumors.The inability to obtain a clear picture of tumor cell activity is the biggest challenge in this endeavor.Based on the motion of swarm robots,which are considered a subset of artificial intelligence,this article proposes a new notion of this kind of behavior,which may be used in various situations.The KCIP algorithm that follows is used in the analytical model to limit the development of certain cell types.According to the findings,it seems that different KCIP speed ratios are beneficial in preventing the development of brain tumors.It is hoped that this study will help researchers better understand the behavior of brain tumors,so as to develop a new drug that is effective in eliminating the tumor cells.

Solving the Binary Linear Programming Model in Polynomial Time

The paper presents a technique for solving the binary linear programming model in polynomial time. The general binary linear programming problem is transformed into a convex quadratic programming problem. The convex quadratic programming problem is then solved by interior point algorithms. This settles one of the open problems of whether P = NP or not. The worst case complexity of interior point algorithms for the convex quadratic problem is polynomial. It can also be shown that every liner integer problem can be converted into binary linear problem.

Approximate Customized Proximal Point Algorithms for Separable Convex Optimization

Proximal point algorithm(PPA)is a useful algorithm framework and has good convergence properties.Themain difficulty is that the subproblems usually only have iterative solutions.In this paper,we propose an inexact customized PPA framework for twoblock separable convex optimization problem with linear constraint.We design two types of inexact error criteria for the subproblems.The first one is absolutely summable error criterion,under which both subproblems can be solved inexactly.When one of the two subproblems is easily solved,we propose another novel error criterion which is easier to implement,namely relative error criterion.The relative error criterion only involves one parameter,which is more implementable.We establish the global convergence and sub-linear convergence rate in ergodic sense for the proposed algorithms.The numerical experiments on LASSO regression problems and total variation-based image denoising problem illustrate that our new algorithms outperform the corresponding exact algorithms.

Multi-View Point Clouds Registration without Feature Extraction for Use in Reverse Engineering of CAD Models

For reverse engineering a CAD model, it is necessary to integrate measured points from several views of an object into a common reference frame. Given a rough initial alignment of point cloud in different views with point-normal method, further refinement is achieved by using an improved iterative closest point (ICP) algorithm. Compared with other methods used for mult-view registration, this approach is automatic because no geometric feature, such as line, plane or sphere needs to be extracted from the original point cloud manually. A good initial alignment can be acquired automatically and the registration accuracy and efficiency is proven better than the normal point-point ICP algorithm both experimentally and theoretically.

Generating barcodes for nanopore sequencing data with PRO

DNA barcodes,short and unique DNA sequences,play a crucial role in sample identification when processing many samples simultaneously,which helps reduce experimental costs.Nevertheless,the low quality of long-read sequencing makes it difficult to identify barcodes accurately,which poses significant challenges for the design of barcodes for large numbers of samples in a single sequencing run.Here,we present a comprehensive study of the generation of barcodes and develop a tool,PRO,that can be used for selecting optimal barcode sets and demultiplexing.We formulate the barcode design problem as a combinatorial problem and prove that finding the optimal largest barcode set in a given DNA sequence space in which all sequences have the same length is theoretically NP-complete.For practical applications,we developed the novel method PRO by introducing the probability divergence between two DNA sequences to expand the capacity of barcode kits while ensuring demultiplexing accuracy.Specifically,the maximum size of the barcode kits designed by PRO is 2,292,which keeps the length of barcodes the same as that of the official ones used by Oxford Nanopore Technologies(ONT).We validated the performance of PRO on a simulated nanopore dataset with high error rates.The demultiplexing accuracy of PRO reached 98.29%for a barcode kit of size 2,922,4.31%higher than that of Guppy,the official demultiplexing tool.When the size of the barcode kit generated by PRO is the same as the official size provided by ONT,both tools show superior and comparable demultiplexing accuracy.