An Adaptive Dual Parametrization Algorithm for Quadratic Semi-infinite Programming Problems

The so called dual parametrization method for quadratic semi-infinite programming (SIP) problems is developed recently for quadratic SIP problems with a single infinite constraint. A dual parametrization algorithm is also proposed for numerical solution of such problems. In this paper, we consider quadratic SIP problems with positive definite objective and multiple linear infinite constraints. All the infinite constraints are supposed to be continuously dependent on their index variable on a compact set which is defined by a number equality and inequalities. We prove that in the multiple infinite constraint case, the minimu parametrization number, just as in the single infinite constraint case, is less or equal to the dimension of the SIP problem. Furthermore, we propose an adaptive dual parametrization algorithm with convergence result. Compared with the previous dual parametrization algorithm, the adaptive algorithm solves subproblems with much smaller number of constraints. The efficiency of the new algorithm is shown by solving a number of numerical examples.     

A Dual Parametrization Method for Convex Semi-Infinite Programming

We formulate convex semi-infinite programming problems in a functional analytic setting and derive optimality conditions and several duality results, based on which we develop a computational framework for solving convex semi-infinite programs.     

An Approximation Approach to Non-strictly Convex Quadratic Semi-infinite Programming

We present in this paper a numerical method for solving non-strictly-convex quadratic semi-infinite programming including linear semi-infinite programming. The proposed method transforms the problem into a series of strictly convex quadratic semi-infinite programming problems. Several convergence results and a numerical experiment are given.     

基于松弛策略解半无限规划模型的显式修正算法

讨论了一类线性半无限最优规划模型的求解算法.采用松弛方法解其系列子问题LP(T_k)及DLP(T_k),基于松弛策略和在适当的假设条件下,提出了一个我们称之为显式算法的新型算法.新算法的主要改进之处是算法在每一步迭代计算时,允许丢弃一些不必要的约束.在这种方式下,算法避免了求解系列太大规模的子问题.最后,基于提出的显式修正算法,并与传统割平面方法和已有文献中的松弛修正算法、对同一问题作了初步的数值比较实验.     

求不定二次规划全局解的一个新算法

本文提出了一个求不定二次规划问题全局最优解的新算法.首先,给出了三种计算下界的方法:线性逼近法、凸松弛法和拉格朗日松弛法;并且证明了拉格朗日对偶界与通过凸松弛得到的下界是相等的;然后建立了基于拉格朗日对偶界和矩形两分法的分枝定界算法,并给出了初步的数值试验结果.     

On Nesterov's Approach to Semi-infinite Programming

We generalize Nesterov's construction for the reduction of various classes of semi-infinite programming problems to the semidefinite programming form. In this way, we are able to consider cones of squares of real-valued and matrix-valued functions as rather particular cases of a unifying abstract scheme. We also interpret from this viewpoint some results of M. Krein and A. Nudelman. This provides (in a way which probably has not been anticipated by these authors) a very powerful tool for solving various optimization problems.     

半无限规划的一个序列线性方程组方法

本基于离散技术，给出了任意初始点下的半无限规划的一个序列线性方程组算法和算法的全局收敛性的证明。并在一定的假设下，证明了算法的一步超线性收敛性。     

不等式约束二次规划的一新算法

文献[1]提出了一般等式约束非线性规划问题一种求解途径．文献[2]应用这一途径给出了等式约束二次规划问题的一种算法，本文在文献[1]和[2]的基础上对不等式约束二次规划问题提出了一种新算法．     

Exact Algorithm for the Surrogate Dual of an Integer Programming Problem: Subgradient Method Approach

One of the critical issues in the effective use of surrogate relaxation for an integer programming problem is how to solve the surrogate dual within a reasonable amount of computational time. In this paper, we present an exact and efficient algorithm for solving the surrogate dual of an integer programming problem. Our algorithm follows the approach which Sarin et al. (Ref. 8) introduced in their surrogate dual multiplier search algorithms. The algorithms of Sarin et al. adopt an ad-hoc stopping rule in solving subproblems and cannot guarantee the optimality of the solutions obtained. Our work shows that this heuristic nature can actually be eliminated. Convergence proof for our algorithm is provided. Computational results show the practical applicability of our algorithm.     

半局部凸多目标半无限规划的最优性

研究半局部凸函数在多目标半无限规划下的最优性.利用半局部凸函数,讨论了在多目标半无限规划下的择一定理,最优性条件.使半局部凸函数运用的范围更加广泛.     

约束非线性规划的神经网络算法

神经网络具有内在大规模并行运算和快速收敛特性,它在最优化技术上的运用近年来受到广泛的重视。本提出一个新的求解一般约束非线性规划的神经网络模型,它具有全局收敛性和广泛的适用性,是求解一般非线性规划问题的新工具。理论分析和模拟计算均表明了模型的有效性。     

