AN EFFECTIVE CONTINUOUS ALGORITHM FOR APPROXIMATE SOLUTIONS OF LARGE SCALE MAX-CUT PROBLEMS

An effective continuous algorithm is proposed to find approximate solutions of NP-hardmax-cut problems.The algorithm relaxes the max-cut problem into a continuous nonlinearprogramming problem by replacing n discrete constraints in the original problem with onesingle continuous constraint.A feasible direction method is designed to solve the resultingnonlinear programming problem.The method employs only the gradient evaluations ofthe objective function,and no any matrix calculations and no line searches are required.This greatly reduces the calculation cost of the method,and is suitable for the solutionof large size max-cut problems.The convergence properties of the proposed method toKKT points of the nonlinear programming are analyzed.If the solution obtained by theproposed method is a global solution of the nonlinear programming problem,the solutionwill provide an upper bound on the max-cut value.Then an approximate solution to themax-cut problem is generated from the solution of the nonlinear programming and providesa lower bound on the max-cut value.Numerical experiments and comparisons on somemax-cut test problems(small and large size)show that the proposed algorithm is efficientto get the exact solutions for all small test problems and well satisfied solutions for mostof the large size test problems with less calculation costs.     

Spectral Collocation Method for Caputo Fractional Multi-point Value Problems北大核心CSCD

Spectral collocation method is investigated for the nonlinear Caputo fractional multi-point value problems. The main idea of the presented method is to solve the corresponding nonlinear weakly singular Volterra–Fredholm integral equations obtained from the nonlinear Caputo fractional multi-point value problems. In order to carry out convergence analysis for the presented method, we investigate the Gronwall type inequality with Volterra–Fredholm integral terms. The provided convergence analysis shows that the presented method has spectral convergence, which is confirmed by the provided numerical experiments. At present, numerical methods for fractional multi-point value problems are rarely studied. The method and convergence analysis in this paper are useful references for the researches of related subjects. © 2022 Chinese Academy of Sciences. All rights reserved.     

基于增广Lagrange函数的RQP方法

Recursive quadratic programming is a family of techniques developd by Bartholomew-Biggs and other authors for solving nonlinear programming problems.This paperdescribes a new method for constrained optimization which obtains its search di-rections from a quadratic programming subproblem based on the well-known aug-mented Lagrangian function.It avoids the penalty parameter to tend to infinity.We employ the Fletcher‘s exact penalty function as a merit function and the use of an approximate directional derivative of the function that avoids the need toevaluate the second order derivatives of the problem functions.We prove that thealgorithm possesses global and superlinear convergence properties.At the sametime, numerical results are reported.     

A Constrained Optimization Approach for LCP

In this paper, LCP is converted to an equivalent nonsmooth nonlinear equation system H(x,y) = 0 by using the famous NCP function-Fischer-Burmeister function. Note that some equations in H(x, y) = 0 are nonsmooth and nonlinear hence difficult to solve while the others are linear hence easy to solve. Then we further convert the nonlinear equation system H(x, y) = 0 to an optimization problem with linear equality constraints. After that we study the conditions under which the K-T points of the optimization problem are the solutions of the original LCP and propose a method to solve the optimization problem. In this algorithm, the search direction is obtained by solving a strict convex programming at each iterative point, However, our algorithm is essentially different from traditional SQP method. The global convergence of the method is proved under mild conditions. In addition, we can prove that the algorithm is convergent superlinearly under the conditions: M is P0 matrix and the limit point is a strict complementarity solution of LCP. Preliminary numerical experiments are reported with this method.     

DISCONTINUOUS SOLUTIONS IN L^∞ FOR HAMILTON-JACOBI EQUATIONS

An approach is introduced to construct global discontinuous solutions in L∞ for Hamilton-Jacobi equations. This approach allows the initial data only in L∞ and applies to the equations with nonconvex Hamiltonians. The profit functions are introduced to formulate the notion of discontinuous solutions in L∞. The existence of global discontinuous solutions in L∞ is established. These solutions in L∞ coincide with the viscosity solutions and the minimax solutions, provided that the initial data are continuous. A prototypical equation is analyzed toexamine the L∞ stability of our L∞ solutions. The analysis also shows that global discontinuous solutions are determined by the topology in which the initial data are approximated.     

A NEW INEXACT SEQUENTIAL QUADRATIC PROGRAMMING ALGORITHM

