求解正定二次规划的一个全局收敛的滤子内点算法

现有的大多数分类问题都能转化成一个正定二次规划问题的求解.通过引入滤子方法,并结合求解非线性规划的原始对偶内点法,给出求解正定二次规划的滤子内点算法.该算法避免了使用效益函数时选取罚因子的困难,在较弱的假设条件下,算法具有全局收敛性.     

一个新的求解半正定规划问题的原始对偶内点算法

选择合适的核函数对设计求解线性规划与半正定规划的原始对偶内点算法以及复杂性分析都十分重要.Bai等针对线性规划提出三种核函数,并给出求解线性规划的大步迭代复杂界,但未给出数值算例验证算法的实际效果(Bai Y Q,Xie W,Zhang J.New parameterized kernel functions for linear optimization.J Global Optim,2012.DOI 10.1007/s10898-012-9934-z).基于这三种核函数设计了新的求解半正定规划问题的原始对内点算法.进一步分析了算法关于大步方法的计算复杂性界,同时通过数值算例验证了算法的有效性和核函数所带参数对计算复杂性的影响.     

解带有二次约束二次规划的一个整体优化方法

在本文中，我们提出了一种解带有二次约束二次规划问题（QP）的新算法，这种方法是基于单纯形分枝定界技术，其中包括极小极大问题和线性规划问题作为子问题，利用拉格朗日松弛和投影次梯度方法来确定问题（QP）最优值的下界，在问题（QP）的可行域是n维的条件下，如果这个算法有限步后终止，得到的点必是问题（QP）的整体最优解；否则，该算法产生的点的序列{v^k}的每一个聚点也必是问题（QP）的整体最优解。     

正定二次型判别条件的证明

正定二次型判别条件的证明刘学鹏（临沂师专２７６００５）在二次型的理论中，正定二次型是一类特殊而重要的二次型，相应的正定矩阵也是一类特殊而重要的矩阵．对于实二次型，其正定性的判别法之一，是利用其顺序主子式是否大于零．此理论根据的证明，笔者依据目前流行的...     

非线性最优化一个可行序列等式约束二次规划算法

本文针对非线性不等式约束优化问题,提出了一个新的可行序列等式约束二次规划算法．在每次迭代中,该算法只需求解三个相同规模且仅含等式约束的二次规划(必要时求解一个辅助的线性规划),因而其计算工作量较小．在一般的条件下,证明了算法具有全局收敛及超线性收敛性．数值实验表明算法是有效的．     

判别线性约束下实二次型正定性的一个算法

本文对经济学中常见的判别线性约束下实二次型的正定性问题通过矩阵分解给出了一个简易且可行的算法，该算法不涉及行列式的计算。     

大规模严格凸二次规划问题一个新算法

根据广义乘子法的思想,将具有等式约束和非负约束的凸二次规划问题转化只有非负约束的简单凸二次规划,通过简单凸二次规划来得到解等式约束一非负约束的凸二次规划新算法,新算法不用求逆矩阵,这样可充分保持矩阵的稀疏性,用来解大规模稀疏问题,数值结果表明：在微机４８６／３３上就能解较大规模的凸二次规划。     

A new algorithm for solving the general quadratic programming problem

For the general quadratic programming problem (including an equivalent form of the linear complementarity problem) a new solution method of branch and bound type is proposed. The branching procedure uses a well-known simplicial subdivision and the bound estimation is performed by solving certain linear programs.     

Dual support method for solving convex quadratic programs

In this article, we present a new dual method for solving convex (but not strictly convex) quadratic programs (QPs). Our method is the generalization of the dual support method, developed by Gabasov and co-workers in 1981, for solving convex QPs. It proceeds in two phases: the first is to construct the initial support, called coordinator support, for the problem and the second is to achieve the optimality of the problem. Results of numerical experiments are given comparing our approach with the active-set method.     

A robust sequential quadratic programming method

The sequential quadratic programming method developed by Wilson, Han and Powell may fail if the quadratic programming subproblems become infeasible, or if the associated sequence of search directions is unbounded. This paper considers techniques which circumvent these difficulties by modifying the structure of the constraint region in the quadratic programming subproblems. Furthermore, questions concerning the occurrence of an unbounded sequence of multipliers and problem feasibility are also addressed.Work supported in part by the National Science Foundation under Grant No. DMS-8602399 and by the Air Force Office of Scientific Research under Grant No. ISSA-860080.Work supported in part by the National Science Foundation under Grant No. DMS-8602419.     

A sparse sequential quadratic programming algorithm

