Directionally nondifferentiable metric projection

A closed convex set inR ² is constructed such that the associated metric projection onto that set is not everywhere directionally differentiable.     

An example of non-approximatively-compact existence set with finite-valued metric projection

An example indicated in the title is constructed in an arbitrary Banach lattice in which the order is defined by a countable symmetric Schauder basis with the symmetry constant 1 and which satisfies the additional condition of strict monotonicity of the norm with respect to the coordinates.     

On the size of the set of points where the metric projection exists

In this paper we answer in the negative a question due to J. P. R. Christensen about almost everywhere existence of nearest points using a decomposition of ℓ₂ due to J. Matoušek and E. Matoušková. We also formulate a similar question about almost everywhere existence of farthest points and answer it in the negative. The author was supported by the grant GAČR 201/00/0767 (from the Grant Agency of the Czech Republic).     

A monotone path-connected set with outer radially lower continuous metric projection is a strict sun

A monotone path-connected set is known to be a sun in a finite-dimensional Banach space. We show that a B-sun (a set whose intersection with each closed ball is a sun or empty) is a sun. We prove that in this event a B-sun with ORL-continuous (outer radially lower continuous) metric projection is a strict sun. This partially converses one well-known result of Brosowski and Deutsch. We also show that a B-solar LG-set (a global minimizer) is a B-connected strict sun.     

Spaces with a uniformly continuous metric projection

This paper contains a characterization of spaces in which the metric projection is uniformly continuous on the class of convex existence sets.     

On constructing games with a convex set of equilibrium strategies

Necessary and sufficient conditions on a convex setC (of strategy pairs) are given for the existence of a 2×n bimatrix game with equilibrium setC. This is done with the use of a geometric-combinatorial solution method for 2×n bimatrix games.

---

Zusammenfassung Es werden notwendige und hinreichende Bedingungen an die konvexe MengeC der Strategiepaare für die Existenz eines 2×n Bimatrix Spieles mit GleichgewichtsmengeC aufgegeben. Dies wird durch eine geometrisch-kombinatorische Lösungsmethode für 2×n Bimatrix Spiele erreicht.

     

On maximal convex lattice polygons inscribed in a plane convex set

Given a convex compact setK ? ?₂ what is the largestn such thatK contains a convex latticen-gon? We answer this question asymptotically. It turns out that the maximaln is related to the largest affine perimeter that a convex set contained inK can have. This, in turn, gives a new characterization ofK ₀, the convex set inK having maximal affine perimeter.     

On convex decompositions of a planar point set

Let P be a planar point set in general position. Neumann-Lara et al. showed that there is a convex decomposition of P with at most elements. In this paper, we improve this upper bound to .     

On matrices leaving invariant a nontrivial convex set

A real square matrix A leaves a nontrivial convex set invariant if there exists a convex set C, which is not a linear subspace, such that A(C) ? C. It is shown that this is equivalent to the statement that A has an eigenvalue λ with λ?0 or |λ|?1.     

On the symmetry function of a convex set

We attempt a broad exploration of properties and connections between the symmetry function of a convex set S ${S \subset\mathbb{R}^n}We attempt a broad exploration of properties and connections between the symmetry function of a convex set S and other arenas of convexity including convex functions, convex geometry, probability theory on convex sets, and computational complexity. Given a point , let sym(x,S) denote the symmetry value of x in S: , which essentially measures how symmetric S is about the point x, and define x ^* is called a symmetry point of S if x ^* achieves the above maximum. The set S is a symmetric set if sym (S)=1. There are many important properties of symmetric convex sets; herein we explore how these properties extend as a function of sym (S) and/or sym (x,S). By accounting for the role of the symmetry function, we reduce the dependence of many mathematical results on the strong assumption that S is symmetric, and we are able to capture and otherwise quantify many of the ways that the symmetry function influences properties of convex sets and functions. The results in this paper include functional properties of sym (x,S), relations with several convex geometry quantities such as volume, distance, and cross-ratio distance, as well as set approximation results, including a refinement of the L?wner-John rounding theorems, and applications of symmetry to probability theory on convex sets. We provide a characterization of symmetry points x ^* for general convex sets. Finally, in the polyhedral case, we show how to efficiently compute sym(S) and a symmetry point x ^* using linear programming. The paper also contains discussions of open questions as well as unproved conjectures regarding the symmetry function and its connection to other areas of convexity theory. Dedicated to Clovis Gonzaga on the occasion of his 60th birthday.     

On a metric for the class of compact convex sets

A distance function, defined in [12], for the class of compact convex sets inn-space is introduced in a new way, and some of its properties are developed. This concept is compared with some traditional distance functions for convex sets.     

Descent algorithm for a class of convex nondifferentiable functions

We present first an -descent basic method for minimizing a convex minmax problem. We consider first- and second-order information in order to generate the search direction. Preliminarily, we introduce some properties for the second-order information, the subhessian, and its characterization for max functions. The algorithm has -global convergence. Finally, we give a generalization of this algorithm for an unconstrained convex problem having second-order information. In this case, we obtain global -convergence.This research was supported in part by CAPES (Coordinação de Aperfeiçoamento de Pessoal de Nivel Superior) and in part by the IM-COPPE/UFRJ, Brazil. The authors wish to thank Nguyen Van Hien and Jean-Jacques Strodiot for their constructive remarks on an earlier draft of the paper. This work was completed while the first author was with the Department of Mathematics of the Facultés Universitaires de Namur. The authors are also grateful for the helpful comments of two anonymous referees.     

A numerical method of nondifferentiable convex optimization with constraints

An iterative process is examined for minimizing a convex nondifferentiable functional on a convex closed set in a real Hilbert space. Convergence of the proposed process is proved. A two-sided bound on the optimal functional value is given.Translated from Vychislitel'naya i Prikladnaya Matematika, No. 57, pp. 124–131, 1985.     

Variable metric methods for minimizing a class of nondifferentiable functions

We develop a class of methods for minimizing a nondifferentiable function which is the maximum of a finite number of smooth functions. The methods proceed by solving iteratively quadratic programming problems to generate search directions. For efficiency the matrices in the quadratic programming problems are suggested to be updated in a variable metric way. By doing so, the methods possess many attractive features of variable metric methods and can be viewed as their natural extension to the nondifferentiable case. To avoid the difficulties of an exact line search, a practical stepsize procedure is also introduced. Under mild assumptions the resulting method converge globally.Research supported by National Science Foundation under grant number ENG 7903881.     

Variable metric gradient projection processes in convex feasible sets defined by nonlinear inequalities

A capture-convergence rate theorem is proved for variable metric gradient projection processes near nonsingular local minimizers in convex feasible sets defined by nonlinear inequalities in a real Hilbert spaceX. The minimizers in question satisfy standard Kuhn-Tucker second-order sufficient conditions for local optimality.Investigation partially supported by National Science Foundation Research Grant No. DMS-85-03746.     

Duality theorem of nondifferentiable convex multiobjective programming

Necessary and sufficient conditions of Fritz John type for Pareto optimality of multiobjective programming problems are derived. This article suggests to establish a Wolfe-type duality theorem for nonlinear, nondifferentiable, convex multiobjective minimization problems. The vector Lagrangian and the generalized saddle point for Pareto optimality are studied. Some previously known results are shown to be special cases of the results described in this paper.This research was partly supported by the National Science Council, Taipei, ROC.The authors would like to thank the two referees for their valuable suggestions on the original draft.