This paper represents an inexact sequential quadratic programming (SQP) algorithm which can solve nonlinear programming (NLP) problems. An inexact solution of the quadratic programming subproblem is determined by a projection and contraction method such that only matrix-vector product is required. Some truncated criteria are chosen such that the algorithm is suitable to large scale NLP problem. The global convergence of the algorithm is proved.     

Convergence analysis for the Secant method based on new recurrence relations

A new convergence theorem for the Secant method in Banach spaces based on new recurrence relations is established for approximating a solution of a nonlinear operator equation.It is assumed that the divided difference of order one of the nonlinear operator is Lipschitz continuous.The convergence conditions differ from some existing ones and are easily satisfied.The results of the paper are justified by numerical examples that cannot be handled by earlier works.     

Convergence analysis for the Secant method based on new recurrence relations

A new convergence theorem for the Secant method in Banach spaces based on new recurrence relations is established for approximating a solution of a nonlinear operator equation. It is assumed that the divided difference of order one of the nonlinear operator is Lipschitz continuous. The convergence conditions differ from some existing ones and are easily satisfied. The results of the paper are justified by numerical examples that cannot be handled by earlier works.     

求解非线性规划的原始对偶内点法(英文)

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.     

Global optimization method for linear multiplicative programming

In this paper, a new global algorithm is presented to globally solve the linear multiplicative programming(LMP). The problem(LMP) is firstly converted into an equivalent programming problem(LMP(H))by introducing p auxiliary variables. Then by exploiting structure of(LMP(H)), a linear relaxation programming(LP(H)) of(LMP(H)) is obtained with a problem(LMP) reduced to a sequence of linear programming problems. The algorithm is used to compute the lower bounds called the branch and bound search by solving linear relaxation programming problems(LP(H)). The proposed algorithm is proven that it is convergent to the global minimum through the solutions of a series of linear programming problems. Some examples are given to illustrate the feasibility of the proposed algorithm.     

An Adaptive Neural Network Model for Nonlinear Programming Problems

In this paper a canonical neural network with adaptively changing synaptic weights and activation function parameters is presented to solve general nonlinear programming problems. The basic part of the model is a sub-network used to find a solution of quadratic programming problems with simple upper and lower bounds. By sequentially activating the sub-network under the control of an external computer or a special analog or digital processor that adjusts the weights and parameters, one then solves general nonlinear programming problems. Convergence proof and numerical results are given.     

Two-Dimensional Riemann Problems for the Compressible Euler System

Riemann problems for the compressible Euler system in two space dimensions are complicated and difficult, but a viable alternative remains missing. The author lists merits of one-dimensional Riemann problems and compares them with those for the current two-dimensional Riemann problems, to illustrate their worthiness. Two-dimensional Riemann problems are approached via the methodology promoted by Andy Majda in the spirits of modern applied mathematics; that is, simplified model is built via asymptotic analysis, numerical simulation and theoretical analysis. A simplified model called the pressure gradient system is derived from the full Euler system via an asymptotic process. State-of-the-art numerical methods in numerical simulations are used to discern smallscale structures of the solutions, e.g., semi-hyperbolic patches. Analytical methods are used to establish the validity of the structure revealed in the numerical simulation. The entire process, used in many of Majda＇s programs, is shown here for the two-dimensional Riemann problems for the compressible Euler systems of conservation laws     

SOLITON SOLUTIONS OF A CLASS OF GENERALIZED NONLINEAR SCHRODINGER EQUATIONS

Soliton solutions of a class of generalized nonlinear evolution equations are discussed ana-lytically and numerically. This is done by using a travelling wave method to formulate one-soliton solution and the finite difference method to the numerical solutions and the interactions betweenthe solitons for the generalized nonlinear Sehrodinger equations. the characteristic behavior of thenonlinearity admintted in the system has been investigated and the soliton states of the system in thelimit when a→Oand a→∞ have been studled. The results presented show that the soliton phe-rtomenon is charaeteristics associated with the nonlinearities of the dynamical systems.     

Solitary Wave Solutions of Some Nonlinear Physical Models Using Riccati Equation Approach

Riccati equation approach is used to look for exact travelling wave solutions of some nonlinear physical models.Solitary wave solutions are established for the modified KdV equation,the Boussinesq equation and the Zakharov-Kuznetsov equation.New generalized solitary wave solutions with some free parameters are derived.The obtained solutions,which includes some previously known solitary wave solutions and some new ones,are expressed by a composition of Riccati differential equation solutions followed by a polynomial.The employed approach,which is straightforward and concise,is expected to be further employed in obtaining new solitary wave solutions for nonlinear physical problems.     

