SOLVING CONVEX QUADRATIC PROGRAMMING BY POTENTIAL-REDUCTION INTERIOR-POINT ALGORITHM

ＩＮＴＲＯＤＵＣＴＩＯＮＩｎｔｈｉｓｐａｐｅｒ,ｗｅｃｏｎｓｉｄｅｒｔｈｅｆｏｌｌｏｗｉｎｇｃｏｎ ｖｅｘｑｕａｄｒａｔｉｃｐｒｏｇｒａｍｍｉｎｇｍｉｎｆ(ｘ) =12 ｘＴＱｘ ｃＴｘｓ.ｔ.Ａｘ≤ｂ ,ｘ≥ 0( 1 )ｗｈｅｒｅｃ ,ｘａｒｅｎ ｖｅｃｔｏｒｓ,ｂｉｓａｎｍ ｖｅｃｔｏｒ,ＡｉｓａｍａｔｒｉｘａｎｄＱｉｓａｓｙｍｍｅｔｒｉｃｐｏｓｉｔｉｖｅｓｅｍｉ ｄｅｆｉｎｉｔｅｍ×ｎｍａｔｒｉｘ .Ｔｈｅｆｏｒｍｏｆ( 1 )ｄｏｅｓｎｏｔｌｏｓｅｇｅｎｅｒａｌｉｔｙ ,ｂｅｃａｕｓｅａｎｙｐｅｑｕａｌｉｔｙｃｏｎ ｓｔ…     

凸二次规划的一个新原-对偶内点算法

In this paper, a new primal-dual interior-point algorithm for convex quadratic optimization (CQO) based on a kernel function is presented. The proposed function has some properties that are easy for checking. These properties enable us to improve the polynomial complexity bound of a large-update interior-point method (IPM) to O (√nlognlogn/ε), which is the currently best known polynomial complexity bound for the algorithm with the large-update method. Numerical tests were conducted to investigate the behavior of the algorithm with different parameters p, q and θ, where p is the growth degree parameter, q is the barrier degree of the kernel function and θ is the barrier update parameter.     

非线性凸半定规划的割平面算法

先把一般的非线性凸半定规划转化成目标函数是线性函数的非线性凸半定规划,然后用割平面算法求解转化后的半定规划．最后证明了割平面算法的收敛性．     

线性约束凸规划的一个新原-对偶路径-跟踪内点算法

In this paper, a primal-dual path-following interior-point algorithm for linearly constrained convex optimization （LCCO） is presented. The algorithm is based on a new technique for finding a class of search directions and the strategy of the central path. At each iteration, only full-Newton steps are used. Finally, the favorable polynomial complexity bound for the algorithm with the small-update method is deserved, namely, O（√nlog n/ε）.     

A predictor-corrector interior-point algorithm for monotone variational inequality problems

Mehrotra's recent suggestion of a predictor-corrector variant of primal-dual interior-point method for linear programming is currently the interior-point method of choice for linear programming. In this work the authors give a predictor-corrector interior-point algorithm for monotone variational inequality problems. The algorithm was proved to be equivalent to a level-1 perturbed composite Newton method. Computations in the algorithm do not require the initial iteration to be feasible. Numerical results of experiments are presented.     

一种求解多目标无约束0—1二次规划问题的文化基因算法

针对多目标无约束0—1二次规划问题,提出一种文化基因算法。该算法采用基于分解的多目标演化算法框架,能够获得分布均匀的非占优解;同时,采用一种简单、有效的禁忌搜索,能够利用更多问题相关的信息,获得质量更优的非占优解。该算法在优化的过程中能够动态地平衡多样性与收敛性。实验结果证明该算法能够很好地求解多目标无约束0-1二次规划问题,并且性能优于目前求解该问题较先进的算法。     

Primal-dual interior-point algorithms with dynamic step-size based on kernel functions for linear programming

In this paper, primal-dual interior-point algorithm with dynamic step size is implemented for linear programming (LP) problems. The algorithms are based on a few kernel functions, including both self-regular functions and non-self-regular ones. The dynamic step size is compared with fixed step size for the algorithms in inner iteration of Newton step. Numerical tests show that the algorithms with dynamic step size are more efficient than those with fixed step size. Project supported by Dutch Organization for Scientific Research (Grant No.613.000.010)     

Global optimality conditions for quadratic 0-1 programming with inequality constraints

Quadratic 0-1 problems with linear inequality constraints are briefly considered in this paper.Global optimality conditions for these problems,including a necessary condition and some sufficient conditions,are presented.The necessary condition is expressed without dual variables.The relations between the global optimal solutions of nonconvex quadratic 0-1 problems and the associated relaxed convex problems are also studied.     

结合非线性互补问题函数的滤子逐次二次规划算法

A mechanism for proving global convergence in filter-SQP(sequence of quadratic programming)method with the nonlinear complementarity problem(NCP)function is described for constrained nonlinear optimization problem.We introduce an NCP function into the filter and construct a new SQP-filter algorithm.Such methods are characterized by their use of the dominance concept of multi-objective optimization,instead of a penalty parameter whose adjustment can be problematic.We prove that the algorithm has global convergence and superlinear convergence rates under some mild conditions.     

