多场址问题的一个全局收敛算法及其推广

设a_1,a_2,…a_m是R~d中m个点,设w_(ji)>0,j=1,2,…,n,i=1,2,…,m,v_(jk)>0,1≤j相似文献   

线性等式约束连续型minimax问题的区间算法

研究线性等式约束连续型minimax问题,其中目标函数为Lipschitz连续函数,基于线性约束函数的区间迭代运算、区域二分原则和无解区域删除原则,建立了求解线性等式约束连续型minimax问题的区间算法,证明了算法的相关定理,给出了数值算例,该算法保证求出问题的整体解,且是可靠和有效的.     

多场址问题的信赖域算法

多场址问题是一类重要的不可微凸规划问题，国内外已有许多学者对其进行研究，并提出了一 算法。但如文「２」中所述，大多数算法或无收敛收保证，或在较强的条件下才保证收敛，本文提出一类解多场址问题的信赖域算法，并在极弱的条件下证明该类算法的全局收敛性。     

连续型凸动态规划的离散近似迭代法研究

为解决连续型凸动态规划的“维数灾”问题,提出了一种新的算法—离散近似迭代法.该算法的基本思路为:首先,将连续型状态变量离散化,根据网络图的构造方法将动态规划问题转化为多阶段有向赋权图;其次,运用极大代数求出起点至终点的最短路,即获得模型的一个可行解;最后,以该可行解为基础,继续迭代直到前后两个可行解非常接近.文章还证明了该算法的收敛性和线性收敛,并以一个具体例子验证了算法的有效性.     

一类矩阵方程异类约束解与Ls解的迭代算法

当多矩阵变量线性矩阵方程(LME)相容时,通过修改共轭梯度法的下降方向及其有关系数,建立求LME的一种异类约束解的迭代算法.当LME不相容时,先通过构造等价的线性矩阵方程组(LMEs),将不相容的LME异类约束最小二乘解(Ls解)问题转化为相容的LMEs异类约束解问题,然后参照求LME的异类约束解的迭代算法,建立求LME的一种异类约束Ls解的迭代算法.不考虑舍入误差时,迭代算法可在有限步计算后求得LME的一组异类约束解或者异类约束Ls解;选取特殊的初始矩阵时,可求得LME的极小范数异类约束解或者异类约束Ls解.此外,还可在LME的异类约束解或者异类约束Ls解集合中给出指定矩阵的最佳逼近矩阵.算例表明,迭代算法是有效的.     

基于拟态物理学的约束多目标共轭梯度混合算法

在拟态物理学优化算法APO的基础上,将一种基于序值的无约束多目标算法RMOAPO的思想引入到约束多目标优化领域中.提出一种基于拟态物理学的约束多目标共轭梯度混合算法CGRMOAPA.算法采取外点罚函数法作为约束问题处理技术,并借鉴聚集函数法的思想,将约束多目标优化问题转化为单目标无约束优化问题,最终利用共轭梯度法进行求解.通过与CRMOAPO、MOGA、NSGA-II的实验对比,表明了算法CGRMOAPA具有较好的分布性能,也为约束多目标优化问题的求解提供了一种新的思路.     

概率约束随机规划的一种近似方法及其它的有效解模式

根据最小风险的投资最优问题，我们给出了一个统一的概率约束随机规划模型。随后我们提出了求解这类概率约束随机规划的一种近似算法，并在一定的条件下证明了算法的收敛性。此外，提出了这种具有概率约束多目标随机规划问题的一种有效解模型。     

带非凸二次约束的二次比式和问题的全局优化算法(英文)

对带非凸二次约束的二次比式和问题(P)给出分枝定界算法,首先将问题(P)转化为其等价问题(Q),然后利用线性化技术,建立了(Q)松弛线性规划问题(RLP),通过对(RLP)可行域的细分及求解一系列线性规划问题,不断更新(Q)的上下界,从理论上证明了算法的收敛性,数值实验表明了算法的可行性和有效性.     

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

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

互补约束优化问题的乘子序列部分罚函数算法

利用互补问题的Lagrange函数,
将互补约束优化问题(MPCC)转化为含参数的约束优化问题.
给出Lagrange乘子的简单修正公式,
并给出求解互补约束优化问题的部分罚函数法. 无须假设二阶必要条件成立,
只要算法产生的迭代点列的极限点满足互补约束优化问题的线性独立约束规范(MPCC-LICQ),
且极限点是MPCC的可行点, 则算法收敛到原问题的M-稳定点. 另外,
在上水平严格互补(ULSC)成立的条件下, 算法收敛到原问题的B-稳定点.     

A globally convergent algorithm for the Euclidean multiplicity location problem

