在闭凸集上连续型多场址的最优选择

本文考虑带有约束的连续型多场址问题(CEMFLC).对于连续型多场址问题(CEMFLC),我们给出了在闭集上选择最优场址的算法,证明了该算法是全局收敛的,最后,我们指出这一算法可用于解有约束或无约束的的高离散型多场址问题(EMFL),而且简化了(EMFL)问题现有的一些算法.     

Globally and Quadratically Convergent Algorithm for Minimizing the Sum of Euclidean Norms

For the problem of minimizing the sum of Euclidean norms (MSN), most existing quadratically convergent algorithms require a strict complementarity assumption. However, this assumption is not satisfied for a number of MSN problems. In this paper, we present a globally and quadratically convergent algorithm for the MSN problem. In particular, the quadratic convergence result is obtained without assuming strict complementarity. Examples without strictly complementary solutions are given to show that our algorithm can indeed achieve quadratic convergence. Preliminary numerical results are reported.     

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.     

Iterative linear programming solution of convex programs

An iterative linear programming algorithm for the solution of the convex programming problem is proposed. The algorithm partially solves a sequence of linear programming subproblems whose solution is shown to converge quadratically, superlinearly, or linearly to the solution of the convex program, depending on the accuracy to which the subproblems are solved. The given algorithm is related to inexact Newton methods for the nonlinear complementarity problem. Preliminary results for an implementation of the algorithm are given.This material is based on research supported by the National Science Foundation, Grants DCR-8521228 and CCR-8723091, and by the Air Force Office of Scientific Research, Grant AFOSR-86-0172. The author would like to thank Professor O. L. Mangasarian for stimulating discussions during the preparation of this paper.     

Exterior point algorithms for nearest points and convex quadratic programs

We consider the problem of finding the nearest point (by Euclidean distance) in a simplicial cone to a given point, and develop an exterior penalty algorithm for it. Each iteration in the algorithm consists of a single Newton step following a reduction in the value of the penalty parameter. Proofs of convergence of the algorithm are given. Various other versions of exterior penalty algorithms for nearest point problems in nonsimplicial polyhedral cones and for convex quadratic programs, all based on a single descent step following a reduction in the value of the penalty parameter per iteration, are discussed. The performance of these algorithms in large scale computational experiments is very encouraging. It shows that the number of iterations grows very slowly, if at all, with the dimension of the problem.Partially supported by NSF Grant No. ECS-8521183, and by the two universities.     

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.     

Robust solutions of uncertain complex-valued quadratically constrained programs

In this paper, we discuss complex convex quadratically constrained optimization with uncertain data. Using S-Lemma, we show that the robust counterpart of complex convex quadratically constrained optimization with ellipsoidal or intersection-of-two-ellipsoids uncertainty set leads to a complex semidefinite program. By exploring the approximate S-Lemma, we give a complex semidefinite program which approximates the NP-hard robust counterpart of complex convex quadratic optimization with intersection-of-ellipsoids uncertainty set.     

A gaussian upper bound for gaussian multi-stage stochastic linear programs

This paper deals with two-stage and multi-stage stochastic programs in which the right-hand sides of the constraints are Gaussian random variables. Such problems are of interest since the use of Gaussian estimators of random variables is widespread. We introduce algorithms to find upper bounds on the optimal value of two-stage and multi-stage stochastic (minimization) programs with Gaussian right-hand sides. The upper bounds are obtained by solving deterministic mathematical programming problems with dimensions that do not depend on the sample space size. The algorithm for the two-stage problem involves the solution of a deterministic linear program and a simple semidefinite program. The algorithm for the multi-stage problem invovles the solution of a quadratically constrained convex programming problem.     

Polynomial algorithms for parametric minquantile and maxcovering planar location problems with locational constraints

A location is sought within some convex region of the plane for the central site of some public service to a finite number of demand points. The parametric maxcovering problem consists in finding for eachR>0 the point from which the total weight of the demand points within distanceR is maximal. The parametric minimal quantile problem asks for each percentage α the point minimising the distance necessary for covering demand points of total weight at least α. We investigate the properties of these two closely related problems and derive polynomial algorithms to solve them both in case of either (possibly inflated) Euclidean or polyhedral distances. The research of the first author is partially supported by Grant PB96-1416-C02-02 of Ministerio de Educación y Cultura, Spain.     

