Difference of two sets and estimation of clarke generalized Jacobian via quasidifferential

The notion of difference for two convex compact sets inR ⁿ , proposed by Rubinovet al, is generalized toR ^m×n . A formula of the difference for the two sets, which are convex hulls of a finite number of points, is developed. In the light of this difference, the relation between Clarke generalized Jacobian and quasidifferential, in the sense of Demyanov and Rubinov, for a nonsnooth function, is established. Based on the relation, the method of estimating Clarke generalized Jacobian via quasidifferential for a certain class of functions, is presented.     

Derivatives with respect to metrics and applications: subgradient marching algorithm

This paper introduces a subgradient descent algorithm to compute a Riemannian metric that minimizes an energy involving geodesic distances. The heart of the method is the Subgradient Marching Algorithm to compute the derivative of the geodesic distance with respect to the metric. The geodesic distance being a concave function of the metric, this algorithm computes an element of the subgradient in O(N ² log(N)) operations on a discrete grid of N points. It performs a front propagation that computes a subgradient of a discrete geodesic distance. We show applications to landscape modeling and to traffic congestion. Both applications require the maximization of geodesic distances under convex constraints, and are solved by subgradient descent computed with our Subgradient Marching. We also show application to the inversion of travel time tomography, where the recovered metric is the local minimum of a non-convex variational problem involving geodesic distances.     

Second order necessary and sufficient conditions for convex composite NDO

In convex composite NDO one studies the problem of minimizing functions of the formF:=h ○f whereh:ℝ ^m → ℝ is a finite valued convex function andf:ℝ ⁿ → ℝ ^m is continuously differentiable. This problem model has a wide range of application in mathematical programming since many important problem classes can be cast within its framework, e.g. convex inclusions, minimax problems, and penalty methods for constrained optimization. In the present work we extend the second order theory developed by A.D. Ioffe in [11, 12, 13] for the case in whichh is sublinear, to arbitrary finite valued convex functionsh. Moreover, a discussion of the second order regularity conditions is given that illuminates their essentially geometric nature.     

A characterization ofC 1-convex sets in Sobolev spaces

In this paper we prove that, ifK is a closed subset ofW ₀ ^1,p (Ω,R ^m ) with 1<p<+∞ andm≥1, thenK is stable under convex combinations withC ¹ coefficients if and only if there exists a closed and convex valued multifunction from Ω toR ^m such that The casem=1 has already been studied by using truncation arguments which rely on the order structure ofR (see [2]). In the casem>1 a different approach is needed, and new techniques involving suitable Lipschitz projections onto convex sets are developed. Our results are used to prove the stability, with respect to the convergence in the sense of Mosco, of the class of convex sets of the form (*); this property may be useful in the study of the limit behaviour of a sequence of variational problems of obstacle type. This article was processed by the author using the Springer-Verlag TEX mamath macro package 1990     

Behavior of Solutions to the Dirichlet Problem for Elliptic Systems in Convex Domains

We consider the Dirichlet problem for strongly elliptic systems of order 2m in convex domains. Under a positivity assumption on the Poisson kernel it is proved that the weak solution has bounded derivatives up to order m provided the outward unit normal has no big jumps on the boundary. In the case of second order symmetric systems in plane convex domains the boundedness of the first derivatives is proved without the assumption on the normal.     

Riemannian convexity of functionals

This paper extends the Riemannian convexity concept to action functionals defined by multiple integrals associated to Lagrangian differential forms on first order jet bundles. The main results of this paper are based on the geodesic deformations theory and their impact on functionals in Riemannian setting. They include the basic properties of Riemannian convex functionals, the Riemannian convexity of functionals associated to differential m-forms or to Lagrangians of class C ¹ respectively C ², the generalization to invexity and geometric meaningful convex functionals. Riemannian convexity of functionals is the central ingredient for global optimization. We illustrate the novel features of this theory, as well as its versatility, by introducing new definitions, theorems and algorithms that bear upon the currently active subject of functionals in variational calculus and optimal control. In fact so deep rooted is the convexity notion that nonconvex problems are tackled by devising appropriate convex approximations.     

On convex optimization without convex representation