The Euclidean single facility location problem (ESFL) and the Euclidean multiplicity location problem (EMFL) are two special nonsmooth convex programming problems which have attracted a large literature. For the ESFL problem, there are algorithms which converge both globally and quadratically. For the EMFL problem, there are some quadratically convergent algorithms, but for global convergence, they all need nontrivial assumptions on the problem.In this paper, we present an algorithm for EMFL. With no assumption on the problem, it is proved that from any initial point, this algorithm generates a sequence of points which converges to the closed convex set of optimal solutions of EMFL.This research is supported in part by the Air Force Office of Scientific Research Grant AFOSR-87-0127, the National Science Foundation Grant DCR-8420935 and University of Minnesota Graduate School Doctoral Dissertation Fellowship awarded to G.L. Xue.     

The solution of the EMFL problem with two new facilities in a quadrangle

This paper is concerned with the analytical solution of the EMFL (Euclidean multifacility location) problem with two new facilities and four existing facilities. In Section 1, the optimality conditions for a general EMFL problem are summarized in the form presented in [1]. In Section 2, they are applied to the considered problem, in order to locate the new facilities and to partition the space of the weights (for a given set of existing facilities) into regions with the same type of solution. However, it is pointed out that a complete solution can be obtained only in particular cases.     

A note on optimality conditions for the Euclidean. Multifacility location problem

Thekey problem of the Euclidean multifacility location (EMFL) problem is to decide whether a givendead point is optimal. If it is not optimal, we wish to compute a descent direction. This paper extends the optimality conditions of Calamai and Conn and Overton to the case when the rows of the active constraints matrix are linearly dependent. We show that linear dependence occurs wheneverG, the graph of the coinciding facilities, has a cycle. In this case the key problem is formulated as a linear least squares problem with bounds on the Euclidean norms of certain subvectors.     

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.     

Locating a Central Hunter on the Plane

Protection, surveillance or other types of coverage services of mobile points call for different, asymmetric distance measures than the traditional Euclidean, rectangular or other norms used for fixed points. In this paper, the destinations are mobile points (prey) moving at fixed speeds and directions and the facility (hunter) can capture them using one of two possible strategies: either it is smart, predicting the prey’s movement in order to minimize the time needed to capture it, or it is dumb, following a pursuit curve, by moving at any moment in the direction of the prey. In either case, the hunter location in a plane is sought in order to minimize the maximum time of capture of any prey. An efficient solution algorithm is developed that uses the particular geometry that both versions of this problem possess. In the case of unpredictable movement of prey, a worst-case type solution is proposed, which reduces to the well-known weighted Euclidean minimax location problem. The work of the second and third authors was supported in part by a grant from Research Projects BFM2003-04062 and MTM2006-15054.     

On the convergence of a modified algorithm for the spherical facility location problem

We study the spherical facility location problem which is a more realistic model than the Euclidean facilities location. We present a modified algorithm for this problem, which has the following good properties: (a) It is very easy to initialize the algorithm with an arbitrary point as its starting point; (b) Under suitable assumptions, it is proved that the algorithm globally converges to a global minimizer of the problem.     

Bounds on the Optimal Location to the Weber Problem under Conditions of Uncertainty

Optimal and Heuristic bounds are given for the optimal location to the Weber problem when the locations of demand points are not deterministic but may be within given circles. Rectilinear, Euclidean and square Euclidean types of distance measure are discussed. The exact shape of all possible optimal points is given in the rectilinear and square Euclidean cases. A heuristic method for the computation of the region of possible optimal points is developed in the case of Euclidean distance problem. The maximal distance between a possible optimal point and the deterministic solution is also computed heuristically.     

A Mini-Max Location Problem with Demand Points Arbitrarily Distributed in a Compact Connected Space

Consider a finite set of demand points which exist anywhere on the boundary of a rectangle contained in the two-dimensional Euclidean space. This paper considers the problem of finding an optimal location (on the boundary of the rectangle) which minimizes the maximum average Euclidean distance to the demand points. The method presented is independent of the number of demand points.     

Capacitated location allocation problem with stochastic location and fuzzy demand: A hybrid algorithm

In this article, a capacitated location allocation problem is considered in which the demands and the locations of the customers are uncertain. The demands are assumed fuzzy, the locations follow a normal probability distribution, and the distances between the locations and the customers are taken Euclidean and squared Euclidean. The fuzzy expected cost programming, the fuzzy β-cost minimization model, and the credibility maximization model are three types of fuzzy programming that are developed to model the problem. Moreover, two closed-form Euclidean and squared Euclidean expressions are used to evaluate the expected distance between customers and facilities. In order to solve the problem at hand, a hybrid intelligent algorithm is applied in which the simplex algorithm, fuzzy simulation, and a modified genetic algorithm are integrated. Finally, in order to illustrate the efficiency of the proposed hybrid algorithm, some numerical examples are presented.     

A polynomial time algorithm for a hemispherical minimax location problem

A polynomial time algorithm to obtain an exact solution for the equiweighted minimax location problem when the demand points are spread over a hemisphere is presented. It is shown that the solution of the minimax problem when the norm under consideration is geodesic is equivalent to solving a maximization problem using the Euclidean norm.