Estimating the diameter of the space of plane convex figures with respect to an affine-invariant metric

A convex figure K ⊂ ℝ² is a compact convex set with nonempty interior, and αK is a homothetic image of K with coefficient α ∈ ℝ. It is proved that for any two convex figures K₁, K₂ ⊂ ℝ² there is an affine transformation T of the plane such that K₁ ⊂ T(K₂) ⊂ 2.7K₁. Bibliography: 2 titles. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 329, 2005, pp. 58–66.     

Set containment characterization with strict and weak quasiconvex inequalities

Dual characterizations of the containment of a convex set, defined by infinite quasiconvex constraints, in an evenly convex set, and in a reverse convex set, defined by infinite quasiconvex constraints, are provided. Notions of quasiconjugate for quasiconvex functions, λ-quasiconjugate and λ-semiconjugate, play important roles to derive the characterizations of the set containments.     

The relation of time indexed formulations of single machine scheduling problems to the node packing problem

 The relation of time indexed formulations of nonpreemptive single machine scheduling problems to the node packing problem is established and then used to provide simple and intuitive alternate proofs of validity and maximality for previously known results on the facial structure of the scheduling problem. Previous work on the facial structure has focused on describing the convex hull of the set of feasible partial schedules, schedules in which not all jobs have to be started. The equivalence between the characteristic vectors of this set and those of the set of feasible node packings in a graph whose structure is determined by the parameters of the scheduling problem is established. The main contribution of this paper is to show that the facet inducing inequalities for the convex hull of the set of feasible partial schedules that have integral coefficients and right hand side 1 or 2 are the maximal clique inequalities and the maximally and sequentially lifted 5-hole inequalities of the convex hull of the set of feasible node packings in this graph respectively. Received: September 10, 2000 / Accepted: April 20, 2002 Published online: September 27, 2002 Key words. scheduling – node packing – polyhedral methods – facet defining graphs – lifted valid inequalities – facet inducing inequalities}     

An analytic center quadratic cut method for the convex quadratic feasibility problem

 We consider a quadratic cut method based on analytic centers for two cases of convex quadratic feasibility problems. In the first case, the convex set is defined by a finite yet large number, N, of convex quadratic inequalities. We extend quadratic cut algorithm of Luo and Sun [3] for solving such problems by placing or translating the quadratic cuts directly through the current approximate center. We show that, in terms of total number of addition and translation of cuts, our algorithm has the same polynomial worst case complexity as theirs [3]. However, the total number of steps, where steps consist of (damped) Newton steps, function evaluations and arithmetic operations, required to update from one approximate center to another is , where ε is the radius of the largest ball contained in the feasible set. In the second case, the convex set is defined by an infinite number of certain strongly convex quadratic inequalities. We adapt the same quadratic cut method for the first case to the second one. We show that in this case the quadratic cut algorithm is a fully polynomial approximation scheme. Furthermore, we show that, at each iteration, k, the total number steps (as described above) required to update from one approximate center to another is at most , with ε as defined above. Received: April 2000 / Accepted: June 2002 Published online: September 5, 2002 Key words. convex quadratic feasibility problem – interior-point methods – analytic center – quadratic cuts – potential function     

The limit shape of convex lattice polygons

It is proved here that, asn→∞, almost all convex (1/n)ℤ²-lattice polygons lying in the square [−1, 1]² are very close to a fixed convex set. This research was partially supported by Hungarian Science Foundation Grants 1907 and 1909.     

Convex programming with single separable constraint and bounded variables

In this paper a minimization problem with convex objective function subject to a separable convex inequality constraint “≤” and bounded variables (box constraints) is considered. We propose an iterative algorithm for solving this problem based on line search and convergence of this algorithm is proved. At each iteration, a separable convex programming problem with the same constraint set is solved using Karush-Kuhn-Tucker conditions. Convex minimization problems subject to linear equality/ linear inequality “≥” constraint and bounds on the variables are also considered. Numerical illustration is included in support of theory.     