We consider the convex optimization problem P:min_x {f(x) : x ? K}{{\rm {\bf P}}:{\rm min}_{\rm {\bf x}} \{f({\rm {\bf x}})\,:\,{\rm {\bf x}}\in{\rm {\bf K}}\}} where f is convex continuously differentiable, and K ì \mathbb Rⁿ{{\rm {\bf K}}\subset{\mathbb R}^n} is a compact convex set with representation {x ? \mathbb Rⁿ : g_j(x) 3 0, j = 1,?,m}{\{{\rm {\bf x}}\in{\mathbb R}^n\,:\,g_j({\rm {\bf x}})\geq0, j = 1,\ldots,m\}} for some continuously differentiable functions (g _j ). We discuss the case where the g _j ’s are not all concave (in contrast with convex programming where they all are). In particular, even if the g _j are not concave, we consider the log-barrier function f_m{\phi_\mu} with parameter μ, associated with P, usually defined for concave functions (g _j ). We then show that any limit point of any sequence (x_m) ì K{({\rm {\bf x}}_\mu)\subset{\rm {\bf K}}} of stationary points of f_m, m? 0{\phi_\mu, \mu \to 0} , is a Karush–Kuhn–Tucker point of problem P and a global minimizer of f on K.     

The characterization of totally geodesic submanifolds ofS m andCP m

We prove a theorem on ruled surfaces that generalizes a theorem of Ferus on totally geodesic foliations. On the basis of this theorem we obtain criteria for totally geodesic submanifolds ofS ^m andCP ^m that generalize and complement certain results of Borisenko, Ferus, and Abe. We give an application to the geodesic differential forms defined by Dombrowski in the case of submanifolds ofS ^m andCP ^m.Translated from Ukrainskií Geometricheskií Sbornik, Issue 28, 1985, pp. 106–116.The author is grateful to V. A. Toponogov for posing this problem and for attention to the work and to A. A. Borisenko for helpful criticisms.     

A projection method for the uncapacitated facility location problem

Several algorithms already exist for solving the uncapacitated facility location problem. The most efficient are based upon the solution of the strong linear programming relaxation. The dual of this relaxation has a condensed form which consists of minimizing a certain piecewise linear convex function. This paper presents a new method for solving the uncapacitated facility location problem based upon the exact solution of the condensed dual via orthogonal projections. The amount of work per iteration is of the same order as that of a simplex iteration for a linear program inm variables and constraints, wherem is the number of clients. For comparison, the underlying linear programming dual hasmn + m + n variables andmn +n constraints, wheren is the number of potential locations for the facilities. The method is flexible as it can handle side constraints. In particular, when there is a duality gap, the linear programming formulation can be strengthened by adding cuts. Numerical results for some classical test problems are included.     

An isoperimetric problem for tetrahedra

It is proved that a regular tetrahedron has the maximal possible surface area among all tetrahedra having surface with unit geodesic diameter. An independent proof of O’Rourke-Schevon’s theorem about polar points on a convex polyhedron is given. A. D. Aleksandrov’s general problem on the area of a convex surface with fixed geodesic diameter is discussed. Bibliography: 4 titles. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 329, 2005, pp. 28–55.     

Second Order Nonlinear Evolution Inclusions Ⅱ： Structure of the Solution Set

We contimle the work initiated in [1] （Second order nonlinear evolution inclusions I： Existence and relaxation results. Acta Mathematics Science, English Series, 21（5）, 977-996 （2005）） and study the structural properties of the solution set of second order evolution inclusions which are defined in the analytic framework of the evolution triple. For the convex problem we show that the solution set is compact Rs, while for the nonconvex problem we show that it is path connected, Also we show that the solution set is closed only if the multivalued nonlinearity is convex valued. Finally we illustrate the results by considering a nonlinear hyperbolic problem with discontinuities.     

Hyperbolic Volume of Manifolds with Geodesic Boundary and Orthospectra

In this paper we describe a function F _n : R ₊ → R ₊ such that for any hyperbolic n-manifold M with totally geodesic boundary ${\partial M \neq \emptyset}In this paper we describe a function F _n : R ₊ → R ₊ such that for any hyperbolic n-manifold M with totally geodesic boundary ?M 1 ?{\partial M \neq \emptyset} , the volume of M is equal to the sum of the values of F _n on the orthospectrum of M. We derive an integral formula for F _n in terms of elementary functions. We use this to give a lower bound for the volume of a hyperbolic n-manifold with totally geodesic boundary in terms of the area of the boundary.     

