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

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

具有线性等式和不等式约束的非线性规划的一个算法

§1.引言既约梯度法是求解非线性规划的一类方法.我们目前只看到约束为线性等式或非线性等式的既约梯度法,对于线性不等式或非线性不等式约束的情形还没有相应的既约梯度法.如果通过松驰变量把线性不等式约束化成线性等式的情形处理,则要增加变量的维数,而这是与既约梯度法的思想背道而驰的.在本文中,我们结合既约梯度法与 Ritter在文献[3]中的思想,对具有线性等式和不等式约束的非线性规划问题给出了一种算法,它保留了既约梯度法降低维数的优点,又简化了 Ritter 在[3]中给出的算法.另外,我们还证明了算法的收敛性.     

一种基于LVI求解二次规划问题的数值算法

给出并研究了一种数值算法(简称94LVI算法),用于求解带等式和双端约束的二次规划问题. 这类带约束的二次规划问题首先被转换为线性变分不等式问题,该问题等价于分段线性投影等式.接着使用94LVI算法求解上述分段线性投影等式,从而得到QP问题的最优解. 进一步给出了94LVI算法的全局收敛性证明. 94LVI算法与经典有效集算法的对比实验结果证实了给出的94LVI算法在求解二次规划问题上的高效性与优越性.     

不等式约束优化基于新型积极识别集的SQCQP算法

本文提出一个新的求解非线性不等式约束优化问题的罚函数型序列二次约束二次规划(SQCQP)算法.算法每次迭代只需求解一个凸二次约束二次规划(QCQP)子问题,且通过引入新型积极识别集技术,QCQP子问题的规模显著减小,从而降低计算成本.在不需要函数凸性等较弱假设下,算法具有全局收敛性.初步的数值试验表明算法是稳定有效的.     

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

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

可行方向法的统一探讨：二阶段算法模型

1 引言可行方向法是非线性规划中一类思想简单数值效果好的基本方法。特别是对线性约束问题,这类方法一直受人欢迎。但由于非线性约束带来的困难,这一领域内的工作近年来并不多见。文[1]曾统一和推广了国内外文献中常见的投影梯度和既约梯度法。本文首先提出一个二阶段算法模型用来解不等式约束问题,大范围地统一和推广了现有的可行方向法。然后,对于一般非线性规划问题,本文利用仅含等式约束的Lagrange函数作为搜索函数,直接应用上述模型的结果给出相应的模型,大大推广和简化了[2]中方法。具体选     

某类等式约束二次规划问题的一个共轭方向法

本文提出了一种求解某类等式约束二次规划问题的一个共轭方向迭代法，并给出了算法的有限终止性证明．同时我们把此算法推广到不等式约束二次规划问题中，从而得到了一种求解不等式约束二次规划问题的算法．     

求连续minimax问题整体解的区间算法

1 引 言 Minimax问题是一类重要的数学规划问题,它来源于实际并有极广泛的应用([1],[2]).用区间数学方法求解 minimax问题已取得了一些成果.文[1]对由 C2类函数构成的无约束连续 minimax问题进行了研究,建立了相应的区间算法,文[6]～[11]分别讨论和建立了无约束和不等式约束的离散minimax问题的区间算法.文[12]、[13]则讨论了最坏     

非线性最优化一个超线收敛的可行下降算法

本文讨论非线性等式和不等式约束最优化的求解方法。首先将原问题扩充成一个只含不等式约束的参数规划，对于充分大的参数，扩充问题与原问题是等价的。然手建立具有以下特点的一个新算法。１）算法对扩充问题而言是可行下降的，参数只须自动调整有限次；２）每次迭代仅需解一个二次规划；３）在适当的假设下，算法超线性收敛于原问题的最优解。     

解线性约束凸规划的次最优化方法和改进

1.引 言 关于线性约束下的非线性规划,很多人进行了研究,Zangwill[3] 于1967年提出了次最优化方法,该方法的原理是将原规划问题化为一系列只含有等式约束的子问题求解,最后找到最优解所在的流形,在此流形上使用无约束规划的各种方法求解原问题即可.薛声家[2]1983     

一种基于区间数多指标信息的FCM聚类算法

针对一类具有不确定性区间数多指标信息的聚类分析问题，依据传统的基于数值信息的FCM聚类算法的思路，提出了一种新的聚类分析算法。章首先描述了具有区间数多指标信息的聚类分析问题；其次给出了基于区间数多指标信息的关于最优划分和最优聚类中心确定的两个定理；然后给出了基于区间数多指标信息的FCM聚类算法的计算步骤。该算法的特点是聚类中心的表现形式为精确的数值，给出的两个定理说明了该聚类算法的收敛性。最后，通过给出一个算例说明了本给出的聚类算法。     

一种求解救灾物资运输问题的改进解法

本文通过对B运输问题建立数学模型,提出了一种求解B运输问题的改进解法。改进解法首先通过最小元素法求出初始解,然后进行变量闭回路法调整,直到求出最优解,并给出了一个计算实例证明了解法的有效性。文章还对改进解法和另外两种现有的算法进行了综合的分析,由于改进解法计算过程中采用的变量闭回路法省略了求检验数的环节,使得新算法比两种现有的算法更简便。     