Affine-inscribed and affine-circumscribed polygons and polytopes

Five theorems on polygons and polytopes inscribed in (or circumscribed about) a convex compact set in the plane or space are proved by topological methods. In particular, it is proved that for every interior point O of a convex compact set in ℝ³, there exists a two-dimensional section through O circumscribed about an affine image of a regular octagon. It is also proved that every compact convex set in ℝ³ (except the cases listed below) is circumscribed about an affine image of a cube-octahedron (the convex hull of the midpoints of the edges of a cube). Possible exceptions are provided by the bodies containing a parallelogram P and contained in a cylinder with directrix P. Bibliography: 29 titles. Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 231, 1995, pp. 286–298. Translated by B. M. Bekker.     

Empty convex polygons in almost convex sets

A finite set of points, in general position in the plane, is almost convex if every triple determines a triangle with at most one point in its interior. For every ℓ ≥ 3, we determine the maximum size of an almost convex set that does not contain the vertex set of an empty convex ℓ-gon. Partially supported by grants T043631 and NK67867 of the Hungarian NFSR (OTKA).     

Geometries in which the planes minimize area

Summary It is shown that for 1≤a≤n an open convex set in n-dimensional affine space can be provided with a complete a-dimensional area for which the a-flats minimize area, and that any such area can be extended to an area with the same propertiés in an open convex set in (n+1)—space. To Enrico Bompiani on his scientific Jubilee. This work was supported by a grant from the National Science Foundation.     

Extreme points for convex mappings ofB n

We exhibit a collection of extreme points of the family of normalized convex mappings of the open unit ball of ℂ ⁿ forn≥2. These extreme points are defined in terms of the extreme points of a closed ball in the Banach space of homogeneous polynomials of degree 2 in ℂ ⁿ⁻¹, which are fully classified. Two examples are given to show that there are more convex mappings than those contained in the closed convex hull of the set of extreme points here exhibited.     

Existence of optimal solutions and duality results under weak conditions

In this paper we consider an ordinary convex program with no qualification conditions (such as Slater’s condition) and for which the optimal set is neither required to be compact, nor to be equal to the sum of a compact set and a linear space. It is supposed only that the infimum α is finite. A very wide class of convex functions is exhibited for which the optimum is always attained and α is equal to the supremum of the ordinary dual program. Additional results concerning the existence of optimal solutions in the non convex case are also given. Received: February 1, 1999 / Accepted: December 15, 1999?Published online February 23, 2000     

Robust Stability and Stabilization of a Class of Nonlinear Switched Discrete-Time Systems with Time-Varying Delays

In this paper, we investigate the problems of robust delay-dependent ℒ₂ gain analysis and feedback control synthesis for a class of nominally-linear switched discrete-time systems with time-varying delays, bounded nonlinearities and real convex bounded parametric uncertainties in all system matrices under arbitrary switching sequences. We develop new criteria for such class of switched systems based on the constructive use of an appropriate switched Lyapunov-Krasovskii functional coupled with Finsler’s Lemma and a free-weighting parameter matrix. We establish an LMI characterization of delay-dependent conditions under which the nonlinear switched delay system is robustly asymptotically stable with an ℒ₂-gain smaller than a prescribed constant level. Switched feedback schemes, based on state measurements, output measurements or by using dynamic output feedback, are designed to guarantee that the corresponding switched closed-loop system enjoys the delay-dependent asymptotic stability with an ℒ₂ gain smaller than a prescribed constant level. All the developed results are expressed in terms of convex optimization over LMIs and tested on representative examples.     

Convex-compact sets and Banach discs

Every relatively convex-compact convex subset of a locally convex space is contained in a Banach disc. Moreover, an upper bound for the class of sets which are contained in a Banach disc is presented. If the topological dual E′ of a locally convex space E is the σ(E′,E)-closure of the union of countably many σ(E′,E)-relatively countably compacts sets, then every weakly (relatively) convex-compact set is weakly (relatively) compact.     