Stochastic Ordering of Multivariate Normal Distributions

We show an interesting identity for Ef(Y) – Ef(X), where X, Yare normally distributed random vectors and f is a function fulfilling some weak regularity condition. This identity will be used for a unified derivation of sufficient conditions for stochastic ordering results of multivariate normal distributions, some well known ones as well as some new ones. Moreover, we will show that many of these conditions are also necessary. As examples we will consider the usual stochastic order, convex order, upper orthant order, supermodular order and directionally convex order.     

Duality for optimization and best approximation over finite intersections

Recently Deutsch, Li and Swetits [2] have studied, in Hilbert space, a dual problem (Q_m ) to the primal problem (P) of minimization of a special class of convex functions f over the intersection of m closed convex sets, where m is finite. In the first part of this paper we obtain, in a locally convex space, some results on problem (Q_m ) and on its relations with the usual Lagrangian dual problem (Q) to (P) (studied in [9]), in the case when (P) has a solution. In the second part we give some applications to duality for the distance to the intersection of m closed convex sets in a normed linear space, in the case when a nearest point exists. Most of our results seem to be new even in the particular cases studied in [9] (the case m = 1), [l] (duality formulas for the distance to the intersection of m closed half-spaces in a normed linear space) and [2].     

Minimization of convex functions on the convex hull of a point set

A basic algorithm for the minimization of a differentiable convex function (in particular, a strictly convex quadratic function) defined on the convex hull of m points in R ⁿ is outlined. Each iteration of the algorithm is implemented in barycentric coordinates, the number of which is equal to m. The method is based on a new procedure for finding the projection of the gradient of the objective function onto a simplicial cone in R ^m , which is the tangent cone at the current point to the simplex defined by the usual constraints on barycentric coordinates. It is shown that this projection can be computed in O(m log m) operations. For strictly convex quadratic functions, the basic method can be refined to a noniterative method terminating with the optimal solution.     

Geodesic convexity in nonlinear optimization

The properties of geodesic convex functions defined on a connected RiemannianC ² k-manifold are investigated in order to extend some results of convex optimization problems to nonlinear ones, whose feasible region is given by equalities and by inequalities and is a subset of a nonlinear space.This research was supported in part by the Hungarian National Research Foundation, Grant No. OTKA-1044.     

Weak and Strong Convergence Theorems for Maximal Monotone Operators in a Banach Space

In this paper, we introduce an iterative sequence for finding a solution of a maximal monotone operator in a uniformly convex Banach space. Then we first prove a strong convergence theorem, using the notion of generalized projection. Assuming that the duality mapping is weakly sequentially continuous, we next prove a weak convergence theorem, which extends the previous results of Rockafellar [SIAM J. Control Optim. 14 (1976), 877–898] and Kamimura and Takahashi [J. Approx. Theory 106 (2000), 226–240]. Finally, we apply our convergence theorem to the convex minimization problem and the variational inequality problem.     

Primal Central Paths and Riemannian Distances for Convex Sets

In this paper, we study the Riemannian length of the primal central path in a convex set computed with respect to the local metric defined by a self-concordant function. Despite some negative examples, in many important situations, the length of this path is quite close to the length of a geodesic curve. We show that in the case of a bounded convex set endowed with a ν-self-concordant barrier, the length of the central path is within a factor O(ν ^1/4) of the length of the shortest geodesic curve. This paper presents research results of the Belgian Program on Interuniversity Poles of Attraction initiated by the Belgian State, Prime Minister’s Office, Science Policy Programming.     

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.     

On the volume of convex hulls of sets on spheres

We prove that for a measurable subset of S ^n–1 with fixed Haar measure, the volume of its convex hull is minimized for a cap (i.e. a ball with respect to the geodesic measure). We solve a similar problem for symmetric sets and n=2, 3. As a consequence, we deduce a result concerning Gaussian measures of dilatations of convex, symmetric sets in R ² and R ³.Partially supported by KBN (Poland), Grant No. 2 1094 91 01.