Efficient solutions in generalized linear vector optimization

This paper establishes several new facts on generalized polyhedral convex sets and shows how they can be used in vector optimization. Among other things, a scalarization formula for the efficient solution sets of generalized linear vector optimization problems is obtained. We also prove that the efficient solution set of a generalized linear vector optimization problem in a locally convex Hausdorff topological vector space is the union of finitely many generalized polyhedral convex sets and it is connected by line segments.     

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.     

Lipschitzian stability of parametric variational inequalities over generalized polyhedra in Banach spaces

This paper concerns the study of solution maps to parameterized variational inequalities over generalized polyhedra in reflexive Banach spaces. It has been recognized that generalized polyhedral sets are significantly different from the usual convex polyhedra in infinite dimensions and play an important role in various applications to optimization, particularly to generalized linear programming. Our main goal is to fully characterize robust Lipschitzian stability of the aforementioned solution maps entirely via their initial data. This is done on the basis of the coderivative criterion in variational analysis via efficient calculations of the coderivative and related objects for the systems under consideration. The case of generalized polyhedra is essentially more involved in comparison with usual convex polyhedral sets and requires developing elaborated techniques and new proofs of variational analysis.     

Uniqueness for first-order Hamilton-Jacobi equations and Hopf formula

We study uniqueness properties for a certain class of Cauchy problems for first-order Hamilton-Jacobi equations for which a solution is given by the Hopf formula. We prove various comparison and characterisation results concerning both convex generalized solutions and viscosity solutions. In particular, we show that the Hopf solution is the maximum convex generalized subsolution and the unique convex viscosity solution of the Cauchy problem.     

On Finite Linear Systems Containing Strict Inequalities

This paper deals with linear systems containing finitely many weak and/or strict inequalities, whose solution sets are referred to as evenly convex polyhedral sets. The classical Motzkin theorem states that every (closed and convex) polyhedron is the Minkowski sum of a convex hull of finitely many points and a finitely generated cone. In this sense, similar representations for evenly convex polyhedra have been recently given by using the standard version for classical polyhedra. In this work, we provide a new dual tool that completely characterizes finite linear systems containing strict inequalities and it constitutes the key for obtaining a generalization of Motzkin theorem for evenly convex polyhedra.     

Geometric approach to convex subdifferential calculus

In this paper, we develop a geometric approach to convex subdifferential calculus in finite dimensions with employing some ideas of modern variational analysis. This approach allows us to obtain natural and rather easy proofs of basic results of convex subdifferential calculus in full generality and also derive new results of convex analysis concerning optimal value/marginal functions, normals to inverse images of sets under set-valued mappings, calculus rules for coderivatives of single-valued and set-valued mappings, and calculating coderivatives of solution maps to parameterized generalized equations governed by set-valued mappings with convex graphs.     

Minimum Distance to the Complement of a Convex Set: Duality Result

The subject of this paper is to study the problem of the minimum distance to the complement of a convex set. Nirenberg has stated a duality theorem treating the minimum norm problem for a convex set. We state a duality result which presents some analogy with the Nirenberg theorem, and we apply this result to polyhedral convex sets. First, we assume that the polyhedral set is expressed as the intersection of some finite collection of m given half-spaces. We show that a global solution is determined by solving m convex programs. If the polyhedral set is expressed as the convex hull of a given finite set of extreme points, we show that a global minimum for a polyhedral norm is obtained by solving a finite number of linear programs.     

Exact Formulae for Coderivatives of Normal Cone Mappings to Perturbed Polyhedral Convex Sets

In this paper, without using any regularity assumptions, we derive a new exact formula for computing the Fréchet coderivative and an exact formula for the Mordukhovich coderivative of normal cone mappings to perturbed polyhedral convex sets. Our development establishes generalizations and complements of the existing results on the topic. An example to illustrate formulae is given.     

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.     

Analytical Linear Inequality Systems and Optimization

In many interesting semi-infinite programming problems, all the constraints are linear inequalities whose coefficients are analytical functions of a one-dimensional parameter. This paper shows that significant geometrical information on the feasible set of these problems can be obtained directly from the given coefficient functions. One of these geometrical properties gives rise to a general purification scheme for linear semi-infinite programs equipped with so-called analytical constraint systems. It is also shown that the solution sets of such kind of consistent systems form a transition class between polyhedral convex sets and closed convex sets in the Euclidean space of the unknowns.     

Characterization of the singular part of the solution of Maxwell's equations in a polyhedral domain

