In this paper, a mortar finite element method for parabolic problem is presented. Multi-grid method is used for solving the resulting discrete system. It is shown that the multigrid method is optimal, i.e, the converg...In this paper, a mortar finite element method for parabolic problem is presented. Multi-grid method is used for solving the resulting discrete system. It is shown that the multigrid method is optimal, i.e, the convergence rate is independent of the mesh size L and the time step parameter τ.展开更多
In this paper, we investigate the coupling of natural boundary element and finite element methods of exterior initial boundary value problems for hyperbolic equations. The governing equation is first discretized in ti...In this paper, we investigate the coupling of natural boundary element and finite element methods of exterior initial boundary value problems for hyperbolic equations. The governing equation is first discretized in time, leading to a time-step scheme, where an exterior elliptic problem has to be solved in each time step. Second, a circular artificial boundary TR consisting of a circle of radius R is introduced, the original problem in an unbounded domain is transformed into the nonlocal boundary value problem in a bounded subdomain. And the natural integral equation and the Poisson integral formula are obtained in the infinite domain Ω2 outside circle of radius R. The coupled variational formulation is given. Only the function itself, not its normal derivative at artificial boundary TR, appears in the variational equation, so that the unknown numbers are reduced and the boundary element stiffness matrix has a few different elements. Such a coupled method is superior to the one based on direct boundary element method. This paper discusses finite element discretization for variational problem and its corresponding numerical technique, and the convergence for the numerical solutions. Finally, the numerical example is presented to illustrate feasibility and efficiency of this method.展开更多
In this paper we present some algorithms for minimization of DC function (difference of two convex functions). They are descent methods of the proximal-type which use the convex properties of the two convex functions ...In this paper we present some algorithms for minimization of DC function (difference of two convex functions). They are descent methods of the proximal-type which use the convex properties of the two convex functions separately. We also consider an approximate proximal point algorithm. Some properties of the ε-subdifferential and the ε-directional derivative are discussed. The convergence properties of the algorithms are established in both exact and approximate forms. Finally, we give some applications to the concave programming and maximum eigenvalue problems.展开更多
In this paper, firstly, we propose several convexification and concavification transformations to convert a strictly monotone function into a convex or concave function, then we propose several convexification and con...In this paper, firstly, we propose several convexification and concavification transformations to convert a strictly monotone function into a convex or concave function, then we propose several convexification and concavification transformations to convert a non-convex and non-concave objective function into a convex or concave function in the programming problems with convex or concave constraint functions, and propose several convexification and concavification transformations to convert a non-monotone objective function into a convex or concave function in some programming problems with strictly monotone constraint functions. Finally, we prove that the original programming problem can be converted into an equivalent concave minimization problem, or reverse convex programming problem or canonical D.C. programming problem. Then the global optimal solution of the original problem can be obtained by solving the converted concave minimization problem, or reverse convex programming problem or canonical D.C. programming problem using the existing algorithms about them.展开更多
In this paper we present a trust region method of conic model for linearly constrained optimization problems. We discuss trust region approaches with conic model subproblems. Some equivalent variation properties and o...In this paper we present a trust region method of conic model for linearly constrained optimization problems. We discuss trust region approaches with conic model subproblems. Some equivalent variation properties and optimality conditions are given. A trust region algorithm based on conic model is constructed. Global convergence of the method is established.展开更多
Recently, double projection methods for solving variational inequalities havereceived much attention due to their fewer projection times at each iteration. In this paper, weunify these double projection methods within...Recently, double projection methods for solving variational inequalities havereceived much attention due to their fewer projection times at each iteration. In this paper, weunify these double projection methods within two unified frameworks, which contain the existingdouble projection methods as special cases. On the basis of this unification, theoretical andnumerical comparison between these double projection methods is presented.展开更多
Based on the two path metrics being equal at a merged node in the trellis employed to describe a Viterbi detector for the detection of data encoded with a rate 6:8 balanced binary code in page-oriented optical memorie...Based on the two path metrics being equal at a merged node in the trellis employed to describe a Viterbi detector for the detection of data encoded with a rate 6:8 balanced binary code in page-oriented optical memories, the combined Viterbi detector scheme is proposed to improve raw biterror rate performance by mitigating the occurrence of a twobit reversing error event in an estimated codeword for the balanced code. The effectiveness of the detection scheme is verified for different data quantizations using Monte Carlo simulations. Key words holographic data storage - balanced code - modulation code - Viterbi algorithm - path metric CLC number TN 911. 21 Foundation item: Supported by National 973 Research Program of China (G1999033006)Biography: Chen Duan-rong (1960-), male, Lecturer, Ph. D candidate, research direction: coding and signal processing for the recording channel of holographic data storage.展开更多
An r-circular coloring of a graph G is a map f from V(G) to the set of open unit intervals of an Euclidean circle of length r, such that f(u) ∩ f(v) = Ф whenever uv ∈ E(G). Circular perfect graphs are defined analo...An r-circular coloring of a graph G is a map f from V(G) to the set of open unit intervals of an Euclidean circle of length r, such that f(u) ∩ f(v) = Ф whenever uv ∈ E(G). Circular perfect graphs are defined analogously to perfect graphs by means of two parameters, the circular chromatic number and the circular clique number. In this paper, we study the properties of circular perfect graphs. We give (1) a necessary condition for a graph to be circular perfect, (2) some circular critical imperfect graphs, and (3) a characterization of graphs with the property that each of their induced subgraphs has circular clique number the same as its clique number, and then the two conjectures that are equivalent to the perfect graph conjecture.展开更多
Let Λ = {λ_k} be an infinite increasing sequence of positive integers withλ_k → ∞. Let X = {X(t), t ∈ R^N} be a multi-parameter fractional Brownian motion of index (0 【α 【 1) in R^d . Subject to certain hypot...Let Λ = {λ_k} be an infinite increasing sequence of positive integers withλ_k → ∞. Let X = {X(t), t ∈ R^N} be a multi-parameter fractional Brownian motion of index (0 【α 【 1) in R^d . Subject to certain hypotheses, we prove that if N 【 αd, then there exist positivefinite constants K_1 and K_2 such that, with unit probability, K_1 ≤ φ - p_Λ(X([0,1])~N) ≤ φ -p_Λ(G_rX([0,1])~N)) ≤ K_2 if and only if there exists γ 】 0 such that ∑ from k=1 to ∞ of1/λ_k~γ = ∞, where φ(s) = s^(N/α)(loglog 1/s)^(N/2(α)), φ - p_Λ(E) is the Packing-typemeasure of E,X([0, 1]) N is the image and G_rX([0, 1]~N ) = {(t,X(t)); t ∈ [0,1]~N} is the graph ofX, respectively. We also establish liminf type laws of the iterated logarithm for the sojournmeasure of X.展开更多
Let G be a graph. An independent set Y in G is called an essential independent set (or essential set for simplicity) if there is {Y1, Y2} 包含于Y such that dist (y1,y2)=2. In this paper, we use the technique of the ve...Let G be a graph. An independent set Y in G is called an essential independent set (or essential set for simplicity) if there is {Y1, Y2} 包含于Y such that dist (y1,y2)=2. In this paper, we use the technique of the vertex insertion on l-connected (l=k or k+1, k≥2) graphs to provide a unified proof for G to be hamiltonian, or hamiltonian-connected. The sufficient conditions are expressed an inequality on ∑i=1 K|N(Yi)|+b|N(y0)| and n(Y) for each essential set Y={y0,y1,…,yk}, where b (1≤b≤k）is an integer,Yi={yi,yi-1,…,yi-(b-1}包含于Y\{y0} for i属于V（G):dist(v,Y)≤2}|.展开更多
Typical solution methods for solving mixed complementarity problems either generate feasible iterates but have to solve relatively complicated subproblems such as quadratic programs or linear complementarity problems,...Typical solution methods for solving mixed complementarity problems either generate feasible iterates but have to solve relatively complicated subproblems such as quadratic programs or linear complementarity problems, or (those methods) have relatively simple subproblems such as system of linear equations but possibly generate infeasible iterates.In this paper, we propose a new Newton-type method for solving monotone mixed complementarity problems, which ensures to generate feasible iterates, and only has to solve a system of well-conditioned linear equations with reduced dimension per iteration. Without any regularity assumption, we prove that the whole sequence of iterates converges to a solution of the problem (truly globally convergent). Furthermore, under suitable conditions,the local superlinear rate of convergence is also established.展开更多
In this paper, the job shop scheduling problem concerned with minimizing make\|span is discussed, and a new local search algorithm is proposed for it. This local search method is based on an improved shifting bottlene...In this paper, the job shop scheduling problem concerned with minimizing make\|span is discussed, and a new local search algorithm is proposed for it. This local search method is based on an improved shifting bottleneck procedure and Tabu Search technique. This new local search is different from the previous Tabu Search (TS) proposed by other authors, which is because the improved shifting bottleneck procedure is a new technology that is provided by us for the problem, and two remarkable strategies--intensification and diversification of TS are modified. To demonstrate the performance, our algorithm has been tested on many common problem instances (benchmarks) with various sizes and levels of hardness and compared with other algorithms, especially the latest TS in the literatures. Computational experiments show that this algorithm is effective and efficient.展开更多
In this paper,we will prove the derivative of tetrahedral quadratic finite element ap-proximation is superapproximate to the derivative of the quadratic Lagrange interpolant of the exact solution in the L^∞-norm, whi...In this paper,we will prove the derivative of tetrahedral quadratic finite element ap-proximation is superapproximate to the derivative of the quadratic Lagrange interpolant of the exact solution in the L^∞-norm, which can be used to enhance the accuracy of the derivative of tetrahedral quadratic finite element approximation to the derivative of the exact solution。展开更多
基金The research was supported by the Special Funds for Major State Basic Research Projects G1999032804 and a grant from LIAMA
文摘In this paper, a mortar finite element method for parabolic problem is presented. Multi-grid method is used for solving the resulting discrete system. It is shown that the multigrid method is optimal, i.e, the convergence rate is independent of the mesh size L and the time step parameter τ.
基金Project supported by the National Natural Science Foundation of China (No.19831050, No.10171086) the Shanxi Provincial Natural Science Foundation of China (No.20011004)+1 种基金 the Key Program of the Ministry of Education of China (No.02023) the Returned A
文摘In this paper, a complete classification of arc-transitive cubic graphs of order 4p is given.
基金The Project was supported by the Special Funds for State Major Basic Research ProjectsNanjing Normal University Sciences Foundation.
文摘In this paper, we investigate the coupling of natural boundary element and finite element methods of exterior initial boundary value problems for hyperbolic equations. The governing equation is first discretized in time, leading to a time-step scheme, where an exterior elliptic problem has to be solved in each time step. Second, a circular artificial boundary TR consisting of a circle of radius R is introduced, the original problem in an unbounded domain is transformed into the nonlocal boundary value problem in a bounded subdomain. And the natural integral equation and the Poisson integral formula are obtained in the infinite domain Ω2 outside circle of radius R. The coupled variational formulation is given. Only the function itself, not its normal derivative at artificial boundary TR, appears in the variational equation, so that the unknown numbers are reduced and the boundary element stiffness matrix has a few different elements. Such a coupled method is superior to the one based on direct boundary element method. This paper discusses finite element discretization for variational problem and its corresponding numerical technique, and the convergence for the numerical solutions. Finally, the numerical example is presented to illustrate feasibility and efficiency of this method.
基金This work was supported by the National Natural Science Foundation of China,the Oversea ExchangeFund of Nanjing Normal University,and CNPq of Brazil
文摘In this paper we present some algorithms for minimization of DC function (difference of two convex functions). They are descent methods of the proximal-type which use the convex properties of the two convex functions separately. We also consider an approximate proximal point algorithm. Some properties of the ε-subdifferential and the ε-directional derivative are discussed. The convergence properties of the algorithms are established in both exact and approximate forms. Finally, we give some applications to the concave programming and maximum eigenvalue problems.
基金This research is supported by the National Natural Science Foundation of China(Grant 10271073).
文摘In this paper, firstly, we propose several convexification and concavification transformations to convert a strictly monotone function into a convex or concave function, then we propose several convexification and concavification transformations to convert a non-convex and non-concave objective function into a convex or concave function in the programming problems with convex or concave constraint functions, and propose several convexification and concavification transformations to convert a non-monotone objective function into a convex or concave function in some programming problems with strictly monotone constraint functions. Finally, we prove that the original programming problem can be converted into an equivalent concave minimization problem, or reverse convex programming problem or canonical D.C. programming problem. Then the global optimal solution of the original problem can be obtained by solving the converted concave minimization problem, or reverse convex programming problem or canonical D.C. programming problem using the existing algorithms about them.
基金This work was supported by the National Natural Science Foundation of China grant 19971042 and grant 10231060 and CNPq of Brazil
文摘In this paper we present a trust region method of conic model for linearly constrained optimization problems. We discuss trust region approaches with conic model subproblems. Some equivalent variation properties and optimality conditions are given. A trust region algorithm based on conic model is constructed. Global convergence of the method is established.
基金This work is supported by the Natural Science Foundation of China (Grant No. 10171055, 10231060).
文摘Recently, double projection methods for solving variational inequalities havereceived much attention due to their fewer projection times at each iteration. In this paper, weunify these double projection methods within two unified frameworks, which contain the existingdouble projection methods as special cases. On the basis of this unification, theoretical andnumerical comparison between these double projection methods is presented.
基金SupportedbyNational973ResearchProgramofChi na (G1 9990 330 0 6)
文摘Based on the two path metrics being equal at a merged node in the trellis employed to describe a Viterbi detector for the detection of data encoded with a rate 6:8 balanced binary code in page-oriented optical memories, the combined Viterbi detector scheme is proposed to improve raw biterror rate performance by mitigating the occurrence of a twobit reversing error event in an estimated codeword for the balanced code. The effectiveness of the detection scheme is verified for different data quantizations using Monte Carlo simulations. Key words holographic data storage - balanced code - modulation code - Viterbi algorithm - path metric CLC number TN 911. 21 Foundation item: Supported by National 973 Research Program of China (G1999033006)Biography: Chen Duan-rong (1960-), male, Lecturer, Ph. D candidate, research direction: coding and signal processing for the recording channel of holographic data storage.
基金This research is supported partially by National Natural Science Funds of China(10001035 and 10371055).
文摘An r-circular coloring of a graph G is a map f from V(G) to the set of open unit intervals of an Euclidean circle of length r, such that f(u) ∩ f(v) = Ф whenever uv ∈ E(G). Circular perfect graphs are defined analogously to perfect graphs by means of two parameters, the circular chromatic number and the circular clique number. In this paper, we study the properties of circular perfect graphs. We give (1) a necessary condition for a graph to be circular perfect, (2) some circular critical imperfect graphs, and (3) a characterization of graphs with the property that each of their induced subgraphs has circular clique number the same as its clique number, and then the two conjectures that are equivalent to the perfect graph conjecture.
基金Supported by the National Natural Science Foundation of China (No.10471148)Sci-tech Innovation Item for Excellent Young and Middle-Aged University Teachers and Major Item of Educational Department of Hubei(No.2003A005)
文摘Let Λ = {λ_k} be an infinite increasing sequence of positive integers withλ_k → ∞. Let X = {X(t), t ∈ R^N} be a multi-parameter fractional Brownian motion of index (0 【α 【 1) in R^d . Subject to certain hypotheses, we prove that if N 【 αd, then there exist positivefinite constants K_1 and K_2 such that, with unit probability, K_1 ≤ φ - p_Λ(X([0,1])~N) ≤ φ -p_Λ(G_rX([0,1])~N)) ≤ K_2 if and only if there exists γ 】 0 such that ∑ from k=1 to ∞ of1/λ_k~γ = ∞, where φ(s) = s^(N/α)(loglog 1/s)^(N/2(α)), φ - p_Λ(E) is the Packing-typemeasure of E,X([0, 1]) N is the image and G_rX([0, 1]~N ) = {(t,X(t)); t ∈ [0,1]~N} is the graph ofX, respectively. We also establish liminf type laws of the iterated logarithm for the sojournmeasure of X.
文摘Let G be a graph. An independent set Y in G is called an essential independent set (or essential set for simplicity) if there is {Y1, Y2} 包含于Y such that dist (y1,y2)=2. In this paper, we use the technique of the vertex insertion on l-connected (l=k or k+1, k≥2) graphs to provide a unified proof for G to be hamiltonian, or hamiltonian-connected. The sufficient conditions are expressed an inequality on ∑i=1 K|N(Yi)|+b|N(y0)| and n(Y) for each essential set Y={y0,y1,…,yk}, where b (1≤b≤k）is an integer,Yi={yi,yi-1,…,yi-(b-1}包含于Y\{y0} for i属于V（G):dist(v,Y)≤2}|.
文摘Typical solution methods for solving mixed complementarity problems either generate feasible iterates but have to solve relatively complicated subproblems such as quadratic programs or linear complementarity problems, or (those methods) have relatively simple subproblems such as system of linear equations but possibly generate infeasible iterates.In this paper, we propose a new Newton-type method for solving monotone mixed complementarity problems, which ensures to generate feasible iterates, and only has to solve a system of well-conditioned linear equations with reduced dimension per iteration. Without any regularity assumption, we prove that the whole sequence of iterates converges to a solution of the problem (truly globally convergent). Furthermore, under suitable conditions,the local superlinear rate of convergence is also established.
文摘In this paper, the job shop scheduling problem concerned with minimizing make\|span is discussed, and a new local search algorithm is proposed for it. This local search method is based on an improved shifting bottleneck procedure and Tabu Search technique. This new local search is different from the previous Tabu Search (TS) proposed by other authors, which is because the improved shifting bottleneck procedure is a new technology that is provided by us for the problem, and two remarkable strategies--intensification and diversification of TS are modified. To demonstrate the performance, our algorithm has been tested on many common problem instances (benchmarks) with various sizes and levels of hardness and compared with other algorithms, especially the latest TS in the literatures. Computational experiments show that this algorithm is effective and efficient.
文摘In this paper,we will prove the derivative of tetrahedral quadratic finite element ap-proximation is superapproximate to the derivative of the quadratic Lagrange interpolant of the exact solution in the L^∞-norm, which can be used to enhance the accuracy of the derivative of tetrahedral quadratic finite element approximation to the derivative of the exact solution。
