An algorithm for finding the Chebyshev center of a convex polyhedron

An algorithm for finding the Chebyshev center of a finite point set in the Euclidean spaceR ⁿ is proposed. The algorithm terminates after a finite number of iterations. In each iteration of the algorithm the current point is projected orthogonally onto the convex hull of a subset of the given point set.Part of this research was done at the University of Würzburg (Institut für Angewandte Mathematik und Statistik) when the first author was supported by the Alexander von Humboldt Foundation, Germany.On leave from the Institute of Mathematics and Mechanics, Ural Department of Russia Academy of Sciences, 620219 Ekaterinburg, S. Kovalevskaya str.16, Russia.     

An algorithm to solve polyhedral convex set optimization problems

An algorithm which computes a solution of a set optimization problem is provided. The graph of the objective map is assumed to be given by finitely many linear inequalities. A solution is understood to be a set of points in the domain satisfying two conditions: the attainment of the infimum and minimality with respect to a set relation. In the first phase of the algorithm, a linear vector optimization problem, called the vectorial relaxation, is solved. The resulting pre-solution yields the attainment of the infimum but, in general, not minimality. In the second phase of the algorithm, minimality is established by solving certain linear programs in combination with vertex enumeration of some values of the objective map.     

An exact algorithm for finding a vector subset with the longest sum

We consider the problem: Given a set of n vectors in the d-dimensional Euclidean space, find a subsetmaximizing the length of the sum vector.We propose an algorithm that finds an optimal solution to this problem in time O(n^d?1(d + logn)). In particular, if the input vectors lie in a plane then the problem is solvable in almost linear time.     

An algorithm for finding the shortest element of a polyhedral set with application to lagrangian duality

An algorithm is developed which finds the point in a compact polyhedral set with smallest Euclidean norm. At each iteration the algorithm requires knowledge of only those vertices of the set which are adjacent to a current reference vertex. This feature is shown to permit the adoption of the technique to find iteratively the shortest subgradient (i.e. the direction of steepest ascent) of the lagrangian dual function for large scale linear programs. Procedures are presented for finding the direction of steepest ascent in both the equality constraint and the inequality constraint cases of lagrangian duality.     

Critical angles in polyhedral convex cones: numerical and statistical considerations

This work concerns the numerical computation of critical angles in polyhedral convex cones. The set of proper critical angles is evaluated explicitly by solving a series of generalized eigenvalue problems involving the generators of the cone. The local maximal angles are identified by using a necessary condition for local maximality. The expected numbers of critical angles in random polyhedral convex cones are estimated experimentally.     

Note: An algorithm to solve polyhedral convex set optimization problems

We provide a counterexample to the remark in Löhne and Schrage [An algorithm to solve polyhedral convex set optimization problems, Optimization 62 (2013), pp. 131-141] that every solution of a polyhedral convex set optimization problem is a pre-solution. A correct statement is that every solution of a polyhedral convex set optimization problem obtained by the algorithm SetOpt is a pre-solution. We also show that every finite infimizer and hence every solution of a polyhedral convex set optimization problem contains a pre-solution.     

Iterative algorithm for minimizing a convex function at the intersection of a spherical surface and a convex compact set

A numerical algorithm for minimizing a convex function on the set-theoretic intersection of a spherical surface and a convex compact set is proposed. The idea behind the algorithm is to reduce the original minimization problem to a sequence of convex programming problems. Necessary extremum conditions are examined, and the convergence of the algorithm is analyzed.     

Tractability of convex vector optimization problems in the sense of polyhedral approximations

There are different solution concepts for convex vector optimization problems (CVOPs) and a recent one, which is motivated from a set optimization point of view, consists of finitely many efficient solutions that generate polyhedral inner and outer approximations to the Pareto frontier. A CVOP with compact feasible region is known to be bounded and there exists a solution of this sense to it. However, it is not known if it is possible to generate polyhedral inner and outer approximations to the Pareto frontier of a CVOP if the feasible region is not compact. This study shows that not all CVOPs are tractable in that sense and gives a characterization of tractable problems in terms of the well known weighted sum scalarization problems.     

An infinite class of convex tangent cones

Since the early 1970's, there have been many papers devoted to tangent cones and their applications to optimization. Much of the debate over which tangent cone is best has centered on the properties of Clarke's tangent cone and whether other cones have these properties. In this paper, it is shown that there are an infinite number of tangent cones with some of the nicest properties of Clarke's cone. These properties are convexity, multiple characterizations, and proximal normal formulas. The nature of these cones indicates that the two extremes of this family of cones, the cone of Clarke and the B-tangent cone or the cone of Michel and Penot, warrant further study. The relationship between these new cones and the differentiability of functions is also considered.     