The solution of Maxwell's equations in a non‐convex polyhedral domain is less regular than in a smooth or convex polyhedral domain. In this paper we show that this solution can be decomposed into the orthogonal sum of a singular part and a regular part, and we give a characterization of the singular part. We also prove that the decomposition is linked to the one associated to the scalar Laplacian. Copyright © 1999 John Wiley & Sons, Ltd.     

Global optimization of a nonconvex single facility location problem by sequential unconstrained convex minimization

The problem of maximizing the sum of certain composite functions, where each term is the composition of a convex decreasing function, bounded from below, with a convex function having compact level sets arises in certain single facility location problems with gauge distance functions. We show that this problem is equivalent to a convex maximization problem over a compact convex set and develop a specialized polyhedral annexation procedure to find a global solution for the case when the inside function is a polyhedral norm. As the problem was solved recently only for local solutions, this paper offers an algorithm for finding a global solution. Implementation and testing are not treated in this short communication.An earlier version of this paper appeared in the proceedings of a conference on Recent Advances in Global Optimization, C. Floudas and P. Pardalos, eds., Princeton University Press, 1991.     

Direct-dual Fejér methods for problems of quadratic programming

The paper deals with the S-technology, which reduces convex problems of quadratic programming to the solution of systems of several linear, and one convex, inequalities. A certain variant of the Fejér method is applied to these systems. In particular, the problem of the constructive separability of convex polyhedral sets by a layer of maximal thickness is solved. This algorithm plays an important role in problems of discriminant analysis.     

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.     

Approximating the convex Edgeworth-Pareto hull in integer multi-objective problems with monotone criteria

A method for the iterative polyhedral approximation of the convex Edgeworth-Pareto hull is proposed and examined experimentally. This method is designed for integer multi-objective problems with monotone objective functions and constraints given by a computational module. It is based on a synthesis of the ideas of the branch-and-bound method and the methods for the polyhedral approximation of convex bodies. A sequence of interior and exterior polyhedral sets is constructed so as to approximate the Edgeworth-Pareto hull to the desired accuracy. The results of the theoretical and experimental analyses of the proposed method are presented.     

Stein's phenomenon in estimation of means restricted to a polyhedral convex cone

This paper treats the problem of estimating the restricted means of normal distributions with a known variance, where the means are restricted to a polyhedral convex cone which includes various restrictions such as positive orthant, simple order, tree order and umbrella order restrictions. In the context of the simultaneous estimation of the restricted means, it is of great interest to investigate decision-theoretic properties of the generalized Bayes estimator against the uniform prior distribution over the polyhedral convex cone. In this paper, the generalized Bayes estimator is shown to be minimax. It is also proved that it is admissible in the one- or two-dimensional case, but is improved on by a shrinkage estimator in the three- or more-dimensional case. This means that the so-called Stein phenomenon on the minimax generalized Bayes estimator can be extended to the case where the means are restricted to the polyhedral convex cone. The risk behaviors of the estimators are investigated through Monte Carlo simulation, and it is revealed that the shrinkage estimator has a substantial risk reduction.     

A smoothing homotopy method for variational inequality problems on polyhedral convex sets

In this paper, based on the Robinson’s normal equation and the smoothing projection operator, a smoothing homotopy method is presented for solving variational inequality problems on polyhedral convex sets. We construct a new smoothing projection operator onto the polyhedral convex set, which is feasible, twice continuously differentiable, uniformly approximate to the projection operator, and satisfies a special approximation property. It is computed by solving nonlinear equations in a neighborhood of the nonsmooth points of the projection operator, and solving linear equations with only finite coefficient matrices for other points, which makes it very efficient. Under the assumption that the variational inequality problem has no solution at infinity, which is a weaker condition than several well-known ones, the existence and global convergence of a smooth homotopy path from almost any starting point in $R^n$ are proven. The global convergence condition of the proposed homotopy method is same with that of the homotopy method based on the equivalent KKT system, but the starting point of the proposed homotopy method is not necessarily an interior point, and the efficiency is more higher. Preliminary test results show that the proposed method is practicable, effective and robust.     

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.     

Method for constructing an external polyhedral estimate of the trajectory tube for a nonlinear dynamic system

A numerical method is proposed for constructing an external polyhedral estimate for the trajectory tube of a nonlinear dynamic system described by a differential inclusion. The method is based on the approximation of cross sections of the trajectory tube (reachable sets) for an auxiliary system described by the convex hull of the graph of the differential inclusion. It produces polyhedral estimates suitable for the direct study of tubes via computer visualization and for the solution of more general problems.