Clarkson's algorithm for violator spaces

Clarkson's algorithm is a three-staged randomized algorithm for solving linear programs. This algorithm has been simplified and adapted to fit the framework of LP-type problems. In this framework we can tackle a number of non-linear problems such as computing the smallest enclosing ball of a set of points in Rd. In 2006, it has been shown that the algorithm in its original form works for violator spaces too, which are a proper generalization of LP-type problems. It was not clear, however, whether previous simplifications of the algorithm carry over to the new setting.In this paper we show the following theoretical results: (a) It is shown, for the first time, that Clarkson's second stage can be simplified. (b) The previous simplifications of Clarkson's first stage carry over to the violator space setting. (c) The equivalence of violator spaces and partitions of the hypercube by hypercubes.     

Removing degeneracy may require unbounded dimension increase

Many geometric algorithms are formulated for input objects in general position; sometimes this is for convenience and simplicity, and sometimes it is essential for the algorithm to work at all. For arbitrary inputs this requires removing degeneracies, which has usually been solved by relatively complicated and computationally demanding perturbation methods. The result of this paper can be regarded as an indication that the problem of removing degeneracies has no simple “abstract” solution. We consider LP-type problems, a successful axiomatic framework for optimization problems capturing, e.g., linear programming and the smallest enclosing ball of a point set. We prove that in order to remove degeneracies of an LP-type problem, we sometimes have to increase its combinatorial dimension by an arbitrarily large amount.     

Removing Degeneracy in LP-Type Problems Revisited

LP-type problems is a successful axiomatic framework for optimization problems capturing, e.g., linear programming and the smallest enclosing ball of a point set. In Matoušek and Škovroň (Theory Comput. 3:159–177, 2007), it is proved that in order to remove degeneracies of an LP-type problem, we sometimes have to increase its combinatorial dimension by a multiplicative factor of at least 1+ε with a certain small positive constant ε. The proof goes by checking the unsolvability of a system of linear inequalities, with several pages of calculations. Here by a short topological argument we prove that the dimension sometimes has to increase at least twice. We also construct 2-dimensional LP-type problems with −∞ for which removing degeneracies forces arbitrarily large dimension increase.     

A Simple Sampling Lemma: Analysis and Applications in Geometric Optimization

Random sampling is an efficient method to deal with constrained optimization problems in computational geometry. In a first step, one finds the optimal solution subject to a random subset of the constraints; in many cases, the expected number of constraints still violated by that solution is then significantly smaller than the overall number of constraints that remain. This phenomenon can be exploited in several ways, and typically results in simple and asymptotically fast algorithms. Very often the analysis of random sampling in this context boils down to a simple identity (the sampling lemma ) which holds in a general framework, yet has not been stated explicitly in the literature. In the more restricted but still general setting of LP-type problems , we prove tail estimates for the sampling lemma, giving Chernoff-type bounds for the number of constraints violated by the solution of a random subset. As an application, we provide the first theoretical analysis of multiple pricing , a heuristic used in the simplex method for linear programming in order to reduce a large problem to few small ones. This follows from our analysis of a reduction scheme for general LP-type problems, which can be considered as a simplification of an algorithm due to Clarkson. The simplified version needs less random resources and allows a Chernoff-type tail estimate. Received June 8, 2000, and in revised form September 10, 2000. Online publication March 26, 2001.     

Violator spaces vs closure spaces

The main goal of the paper is to make connections between two well-known, but, up to now, independently developed theories: the theory of violator spaces and the theory of closure spaces. Violator spaces were introduced by Matoušek et al. in 2008 as generalization of linear programming problems. The notion of closure arises in many disciplines, including topology, algebra, convexity analysis, logic etc. In this work, we investigate interrelations between violator spaces and closure spaces. We show that a violator mapping may be defined by a weak version of a closure operator. Interrelations between violator spaces and closure spaces give new insights on a number of well known findings. For example, we prove that violator spaces with a unique basis satisfy both the anti-exchange and the Krein–Milman properties.Finally, based on subsequent relaxations of the closure operator notion we introduce convex spaces as a generalization of violator spaces.     

Some Randomized Algorithms for Convex Quadratic Programming

We adapt some randomized algorithms of Clarkson [3] for linear programming to the framework of so-called LP-type problems, which was introduced by Sharir and Welzl [10]. This framework is quite general and allows a unified and elegant presentation and analysis. We also show that LP-type problems include minimization of a convex quadratic function subject to convex quadratic constraints as a special case, for which the algorithms can be implemented efficiently, if only linear constraints are present. We show that the expected running times depend only linearly on the number of constraints, and illustrate this by some numerical results. Even though the framework of LP-type problems may appear rather abstract at first, application of the methods considered in this paper to a given problem of that type is easy and efficient. Moreover, our proofs are in fact rather simple, since many technical details of more explicit problem representations are handled in a uniform manner by our approach. In particular, we do not assume boundedness of the feasible set as required in related methods. Accepted 7 May 1997     