凸二次规划问题基于核函数的全牛顿步内点算法

针对凸二次规划问题,构造了新的核函数.通过构造的核函数来确定搜索方向和逼近度量,接着给出了求解凸二次规划问题的全牛顿步内点算法,最后给出了算法的复杂性界.     

基于一个新核函数的半定规划的内点算法的复杂性分析

Interior-point methods （IPMs） for linear optimization （LO） and semidefinite optimization （SDO） have become a hot area in mathematical programming in the last decades. In this paper, a new kernel function with simple algebraic expression is proposed. Based on this kernel function, a primal-dual interior-point methods （IPMs） for semidefinite optimization （SDO） is designed. And the iteration complexity of the algorithm as O（n^3/4 log n/ε） with large-updates is established. The resulting bound is better than the classical kernel function, with its iteration complexity O（n log n/ε） in large-updates case.     

一种基于二次规划模型的模糊偏好关系排序法

研究了决策信息以模糊偏好关系给出的有限方案决策问题,提出了一种简洁且实用的模糊偏好关系排序方法.该方法首先建立一个二次规划模型,然后基于该模型推导出求解模糊偏好关系排序向量的一个简洁公式.基于获得的排序向量,利用一致性比例对模糊偏好关系进行一致性检验.对于一致性较差的模糊偏好关系,则需反馈给决策者重新进行判断,直至得到一个一致性可接受的模糊偏好关系为止.最后,利用2个算例对该方法进行分析和说明,数值结果表明该方法简洁、有效,且易于在计算机上操作.     

Smoothing Newton algorithm for linear programming over symmetric cones

By using the theory of Euclidean Jordan algebras,based on a new class of smoothing functions,the QiSun-Zhou's smoothing Newton algorithm is extended to solve linear programming over symmetric cones (SCLP).The algorithm is globally convergent under suitable assumptions.     

线性规划的原始松弛——对偶MBU单纯形算法

线性最优化广泛应用于经济与管理的各个领域.对于含有等式约束的线性规划问题,单纯形算法需要构造辅助的第一阶段问题求得问题的一个可行基.本文提出了一种原始松弛—对偶MBU单纯形算法(来求解第一阶段问题).首先,忽略不等式约束构造一个原始可行的松弛子问题,再用原始单纯形法求解该子问题;然后用对偶MBU单纯形法求解第一阶段问题.通过大规模数值试验对这种算法进行计算检验,数值结果表明,与经典单纯形算法相比,本文所提出的算法简便可行且具有更高的计算效率.     

A new heuristic algorithm for general integer linear programming problems

1 Introduction ? Since the cutting plane method [1] and branch-and- bound principle [2] were developed as two types of efficient approaches for integer linear programming problems, how to improve them or to find new algorithms more efficient has become an…     

Non-interior continuation algorithm for solving system of inequalities over symmetric cones

As a basic mathematical structure,the system of inequalities over symmetric cones and its solution can provide an effective method for solving the startup problem of interior point method which is used to solve many optimization problems.In this paper,a non-interior continuation algorithm is proposed for solving the system of inequalities under the order induced by a symmetric cone.It is shown that the proposed algorithm is globally convergent and well-defined.Moreover,it can start from any point and only needs to solve one system of linear equations at most at each iteration.Under suitable assumptions,global linear and local quadratic convergence is established with Euclidean Jordan algebras.Numerical results indicate that the algorithm is efficient.The systems of random linear inequalities were tested over the second-order cones with sizes of 10,100,,1 000 respectively and the problems of each size were generated randomly for 10 times.The average iterative numbers show that the proposed algorithm can generate a solution at one step for solving the given linear class of problems with random initializations.It seems possible that the continuation algorithm can solve larger scale systems of linear inequalities over the secondorder cones quickly.Moreover,a system of nonlinear inequalities was also tested over Cartesian product of two simple second-order cones,and numerical results indicate that the proposed algorithm can deal with the nonlinear cases.     

Solving Hitchcock''s transportation problem by a genetic algorithm

Genetic algorithms (GAs) employ the evolutionary process of Darwin's nature selection theory to find the solutions of optimization problems. In this paper, an implementation of genetic algorithm is put forward to solve a classical transportation problem, namely the Hitchcock's Transportation Problem (HTP), and the GA is improved to search for all optimal solutions and identify them automatically. The algorithm is coded with C and validated by numerical examples. The computational results show that the algorithm is efficient for solving the Hitchcock's transportation problem.     

基于对数变换的凸二次规划不可行内点算法

基于对数变换和不可行内点算法,对凸二次规划提出了一种新的迭代方向原始-对偶不可行内点算法,并证明了算法的全局收敛性和多项式复杂性,该算法可以看做近期Pan等人关于线性规划算法的推广.