A note on convex cones and constraint qualifications in infinite-dimensional vector spaces

In connection with mathematical programming in infinite-dimensional vector spaces, Zowe has studied the relationship between the Slater constraint qualification and a formally weaker qualification used by Kurcyusz. The attractive feature of the latter is that it involves only active constraints. Zowe has proved that, in barreled spaces, the two qualifications are equivalent and has asked whether the assumption of barreledness is superfluous. By studying cores and interiors of convex cones, we show that the two constraint qualifications are equivalent in a given topological vector spaceE iff every barrel inE is a neighborhood of the origin. Thus, whenE is locally convex, the two constraint qualifications are equivalent iffE is barreled. Other questions of Zowe are also answered.This research was supported in part by the Office of Naval Research, and in part by the Sonderforschungsbereich 21, Institut für Operations Research, Bonn, Federal Republic of Germany. The author is indebted to Professor J. Zowe for some helpful comments.     

On the intersection of contingent cones

In this paper, we give a new condition that ensures the equalityT _K (x) T _L (x)=T _{K L} (x) for convex closed setsK,L. This condition, which is given in terms of support functions of the setsK,L, generalizes, in a Hilbert space, the usual condition 0int(K–L).     

An active index algorithm for the nearest point problem in a polyhedral cone

We consider the problem of finding the nearest point in a polyhedral cone C={x∈R ⁿ :D x≤0} to a given point b∈R ⁿ , where D∈R ^m×n . This problem can be formulated as a convex quadratic programming problem with special structure. We study the structure of this problem and its relationship with the nearest point problem in a pos cone through the concept of polar cones. We then use this relationship to design an efficient algorithm for solving the problem, and carry out computational experiments to evaluate its effectiveness. Our computational results show that our proposed algorithm is more efficient than other existing algorithms for solving this problem.     

An algorithm for constrained convex optimization

This paper presents a feasible direction algorithm for the minimization of a pseudoconvex function over a smooth, compact, convex set. We establish that each cluster point of the generated sequence is an optimal solution of the problem without introducing anti-jamming procedures. Each iteration of the algorithm involves as subproblems only one line search for a zero of a continuously differentiable convex function and one univariate function minimization on a compact interval.     

An improved computational algorithm for finding the factorial

In the present paper, we consider a method for improving the computational algorithm for finding the factorials of integers; this method linearly accelerates the computations. We also present several algorithms effectively realizing this method and analyze their complexity.     

An algorithm for finding planar surfaces in three-manifolds

By a slope in the boundary ∂M of a 3-manifold, we mean the isotopy class α of a finite set of disjoint simple closed curves in ∂M that are nontrivial and pairwise nonparallel. In this paper, we construct an algorithm to decide whether or not a given orientable 3-manifold M contains an essential planar surface whose boundary has a given slope α. __________ Translated from Fundamentalnaya i Prikladnaya Matematika, Vol. 11, No. 4, pp. 197–202, 2005.     

An algorithm for finding the nucleolus of assignment games

Assignment games with side payments are models of certain two-sided markets. It is known that prices which competitively balance supply and demand correspond to elements in the core. The nucleolus, lying in the lexicographic center of the nonempty core, has the additional property that it satisfies each coalition as much as possible. The corresponding prices favor neither the sellers nor the buyers, hence provide some stability for the market. An algorithm is presented that determines the nucleolus of an assignment game. It generates a finite number of payoff vectors, monotone increasing on one side, and decreasing on the other. The decomposition of the payoff space and the lattice-type structure of the feasible set are utilized in associating a directed graph. Finding the next payoff is translated into determining the lengths of longest paths to the nodes, if the graph is acyclic, or otherwise, detecting the cycle(s). In an (m,n)-person assignment game withm = min(m,n) the nucleolus is found in at most 1/2·m(m + 3) steps, each one requiring at mostO(m·n) elementary operations.     

An optimal algorithm for finding all the jumps of a monotone step-function

The idea of binary search is generalized as follows. Given ?: {0, 1,…, N} → {0,…, K} such that $\text{?(0) = 0}$, $\text{?(N) = K}$, and $\text{?(i) ? ?(j)}$ for i < j, all the “jumps” of f, i.e., all is such that $\text{?(i) > ?(i ? 1)}$ together with the difference $\text{?(i) ? ?(i ? 1)}$ are recognized within f-evaluations. This is proved to be the exact bound in the non-trivial case when K ? N. An optimal strategy is as follows: The first query will be at i = 2^m, where $\text{m = [}\text{log}{}_2\text{(}\text{N}\text{K}\text{)]}$. An adversary will then respond either $\text{?(i) = 0}$ or $\text{?(i) - 1}$ as explained in the paper.