Based on a new efficient identification technique of active constraints introduced in this paper, a new sequential systems of linear equations (SSLE) algorithm generating feasible iterates is proposed for solving no...Based on a new efficient identification technique of active constraints introduced in this paper, a new sequential systems of linear equations (SSLE) algorithm generating feasible iterates is proposed for solving nonlinear optimization problems with inequality constraints. In this paper, we introduce a new technique for constructing the system of linear equations, which recurs to a perturbation for the gradients of the constraint functions. At each iteration of the new algorithm, a feasible descent direction is obtained by solving only one system of linear equations without doing convex combination. To ensure the global convergence and avoid the Maratos effect, the algorithm needs to solve two additional reduced systems of linear equations with the same coefficient matrix after finite iterations. The proposed algorithm is proved to be globally and superlinearly convergent under some mild conditions. What distinguishes this algorithm from the previous feasible SSLE algorithms is that an improving direction is obtained easily and the computation cost of generating a new iterate is reduced. Finally, a preliminary implementation has been tested.展开更多
Presents information on a study which proposed a superlinearly convergent algorithm of sequential systems of linear equations or nonlinear optimization problems with inequality constraints. Assumptions; Discussion on ...Presents information on a study which proposed a superlinearly convergent algorithm of sequential systems of linear equations or nonlinear optimization problems with inequality constraints. Assumptions; Discussion on lemmas about several matrices related to the common coefficient matrix F; Strengthening of the regularity assumptions on the functions involved; Numerical experiments.展开更多
Fundamental matrix operations and solving linear systems of equations are ubiquitous in scientific investigations.Using the‘sender-receiver’model,we propose quantum algorithms for matrix operations such as matrix-ve...Fundamental matrix operations and solving linear systems of equations are ubiquitous in scientific investigations.Using the‘sender-receiver’model,we propose quantum algorithms for matrix operations such as matrix-vector product,matrix-matrix product,the sum of two matrices,and the calculation of determinant and inverse matrix.We encode the matrix entries into the probability amplitudes of the pure initial states of senders.After applying proper unitary transformation to the complete quantum system,the desired result can be found in certain blocks of the receiver’s density matrix.These quantum protocols can be used as subroutines in other quantum schemes.Furthermore,we present an alternative quantum algorithm for solving linear systems of equations.展开更多
This paper proposes a parallel algorithm, called KDOP (K-DimensionalOptimal Parallel algorithm), to solve a general class of recurrence equations efficiently. The KDOP algorithm partitions the computation into a serie...This paper proposes a parallel algorithm, called KDOP (K-DimensionalOptimal Parallel algorithm), to solve a general class of recurrence equations efficiently. The KDOP algorithm partitions the computation into a series of sub-computations, each of which is executed in the fashion that all the processors work simultaneously with each one executing an optimal sequential algorithm to solve a subcomputation task. The algorithm solves the equations in O(N/p)steps in EREW PRAM model (Exclusive Read Exclusive Write Parallel Ran-dom Access Machine model) using p<N1-e processors, where N is the size of the problem, and e is a given constant. This is an optimal algorithm (itsspeedup is O(p)) in the case of p<N1-e. Such an optimal speedup for this problem was previously achieved only in the case of p<N0.5. The algorithm can be implemented on machines with multiple processing elements or pipelined vector machines with parallel memory systems.展开更多
For the large sparse systems of linear and nonlinear equations, a new class of generalized asynchronous parallel multisplitting iterative method is presented, and its convergence theory is established under suitable c...For the large sparse systems of linear and nonlinear equations, a new class of generalized asynchronous parallel multisplitting iterative method is presented, and its convergence theory is established under suitable conditions. This method not only unifies the discussions of various existing asynchronous multisplitting iterations, but also affords new algorithmic and theoretical results for the parallel solution of large sparse system of linear equations. Besides its generality, this method is also much more suitable for implementing on the MIMD multiprocessor systems.展开更多
基金Supported by National Natural Science Foundation of China (Grant No. 10771040)Guangxi Science Foundation (Grant No. 0832052)Guangxi University for Nationalities Youth Foundation (Grant No. 2007QN24)
文摘Based on a new efficient identification technique of active constraints introduced in this paper, a new sequential systems of linear equations (SSLE) algorithm generating feasible iterates is proposed for solving nonlinear optimization problems with inequality constraints. In this paper, we introduce a new technique for constructing the system of linear equations, which recurs to a perturbation for the gradients of the constraint functions. At each iteration of the new algorithm, a feasible descent direction is obtained by solving only one system of linear equations without doing convex combination. To ensure the global convergence and avoid the Maratos effect, the algorithm needs to solve two additional reduced systems of linear equations with the same coefficient matrix after finite iterations. The proposed algorithm is proved to be globally and superlinearly convergent under some mild conditions. What distinguishes this algorithm from the previous feasible SSLE algorithms is that an improving direction is obtained easily and the computation cost of generating a new iterate is reduced. Finally, a preliminary implementation has been tested.
基金This research was supported by the National Natural Science Foundation of China(19571001, 19971002, 79970014) Cross-century Excellent Personnel Award and Teaching and Research Award Program for Outstanding Young Teachers in High Education Ministry o
文摘Presents information on a study which proposed a superlinearly convergent algorithm of sequential systems of linear equations or nonlinear optimization problems with inequality constraints. Assumptions; Discussion on lemmas about several matrices related to the common coefficient matrix F; Strengthening of the regularity assumptions on the functions involved; Numerical experiments.
基金supported by the National Natural Science Foundation of China(Grant No.12031004 and Grant No.12271474,61877054)the Fundamental Research Foundation for the Central Universities(Project No.K20210337)+1 种基金the Zhejiang University Global Partnership Fund,188170+194452119/003partially funded by a state task of Russian Fundamental Investigations(State Registration No.FFSG-2024-0002)。
文摘Fundamental matrix operations and solving linear systems of equations are ubiquitous in scientific investigations.Using the‘sender-receiver’model,we propose quantum algorithms for matrix operations such as matrix-vector product,matrix-matrix product,the sum of two matrices,and the calculation of determinant and inverse matrix.We encode the matrix entries into the probability amplitudes of the pure initial states of senders.After applying proper unitary transformation to the complete quantum system,the desired result can be found in certain blocks of the receiver’s density matrix.These quantum protocols can be used as subroutines in other quantum schemes.Furthermore,we present an alternative quantum algorithm for solving linear systems of equations.
文摘This paper proposes a parallel algorithm, called KDOP (K-DimensionalOptimal Parallel algorithm), to solve a general class of recurrence equations efficiently. The KDOP algorithm partitions the computation into a series of sub-computations, each of which is executed in the fashion that all the processors work simultaneously with each one executing an optimal sequential algorithm to solve a subcomputation task. The algorithm solves the equations in O(N/p)steps in EREW PRAM model (Exclusive Read Exclusive Write Parallel Ran-dom Access Machine model) using p<N1-e processors, where N is the size of the problem, and e is a given constant. This is an optimal algorithm (itsspeedup is O(p)) in the case of p<N1-e. Such an optimal speedup for this problem was previously achieved only in the case of p<N0.5. The algorithm can be implemented on machines with multiple processing elements or pipelined vector machines with parallel memory systems.
文摘For the large sparse systems of linear and nonlinear equations, a new class of generalized asynchronous parallel multisplitting iterative method is presented, and its convergence theory is established under suitable conditions. This method not only unifies the discussions of various existing asynchronous multisplitting iterations, but also affords new algorithmic and theoretical results for the parallel solution of large sparse system of linear equations. Besides its generality, this method is also much more suitable for implementing on the MIMD multiprocessor systems.