One recently proposed criterion to separate two datasets in discriminant analysis, is to use a hyperplane which minimises the sum of distances to it from all the misclassified data points. Here all distances are supposed to be measured by way of some fixed norm,while misclassification means lying on the wrong side of the hyperplane, or … Read more
We present a new complexity result on solving the Markov decision problem (MDP) with $n$ states and a number of actions for each state, a special class of real-number linear programs with the Leontief matrix structure. We prove that, when the discount factor $\theta$ is strictly less than $1$, the problem can be solved in … Read more
This paper presents a new primal dual simplex method and investigates the duality formation implying in classical simplex methods. We reviews classical simplex methods for linear programming problems and give a detail discussion for the relation between modern and classical algorithms. The two modified versions are present. The advantages of the new algorithms are simplicity … Read more
In this survey we review the many faces of the S-lemma, a result about the correctness of the S-procedure. The basic idea of this widely used method came from control theory but it has important consequences in quadratic and semidefinite optimization, convex geometry and linear algebra as well. These were active research areas, but as … Read more
Managing shelf space is critical for retailers to attract customers and to optimize profit. This paper develops a shelf space allocation optimization model that explicitly incorporates essential in-store costs and considers space- and cross-elasticities. The resultant model maximizes a signomial objective function over linear and bilinear constraints in mixed-integer variables. We propose a piecewise linearization … Read more
We show that for even quasi-concave objective functions the worst-case distribution, with respect to a family of unimodal distributions, of a stochastic programming problem is a uniform distribution. This extends the so-called “Uniformity Principle” of Barmish and Lagoa (1997) where the objective function is the indicator function of a convex symmetric set. Article Download View … Read more
We consider probabilistic constrained linear programs with general distributions for the uncertain parameters. These problems generally involve non-convex feasible sets. We develop a branch and bound algorithm that searches for a global solution to this problem by successively partitioning the non-convex feasible region and by using bounds on the objective function to fathom inferior partitions. … Read more
Optimality of a linear inequality in finitely many graph invariants is defined through a geometric approach. For a fixed number of graph nodes, consider all the tuples of values taken by the invariants on a selected class of graphs. Then form the polytope which is the convex hull of all these tuples. By definition, the … Read more
Two interior-point algorithms are proposed and analyzed, for the (local) solution of (possibly) indefinite quadratic programming problems. They are of the Newton-KKT variety in that (much like in the case of primal-dual algorithms for linear programming) search directions for the `primal´ variables and the Karush-Kuhn-Tucker (KKT) multiplier estimates are components of the Newton (or quasi-Newton) … Read more
This paper proves the existence of non-empty cores for directed network and two-sided network problems with quotas. Article Download View The Core of Network Problems with Quotas