张量空间中的多面体锥

本文利用文献 [1 ]中的结果给出了张量空间中多面体锥的性质 ,指出当 K1,K2 分别为 V1,V2中的多面体锥时 ,由它们所生成的 V1 V2 中的最小真正锥也是多面体锥 ,这一条件不仅是充分的也是必要的 .并利用这一结果对多面体锥的已有结论给出了新的证明     

Zero polyhedral cones

Properties of zero polyhedral cones are studied by making use of Fourier-Motzkin eliminations. Algorithms are presented for the characterization of zero polyhedral cones.     

Critical angles in polyhedral convex cones: numerical and statistical considerations

This work concerns the numerical computation of critical angles in polyhedral convex cones. The set of proper critical angles is evaluated explicitly by solving a series of generalized eigenvalue problems involving the generators of the cone. The local maximal angles are identified by using a necessary condition for local maximality. The expected numbers of critical angles in random polyhedral convex cones are estimated experimentally.     

Generalized equitable preference in multiobjective programming

The concept of equitability in multiobjective programming is generalized within a framework of convex cones. Two models are presented. First, more general polyhedral cones are assumed to determine the equitable preference. Second, the Pareto cone appearing in the monotonicity axiom of equitability is replaced with a permutation-invariant polyhedral cone. The conditions under which the new models are related and satisfy original and modified axioms of the equitable preference are developed. Relationships between generalized equitability and relative importance of criteria and stochastic dominance are revealed.     

Extreme positive operators on minimal and almost minimal cones

Fiedler and Pták called a cone minimal if it is n-dimensional and has n+1 extremal rays. We call a cone almost minimal if it is n-dimensional and has n+2 extremal rays. Duality properties stemming from the use of Gale pairs lead to a general technique for identifying the extreme cone-preserving (positive) operators between polyhedral cones. This technique is most effective for cones with dimension not much smaller than the number of their extreme rays. In particular, the Fiedler-Pták characterization of extreme positive operators between minimal cones is extended to the following cases: (i) operators from a minimal cone to an arbitrary polyhedral cone, (ii) operators from an almost minimal cone to a minimal cone.     

An axiomatic duality framework for the theta body and related convex corners

Lovász theta function and the related theta body of graphs have been in the center of the intersection of four research areas: combinatorial optimization, graph theory, information theory, and semidefinite optimization. In this paper, utilizing a modern convex optimization viewpoint, we provide a set of minimal conditions (axioms) under which certain key, desired properties are generalized, including the main equivalent characterizations of the theta function, the theta body of graphs, and the corresponding antiblocking duality relations. Our framework describes several semidefinite and polyhedral relaxations of the stable set polytope of a graph as generalized theta bodies. As a by-product of our approach, we introduce the notion of “Schur Lifting” of cones which is dual to PSD Lifting (more commonly used in SDP relaxations of combinatorial optimization problems) in our axiomatic generalization. We also generalize the notion of complements of graphs to diagonally scaling-invariant polyhedral cones. Finally, we provide a weighted generalization of the copositive formulation of the fractional chromatic number by Dukanovic and Rendl from 2010.     

Subdivisions from primal and dual cones and polytopes

A conic subdivision of euclidean half-space is obtained where the cones are generated using faces and dual faces of a closed polyhedral convex set and its dual.     

Geometry of optimal value functions with applications to redundancy in linear programming

In 1967, Wets and Witzgall (Ref. 1) made, in passing, a connection between frames of polyhedral cones and redundancy in linear programming. The present work elaborates and formalizes the theoretical details needed to establish this relation. We study the properties of optimal value functions in order to derive the correspondence between problems in redundancy and the frame of a polyhedral cone. The insights obtained lead to schemes to improve the efficiency of procedures to detect redundancy in the areas of linear programming, stochastic programming, and computational geometry.The author is indebted to G. Dewan for his review and discussions.     

Some applications of optimization in matrix theory

We apply a recent characterization of optimality for the abstract convex program with a cone constraint to three matrix theory problems: (1) a generalization of Farkas's lemma; (2) paired duality in linear programming over cones; (3) a constrained matrix best approximation problem. In particular, these results are not restricted to polyhedral or closed cones.     

Normal Fans of Polyhedral Convex Sets

The normal fan of a polyhedral convex set in ? ⁿ is the collection of its normal cones. The structure of the normal fan reflects the geometry of that set. This paper reviews and studies properties about the normal fan. In particular, it investigates situations in which the normal fan of a polyhedral convex set refines, or is a subfan of, that of another set. It then applies these techniques in several examples. One of these concerns the face structure and normal manifold of the critical cone of a polyhedral convex set associated with a point in ? ⁿ . Another concerns how perturbation of the right hand side of the linear constraints defining such a set affects the normal fan and the face structure.     

Group inverses of certain positive operators

Positive operators on certain polyhedral cones with the property that the group inverse of the operator is equal to some power of the operator are characterized. The special case of the Moore-Penrose inverse is also considered.     

About separation by cones

The notion of separation by hyperplanes is extended, so as to include separation by acute polyhedral cones.     

Intersection probabilities and kinematic formulas for polyhedral cones

For polyhedral convex cones in \({\mathbb{R}^d}\), we give a proof for the conic kinematic formula for conic curvature measures, which avoids the use of characterization theorems. For the random cones defined as typical cones of an isotropic random central hyperplane arrangement, we find probabilities for non-trivial intersection, either with a fixed cone, or for two independent random cones of this type.     

