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.     

Interval solution of nonlinear equations using linear programming

A new computational test is proposed for nonexistence of a solution to a system of nonlinear equations in a convex polyhedral regionX. The basic idea proposed here is to formulate a linear programming problem whose feasible region contains all solutions inX. Therefore, if the feasible region is empty (which can be easily checked by Phase I of the simplex method), then the system of nonlinear equations has no solution inX. The linear programming problem is formulated by surrounding the component nonlinear functions by rectangles using interval extensions. This test is much more powerful than the conventional test if the system of nonlinear equations consists of many linear terms and a relatively small number of nonlinear terms. By introducing the proposed test to interval analysis, all solutions of nonlinear equations can be found very efficently. This work was partially supported by the Japanese Ministry of Education.     

A FEASIBLE DIRECTION ALGORITHM WITHOUT LINE SEARCH FOR SOLVING MAX-BISECTION PROBLEMS

This paper concerns the solution of the NP-hard max-bisection problems. NCP func-tions are employed to convert max-bisection problems into continuous nonlinear program-ming problems. Solving the resulting continuous nonlinear programming problem generatesa solution that gives an upper bound on the optimal value of the max-bisection problem.From the solution, the greedy strategy is used to generate a satisfactory approximate so-lution of the max-bisection problem. A feasible direction method without line searches isproposed to solve the resulting continuous nonlinear programming, and the convergenceof the algorithm to KKT point of the resulting problem is proved. Numerical experimentsand comparisons on well-known test problems, and on randomly generated test problemsshow that the proposed method is robust, and very efficient.     

离散型指数族非线性模型的变离差检验

It is necessary to test for varying dispersion in generalized nonlinear models. Wei,et al (1998) developed a likelihood ratio test,a score test and their adjustments to test for varying dispersion in continuous exponential family nonlinear models. This type of problem in the framework of general discrete exponential family nonlinear models is discussed. Two types of varying dispersion, which are random coefficients model and random effects model, are proposed ,and corresponding score test statistics are constructed and expressed in simple ,easy to use ,matrix formulas.     

TESTING FOR VARYING DISPERSION IN DISCRETE EXPONENTIAL FAMILY NONLINEAR MODELS

§ 1　 Introduction and modelsThe general form of exponential family nonlinear models isg(μi) =f(xi,﹀) , (1 )where,g(· ) is a monotonic link function,f is a known differentiable nonlinear functionand﹀ is a p-vectoroffixed population parameters;μi=E(yi) and the density of response yiisp(yi) =exp{[yiθi -b(θi) -c(yi) ] -12 a(yi,) } ,(2 )whereθi is the natural parameter, is the dispersion parameter.From [1 1 ] ,μi=b(θi) ,Vi=Var(yi) =- 1 b(θi) .If f(xi,β) =x Ti ﹀,then mod…     

Modeling and computer simulation of the identification problem related to the sludge concentration in a settler

The mathematical model of sludge particles settling in the water treatment plant (settler) is considered. In the case of the residence time of sludge particles in the settler the model leads to a nonlinear age-dependent transport–diffusion with a nonlocal additional condition. This problem is formulated as an identification/optimal control problem, where the sludge concentration is assumed to be a control. For the case of constant (“average”) velocity, as a characterization of the optimal control problem two necessary conditions are obtained. These conditions permit reducing the nonlinear coupled two-dimensional problem to the two-point boundary value problem for the second order nonlinear ordinary differential equation, and then, to a nonlinear equation, with respect to sludge concentration. For the solution of the problem an iteration algorithm is derived. Convergence of the iteration algorithm is analyzed theoretically, as well as on test examples. The numerical procedure for the considered problem is demonstrated on concrete examples.     

The multi-product newsboy problem with supplier quantity discounts and a budget constraint

This paper considers the multi-product newsboy problem with both supplier quantity discounts and a budget constraint, while each feature has been addressed separately in the literature. Different from most previous nonlinear optimization models on the topic, the problem is formulated as a mixed integer nonlinear programming model due to price discounts. A Lagrangian relaxation approach is presented to solve the problem. Computational results on both small and large-scale test instances indicate that the proposed algorithm is extremely effective for the problem. An extension to multiple constraints and preliminary computational results are also reported.     

An exact penalty function method for nonlinear mixed discrete programming problems

