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.     

求解最大割问题的半定规划松驰的序列线性规划方法

本文基于最大割问题的半定规划松弛,利用矩阵分解的方法给出了与半定规划松弛等价的非线性规划模型,提出一种序列线性规划方法求解该模型.并在适当的条件下,证明了算法的全局收敛性.数值实验表明:序列线性规划方法在时间上要优于半定规划的内点算法.所以序列线性规划方法能更有效地求解大规模的最大割问题的半定规划松弛.     

A discrete filled function algorithm embedded with continuous approximation for solving max-cut problems

In this paper, a discrete filled function algorithm embedded with continuous approximation is proposed to solve max-cut problems. A new discrete filled function is defined for max-cut problems, and properties of the function are studied. In the process of finding an approximation to the global solution of a max-cut problem, a continuation optimization algorithm is employed to find local solutions of a continuous relaxation of the max-cut problem, and then global searches are performed by minimizing the proposed filled function. Unlike general filled function methods, characteristics of max-cut problems are used. The parameters in the proposed filled function need not to be adjusted and are exactly the same for all max-cut problems that greatly increases the efficiency of the filled function method. Numerical results and comparisons on some well known max-cut test problems show that the proposed algorithm is efficient to get approximate global solutions of max-cut problems.     

A discrete filled function algorithm for approximate global solutions of max-cut problems

A discrete filled function algorithm is proposed for approximate global solutions of max-cut problems. A new discrete filled function is defined for max-cut problems and the properties of the filled function are studied. Unlike general filled function methods, using the characteristic of max-cut problems, the parameters in proposed filled function need not be adjusted. This greatly increases the efficiency of the filled function method. By combining a procedure that randomly generates initial points for minimization of the filled function, the proposed algorithm can greatly reduce the calculation cost and be applied to large scale max-cut problems. Numerical results on different sizes and densities test problems indicate that the proposed algorithm is efficient and stable to get approximate global solutions of max-cut problems.     

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.     

A new discrete filled function method for solving large scale max-cut problems

The global optimization method based on discrete filled function is a new method that solves large scale max-cut problems. We first define a new discrete filled function based on the structure of the max-cut problem and analyze its properties. Unlike the continuous filled function methods, by the characteristic of the max-cut problem, the parameters in the proposed filled function does not need to be adjusted. By combining a procedure that randomly generates initial points for minimization of the proposed filled function, the proposed algorithm can greatly reduce the computational time and be applied to large scale max-cut problems. Numerical results and comparisons with several heuristic methods indicate that the proposed algorithm is efficient and stable to obtain high quality solution of large scale max-cut problems.     

A simple SLP algorithm for solving a class of nonlinear programs

Successive linear programming (SLP) algorithms solve nonlinear optimization problems via a sequence of linear programs. We present an approach for a special class of nonlinear programming problems, which arise in multiperiod coal blending. The class of nonlinear programming problems and the solution approach considered in this paper are quite different from previous work. The algorithm is very simple, easy to apply and can be applied to as large a problem as the linear programming code can handle. The quality of solution, produced by the proposed algorithm, is discussed and the results of some test problems, in the real world environment, are provided.     

An accelerated multiplier method for nonlinear programming

This paper describes an accelerated multiplier method for solving the general nonlinear programming problem. The algorithm poses a sequence of unconstrained optimization problems. The unconstrained problems are solved using a rank-one recursive algorithm described in an earlier paper. Multiplier estimates are obtained by minimizing the error in the Kuhn-Tucker conditions using a quadratic programming algorithm. The convergence of the sequence of unconstrained problems is accelerated by using a Newton-Raphson extrapolation process. The numerical effectiveness of the algorithm is demonstrated on a relatively large set of test problems.This work was supported by the US Air Force under Contract No. F04701-74-C-0075.     

线性比式和规划问题的输出空间分支定界算法

本文旨在针对线性比式和规划这一NP-Hard非线性规划问题提出新的全局优化算法.首先,通过引入p个辅助变量把原问题等价的转化为一个非线性规划问题,这个非线性规划问题的目标函数是乘积和的形式并给原问题增加了p个新的非线性约束,再通过构造凸凹包络的技巧对等价问题的目标函数和约束条件进行相应的线性放缩,构成等价问题的一个下界线性松弛规划问题,从而提出了一个求解原问题的分支定界算法,并证明了算法的收敛性.最后,通过数值结果比较表明所提出的算法是可行有效的.     

A New Filled Function Method for Global Optimization

A novel filled function is suggested in this paper for identifying a global minimum point for a general class of nonlinear programming problems with a closed bounded domain. Theoretical and numerical properties of the proposed filled function are investigated and a solution algorithm is proposed. The implementation of the algorithm on several test problems is reported with satisfactory numerical results.     

Global optimization for the sum of generalized polynomial fractional functions

In this paper, a branch and bound approach is proposed for global optimization problem (P) of the sum of generalized polynomial fractional functions under generalized polynomial constraints, which arises in various practical problems. Due to its intrinsic difficulty, less work has been devoted to globally solving this problem. By utilizing an equivalent problem and some linear underestimating approximations, a linear relaxation programming problem of the equivalent form is obtained. Consequently, the initial non-convex nonlinear problem (P) is reduced to a sequence of linear programming problems through successively refining the feasible region of linear relaxation problem. The proposed algorithm is convergent to the global minimum of the primal problem by means of the solutions to a series of linear programming problems. Numerical results show that the proposed algorithm is feasible and can successfully be used to solve the present problem (P).     