Computational acceleration of projection algorithms for the linear best approximation problem

This is an experimental computational account of projection algorithms for the linear best approximation problem. We focus on the sequential and simultaneous versions of Dykstra’s algorithm and the Halpern-Lions-Wittmann-Bauschke algorithm for the best approximation problem from a point to the intersection of closed convex sets in the Euclidean space. These algorithms employ different iterative approaches to reach the same goal but no mathematical connection has yet been found between their algorithmic schemes. We compare these algorithms on linear best approximation test problems that we generate so that the solution will be known a priori and enable us to assess the relative computational merits of these algorithms. For the simultaneous versions we present a new component-averaging variant that substantially accelerates their initial behavior for sparse systems.     

Interior projection-like methods for monotone variational inequalities

We propose new interior projection type methods for solving monotone variational inequalities. The methods can be viewed as a natural extension of the extragradient and hyperplane projection algorithms, and are based on using non Euclidean projection-like maps. We prove global convergence results and establish rate of convergence estimates. The projection-like maps are given by analytical formulas for standard constraints such as box, simplex, and conic type constraints, and generate interior trajectories. We then demonstrate that within an appropriate primal-dual variational inequality framework, the proposed algorithms can be applied to general convex constraints resulting in methods which at each iteration entail only explicit formulas and do not require the solution of any convex optimization problem. As a consequence, the algorithms are easy to implement, with low computational cost, and naturally lead to decomposition schemes for problems with a separable structure. This is illustrated through examples for convex programming, convex-concave saddle point problems and semidefinite programming.The work of this author was partially supported by the United States–Israel Binational Science Foundation, BSF Grant No. 2002-2010.     

Steiner minimal trees for three points with one convex polygonal obstacle

The problem of constructing Steiner minimal trees in the Euclidean plane is NP-hard. When in addition obstacles are present, difficulties of constructing obstacle-avoiding Steiner minimal trees are compounded. This problem, which has many obvious practical applications when designing complex transportation and distribution systems, has received very little attention in the literature. The construction of Steiner minimal trees for three terminal points in the Euclidean plane (without obstacles) has been completely solved (among others by Fermat, Torricelli, Cavallieri, Simpson, Heinen) during the span of the last three centuries. This construction is a cornerstone for both exact algorithms and heuristics for the Euclidean Steiner tree problem with arbitrarily many terminal points. An algorithm for three terminal points in the presence of one polygonal convex obstacle is given. It is shown that this algorithm has the worst-case time complexityO(n), wheren is the number of extreme points on the obstacle. As an extension to the underlying algorithm, if the obstacle is appropriately preprocessed inO(n) time, we can solve any problem instance with three arbitrary terminal points and the preprocessed convex polygonal obstacle inO(logn) time. We believe that the three terminal points algorithm will play a critical role in the development of heuristics for problem instances with arbitrarily many terminal points and obstacles.     

Euclidean Jordan Algebras and Interior-point Algorithms

We provide an introduction to the theory of interior-point algorithms of optimization based on the theory of Euclidean Jordan algebras. A short-step path-following algorithm for the convex quadratic problem on the domain, obtained as the intersection of a symmetric cone with an affine subspace, is considered. Connections with the Linear monotone complementarity problem are discussed. Complexity estimates in terms of the rank of the corresponding Jordan algebra are obtained. Necessary results from the theory of Euclidean Jordan algebras are presented.     

Simulated N-Body: New Particle Physics-Based Heuristics for a Euclidean Location-Allocation Problem

The general facility location problem and its variants, including most location-allocation and P-median problems, are known to be NP-hard combinatorial optimization problems. Consequently, there is now a substantial body of literature on heuristic algorithms for a variety of location problems, among which can be found several versions of the well-known simulated annealing algorithm. This paper presents an optimization paradigm that, like simulated annealing, is based on a particle physics analogy but is markedly different from simulated annealing. Two heuristics based on this paradigm are presented and compared to simulated annealing for a capacitated facility location problem on Euclidean graphs. Experimental results based on randomly generated graphs suggest that one of the heuristics outperforms simulated annealing both in cost minimization as well as execution time. The particular version of location problem considered here, a location-allocation problem, involves determining locations and associated regions for a fixed number of facilities when the region sizes are given. Intended applications of this work include location problems with congestion costs as well as graph and network partitioning problems.     