In this paper, we consider a general class of nonlinear mixed discrete programming problems. By introducing continuous variables to replace the discrete variables, the problem is first transformed into an equivalent nonlinear continuous optimization problem subject to original constraints and additional linear and quadratic constraints. Then, an exact penalty function is employed to construct a sequence of unconstrained optimization problems, each of which can be solved effectively by unconstrained optimization techniques, such as conjugate gradient or quasi-Newton methods. It is shown that any local optimal solution of the unconstrained optimization problem is a local optimal solution of the transformed nonlinear constrained continuous optimization problem when the penalty parameter is sufficiently large. Numerical experiments are carried out to test the efficiency of the proposed method.     

A nonlinear Lagrangian for constrained optimization problems

A novel nonlinear Lagrangian is presented for constrained optimization problems with both inequality and equality constraints, which is nonlinear with respect to both functions in problem and Lagrange multipliers. The nonlinear Lagrangian inherits the smoothness of the objective and constraint functions and has positive properties. The algorithm on the nonlinear Lagrangian is demonstrated to possess local and linear convergence when the penalty parameter is less than a threshold (the penalty parameter in the penalty method has to approximate zero) under a set of suitable conditions, and be super-linearly convergent when the penalty parameter is decreased following Lagrange multiplier update. Furthermore, the dual problem based on the nonlinear Lagrangian is discussed and some important properties are proposed, which fail to hold for the dual problem based on the classical Lagrangian. At last, the preliminary and comparing numerical results for several typical test problems by using the new nonlinear Lagrangian algorithm and the other two related nonlinear Lagrangian algorithms, are reported, which show that the given nonlinear Lagrangian is promising.     

Finding all Solutions of Systems of Nonlinear Equations Using the Dual Simplex Method

An efficient algorithm is proposed for finding all solutions of nonlinear equations using linear programming (LP). This algorithm is based on a simple test (termed the LP test) for nonexistence of a solution to a system of nonlinear equations in a given region. In the conventional LP test, the system of nonlinear equations is transformed into an LP problem, to which the simplex method is applied. However, although the LP test is very powerful, it requires many pivotings for each region. In this paper, we use the dual simplex method in the LP test, which makes the average number of pivotings per region much smaller (less than one, for example) and makes the algorithm very efficient. By numerical examples, it is shown that the proposed algorithm can find all solutions of systems of 200 nonlinear equations in practical computation time.     

A Continuation Algorithm for Max-Cut Problem

A continuation algorithm for the solution of max-cut problems is proposed in this paper. Unlike the available semi-definite relaxation, a max-cut problem is converted into a continuous nonlinear programming by employing NCP functions, and the resulting nonlinear programming problem is then solved by using the augmented Lagrange penalty function method. The convergence property of the proposed algorithm is studied. Numerical experiments and comparisons with the Geomeans and Williamson randomized algorithm made on some max-cut test problems show that the algorithm generates satisfactory solutions for all the test problems with much less computation costs.     

CVaR-constrained stochastic programming reformulation for stochastic nonlinear complementarity problems

We reformulate a stochastic nonlinear complementarity problem as a stochastic programming problem which minimizes an expected residual defined by a restricted NCP function with nonnegative constraints and CVaR constraints which guarantee the stochastic nonlinear function being nonnegative with a high probability. By applying smoothing technique and penalty method, we propose a penalized smoothing sample average approximation algorithm to solve the CVaR-constrained stochastic programming. We show that the optimal solution of the penalized smoothing sample average approximation problem converges to the solution of the corresponding nonsmooth CVaR-constrained stochastic programming problem almost surely. Finally, we report some preliminary numerical test results.     

A comparison of some algorithms for the nonlinear least squares problem

The problem of minimizing a sum of squares of nonlinear functions is studied. To solve this problem one usually takes advantage of the fact that the objective function is of this special form. Doing this gives the Gauss-Newton method or modifications thereof. To study how these specialized methods compare with general purpose nonlinear optimization routines, test problems were generated where parameters determining the local behaviour of the algorithms could be controlled. The order of 1000 test problems were generated for testing three algorithms: the Gauss-Newton method, the Levenberg-Marquardt method and a quasi-Newton method.     

On a multiscale analysis of an inverse problem of nonlinear transfer law identification in periodic microstructure