Nonlinear Lagrangians for Nonlinear Programming Based on Modified Fischer-Burmeister NCP Functions

This paper proposes nonlinear Lagrangians based on modified Fischer-Burmeister NCP functions for solving nonlinear programming problems with inequality constraints. The convergence theorem shows that the sequence of points generated by this nonlinear Lagrange algorithm is locally convergent when the penalty parameter is less than a threshold under a set of suitable conditions on problem functions, and the error bound of solution, depending on the penalty parameter, is also established. It is shown that the condition number of the nonlinear Lagrangian Hessian at the optimal solution is proportional to the controlling penalty parameter. Moreover, the paper develops the dual algorithm associated with the proposed nonlinear Lagrangians. Numerical results reported suggest that the dual algorithm based on proposed nonlinear Lagrangians is effective for solving some nonlinear optimization problems.     

Nonlinear goal programming using multi-objective genetic algorithms

Goal programming is a technique often used in engineering design activities primarily to find a compromised solution which will simultaneously satisfy a number of design goals. In solving goal programming problems, classical methods reduce the multiple goal-attainment problem into a single objective of minimizing a weighted sum of deviations from goals. This procedure has a number of known difficulties. First, the obtained solution to the goal programming problem is sensitive to the chosen weight vector. Second, the conversion to a single-objective optimization problem involves additional constraints. Third, since most real-world goal programming problems involve nonlinear criterion functions, the resulting single-objective optimization problem becomes a nonlinear programming problem, which is difficult to solve using classical optimization methods. In tackling nonlinear goal programming problems, although successive linearization techniques have been suggested, they are found to be sensitive to the chosen starting solution. In this paper, we pose the goal programming problem as a multi-objective optimization problem of minimizing deviations from individual goals and then suggest an evolutionary optimization algorithm to find multiple Pareto-optimal solutions of the resulting multi-objective optimization problem. The proposed approach alleviates all the above difficulties. It does not need any weight vector. It eliminates the need of having extra constraints needed with the classical formulations. The proposed approach is also suitable for solving goal programming problems having nonlinear criterion functions and having a non-convex trade-off region. The efficacy of the proposed approach is demonstrated by solving a number of nonlinear goal programming test problems and an engineering design problem. In all problems, multiple solutions (each corresponding to a different weight vector) to the goal programming problem are found in one single simulation run. The results suggest that the proposed approach is an effective and practical tool for solving real-world goal programming problems.     

A new filled function method for unconstrained global optimization

In this paper, a new filled function which has better properties is proposed for identifying a global minimum point for a general class of nonlinear programming problems within a closed bounded domain. An algorithm for unconstrained global optimization is developed from the new filled function. Theoretical and numerical properties of the proposed filled function are investigated. The implementation of the algorithm on seven test problems is reported with satisfactory numerical results.     

A dual-relax penalty function approach for solving nonlinear bilevel programming with linear lower level problem

The penalty function method, presented many years ago, is an important numerical method for the mathematical programming problems. In this article, we propose a dual-relax penalty function approach, which is significantly different from penalty function approach existing for solving the bilevel programming, to solve the nonlinear bilevel programming with linear lower level problem. Our algorithm will redound to the error analysis for computing an approximate solution to the bilevel programming. The error estimate is obtained among the optimal objective function value of the dual-relax penalty problem and of the original bilevel programming problem. An example is illustrated to show the feasibility of the proposed approach.     

一种求解非线性整数规划问题的填充函数算法(英文)

在本文中,对于求解非线性整数规划的问题,提出了一个新的填充函数和相应的算法,该函数只有一个参数,具有较好的可操作性.数值试验显示,该算法是有效和可靠的.     

求解特征值互补问题的一类ABS算法

ABS算法是20世纪80年代初,由Abaffy,Broyden和Spedicato完成的用于求解线性方程组的含有三个参量的投影算法,是一类有限次迭代直接法。目前,ABS算法不仅可以求解线性与非线性方程组,还可以求解线性规划和具有线性约束的非线性规划等问题。本文即是利用ABS算法求解特征值互补问题的一种尝试,构造了求解特征值互补问题的ABS算法,证明了求解特征值互补问题的ABS算法的收敛性。数值例子充分验证了求解特征值互补问题的ABS算法的有效性。     

一个解非线性0-1整数规划问题基于罚函数的混合粒子群优化算法

利用罚函数思想把非线性0-1整数规划问题转化为无约束最优化问题,然后把粒子群优化和罚函数方法结合构造出一个基于罚函数的混合粒子群优化算法,数值结果表明所提出的算法是有效的.     

A discrete dynamic convexized method for the max-cut problem

The max-cut problem is a classical NP-hard problem in graph theory. In this paper, we adopt a local search method, called MCFM, which is a simple modification of the Fiduccia-Mattheyses heuristic method in Fiduccia and Mattheyses (Proc. ACM/IEEE DAC, pp. 175?C181, 1982) for the circuit partitioning problem in very large scale integration of circuits and systems. The method uses much less computational cost than general local search methods. Then, an auxiliary function is presented which has the same global maximizers as the max-cut problem. We show that maximization of the function using MCFM can escape successfully from previously converged discrete local maximizers by taking increasing values of a parameter. An algorithm is proposed for the max-cut problem, by maximizing the auxiliary function using MCFM from random initial solutions. Computational experiments were conducted on three sets of standard test instances from the literature. Experimental results show that the proposed algorithm is effective for the three sets of standard test instances.