Exact solutions of Kolmogorov-Petrovskii-Piskunov equation using the modified simple equation method

The modified simple equation method is employed to find the exact solutions of the nonlinear Kolmogorov-Petrovskii-Piskunov （KPP） equation. When certain parameters of the equations are chosen to be special values, the solitary wave solutions are derived from the exact solutions. It is shown that the modified simple equation method provides an effective and powerful mathematical tool for solving nonlinear evolution equations in mathematical physics.     

Rarefaction Wave Interaction and Shock-Rarefaction Composite Wave Interaction for a Two-Dimensional Nonlinear Wave System

In order to construct global solutions to two-dimensional(2 D for short)Riemann problems for nonlinear hyperbolic systems of conservation laws,it is important to study various types of wave interactions.This paper deals with two types of wave interactions for a 2 D nonlinear wave system with a nonconvex equation of state:Rarefaction wave interaction and shock-rarefaction composite wave interaction.In order to construct solutions to these wave interactions,the authors consider two types of Goursat problems,including standard Goursat problem and discontinuous Goursat problem,for a 2 D selfsimilar nonlinear wave system.Global classical solutions to these Goursat problems are obtained by the method of characteristics.The solutions constructed in the paper may be used as building blocks of solutions of 2 D Riemann problems.     

The Global Convergence of Self-Scaling BFGS Algorithm with Nonmonotone Line Search for Unconstrained Nonconvex Optimization Problems

The self-scaling quasi-Newton method solves an unconstrained optimization problem by scaling the Hessian approximation matrix before it is updated at each iteration to avoid the possible large eigenvalues in the Hessian approximation matrices of the objective function. It has been proved in the literature that this method has the global and superlinear convergence when the objective function is convex （or even uniformly convex）. We propose to solve unconstrained nonconvex optimization problems by a self-scaling BFGS algorithm with nonmonotone linear search. Nonmonotone line search has been recognized in numerical practices as a competitive approach for solving large-scale nonlinear problems. We consider two different nonmonotone line search forms and study the global convergence of these nonmonotone self-scale BFGS algorithms. We prove that, under some weaker condition than that in the literature, both forms of the self-scaling BFGS algorithm are globally convergent for unconstrained nonconvex optimization problems.     

ON THE SEPARABLE NONLINEAR LEAST SQUARES PROBLEMS

Separable nonlinear least squares problems are a special class of nonlinear least squares problems, where the objective functions are linear and nonlinear on different parts of variables. Such problems have broad applications in practice. Most existing algorithms for this kind of problems are derived from the variable projection method proposed by Golub and Pereyra, which utilizes the separability under a separate framework. However, the methods based on variable projection strategy would be invalid if there exist some constraints to the variables, as the real problems always do, even if the constraint is simply the ball constraint. We present a new algorithm which is based on a special approximation to the Hessian by noticing the fact that certain terms of the Hessian can be derived from the gradient. Our method maintains all the advantages of variable projection based methods, and moreover it can be combined with trust region methods easily and can be applied to general constrained separable nonlinear problems. Convergence analysis of our method is presented and numerical results are also reported.     

A LQP BASED INTERIOR PREDICTION-CORRECTION METHOD FOR NONLINEAR COMPLEMENTARITY PROBLEMS

To solve nonlinear complementarity problems （NCP）, at each iteration, the classical proximal point algorithm solves a well-conditioned sub-NCP while the Logarithmic-Quadratic Proximal （LQP） method solves a system of nonlinear equations （LQP system）. This paper presents a practical LQP method-based prediction-correction method for NCP. The predictor is obtained via solving the LQP system approximately under significantly relaxed restriction, and the new iterate （the corrector） is computed directly by an explicit formula derived from the original LQP method. The implementations are very easy to be carried out. Global convergence of the method is proved under the same mild assumptions as the original LQP method. Finally, numerical results for traffic equilibrium problems are provided to verify that the method is effective for some practical problems.     

非线性比式和问题的全局优化算法

In this paper,a global optimization algorithm is proposed for nonlinear sum of ratios problem(P).The algorithm works by globally solving problem(P1) that is equivalent to problem(P),by utilizing linearization technique a linear relaxation programming of the (P1) is then obtained.The proposed algorithm is convergent to the global minimum of(P1) through the successive refinement of linear relaxation of the feasible region of objective function and solutions of a series of linear relaxation programming.Nume...