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.     

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.     

Critical angles in random polyhedral cones

This work concerns the angular structure of random polyhedral cones generated by p stochastically independent vectors uniformly distributed on the unit sphere of Rn. We comment on the expected number of critical angles and the mathematical expectation of the extremal angles.     

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.     

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.     

Critical angles between two convex cones II. Special cases

The concept of critical angle between two linear subspaces has applications in statistics, numerical linear algebra and other areas. Such concept has been abundantly studied in the literature. Part I of this work is an attempt to build up a theory of critical angles for a pair of closed convex cones. The need of such theory is motivated, among other reasons, by some specific problems arising in regression analysis of cone-constrained data, see Tenenhaus in (Psychometrika 53:503–524, 1988). Angle maximization and/or angle minimization problems involving a pair of convex cones are at the core of our discussion. Such optimization problems are nonconvex in general and their numerical resolution offers a number of challenges. Part II of this work focusses on the practical computation of the maximal angle between specially structured cones.     

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.     

Motzkin decomposition of closed convex sets

Theodore Motzkin proved, in 1936, that any polyhedral convex set can be expressed as the (Minkowski) sum of a polytope and a polyhedral convex cone. This paper provides five characterizations of the larger class of closed convex sets in finite dimensional Euclidean spaces which are the sum of a compact convex set with a closed convex cone. These characterizations involve different types of representations of closed convex sets as the support functions, dual cones and linear systems whose relationships are also analyzed in the paper. The obtaining of information about a given closed convex set F and the parametric linear optimization problem with feasible set F from each of its different representations, including the Motzkin decomposition, is also discussed.     

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.     

Critical angles between two convex cones I. General theory

The concept of critical (or principal) angle between two linear subspaces has applications in statistics, numerical linear algebra, and other areas. Such concept has been abundantly studied in the literature, both from a theoretical and computational point of view. Part I of this work is an attempt to build a general theory of critical angles for a pair of closed convex cones. The need of such theory is motivated, among other reasons, by some specific problems arising in regression analysis of cone-constrained data, see Tenenhaus (Psychometrika 53:503–524, 1988). Angle maximization and/or angle minimization problems involving a pair of convex cones are at the core of our discussion. Such optimization problems are nonconvex in general and their numerical resolution offer a number of challenges. Part II of this work focusses on the practical computation of the maximal and/or minimal angle between specially structured cones.     

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.     

On Solvability of Convex Noncoercive Quadratic Programming Problems

Using a known result on minimization of convex functionals on polyhedral cones, the Frank–Wolfe theorem, and basic linear algebra, we give a simple proof that the general convex quadratic programming problem which satisfies a natural necessary condition has a solution.     

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     

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.     

Tangible convex bodies. Appendix to “Multivariable Wiener-Hopf Operators I”

Study in a local geometry of non-smooth convex bodies via their supporting cones. The supporting cones are differential objects if the convex bodies are tangible. Examples of completely tangible and non-tangible convex bodies are presented.     

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.     

Local minima of quadratic forms on convex cones

We study the local minima and the critical values of a quadratic form on the trace of a convex cone. This variational problem leads to the development of a spectral theory that combines matrix algebra and facial analysis of convex cones.      

On the structure of the optimal server control for fluid networks

This paper derives the optimal trajectories in a general fluid network with server control. The stationary optimal policy in the complete state space is constructed. The optimal policy is constant on polyhedral convex cones. An algorithm is derived that computes these cones and the optimal policy. Generalized Klimov indices are introduced, they are used for characterizing myopic and time-uniformly optimal policies.Received: November 2004 / Revised: February 2005The research of this author has been supported by the project ‘‘Stochastic Networks’’ of the Netherlands Organisation for Scientific Research NWO.     

An algorithm for finding a vector in the intersection of open convex polyhedral cones

This paper establishes necessary and sufficient conditions for the intersection ofm open convex polyhedral cones to be nonempty. An algorithm is given which indicates if the intersection is empty or not, and eventually computes a vector in the intersection.     

On Some Generalized Polyhedral Convex Constructions

Generalized polyhedral convex sets, generalized polyhedral convex functions on locally convex Hausdorff topological vector spaces, and the related constructions such as sum of sets, sum of functions, directional derivative, infimal convolution, normal cone, conjugate function, subdifferential are studied thoroughly in this paper. Among other things, we show how a generalized polyhedral convex set can be characterized through the finiteness of the number of its faces. In addition, it is proved that the infimal convolution of a generalized polyhedral convex function and a polyhedral convex function is a polyhedral convex function. The obtained results can be applied to scalar optimization problems described by generalized polyhedral convex sets and generalized polyhedral convex functions.