Adhesivity of polymatroids

Two polymatroids are adhesive if a polymatroid extends both in such a way that two ground sets become a modular pair. Motivated by entropy functions, the class of polymatroids with adhesive restrictions and a class of selfadhesive polymatroids are introduced and studied. Adhesivity is described by polyhedral cones of rank functions and defining inequalities of the cones are identified, among them known and new non-Shannon type information inequalities for entropy functions. The selfadhesive polymatroids on a four-element set are characterized by Zhang-Yeung inequalities.     

Intersection cuts for convex mixed integer programs from translated cones

We develop a general framework for linear intersection cuts for convex integer programs with full-dimensional feasible regions by studying integer points of their translated tangent cones, generalizing the idea of Balas (1971). For proper (i.e, full-dimensional, closed, convex, pointed) translated cones with fractional vertices, we show that under certain mild conditions all intersection cuts are indeed valid for the integer hull, and a large class of valid inequalities for the integer hull are intersection cuts, computable via polyhedral approximations. We also give necessary conditions for a class of valid inequalities to be tangent halfspaces of the integer hull of proper translated cones. We also show that valid inequalities for non-pointed regular translated cones can be derived as intersection cuts for associated proper translated cones under some mild assumptions.     

Theory of convex cones in multicriteria decision making

We develop the theory of convex polyhedral cones in the objective-function space of a multicriteria decision problem. The convex cones are obtained from the decision-maker's pairwise judgments of decision alternatives and are applicable to any quasiconcave utility function. Therefore, the cones can be used in any progressively articulated solution procedure that employs pairwise comparisons. The cones represent convex sets of solutions that are inferior to known solutions to a multicriteria problem. Therefore, these convex sets can be eliminated from consideration while solving the problem. We develop the underlying theory and a framework for representing knowledge about the decision-maker's preference structure using convex cones. This framework can be adopted in the interactive solution of any multicriteria problem after taking into account the characteristics of the problem and the solution procedure. Our computational experience with different multicriteria problems shows that this approach is both viable and efficient in solving practical problems of moderate size.     

A method for constructing the polar cone of a polyhedral cone,with applications to linear multicriteria decision problems

The necessary and sufficient conditions for solution sets of linear multicriteria decision problems are given in the first part of this paper. In order to find the solution sets by applying the theorem describing the conditions, the constructions of the open polar cone and the semi-open polar cone of a given polyhedral cone are required.A method of construction of the polar cone, open polar cone, and semi-open polar cone is presented. For this purpose, edge vectors of the polar cone are introduced and characterized in terms of the generating vectors of a given polyhedral cone. It is shown that these polar cones are represented by the edge vectors.Numerical examples of linear multicriteria decision problems are solved to illustrate the construction of the polar cones and to explain the application of the theorem to obtain the solution sets.The author is grateful to Professor P. L. Yu for helpful comments concerning the development of Theorem 2.1.     

When do the Recession Cones of a Polyhedral Complex Form a Fan?

We study the problem of when the collection of the recession cones of a polyhedral complex also forms a complex. We exhibit an example showing that this is no always the case. We also show that if the support of the given polyhedral complex satisfies a Minkowski–Weyl-type condition, then the answer is positive. As a consequence, we obtain a classification theorem for proper toric schemes over a discrete valuation ring in terms of complete strongly convex rational polyhedral complexes.     

Convex relaxations for nonconvex quadratically constrained quadratic programming: matrix cone decomposition and polyhedral approximation

We present a decomposition-approximation method for generating convex relaxations for nonconvex quadratically constrained quadratic programming (QCQP). We first develop a general conic program relaxation for QCQP based on a matrix decomposition scheme and polyhedral (piecewise linear) underestimation. By employing suitable matrix cones, we then show that the convex conic relaxation can be reduced to a semidefinite programming (SDP) problem. In particular, we investigate polyhedral underestimations for several classes of matrix cones, including the cones of rank-1 and rank-2 matrices, the cone generated by the coefficient matrices, the cone of positive semidefinite matrices and the cones induced by rank-2 semidefinite inequalities. We demonstrate that in general the new SDP relaxations can generate lower bounds at least as tight as the best known SDP relaxations for QCQP. Moreover, we give examples for which tighter lower bounds can be generated by the new SDP relaxations. We also report comparison results of different convex relaxation schemes for nonconvex QCQP with convex quadratic/linear constraints, nonconvex quadratic constraints and 0–1 constraints.     

Strong conical hull intersection property, bounded linear regularity, Jameson’s property (G), and error bounds in convex optimization

The strong conical hull intersection property and bounded linear regularity are properties of a collection of finitely many closed convex intersecting sets in Euclidean space. These fundamental notions occur in various branches of convex optimization (constrained approximation, convex feasibility problems, linear inequalities, for instance). It is shown that the standard constraint qualification from convex analysis implies bounded linear regularity, which in turn yields the strong conical hull intersection property. Jameson’s duality for two cones, which relates bounded linear regularity to property (G), is re-derived and refined. For polyhedral cones, a statement dual to Hoffman’s error bound result is obtained. A sharpening of a result on error bounds for convex inequalities by Auslender and Crouzeix is presented. Finally, for two subspaces, property (G) is quantified by the angle between the subspaces. Received October 1, 1997 / Revised version received July 21, 1998? Published online June 11, 1999