Described here is the structure and theory for a sequential quadratic programming algorithm for solving sparse nonlinear optimization problems. Also provided are the details of a computer implementation of the algorithm along with test results. The algorithm maintains a sparse approximation to the Cholesky factor of the Hessian of the Lagrangian. The solution to the quadratic program generated at each step is obtained by solving a dual quadratic program using a projected conjugate gradient algorithm. An updating procedure is employed that does not destroy sparsity.     

A new descent algorithm for solving quadratic bilevel programming problems

1. IntroductionA bilevel programming problem (BLPP) involves two sequential optimization problems where the constraint region of the upper one is implicitly determined by the solutionof the lower. It is proved in [1] that even to find an approximate solution of a linearBLPP is strongly NP-hard. A number of algorithms have been proposed to solve BLPPs.Among them, the descent algorithms constitute an important class of algorithms for nonlinear BLPPs. However, it is assumed for almost all…     

强正定二次型与Weyl-Heisenberg 框架的构造

本文研究了一类具有特殊结构的无限维二次型, 得到这类二次型的对称矩阵是符号为多项式的模的平方的Laurent 矩阵, 进一步得到了这类二次型是强正定的判断标准以及一类Weyl-Heisenberg 框架的构造. 本文还研究了这类二次型的矩阵的所有有限维主对角子矩阵的强正定性, 并由此得到一类子空间Weyl-Heisenberg 框架的构造. 最后举例说明本文的主要结果及其应用. 本文建立了两个看似不相关的领域间的联系.     

Resolving degeneracy in quadratic programming

A technique for the resolution of degeneracy in an Active Set Method for Quadratic Programming is described. The approach generalises Fletcher's method [2] which applies to the LP case. The method is described in terms of an LCP tableau, which is seen to provide useful insights. It is shown that the degeneracy procedure only needs to operate when the degenerate constraints are linearly dependent on those in the active set. No significant overheads are incurred by the degeneracy procedure. It is readily implemented in a null space format, and no complications in the matrix algebra are introduced.The guarantees of termination provided by [2], extending in particular to the case where round-off error is present, are preserved in the QP case. It is argued that the technique gives stronger guarantees than are available with other popular methods such as Wolfe's method [11] or the method of Goldfarb and Idnani [7].Presented at the 14th International Symposium on Mathematical Programming, Amsterdam, August 5–9, 1991.     

A sequential quadratic programming with a dual parametrization approach to nonlinear semi-infinite programming

In the sequel of the work reported in Liu et al. (1999), in which a method based on a dual parametrization is used to solve linear-quadratic semi-infinite programming (SIP) problems, a sequential quadratic programming technique is proposed to solve nonlinear SIP problems. A merit function to measure progress toward the solution and a procedure to compute the penalty parameter are also proposed.     

A reformulation-convexification approach for solving nonconvex quadratic programming problems

In this paper, we consider the class of linearly constrained nonconvex quadratic programming problems, and present a new approach based on a novel Reformulation-Linearization/Convexification Technique. In this approach, a tight linear (or convex) programming relaxation, or outer-approximation to the convex envelope of the objective function over the constrained region, is constructed for the problem by generating new constraints through the process of employing suitable products of constraints and using variable redefinitions. Various such relaxations are considered and analyzed, including ones that retain some useful nonlinear relationships. Efficient solution techniques are then explored for solving these relaxations in order to derive lower and upper bounds on the problem, and appropriate branching/partitioning strategies are used in concert with these bounding techniques to derive a convergent algorithm. Computational results are presented on a set of test problems from the literature to demonstrate the efficiency of the approach. (One of these test problems had not previously been solved to optimality). It is shown that for many problems, the initial relaxation itself produces an optimal solution.     

A global continuation algorithm for solving binary quadratic programming problems

In this paper, we propose a new continuous approach for the unconstrained binary quadratic programming (BQP) problems based on the Fischer-Burmeister NCP function. Unlike existing relaxation methods, the approach reformulates a BQP problem as an equivalent continuous optimization problem, and then seeks its global minimizer via a global continuation algorithm which is developed by a sequence of unconstrained minimization for a global smoothing function. This smoothing function is shown to be strictly convex in the whole domain or in a subset of its domain if the involved barrier or penalty parameter is set to be sufficiently large, and consequently a global optimal solution can be expected. Numerical results are reported for 0-1 quadratic programming problems from the OR-Library, and the optimal values generated are made comparisons with those given by the well-known SBB and BARON solvers. The comparison results indicate that the continuous approach is extremely promising by the quality of the optimal values generated and the computational work involved, if the initial barrier parameter is chosen appropriately. This work is partially supported by the Doctoral Starting-up Foundation (B13B6050640) of GuangDong Province.