The L p -curvature images of convex bodies and L p -projection bodies

Associated with the L _p -curvature image defined by Lutwak, some inequalities for extended mixed p-affine surface areas of convex bodies and the support functions of L _p -projection bodies are established. As a natural extension of a result due to Lutwak, an L _p -type affine isoperimetric inequality, whose special cases are L _p -Busemann-Petty centroid inequality and L _p -affine projection inequality, respectively, is established. Some L _p -mixed volume inequalities involving L _p -projection bodies are also established.     

Fitting hyperplanes by minimizing orthogonal deviations

Hyperplanes withm + 1 parameters are fitted by minimizing the sum of weighted orthogonal deviations to a set ofN points. There is no inverse regression incompatibility. For unweighted orthogonall ₁-fits essentially the same number of points are on either side of an optimal hyperplane. The criterion function is neither convex, nor concave, nor even differentiable. The main result is that each orthogonall _p -fit interpolates at leastm + 1 points, for 0 <p 1. This enables the combinatorial strategy of systematically trying all possible hyperplanes which interpolatem + 1 data points.     

Geometric dual formulation for first-derivative-based univariate cubic <Emphasis Type="Italic">L</Emphasis><Subscript>1</Subscript> splines

With the objective of generating “shape-preserving” smooth interpolating curves that represent data with abrupt changes in magnitude and/or knot spacing, we study a class of first-derivative-based -smooth univariate cubic L ₁ splines. An L ₁ spline minimizes the L ₁ norm of the difference between the first-order derivative of the spline and the local divided difference of the data. Calculating the coefficients of an L ₁ spline is a nonsmooth non-linear convex program. Via Fenchel’s conjugate transformation, the geometric dual program is a smooth convex program with a linear objective function and convex cubic constraints. The dual-to-primal transformation is accomplished by solving a linear program.     

Kolmogorov Entropy for Classes of Convex Functions

Kolmogorov ε-entropy of a compact set in a metric space measures its metric massivity and thus replaces its dimension which is usually infinite. The notion quantifies the compactness property of sets in metric spaces, and it is widely applied in pure and applied mathematics. The ε-entropy of a compact set is the most economic quantity of information that permits a recovery of elements of this set with accuracy ε. In the present article we study the problem of asymptotic behavior of the ε-entropy for uniformly bounded classes of convex functions in L _p -metric proposed by A.I.   Shnirelman. The asymptotic of the Kolmogorov ε-entropy for the compact metric space of convex and uniformly bounded functions equipped with L _p -metric is ε ^−1/2, ε→0₊.      

S-convexity revisited (fuzzy): long version

In this revisional article, we criticize (strongly) the use made by Medar et al., and those whose work they base themselves on, of the name ‘convexity’ in definitions which intend to relate to convex functions, or cones, or sets, but actually seem to be incompatible with the most basic consequences of having the name ‘convexity’ associated to them. We then believe to have fixed the ‘denominations’ associated with Medar’s (et al.) work, up to a point of having it all matching the existing literature in the field [which precedes their work (by long)]. We also expand his work scope by introducing s ₁-convexity concepts to his group of definitions, which encompasses only convex and its proper extension, s ₂-convex, so far. This article is a long version of our previous review of Medar’s work, published by FJMS (Pinheiro, M.R.: S-convexity revisited. FJMS, 26/3, 2007).     

<Emphasis Type="Italic">L</Emphasis><Subscript><Emphasis Type="Italic">p</Emphasis></Subscript> discrepancy of generalized two-dimensional Hammersley point sets

We determine the L _p discrepancy of the two-dimensional Hammersley point set in base b. These formulas show that the L _p discrepancy of the Hammersley point set is not of best possible order with respect to the general (best possible) lower bound on L _p discrepancies due to Roth and Schmidt. To overcome this disadvantage we introduce permutations in the construction of the Hammersley point set and show that there always exist permutations such that the L _p discrepancy of the generalized Hammersley point set is of best possible order. For the L ₂ discrepancy such permutations are given explicitly. F.P. is supported by the Austrian Science Foundation (FWF), Project S9609, that is part of the Austrian National Research Network “Analytic Combinatorics and Probabilistic Number Theory”.     

Characterisations of Chebyshev sets in c0