This paper is devoted to the multiscale analysis of a homogenization inverse problem of the heat exchange law identification, which is governed by parabolic equations with nonlinear transmission conditions in a periodic heterogeneous medium. The aim of this work is to transform this inverse problem with nonlinear transmission conditions into a new one governed by a less complex nonlinear parabolic equation, while preserving the same form and physical properties of the heat exchange law that it will be identified, based on periodic homogenization theory. For this, we reformulate first the encountered homogenization inverse problem to an optimal control one. Then, we study the well-posedness of the state problem using the Leray–Schauder topological degrees and we also check the existence of the solution for the obtained optimal control problem. Finally, using the periodic homogenization theory and priori estimates, with justified choise of test functions, we reduce our inverse problem to a less complex one in a homogeneous medium.     

一类非线性扩散问题解的局部化

This paper concerns with properties of solutions of a nonlinear diffusion problem in non-divergence form.By constructing proper test functions,it is proved that solutions of the problem possess the property of localization.     

A modified Primal–Dual Logarithmic-Barrier Method for solving the Optimal Power Flow problem with discrete and continuous control variables

The aim of solving the Optimal Power Flow problem is to determine the optimal state of an electric power transmission system, that is, the voltage magnitude and phase angles and the tap ratios of the transformers that optimize the performance of a given system, while satisfying its physical and operating constraints. The Optimal Power Flow problem is modeled as a large-scale mixed-discrete nonlinear programming problem. This paper proposes a method for handling the discrete variables of the Optimal Power Flow problem. A penalty function is presented. Due to the inclusion of the penalty function into the objective function, a sequence of nonlinear programming problems with only continuous variables is obtained and the solutions of these problems converge to a solution of the mixed problem. The obtained nonlinear programming problems are solved by a Primal–Dual Logarithmic-Barrier Method. Numerical tests using the IEEE 14, 30, 118 and 300-Bus test systems indicate that the method is efficient.     

A new filled function method for an unconstrained nonlinear equation

In this paper, we transform an unconstrained system of nonlinear equations into a special optimization problem. A new filled function is constructed by employing the special properties of the transformed optimization problem. Theoretical and numerical properties of the proposed filled function are investigated and a solution of the algorithm is proposed. Under some conditions, we can find a solution or an approximate solution to the system of nonlinear equations in finite iterations. The implementation of the algorithm on six test problems is reported with satisfactory numerical results.     

Numerical validation of solutions of complementarity The nonlinear case

Summary. This paper proposes a validation method for solutions of nonlinear complementarity problems. The validation procedure performs a computational test. If the result of the test is positive, then it is guaranteed that a given multi-dimensional interval either includes a solution or excludes all solutions of the nonlinear complementarity problem. Received September 22, 2000 / Revised version received April 11, 2001 / Published online October 17, 2001     

On the blow-up of solutions to nonlinear initial-boundary value problems

We consider the problem of nonexistence (blow-up) of solutions of nonlinear evolution equations in the case of a bounded (with respect to the space variables) domain. Following the method of nonlinear capacity based on the application of test functions that are optimal (“characteristic”) for the corresponding nonlinear operators, we obtain conditions for the blowup of solutions to nonlinear initial-boundary value problems. We also show by examples that these conditions are sharp in the class of problems under consideration.     

Finite difference reaction diffusion equations with nonlinear boundary conditions

This article is concerned with numerical solutions of finite difference systems of reaction diffusion equations with nonlinear internal and boundary reaction functions. The nonlinear reaction functions are of general form and the finite difference systems are for both time-dependent and steady-state problems. For each problem a unified system of nonlinear equations is treated by the method of upper and lower solutions and its associated monotone iterations. This method leads to a monotone iterative scheme for the computation of numerical solutions as well as an existence-comparison theorem for the corresponding finite difference system. Special attention is given to the dynamical property of the time-dependent solution in relation to the steady-state solutions. Application is given to a heat-conduction problem where a nonlinear radiation boundary condition obeying the Boltzmann law of cooling is considered. This application demonstrates a bifurcation property of two steady-state solutions, and determines the dynamic behavior of the time-dependent solution. Numerical results for the heat-conduction problem, including a test problem with known analytical solution, are presented to illustrate the various theoretical conclusions. © 1995 John Wiley & Sons, Inc.