Simultaneous column-and-row generation for large-scale linear programs with column-dependent-rows

In this paper, we develop a simultaneous column-and-row generation algorithm that could be applied to a general class of large-scale linear programming problems. These problems typically arise in the context of linear programming formulations with exponentially many variables. The defining property for these formulations is a set of linking constraints, which are either too many to be included in the formulation directly, or the full set of linking constraints can only be identified, if all variables are generated explicitly. Due to this dependence between columns and rows, we refer to this class of linear programs as problems with column-dependent-rows. To solve these problems, we need to be able to generate both columns and rows on-the-fly within an efficient solution approach. We emphasize that the generated rows are structural constraints and distinguish our work from the branch-and-cut-and-price framework. We first characterize the underlying assumptions for the proposed column-and-row generation algorithm. These assumptions are general enough and cover all problems with column-dependent-rows studied in the literature up until now to the best of our knowledge. We then introduce in detail a set of pricing subproblems, which are used within the proposed column-and-row generation algorithm. This is followed by a formal discussion on the optimality of the algorithm. To illustrate our approach, the paper is concluded by applying the proposed framework to the multi-stage cutting stock and the quadratic set covering problems.     

Minimax linear programming problem

In this paper, we consider the following minimax linear programming problem: min z = max_{1 ≤ j ≤ n}{C_jX_j}, subject to Ax = g, x ≥ 0. It is well known that this problem can be transformed into a linear program by introducing n additional constraints. We note that these additional constraints can be considered implicitly by treating them as parametric upper bounds. Based on this approach we develop two algorithms: a parametric algorithm and a primal—dual algorithm. The parametric algorithm solves a linear programming problem with parametric upper bounds and the primal—dual algorithm solves a sequence of related dual feasible linear programming problems. Computation results are also presented, which indicate that both the algorithms are substantially faster than the simplex algorithm applied to the enlarged linear programming problem.     

A NEW GENERALIZED GRADIENT PROJECTION TYPEALGORITHM FOR LINEARLY CONSTRAINED PROBLEMS

In this paper, we provide a new generalized gradient projection algorithm for nonlinear programming problems with linear constraints. This algorithm has simple structure and is very practical and stable. Under the weaker assumptions, we have proved the global convergence of our algorithm.     

On generalized Nash equilibrium problems with linear coupling constraints and mixed-integer variables

ABSTRACT

We define and discuss different enumerative methods to compute solutions of generalized Nash equilibrium problems with linear coupling constraints and mixed-integer variables. We propose both branch-and-bound methods based on merit functions for the mixed-integer game, and branch-and-prune methods that exploit the concept of dominance to make effective cuts. We show that under mild assumptions the equilibrium set of the game is finite and we define an enumerative method to compute the whole of it. We show that our branch-and-prune method can be suitably modified in order to make a general equilibrium selection over the solution set of the mixed-integer game. We define an application in economics that can be modelled as a Nash game with linear coupling constraints and mixed-integer variables, and we adapt the branch-and-prune method to efficiently solve it.     

Using duality to solve generalized fractional programming problems

In this paper we explore the relations between the standard dual problem of a convex generalized fractional programming problem and the partial dual problem proposed by Barros et al. (1994). Taking into account the similarities between these dual problems and using basic duality results we propose a new algorithm to directly solve the standard dual of a convex generalized fractional programming problem, and hence the original primal problem, if strong duality holds. This new algorithm works in a similar way as the algorithm proposed in Barros et al. (1994) to solve the partial dual problem. Although the convergence rates of both algorithms are similar, the new algorithm requires slightly more restrictive assumptions to ensure a superlinear convergence rate. An important characteristic of the new algorithm is that it extends to the nonlinear case the Dinkelbach-type algorithm of Crouzeix et al. (1985) applied to the standard dual problem of a generalized linear fractional program. Moreover, the general duality results derived for the nonlinear case, yield an alternative way to derive the standard dual of a generalized linear fractional program. The numerical results, in case of quadratic-linear ratios and linear constraints, show that solving the standard dual via the new algorithm is in most cases more efficient than applying directly the Dinkelbach-type algorithm to the original generalized fractional programming problem. However, the numerical results also indicate that solving the alternative dual (Barros et al., 1994) is in general more efficient than solving the standard dual.This research was carried out at the Econometric Institute, Erasmus University Rotterdam, the Netherlands and was supported by the Tinbergen Institute Rotterdam     

Global optimization algorithm for sum of generalized polynomial ratios problem

In this paper, a global optimization algorithm is proposed for solving sum of generalized polynomial ratios problem (P) which arises in various practical problems. Due to its intrinsic difficulty, less work has been devoted to globally solve the problem (P). For such problems, we present a branch and bound algorithm. In this method, by utilizing exponent transformation and new three-level linear relaxation method, a sequence of linear relaxation programming of the initial nonconvex programming problem (P) are derived which are embedded in a branch and bound algorithm. The proposed method need not introduce new variables and constraints and it is convergent to the global minimum of prime problem by means of the subsequent solutions of a series of linear programming problems. Several numerical examples in the literatures are tested to demonstrate that the proposed algorithm can systematically solve these examples to find the approximate ?-global optimum.     