Simplex-inspired algorithms for solving a class of convex programming problems

We consider a class of convex programming problems whose objective function is given as a linear function plus a convex function whose arguments are linear functions of the decision variables and whose feasible region is a polytope. We show that there exists an optimal solution to this class of problems on a face of the constraint polytope of dimension not more than the number of arguments of the convex function. Based on this result, we develop a method to solve this problem that is inspired by the simplex method for linear programming. It is shown that this method terminates in a finite number of iterations in the special case that the convex function has only a single argument. We then use this insight to develop a second algorithm that solves the problem in a finite number of iterations for an arbitrary number of arguments in the convex function. A computational study illustrates the efficiency of the algorithm and suggests that the average-case performance of these algorithms is a polynomial of low order in the number of decision variables. The work of T. C. Sharkey was supported by a National Science Foundation Graduate Research Fellowship. The work of H. E. Romeijn was supported by the National Science Foundation under Grant No. DMI-0355533.     

Convergence of a non-interior continuation algorithm for the monotone SCCP

It is well known that the symmetric cone complementarity problem（SCCP） is a broad class of optimization problems which contains many optimization problems as special cases.Based on a general smoothing function,we propose in this paper a non-interior continuation algorithm for solving the monotone SCCP.The proposed algorithm solves at most one system of linear equations at each iteration.By using the theory of Euclidean Jordan algebras,we show that the algorithm is globally linearly and locally quadratically convergent under suitable assumptions.     

On the convergence of the generalized Weiszfeld algorithm

In this paper we consider Weber-like location problems. The objective function is a sum of terms, each a function of the Euclidean distance from a demand point. We prove that a Weiszfeld-like iterative procedure for the solution of such problems converges to a local minimum (or a saddle point) when three conditions are met. Many location problems can be solved by the generalized Weiszfeld algorithm. There are many problem instances for which convergence is observed empirically. The proof in this paper shows that many of these algorithms indeed converge.     

Coloring arcs of convex sets

In this note we consider Ramsey-type problems on graphs whose vertices are represented by the vertices of a convex polygon in the Euclidean plane. The edges of the graph are represented by the segments between the points of the polygon. The edges are arbitrarily colored by a fixed number of colors and the problem is to decide whether there exist monochromatic subgraphs of certain types satisfying some geometric conditions. We will give lower and upper bounds for these geometric Ramsey numbers for certain paths and cycles and also some exact values. It turns out that the particular type of the embedding is crucial for the growth rate of the corresponding geometric Ramsey numbers. In particular, the Ramsey numbers for crossing 4-cycles and t colors grow quadratically in t, while for convex 4-cycles they grow at least exponentially.     

An efficient solution method for Weber problems with barriers based on genetic algorithms

In this paper we consider the problem of locating one new facility with respect to a given set of existing facilities in the plane and in the presence of convex polyhedral barriers. It is assumed that a barrier is a region where neither facility location nor travelling are permitted. The resulting non-convex optimization problem can be reduced to a finite series of convex subproblems, which can be solved by the Weiszfeld algorithm in case of the Weber objective function and Euclidean distances. A solution method is presented that, by iteratively executing a genetic algorithm for the selection of subproblems, quickly finds a solution of the global problem. Visibility arguments are used to reduce the number of subproblems that need to be considered, and numerical examples are presented.     

Algorithmic equivalence in quadratic programming,I: A least-distance programming problem

It is demonstrated that Wolfe's algorithm for finding the point of smallest Euclidean norm in a given convex polytope generates the same sequence of feasible points as does the van de Panne-Whinstonsymmetric algorithm applied to the associated quadratic programming problem. Furthermore, it is shown how the latter algorithm may be simplified for application to problems of this type.This work was supported by the National Science Foundation, Grant No. MCS-71-03341-AO4, and by the Office of Naval Research, Contract No. N00014-75-C-0267.