Balinski—Tucker simplex tableaus: Dimensions, degeneracy degrees, and interior points of optimal faces

This paper shows the relationship between degeneracy degrees and multiple solutions in linear programming (LP) models. The usual definition of degeneracy is restricted to vertices of a polyhedron. We introduce degeneracy for nonempty subsets of polyhedra and show that for LP-models for which the feasible region contains at least one vertex it holds that the dimension of the optimal face is equal to the degeneracy degree of the optimal face of the corresponding dual model. This result is obtained by means of the so-called Balinski—Tucker (B—T) Simplex Tableaus. Furthermore, we give a strong polynomial algorithm for constructing such a B—T Simplex Tableau when a solution in the relative interior of the optimal face is known. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.     

Variational Interpolation of Subsets

We consider the problem of the variational interpolation of subsets of Euclidean spaces by curves such that the L² norm of the second derivative is minimized. It is well-known that the resulting curves are cubic spline curves. We study geometric boundary conditions arising for various types of subsets such as subspaces, polyhedra, and submanifolds, and we indicate how solutions can be computed in the case of convex polyhedra.     

Edge-Directions of Standard Polyhedra with Applications to Network Flows

Recent results show that edge-directions of polyhedra play an important role in (combinatorial) optimization; in particular, a d-dimensional polyhedron with |D| distinct edge-directions has at most O(|D|^d-1) vertices. Here, we obtain a characterization of the directions of edges that are adjacent to a given vertex of a standard polyhedron of the form P = {x : Ax = b, l⩽ x⩽ u, tightening a standard necessary condition which asserts that such directions must be minimal support solutions of the homogenous equation Ax = 0 which are feasible at the given vertex. We specialize the characterization for polyhedra that correspond to network flows, obtaining a graph characterization of circuits which correspond to edge-directions. Applications to partitioning polyhedra are discussed. Research of these authors was supported by a grant from ISF – the Israel Science Foundation, by a VPR grant at the Technion, and by the Fund for the Promotion of Research at the Technion.     

Weak linear degeneracy and global classical solutions for general quasilinear hyperbolic systems

By introducing the concept of the weak linear degeneracy the authors give a complete result for the global existence and for the life span of C¹ solutions to the Cauchy problem for general first order quasilinear hyperbolic systems with initial data small in C¹ norm and with compact support.     

Higher Schläfli Formulas and Applications

The classical Schläfli formula relates the variations of the dihedral angles of a smooth family of polyhedra in a space-form to the variation of the enclosed volume. We give higher analogues of this formula: for each p, we prove a simple formula relating the variation of the volumes of the codimension p faces to the variation of the 'curvature' – the volumes of the duals of the links in the convex case – of codimension p+2 faces. It is valid also for ideal polyhedra, or for polyhedra with some ideal vertices. This extends results of Suárez-Peiró. The proof is through analoguous smooth formulas. Some applications are described.     

Decompositions and boundary coverings of non-convex fat polyhedra

We show that any locally-fat (or (α,β)-covered) polyhedron with convex fat faces can be decomposed into O(n) tetrahedra, where n is the number of vertices of the polyhedron. We also show that the restriction that the faces are fat is necessary: there are locally-fat polyhedra with non-fat faces that require Ω(n²) pieces in any convex decomposition. Furthermore, we show that if we want the tetrahedra in the decomposition to be fat themselves, then their number cannot be bounded as a function of n in the worst case. Finally, we obtain several results on the problem where we want to only cover the boundary of the polyhedron, and not its entire interior.     

Grid Vertex-Unfolding Orthogonal Polyhedra

An edge-unfolding of a polyhedron is produced by cutting along edges and flattening the faces to a net, a connected planar piece with no overlaps. A grid unfolding allows additional cuts along grid edges induced by coordinate planes passing through every vertex. A vertex-unfolding allows faces in the net to be connected at single vertices, not necessarily along edges. We show that any orthogonal polyhedra of genus zero has a grid vertex-unfolding. (There are orthogonal polyhedra that cannot be vertex-unfolded, so some type of “gridding” of the faces is necessary.) For any orthogonal polyhedron P with n vertices, we describe an algorithm that vertex-unfolds P in O(n ²) time. Enroute to explaining this algorithm, we present a simpler vertex-unfolding algorithm that requires a 3×1×1 refinement of the vertex grid. This is a significant revision of the preliminary version that appeared in [2]. J. O’Rourke’s research was supported by NSF award DUE-0123154.     

Some continuous functions related to corner polyhedra,II

The group problem on the unit interval is developed, with and without continuous variables. The connection with cutting planes, or valid inequalities, is reviewed. Certain desirable properties of valid inequalities, such as minimality and extremality are developed, and the connection between valid inequalities for P(I, u ₀) and P _- ⁺ (I, u ₀) is developed. A class of functions is shown to give extreme valid inequalities for P _- ⁺ (I, u ₀) and for certain subsetsU ofI. A method is used to generate such functions. These functions give faces of certain corner polyhedra. Other functions which do not immediately give extreme valid inequalities are altered to construct a class of faces for certain corner polyhedra. This class of faces grows exponentially as the size of the group grows.     

Weak Galerkin finite element methods for the biharmonic equation on polytopal meshes

A new weak Galerkin (WG) finite element method is introduced and analyzed in this article for the biharmonic equation in its primary form. This method is highly robust and flexible in the element construction by using discontinuous piecewise polynomials on general finite element partitions consisting of polygons or polyhedra of arbitrary shape. The resulting WG finite element formulation is symmetric, positive definite, and parameter‐free. Optimal order error estimates in a discrete H² norm is established for the corresponding WG finite element solutions. Error estimates in the usual L² norm are also derived, yielding a suboptimal order of convergence for the lowest order element and an optimal order of convergence for all high order of elements. Numerical results are presented to confirm the theory of convergence under suitable regularity assumptions. © 2014 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 30: 1003–1029, 2014     

Some geometric results in semidefinite programming

The purpose of this paper is to develop certain geometric results concerning the feasible regions of Semidefinite Programs, called hereSpectrahedra.We first develop a characterization for the faces of spectrahedra. More specifically, given a pointx in a spectrahedron, we derive an expression for the minimal face containingx. Among other things, this is shown to yield characterizations for extreme points and extreme rays of spectrahedra. We then introduce the notion of an algebraic polar of a spectrahedron, and present its relation to the usual geometric polar.Support received under the grants: NSF-STC91-19999 (DIMACS) and Air Force grant F49620-93-1-0041 (RUTCOR).Support from the NSF grant ECS-9111548 is acknowledged.     

Chiral Polyhedra in Ordinary Space, I

Chiral polyhedra in ordinary euclidean space E³ are nearly regular polyhedra; their geometric symmetry groups have two orbits on the flags, such that adjacent flags are in distinct orbits. This paper completely enumerates the discrete infinite chiral polyhedra in E³ with finite skew faces and finite skew vertex-figures. There are several families of such polyhedra of types {4,6}, {6,4} and {6,6}. Their geometry and combinatorics are discussed in detail. It is also proved that a chiral polyhedron in E³ cannot be finite. Part II of the paper will complete the classification of all chiral polyhedra in E³. All chiral polyhedra not described in Part I have infinite, helical faces and again occur in families. So, in effect, Part I enumerates all chiral polyhedra in E³ with finite faces.     

Harnack inequality and regularity for degenerate quasilinear elliptic equations

We prove Harnack inequality and local regularity results for weak solutions of a quasilinear degenerate equation in divergence form under natural growth conditions. The degeneracy is given by a suitable power of a strong A _∞ weight. Regularity results are achieved under minimal assumptions on the coefficients and, as an application, we prove C ^1,α local estimates for solutions of a degenerate equation in non divergence form.     

Espace des modules de certains polyèdres projectifs miroirs

A projective mirror polyhedron is a projective polyhedron endowed with reflections across its faces. We construct an explicit diffeomorphism between the moduli space of a mirror projective polyhedron with fixed dihedral angles in (0,\fracp2]{(0,\frac{\pi}{2}]}, and the union of n copies of \mathbbR^d{\mathbb{R}^{d}}, when the polyhedron has the combinatorics of an ecimahedron, an infinite class of combinatorial polyhedra we introduce here. Moreover, the integers n and d can be computed explicitly in terms of the combinatorics and the fixed dihedral angles.     

On degeneracy in enumeration

In the case of degeneracy in an LP-formulation, there is not a one-to-one correspondence between extreme points and feasible bases. If the task is to find thek best extreme points in the set of feasible solutions to an LP, this lack of correspondence has a certain importance, since methods based on the Simplex Algorithm are oriented towards feasible bases instead of the relevant extreme points. We therefore present an easily implementable method to avoid this problem.     

Behavioral measures and their correlation with IPM iteration counts on semi-definite programming problems

We study four measures of problem instance behavior that might account for the observed differences in interior-point method (IPM) iterations when these methods are used to solve semidefinite programming (SDP) problem instances: (i) an aggregate geometry measure related to the primal and dual feasible regions (aspect ratios) and norms of the optimal solutions, (ii) the (Renegar-) condition measure C(d) of the data instance, (iii) a measure of the near-absence of strict complementarity of the optimal solution, and (iv) the level of degeneracy of the optimal solution. We compute these measures for the SDPLIB suite problem instances and measure the sample correlation (CORR) between these measures and IPM iteration counts (solved using the software SDPT3) when these measures have finite values. Our conclusions are roughly as follows: the aggregate geometry measure is highly correlated with IPM iterations (CORR = 0.901), and provides a very good explanation of IPM iterations, particularly for problem instances with solutions of small norm and aspect ratio. The condition measure C(d) is also correlated with IPM iterations, but less so than the aggregate geometry measure (CORR = 0.630). The near-absence of strict complementarity is weakly correlated with IPM iterations (CORR = 0.423). The level of degeneracy of the optimal solution is essentially uncorrelated with IPM iterations. This research has been partially supported through the MIT-Singapore Alliance.     

Chiral Polyhedra in Ordinary Space, II

A chiral polyhedron has a geometric symmetry group with two orbits on the flags, such that adjacent flags are in distinct orbits. Part I of the paper described the discrete chiral polyhedra in ordinary euclidean space E³ with finite skew faces and finite skew vertex-figures; they occur in infinite families and are of types {4,6}, {6,4} and {6,6}. Part II completes the enumeration of all discrete chiral polyhedra in E³. There exist several families of chiral polyhedra of types {∞,3} and {∞,4} with infinite, helical faces. In particular, there are no discrete chiral polyhedra with finite faces in addition to those described in Part I.     

Towards minimal assumptions for the infimal convolution regularization

We encompass the Moreau-Yosida regularization process by infimal convolution into a general framework. This sheds light on the assumptions required for obtaining the usual properties. In particular the class of lower-T² mappings is shown to be a suitable class for performing the usual proximal regularization in open subsets of Hilbert spaces. The role of growth conditions is pointed out.     

Completely classifying all vertex-transitive and edge-transitive polyhedra

Recently A. Dress completed the classification of the regular polyhedra in E ³ by adding one class to the enumeration given by Grünbaum on this subject. This classification is the only systematic study of a collection of polyhedra possessing special symmetries which uses the generalized definition of a polygon allowing for skew polygons as well as planar polygons in E ³. This study gives necessary conditions for polyhedra to be vertex-transitive and edge-transitive. These conditions are restrictive enough to make the task of completely enumerating such polyhedra realizable and efficient. Examples of this process are given, and an explanation of the basic process is discussed. These new polyhedra are appearing more frequently in applications of geometry, and this examination is a beginning of the classifications of polyhedra having special symmetries even though there are many other such classes which lack this scrutiny.     

On structures of bisubmodular polyhedra

A bisubmodular polyhedron is defined in terms of a so-called bisubmodular function on a family of ordered pairs of disjoint subsets of a finite set. We examine the structures of bisubmodular polyhedra in terms of signed poset and exchangeability graph. We give a characterization of extreme points together with an O(n ²) algorithm for discerning whether a given point is an extreme point, wheren is the cardinality of the underlying set, and we assume a function evaluation oracle for the bisubmodular function. The algorithm also determines the signed posetructure associated with the given point if it is an extreme point. We reveal the adjacency relation of extreme points by means of the Hasse diagrams of the associated signed posets. Moreover, we investigate the connectivity and the decomposition of a bisubmodular system into its connected components.