A subset MX of a normed linear space X is a Chebyshev set if, for every xX, the set of all nearest points from M to x is a singleton. We obtain a geometrical characterisation of approximatively compact Chebyshev sets in c₀. Also, given an approximatively compact Chebyshev set M in c₀ and a coordinate affine subspace Hc₀ of finite codimension, if M∩H≠, then M∩H is a Chebyshev set in H, where the norm on H is induced from c₀.     

Point sets with low <Emphasis Type="Italic">L</Emphasis><Subscript><Emphasis Type="Italic">p</Emphasis></Subscript>-discrepancy

In this paper we study the L _p -discrepancy of digitally shifted Hammersley point sets. While it is known that the (unshifted) Hammersley point set (which is also known as Roth net) with N points has L _p -discrepancy (p an integer) of order (log N)/N, we show that there always exists a shift such that the digitally shifted Hammersley point set has L _p -discrepancy (p an even integer) of order which is best possible by a result of W. Schmidt. Further we concentrate on the case p = 2. We give very tight lower and upper bounds for the L ₂-discrepancy of digitally shifted Hammersley point sets which show that the value of the L ₂-discrepancy of such a point set mostly depends on the number of zero coordinates of the shift and not so much on the position of these. This work is supported by the Austrian Research Fund (FWF), Project P17022-N12 and Project S8305.     

Block-Coordinate Gradient Descent Method for?Linearly Constrained Nonsmooth Separable Optimization

We consider the problem of minimizing the weighted sum of a smooth function f and a convex function P of n real variables subject to m linear equality constraints. We propose a block-coordinate gradient descent method for solving this problem, with the coordinate block chosen by a Gauss-Southwell-q rule based on sufficient predicted descent. We establish global convergence to first-order stationarity for this method and, under a local error bound assumption, linear rate of convergence. If f is convex with Lipschitz continuous gradient, then the method terminates in O(n ²/ε) iterations with an ε-optimal solution. If P is separable, then the Gauss-Southwell-q rule is implementable in O(n) operations when m=1 and in O(n ²) operations when m>1. In the special case of support vector machines training, for which f is convex quadratic, P is separable, and m=1, this complexity bound is comparable to the best known bound for decomposition methods. If f is convex, then, by gradually reducing the weight on P to zero, the method can be adapted to solve the bilevel problem of minimizing P over the set of minima of f+δ _X , where X denotes the closure of the feasible set. This has application in the least 1-norm solution of maximum-likelihood estimation. This research was supported by the National Science Foundation, Grant No. DMS-0511283.     

Transfer Function Optimization Procedure for the H 2/H ∞ Problem

In this paper, the H ₂/H problem is considered in a transfer-function setting, i.e., without a priori chosen bounds on the controller order. An optimization procedure is described which is based on a parametrization of all feasible descending directions stemming from a given point of the feasible transfer-function set. A search direction at each such point can be obtained on the basis of the solution of a convex finite-dimensional problem which can be converted into a LMI problem. Moving along the chosen direction in each step, the procedure in question generates a sequence of feasible points whose cost functional values converge to the optimal value of the H ₂/H problem. Moreover, this sequence of feasible points is shown to converge in the sense of a weighted H ₂ norm; and it does so to the solution of the H ₂/H problem whenever such a solution exists.     

A bott periodicity map for crossed products of C*-algebras by discrete groups

A generalization is given of the canonical map from a discrete group into K ₁ of the group C ^*-algebra. Our map also generalizes Rieffel's construction of a projection in an irrational rotation C ^*-algebra.     

Embedding into l ∞2 Is Easy, Embedding into l ∞3 Is?NP-Complete

We give a new algorithm for enumerating all possible embeddings of a metric space (i.e., the distances between every pair within a set of n points) into ℝ² Cartesian space preserving their l _∞ (or l ₁) metric distances. Its expected time is (i.e., within a poly-log of the size of the input) beating the previous algorithm. In contrast, we prove that detecting l _∞³ embeddings is NP-complete. The problem is also NP-complete within l ₁² or l _∞² with the added constraint that the locations of two of the points are given or alternatively that the two dimensions are curved into a three-dimensional sphere. We also refute a compaction theorem by giving a metric space that cannot be embedded in l _∞³; however, it can be embedded if any single point is removed. This research is partially supported by NSERC grants. I would like to thank Steven Watson for his extensive help on this paper.     

