In this talk, we show that semidefinite programming (SDP) can be effectively used in addressing the universal rigidity problem. In particular, we use the notion of SDP non-degeneracy to obtain a sufficient condition for universal rigidity, and to re-derive the known sufficient condition for generic universal rigidity. We present new results concerning positive semidefinite stress matrices and we use a semidefinite version of Farkas's lemma to characterize bar frameworks that admit a nonzero positive semidefinite stress matrix.
Modern non-smooth analysis is now roughly thirty-five years old. In this talk and the associated paper I shall attempt to analyse (briefly): where the subject stands today, where it should be going, and what it will take to get there? Summary: the first order theory is rather impressive, as are some applications. The second order theory is by comparison somewhat underdeveloped and wanting.
See http://carma.newcastle.edu.au/~jb616/vasurvey.pdf for further reference.
Hit and Run algorithms, most notably the Hypersphere Directions or HD algorithm and the Coordinate Directions or CD algorithm, originated thirty years ago with the work of Boneh, Smith and Telgen. Since then numerous papers have been written that have either generalized the algorithms, provided theoretical analysis, or adapted the methodology to new situations.
In this paper we present a new generalization for direction choice for both the CD and HD algorithm. We show that this variant keeps all the positive aspects of the algorithms and adds new ones, such as the ability to work with linear equality constraints. We use our generalization with the set covering paradigm introduced by Boneh for constraint analysis and we present new ideas to help determine the number of iterations that should be completed by these probabilistic methods. We demonstrate our advancements with the analysis of systems of linear constraints having both equalities and inequalities.
Hybrid dynamical systems are systems that combine features of continuous-time dynamical systems and discrete-time dynamical systems, and can be modeled by a combination of differential equations or inclusions, difference equations or inclusions, and constraints.
The talk presents techniques for approximating hybrid dynamical systems that generalize classical linearization techniques. The approximation techniques involve linearizations, tangent cones, homogeneous approximations of functions and set-valued mappings, and tangent homogeneous cones, where homogeneity is considered with respect to general dilations. Main results deduce asymptotic stability of an equilibrium for a hybrid dynamical system from pre-asymptotic stability of the equilibrium for an approximate system.
The results come from joint work with Andy Teel.
Recently, researchers have examine the question of how to smoothly transform one function into another. This is, given functions f0 and f1, how can we build a "well-behaved" parameterized function F(x,p) such that F(x,0) = f0(x) and F(x,1) = f1(x)? For convex functions the idea of a "proximal average" has been shown to be highly effective. We explore the proximal average, provide some previous results regarding convex functions, and develop a method to extend these results to non-convex functions. In doing so we develop a new version of the proximal average, which is more complicated but provides stronger stability results.
We present criteria for convexity of closed sets in Banach spaces in terms of Clarke and Bouligand tangent cones. In the case of uniformly convex Banach spaces we also state such criteria in terms of proximal normal cones.
The main result is:
For closed subsets S of Banach space X the following relations are equivalent:
(a) S is convex;
(b) S Ì x + TSC(x) for any x Î S;
(c) S Ì x + TSB(x) for any x Î S. In the case of uniformly convex Banach space X, the previous relations are also equivalent to the next one;
(d) S Ì x + (NSP)* (x) for any x Î S.
As an example of application of criteria for convexity we derive sufficient conditions for convexity of images F(Cg) of a set
This is a joint work with Francis Clarke of Institut Camille Jardine, Université Claude Bernard, Lyon, France.
Computational Convex Analysis algorithms have been rediscovered several times in the past by researchers from different fields. To further communications between practitioners, we review the field of Computational Convex Analysis, which focuses on the numerical computation of fundamental transforms arising from convex analysis. Current models use symbolic, numeric, and hybrid symbolic-numeric algorithms. Our objective is to disseminate widely the most efficient numerical algorithms useful for applications in image processing (computing the distance transform, the generalized distance transform, and mathematical morphology operators), partial differential equations (solving Hamilton-Jacobi equations, and using differential equations numerical schemes to compute the convex envelope), max-plus algebra (computing the equivalent of the Fast Fourier Transform), multi-fractal analysis, etc. The fields of applications include, among others, computer vision, robot navigation, thermodynamics, electrical networks, medical imaging, and network communication.
The talk concerns the study of variational systems described by parameterized generalized equations/variational conditions important for many aspects of nonlinear analysis, optimization, and their applications. Focusing on the fundamental properties of metric regularity and Lipschitzian stability, we establish various qualitative and quantitative relationships between these properties for multivalued parts/fields of parametric generalized equations and the corresponding solution maps for them in the framework of arbitrary Banach spaces of decision and parameter variables.
Based on joint work with Francisco Aragon Artacho.
Lift-and-project operators provide an automatic way for constructing all facets of the convex hull of 0,1 vectors in a polytope given by linear or polynomial inequalities. They also yield tractable approximations provided that the input polytope is tractable and that we only apply the operators O(1) times. There are many generalizations of these operators which can be used to generate arbitrarily tight, convex relaxations of essentially arbitrary nonconvex sets.
I will show how to utilize some fundamental theorems in convex optimization to provide convergence theories for convex relaxation hierarchies and show how to use these techniques to prove sum-of-squares type representation theorems for polynomials that are nonnegative over some compact set.
Normal compactness is an important property for the calculus of generalized differentiation in infinite-dimensional variational analysis, especially for the limiting constructions including Mordukhovich subdifferentials, coderivatives, and normal cones. It closely relates to the Lipschitz properties of mappings/functions. In this talk, we will explore the evolution of this concept in modern variational analysis, as well as its recent development including different kinds of extensions. Calculus rules and applications of the extensions will also be discussed.
Monotone operators play fundamental roles in optimization. In 1970, Asplund studied irreducible decompositions of a monotone mapping as the sum of a subdifferential mapping and an "irreducible" monotone mapping. In 2007, Browein and Wiersma introduced skew decompositions of a monotone mapping as the sum of a subdifferential mapping and a "skew" monotone mapping. These decompositions provide intrinsic insights to monotone operators, and they are variants of the well-known decomposition of a matrix into its symmetric and antisymmetric parts. In this talk, we consider the Borwein-Wiersma decomposition of a maximal monotone linear relation (e.g. its graph is linear). We give sufficient conditions and characterizations for a maximal monotone linear relation to be Borwein-Wiersma decomposable. Explicit Borwein-Wiersma decompositions of maximal monotone linear linear relations in Hilbert spaces are given.
This is a joint work with Heinz Bauschke and Liangjin Yao.
The elegant results for strong duality and strict complementarity for LP can fail for cone programming over nonpolyhedral cones. We take a fresh look at known and new results for duality, optimality, constraint qualifications, and strict complementarity. These results include:
In his 1975-1976 pioneering work, Clarke introduced based on Rademacher's theorem the generalized Jacobian, ¶c f(p), of a Lipschitz f : D ® Y : = Rn, where D Í X and X is of finite dimension. If f is real-valued, he showed that
Recently an extension of Clarke's Jacobian to the case when X is any normed space, and Y is of finite dimension was obtained by the author jointly with Zs. Páles. The difficulty caused by the infinite dimensionality of X is handled by introducing an L-Jacobian ¶L f defined on finite dimensional spaces L Í X so that Rademacher's theorem remains applicable. The fundamental results for deriving many of the properties of ¶f(p) and its calculus are
The extension of Clarke's Jacobian as a subset of L(X,Y) to the case where X and Y are of infinite dimension, is an open question. First we show that it is not in general possible to obtain a Jacobian extending Clarke's and living in L(X,Y). Thus, to stay in this latter set extra assumption must be imposed on the space Y.
In this talk an answer is provided to this question by tackling two extra difficulties that manifest in this setting. The first is the differentiability issue related to the Rademacher theorem in infinite dimension. This issue will be handled by assuming the image space Y to satisfy the Radon-Nikodým property. This implies that the restriction of a Lipschitz function f : D® Y to a finite dimensional domain is almost everywhere differentiable. The second difficulty is pertaining finding a topology in the space of linear operators L(X,Y), where the generalized Jacobian lives, so that bounded sequences would have cluster points in this topology. To overcome this difficulty, we also assume that the image space Y is a dual of a normed space. In this setting all the properties expected from a derivative-like set will be obtained for the generalized Jacobian ¶f(p).
This paper is concerned with the optimality of a trend-following trading rule. The idea is to catch a bull market at its early stage, ride the trend, and liquidate the position at the first evidence of the subsequent bear market. We characterize the bull and bear phases of the markets mathematically using the conditional probabilities of the bull market given the up-to-date stock prices. A dynamic programming approach is used to analyze the problem. The optimal buying and selling times are given in terms of a sequence of stopping times determined by two threshold curves. Numerical experiments are conducted to validate the theoretical results and demonstrate how they perform in a marketplace. How to handle nonsmooth optimal value functions is an interesting challenge to variational analysts.
This is a joint work with D. Min (National University of Singapore, Singapore) and Q. Zhang (The University of Georgia, Athens, Georgia, USA).