Finite iterative algorithm for the complex generalized Sylvester tensor equations

A finite iterative algorithm is proposed to solve a class of complex generalized Sylvester tensor equations. The properties of this proposed algorithm are discussed based on a real inner product of two complex tensors and the finite convergence of this algorithm is obtained. Two numerical examples are offered to illustrate the effectiveness of the proposed algorithm.     

Solving sum of quadratic ratios fractional programs via monotonic function

In this paper, a branch-reduce-bound algorithm is proposed for globally solving a sum of quadratic ratios fractional programming with nonconvex quadratic constraints. Due to its intrinsic difficulty, less work has been devoted to globally solving this problem. The proposed algorithm is based on reformulating the problem as a monotonic optimization problem, and it turns out that the optimal solution which is provided by the algorithm is adequately guaranteed to be feasible and to be close to the actual optimal solution. Convergence of the algorithm is shown and the numerical experiments are given to show the feasibility of the proposed algorithm.     

A Newton Acceleration of the Weiszfeld Algorithm for Minimizing the Sum of Euclidean Distances

The Weiszfeld algorithm for continuous location problems can be considered as an iteratively reweighted least squares method. It generally exhibits linear convergence. In this paper, a Newton algorithm with similar simplicity is proposed to solve a continuous multifacility location problem with the Euclidean distance measure. Similar to the Weiszfeld algorithm, the main computation can be solving a weighted least squares problem at each iteration. A Cholesky factorization of a symmetric positive definite band matrix, typically with a small band width (e.g., a band width of two for a Euclidean location problem on a plane) is performed. This new algorithm can be regarded as a Newton acceleration to the Weiszfeld algorithm with fast global and local convergence. The simplicity and efficiency of the proposed algorithm makes it particularly suitable for large-scale Euclidean location problems and parallel implementation. Computational experience suggests that the proposed algorithm often performs well in the absence of the linear independence or strict complementarity assumption. In addition, the proposed algorithm is proven to be globally convergent under similar assumptions for the Weiszfeld algorithm. Although local convergence analysis is still under investigation, computation results suggest that it is typically superlinearly convergent.     

求线性比试和问题的确定性全局优化算法

为求线性比试和问题的全局最优解,本文给出了一个分支定界算法.通过一个等价问题和一个新的线性化松弛技巧,初始的非凸规划问题归结为一系列线性规划问题的求解.借助于这一系列线性规划问题的解,算法可收敛于初始非凸规划问题的最优解.算法的计算量主要是一些线性规划问题的求解.数值算例表明算法是切实可行的.     

快速三维散乱数据点重建算法

提出了一种快速三维散乱数据点重建算法.我们对包围盒算法进行了改进,减少了建立散乱点近邻关系所需的计算量;同时针对位置相对平坦的数据点,结合最小二乘法给出了一种计算法矢的混合方法.实例表明,该算法是有效的.     

A hybrid simulated annealing and column generation approach for capacitated multicommodity network design

This paper presents a hybrid simulated annealing (SA) and column generation (CG) algorithm for the path-based formulation of the capacitated multicommodity network design (PCMND) problem. In the proposed method, the SA metaheuristic algorithm manages open and closed arcs. Several strategies for adding and dropping arcs are suggested and evaluated. For a given design vector in the proposed hybrid approach, the PCMND problem becomes a capacitated multicommodity minimum cost flow (CMCF) problem. The exact evaluation of the CMCF problem is performed using the CG algorithm. The parameter tuning is done by means of design of experiments approach. The performance of the proposed algorithm is evaluated by solving several benchmark instances. The results of the proposed algorithm are compared with the solutions of CPLEX solver and the best-known method in the literature under different time limits. Statistical analysis proves that the proposed algorithm is able to obtain better solutions.     

顺序相依拆卸线平衡多目标优化模型及算法研究

拆卸是产品回收过程最关键环节之一,拆卸效率直接影响再制造成本。本文在分析现有模型不足基础上,考虑最小化总拆卸时间,建立多目标顺序相依拆卸线平衡问题优化模型,并提出了一种自适应进化变邻域搜索算法。所提算法引入种群进化机制,并采用一种组合策略构建初始种群,通过锦标赛法选择个体进化;在局部搜索时,设计了邻域结构自适应选择策略,并采用基于交叉的全局学习机制加速跳出局部最优,以提高算法寻优能力。对比实验结果,证实了所提模型的合理性以及算法的高效性。     

Constrained global optimization of multivariate polynomials using Bernstein branch and prune algorithm

We propose an algorithm for constrained global optimization to tackle non-convex nonlinear multivariate polynomial programming problems. The proposed Bernstein branch and prune algorithm is based on the Bernstein polynomial approach. We introduce several new features in this proposed algorithm to make the algorithm more efficient. We first present the Bernstein box consistency and Bernstein hull consistency algorithms to prune the search regions. We then give Bernstein contraction algorithm to avoid the computation of Bernstein coefficients after the pruning operation. We also include a new Bernstein cut-off test based on the vertex property of the Bernstein coefficients. The performance of the proposed algorithm is numerically tested on 13 benchmark problems. The results of the tests show the proposed algorithm to be overall considerably superior to existing method in terms of the chosen performance metrics.