A one-phase algorithm for semi-infinite linear programming

We present an algorithm for solving a large class of semi-infinite linear programming problems. This algorithm has several advantages: it handles feasibility and optimality together; it has very weak restrictions on the constraints; it allows cuts that are not near the most violated cut; and it solves the primal and the dual problems simultaneously. We prove the convergence of this algorithm in two steps. First, we show that the algorithm can find an-optimal solution after finitely many iterations. Then, we use this result to show that it can find an optimal solution in the limit. We also estimate how good an-optimal solution is compared to an optimal solution and give an upper bound on the total number of iterations needed for finding an-optimal solution under some assumptions. This algorithm is generalized to solve a class of nonlinear semi-infinite programming problems. Applications to convex programming are discussed.     

Global optimization for the sum of generalized polynomial fractional functions

In this paper, a branch and bound approach is proposed for global optimization problem (P) of the sum of generalized polynomial fractional functions under generalized polynomial constraints, which arises in various practical problems. Due to its intrinsic difficulty, less work has been devoted to globally solving this problem. By utilizing an equivalent problem and some linear underestimating approximations, a linear relaxation programming problem of the equivalent form is obtained. Consequently, the initial non-convex nonlinear problem (P) is reduced to a sequence of linear programming problems through successively refining the feasible region of linear relaxation problem. The proposed algorithm is convergent to the global minimum of the primal problem by means of the solutions to a series of linear programming problems. Numerical results show that the proposed algorithm is feasible and can successfully be used to solve the present problem (P).     

A best-response approach for equilibrium selection in two-player generalized Nash equilibrium problems

ABSTRACT

In this paper, we propose a best-response approach to select an equilibrium in a two-player generalized Nash equilibrium problem. In our model we solve, at each of a finite number of time steps, two independent optimization problems. We prove that convergence of our Jacobi-type method, for the number of time steps going to infinity, implies the selection of the same equilibrium as in a recently introduced continuous equilibrium selection theory. Thus the presented approach is a different motivation for the existing equilibrium selection theory, and it can also be seen as a numerical method. We show convergence of our numerical scheme for some special cases of generalized Nash equilibrium problems with linear constraints and linear or quadratic cost functions.     

Preemptive scheduling and antichain polyhedra

We present a theoretical framework, which is based upon notions of ordered hypergraphs and antichain polyhedra, and which is dedicated to the combinatorial analysis of preemptive scheduling problems submitted to parallelization constraints.This framework allows us to characterize specific partially ordered structures which are such that induced preemptive scheduling problems may be solved through linear programming. To prove that, in the general case, optimal preemptive schedules may be searched inside some connected subset of the vertex set of an Antichain Polyhedron.     

Nonlinear mappings associated with the generalized linear complementarity problem

We show that the Cottle—Dantzig generalized linear complementarity problem (GLCP) is equivalent to a nonlinear complementarity problem (NLCP), a piecewise linear system of equations (PLS), a multiple objective programming problem (MOP), and a variational inequalities problem (VIP). On the basis of these equivalences, we provide an algorithm for solving problem GLCP.Project partially supported by a grant from Oak Ridge Associated Universities, TN, USA.     

On generalized operator quasi-equilibrium problems

In this paper, we will introduce the generalized operator equilibrium problem and generalized operator quasi-equilibrium problem which generalize the operator equilibrium problem due to Kazmi and Raouf [K.R. Kazmi, A. Raouf, A class of operator equilibrium problems, J. Math. Anal. Appl. 308 (2005) 554-564] into multi-valued and quasi-equilibrium problems. Using a Fan-Browder type fixed point theorem in [S. Park, Foundations of the KKM theory via coincidences of composites of upper semicontinuous maps, J. Korean Math. Soc. 31 (1994) 493-519] and an existence theorem of equilibrium for 1-person game in [X.-P. Ding, W.K. Kim, K.-K. Tan, Equilibria of non-compact generalized games with L^∗-majorized preferences, J. Math. Anal. Appl. 164 (1992) 508-517] as basic tools, we prove new existence theorems on generalized operator equilibrium problem and generalized operator quasi-equilibrium problem which includes operator equilibrium problems.     

Chance-constrained programming with fuzzy stochastic coefficients

We consider fuzzy stochastic programming problems with a crisp objective function and linear constraints whose coefficients are fuzzy random variables, in particular of type L-R. To solve this type of problems, we formulate deterministic counterparts of chance-constrained programming with fuzzy stochastic coefficients, by combining constraints on probability of satisfying constraints, as well as their possibility and necessity. We discuss the possible indices for comparing fuzzy quantities by putting together interval orders and statistical preference. We study the convexity of the set of feasible solutions under various assumptions. We also consider the case where fuzzy intervals are viewed as consonant random intervals. The particular cases of type L-R fuzzy Gaussian and discrete random variables are detailed.