An Efficient Algorithm for Min-Max Convex Semi-Infinite Programming Problems

In this article, we consider the convex min-max problem with infinite constraints. We propose an exchange method to solve the problem by using efficient inactive constraint dropping rules. There is no need to solve the maximization problem over the metric space, as the algorithm has merely to find some points in the metric space such that a certain criterion is satisfied at each iteration. Under some mild assumptions, the proposed algorithm is shown to terminate in a finite number of iterations and to provide an approximate solution to the original problem. Preliminary numerical results with the algorithm are promising. To our knowledge, this article is the first one conceived to apply explicit exchange methods for solving nonlinear semi-infinite convex min-max problems.     

Canonical Duality Theory and Solutions to Constrained Nonconvex Quadratic Programming

This paper presents a perfect duality theory and a complete set of solutions to nonconvex quadratic programming problems subjected to inequality constraints. By use of the canonical dual transformation developed recently, a canonical dual problem is formulated, which is perfectly dual to the primal problem in the sense that they have the same set of KKT points. It is proved that the KKT points depend on the index of the Hessian matrix of the total cost function. The global and local extrema of the nonconvex quadratic function can be identified by the triality theory [11]. Results show that if the global extrema of the nonconvex quadratic function are located on the boundary of the primal feasible space, the dual solutions should be interior points of the dual feasible set, which can be solved by deterministic methods. Certain nonconvex quadratic programming problems in {\open {R}}^{n} can be converted into a dual problem with only one variable. It turns out that a complete set of solutions for quadratic programming over a sphere is obtained as a by-product. Several examples are illustrated.     

A Dual Projective Pivot Algorithm for Linear Programming

Recently, a linear programming problem solver, called dual projective simplex method, was proposed (Pan, Computers and Mathematics with Applications, vol. 35, no. 6, pp. 119–135, 1998). This algorithm requires a crash procedure to provide an initial (normal or deficient) basis. In this paper, it is recast in a more compact form so that it can get itself started from scratch with any dual (basic or nonbasic) feasible solution. A new dual Phase-1 approach for producing such a solution is proposed. Reported are also computational results obtained with a set of standard NETLIB problems.     

最大割问题的二次规划方法

本文给出了最大割问题的二次规划算法。这种算法通过求解最大割问题的二次规划松弛给出了一种较好的界，然后用分支定界法得到了最大割问题的解。数值结果表明这种算法是非常有效的。     

A Combined Algorithm for Fractional Programming

In this paper, we present an outer approximation algorithm for solving the following problem: max _xS {f(x)/g(x)}, where f(x)0 and g(x)>0 are d.c. (difference of convex) functions over a convex compact subset S of R ⁿ . Let ()=max _xS (f(x)–g(x)), then the problem is equivalent to finding out a solution of the equation ()=0. Though the monotonicity of () is well known, it is very time-consuming to solve the previous equation, because that maximizing (f(x)–g(x)) is very hard due to that maximizing a convex function over a convex set is NP-hard. To avoid such tactics, we give a transformation under which both the objective and the feasible region turn to be d.c. After discussing some properties, we propose a global optimization approach to find an optimal solution for the encountered problem.     

对称弧式连通凸多目标半无限规划的最优性

以弧式连通函数和对称梯度为基础,研究新函数在多目标半无限规划下的最优性理论.定义了一类新的弧式连通函数,对称弧式连通函数、对称拟弧式连通函数、对称弱拟弧式连通函数、对称伪弧式连通函数、对称严格伪弧式连通函数,讨论了这些函数在多目标半无限规划下的最优性.给出更加广义的弧式连通函数,将它们运用到多目标半无限规划.     

一种非增值型凸二次双层规划的有效算法

主要研究了非增值型凸二次双层规划的一种有效求解算法。首先利用数学规划的对偶理论,将所求双层规划转化为一个下层只有一个无约束凸二次子规划的双层规划问题.然后根据两个双层规划的最优解和最优目标值之间的关系,提出一种简单有效的算法来解决非增值型凸二次双层规划问题.并通过数值算例的计算结果说明了该算法的可行性和有效性。     

关于线性规划问题熵障碍对偶法的注记

线性规划是目标优化问题中最常用的模型。关于大规模线性规划问题的有效求解问题一直受到人们的关注。熵障碍对偶法是继内点法之后,又一解线性规划问题的新的算法。本文讨论了熵障碍对偶法的推广形式及其梯度类算法的收敛性。     

一种新的可分凸二次规划的不可行内点算法

本文对可分凸二次规划提出了一个新的不可行内点算法 ,证明了该算法是一个多项式时间算法 ,并将迭代复杂性界降至O(nL) .