The Minimality Properties of Chebyshev Polynomials and Their Lacunary Series

By considering four kinds of Chebyshev polynomials, an extended set of (real) results are given for Chebyshev polynomial minimality in suitably weighted Hölder norms on [–1,1], as well as (L ) minimax properties, and best L ₁ sufficiency requirements based on Chebyshev interpolation. Finally we establish best L _p , L and L ₁ approximation by partial sums of lacunary Chebyshev series of the form _i=0 a ⁱ _b ⁱ(x) where _n (x) is a Chebyshev polynomial and b is an odd integer 3. A complete set of proofs is provided.     

LMI Approach to Robust Delay-Dependent Mixed H 2/H ∞ Controller of Uncertain Neutral Systems with Discrete and Distributed Time-Varying Delays

The design of a robust mixed H ₂/H _∞ controller for a class of uncertain neutral systems with discrete, distributed, and input time-varying delays is considered. More precisely, the proposed robust mixed H ₂/H _∞ controller minimizes an upper bound of the H ₂ performance measure, while guaranteeing an H _∞ norm bound constraint. Based on the Lyapunov-Krasovskii functional theory, a delay-dependent criterion is derived for the existence of a desired mixed H ₂/H _∞ controller, which can be constructed easily via feasible linear matrix inequalities (LMIs). Furthermore, a convex optimization problem satisfying some LMI constraints is formulated to obtain a suboptimal robust mixed H ₂/H _∞ controller achieving the minimization of an upper bound of the closed-loop H ₂ performance measure. Finally, a numerical example is illustrated to show the usefulness of the obtained design method.The research reported here was supported by the National Science Council of Taiwan, ROC under Grant NSC 94-2213-E-507-002.     

Weak Equality and Exact Sequences in H v -modules

The largest class of multivalued systems satisfying the module-like axioms is the H_v-module. H_v-modules first were introduced by Vougiouklis. In this paper we define weak equality between two subsets of an H_v-module and introduced the notion of exact sequences of H_v-modules. Also some results on the weak equality and exact sequences are given.     

On the Proper Homotopy Invariance of the Tucker Property

A non-compact polyhedron P is Tucker if, for any compact subset K begong to P, the fundamental group π1 （P - K） is finitely generated. The main result of this note is that a manifold which is proper homotopy equivalent to a Tucker polyhedron is Tucker. We use Poenaru＇s theory of the equivalence relations forced by the singularities of a non-degenerate simplicial map.     

Weak continuity of metric projections

A necessary and sufficient condition is found for weak continuity of a metric projection onto a finite-dimensional subspace inl _p (1<p≠2). A metric projection onto a boundedly compact set inl _p is sequentially weakly upper semicontinueus. An example is given on a convex, compact set inl ₂ onto which the metric projection is not weakly continuous. Translated from Matematicheskie Zametki, Vol. 22, No. 3, pp. 345–356, September, 1977.     

Supports and convex envelopes

The construct of anL ₁-Support is extended to the environment of a lower semicontinuous function over a solid, finite union of polytopes by utilizing the convex envelope of the function. The existence of and a characterization for theL ₁-Support of the convex envelope are established. The characterization is solely dependent upon the original function’s characteristics and thus the need to calculate the functional form of the convex envelope explicity is eliminated.     

Controller design to optimize a composite performance measure

This paper studies a mixed objective problem of minimizing a composite measure of thel ₁, ₂, andl -norms together with thel -norm of the step response of the closed loop. This performance index can be used to generate Pareto-optimal solutions with respect to the individual measures. The problem is analyzed for discrete-time, single-input single-output (SISO), linear time-invariant systems. It is shown via Lagrange duality theory that the problem can be reduced to a convex optimization problem with a priori known dimension. In addition, continuity of the unique optimal solution with respect to changes in the coefficients of the linear combination that defines the performance measure is estabilished.This research was supported by the National Science Foundation under Grants No. ECS-92-04309, ECS-92-16690 and ECS-93-08481.     

A geometric inequality on mixed volumes

We develop some geometric inequality for a kind of generalized convex set. The integral of (n – 2)-th mean curvature of the generalized convex set, the mixed volume of the convex hull of the set, and a reference convex set are involved in the inequality.Partially supported by grants from Kosef and BSRI-95-1419.