The Maximal Number of Geometric Permutations for n Disjoint Translates of a Convex Set in ℝ Is Ω(n)

A geometric permutation induced by a transversal line of a finite family of disjoint convex sets in ℝ^d is the order in which the transversal meets the members of the family. It is known that the maximal number of geometric permutations in families of n disjoint translates of a convex set in ℝ³ is 3. We prove that for d ≥ 3 the maximal number of geometric permutations for such families in ℝ^d is Ω(n).     

Involutorische Automorphismen ebener konvexer Mengen

 A bijection of the compact convex set with is called a reflection of K, if σ maps convex subsets of K into convex subsets. Conditions are stated unter which the existence of few reflections imply that is an ellipse. Received 4 March, 1998     

On the convexity of global solvability sets for controlled initial-boundary value problems

We consider a controlled functional-operator equation that is a convenient form for describing of controlled initial-boundary value problems. For this equation, considered in a Banach ideal space, we define the set Ω of global solvability as the set of all admissible controls for which the equation has a global solution. We show that Ω is convex under the conditions imposed on the right-hand side of the equation. For each control in a given segment in Ω, we obtain a two-sided pointwise estimate for the corresponding solution under the abovementioned assumptions. We prove the theorem on the convex continuous dependence of the solution on the parameter specifying the displacement along the segment.     

Separately continuous selectors

The existence of separately continuous selectors of a separately lower and upper semicontinuous many-valued multivariate map is proved, provided its domain is a compact set and its range is a convex closed subset of a metrizable convex compact set. Translated fromMatematicheskie Zametki, Vol. 63, No. 2, pp. 209–216, February, 1998. This research was partially supported by the Russian Foundation for Basic Research under grant No. 93-01-00264.     

Convex extensions and envelopes of lower semi-continuous functions

 We define a convex extension of a lower semi-continuous function to be a convex function that is identical to the given function over a pre-specified subset of its domain. Convex extensions are not necessarily constructible or unique. We identify conditions under which a convex extension can be constructed. When multiple convex extensions exist, we characterize the tightest convex extension in a well-defined sense. Using the notion of a generating set, we establish conditions under which the tightest convex extension is the convex envelope. Then, we employ convex extensions to develop a constructive technique for deriving convex envelopes of nonlinear functions. Finally, using the theory of convex extensions we characterize the precise gaps exhibited by various underestimators of $x/y$ over a rectangle and prove that the extensions theory provides convex relaxations that are much tighter than the relaxation provided by the classical outer-linearization of bilinear terms. Received: December 2000 / Accepted: May 2002 Published online: September 5, 2002 RID="*" ID="*" The research was funded in part by a Computational Science and Engineering Fellowship to M.T., and NSF CAREER award (DMI 95-02722) and NSF/Lucent Technologies Industrial Ecology Fellowship (NSF award BES 98-73586) to N.V.S. Key words. convex hulls and envelopes – multilinear functions – disjunctive programming – global optimization     

Convexes divisibles IV : Structure du bord en dimension 3

Divisible convex sets IV: Boundary structure in dimension 3 Let Ω be an indecomposable properly convex open subset of the real projective 3-space which is divisible i.e. for which there exists a torsion free discrete group Γ of projective transformations preserving Ω such that the quotient M := Γ\Ω is compact. We study the structure of M and of ∂Ω, when Ω is not strictly convex: The union of the properly embedded triangles in Ω projects in M onto an union of finitely many disjoint tori and Klein bottles which induces an atoroidal decomposition of M. Every non extremal point of ∂Ω is on an edge of a unique properly embedded triangle in Ω and the set of vertices of these triangles is dense in the boundary of Ω (see Figs. 1 to 4). Moreover, we construct examples of such divisible convex open sets Ω.