Solving large quadratic assignment problems on computational grids

The quadratic assignment problem (QAP) is among the hardest combinatorial optimization problems. Some instances of size n = 30 have remained unsolved for decades. The solution of these problems requires both improvements in mathematical programming algorithms and the utilization of powerful computational platforms. In this article we describe a novel approach to solve QAPs using a state-of-the-art branch-and-bound algorithm running on a federation of geographically distributed resources known as a computational grid. Solution of QAPs of unprecedented complexity, including the nug30, kra30b, and tho30 instances, is reported. Received: September 29, 2000 / Accepted: June 5, 2001?Published online October 2, 2001     

Probabilistic programming with discrete distributions and precedence constrained knapsack polyhedra

 We consider stochastic programming problems with probabilistic constraints involving random variables with discrete distributions. They can be reformulated as large scale mixed integer programming problems with knapsack constraints. Using specific properties of stochastic programming problems and bounds on the probability of the union of events we develop new valid inequalities for these mixed integer programming problems. We also develop methods for lifting these inequalities. These procedures are used in a general iterative algorithm for solving probabilistically constrained problems. The results are illustrated with a numerical example. Received: October 8, 2000 / Accepted: August 13, 2002 Published online: September 27, 2002 Key words. stochastic programming – integer programming – valid inequalities     

Nonlinear programming without a penalty function

In this paper the solution of nonlinear programming problems by a Sequential Quadratic Programming (SQP) trust-region algorithm is considered. The aim of the present work is to promote global convergence without the need to use a penalty function. Instead, a new concept of a “filter” is introduced which allows a step to be accepted if it reduces either the objective function or the constraint violation function. Numerical tests on a wide range of test problems are very encouraging and the new algorithm compares favourably with LANCELOT and an implementation of Sl₁QP. Received: October 17, 1997 / Accepted: August 17, 2000?Published online September 3, 2001     

Global s-type error bound for the extended linear complementarity problem and applications

For the extended linear complementarity problem over an affine subspace, we first study some characterizations of (strong) column/row monotonicity and (strong) R ₀-property. We then establish global s-type error bound for this problem with the column monotonicity or R ₀-property, especially for the one with the nondegeneracy and column monotonicity, and give several equivalent formulations of such error bound without the square root term for monotone affine variational inequality. Finally, we use this error bound to derive some properties of the iterative sequence produced by smoothing methods for solving such a problem under suitable assumptions. Received: May 2, 1999 / Accepted: February 21, 2000?Published online July 20, 2000     

On generalized trade-off directions in nonconvex multiobjective optimization

Trade-off information related to Pareto optimal solutions is important in multiobjective optimization problems with conflicting objectives. Recently, the concept of trade-off directions has been introduced for convex problems. These trade-offs are characterized with the help of tangent cones. Generalized trade-off directions for nonconvex problems can be defined by replacing convex tangent cones with nonconvex contingent cones. Here we study how the convex concepts and results can be generalized into a nonconvex case. Giving up convexity naturally means that we need local instead of global analysis. Received: December 2000 / Accepted: October 2001?Published online February 14, 2002     

On consistency of stochastic dominance and mean–semideviation models

We analyze relations between two methods frequently used for modeling the choice among uncertain outcomes: stochastic dominance and mean–risk approaches. New necessary conditions for stochastic dominance are developed. These conditions compare values of a certain functional, which contains two components: the expected value of a random outcome and a risk term represented by the central semideviation of the corresponding degree. If the weight of the semideviation in the composite objective does not exceed the weight of the expected value, maximization of such a functional yields solutions which are efficient in terms of stochastic dominance. The results are illustrated graphically. Received: September 15, 1998 / Accepted: October 1, 2000?Published online December 15, 2000     

Optimality conditions for nonconvex semidefinite programming

This paper concerns nonlinear semidefinite programming problems for which no convexity assumptions can be made. We derive first- and second-order optimality conditions analogous to those for nonlinear programming. Using techniques similar to those used in nonlinear programming, we extend existing theory to cover situations where the constraint matrix is structurally sparse. The discussion covers the case when strict complementarity does not hold. The regularity conditions used are consistent with those of nonlinear programming in the sense that the conventional optimality conditions for nonlinear programming are obtained when the constraint matrix is diagonal. Received: May 15, 1998 / Accepted: April 12, 2000?Published online May 12, 2000     

A second-order bundle method to minimize the maximum eigenvalue function

In this paper we present a nonsmooth algorithm to minimize the maximum eigenvalue of matrices belonging to an affine subspace of n×n symmetric matrices. We show how a simple bundle method, the approximate eigenvalue method can be used to globalize the second-order method developed by M.L. Overton in the eighties and recently revisited in the framework of the ?-Lagrangian theory. With no additional assumption, the resulting algorithm generates a minimizing sequence. A geometrical and constructive proof is given. To prove that quadratic convergence is achieved asymptotically, some strict complementarity and non-degeneracy assumptions are needed. We also introduce new variants of bundle methods for semidefinite programming. Received: February 9, 1998 / Accepted: May 2, 2000?Published online September 20, 2000     

Relations between stochastic and parametric programming for decision problems with a random objective function

In this paper we study the relation between the general concept for an optimal solution for stochastic programming problems with a random objective function-the concept of an £-efficient solution-and the associated parametric problem, We show that it is possible under certain assumptions to obtain some or even all £-efficient solutions of the stochastic problem by solving the parametric problem with respect to a certain parameter set.     

Solving a class of semidefinite programs via nonlinear programming

In this paper, we introduce a transformation that converts a class of linear and nonlinear semidefinite programming (SDP) problems into nonlinear optimization problems. For those problems of interest, the transformation replaces matrix-valued constraints by vector-valued ones, hence reducing the number of constraints by an order of magnitude. The class of transformable problems includes instances of SDP relaxations of combinatorial optimization problems with binary variables as well as other important SDP problems. We also derive gradient formulas for the objective function of the resulting nonlinear optimization problem and show that both function and gradient evaluations have affordable complexities that effectively exploit the sparsity of the problem data. This transformation, together with the efficient gradient formulas, enables the solution of very large-scale SDP problems by gradient-based nonlinear optimization techniques. In particular, we propose a first-order log-barrier method designed for solving a class of large-scale linear SDP problems. This algorithm operates entirely within the space of the transformed problem while still maintaining close ties with both the primal and the dual of the original SDP problem. Global convergence of the algorithm is established under mild and reasonable assumptions. Received: January 5, 2000 / Accepted: October 2001?Published online February 14, 2002     

An improved rounding method and semidefinite programming relaxation for graph partition

Given an undirected graph G=(V,E) with |V|=n and an integer k between 0 and n, the maximization graph partition (MAX-GP) problem is to determine a subset S⊂V of k nodes such that an objective function w(S) is maximized. The MAX-GP problem can be formulated as a binary quadratic program and it is NP-hard. Semidefinite programming (SDP) relaxations of such quadratic programs have been used to design approximation algorithms with guaranteed performance ratios for various MAX-GP problems. Based on several earlier results, we present an improved rounding method using an SDP relaxation, and establish improved approximation ratios for several MAX-GP problems, including Dense-Subgraph, Max-Cut, Max-Not-Cut, and Max-Vertex-Cover. Received: March 10, 2000 / Accepted: July 13, 2001?Published online February 14, 2002     

Global error bounds with fractional exponents

Using the partial order induced by a proper weakly lower semicontinuous function on a reflexive Banach space X we give a sufficient condition for f to have error bounds with fractional exponents. Application is given to identify the set of such exponents for quadratic functions. Received: August 20, 1999 / Accepted: March 20, 2000?Published online July 20, 2000     

Distribution sensitivity in stochastic programming

In this paper, stochastic programming problems are viewed as parametric programs with respect to the probability distributions of the random coefficients. General results on quantitative stability in parametric optimization are used to study distribution sensitivity of stochastic programs. For recourse and chance constrained models quantitative continuity results for optimal values and optimal solution sets are proved (with respect to suitable metrics on the space of probability distributions). The results are useful to study the effect of approximations and of incomplete information in stochastic programming.This research was presented in parts at the 4th International Conference on Stochastic Programming held in Prague in September 1986.     

Upper Lipschitz behavior of solutions to perturbed. C1,1 programs

We analyze the local upper Lipschitz behavior of critical points, stationary solutions and local minimizers to parametric C ^1,1 programs. In particular, we derive a characterization of this property for the stationary solution set map without assuming the Mangasarian–Fromovitz CQ. Moreover, conditions which also ensure the persistence of solvability are given, and the special case of linear constraints is handled. The present paper takes pattern from [21] by continuing the approach via contingent derivatives of the Kojima function associated with the given optimization problem. Received: June 10, 1999 / Accepted: November 15, 1999?Published online July 20, 2000     

On existence and uniqueness of stationary points in semi-infinite optimization

The paper deals with semi-infinite optimization problems which are defined by finitely many equality constraints and infinitely many inequality constraints. We generalize the concept of strongly stable stationary points which was introduced by Kojima for finite problems; it refers to the local existence and uniqueness of a stationary point for each sufficiently small perturbed problem, where perturbations up to second order are allowed. Under the extended Mangasarian-Fromovitz constraint qualification we present equivalent conditions for the strong stability of a considered stationary point in terms of first and second derivatives of the involved functions. In particular, we discuss the case where the reduction approach is not satisfied. Received June 30, 1995 / Revised version received October 9, 1998? Published online June 11, 1999     

Characterizations, bounds, and probabilistic analysis of two complexity measures for linear programming problems

This note studies _A , a condition number used in the linear programming algorithm of Vavasis and Ye [14] whose running time depends only on the constraint matrix A∈ℝ ^m×n , and (A), a variant of another condition number due to Ye [17] that also arises in complexity analyses of linear programming problems. We provide a new characterization of _A and relate _A and (A). Furthermore, we show that if A is a standard Gaussian matrix, then E(ln _A )=O(min{mlnn,n}). Thus, the expected running time of the Vavasis-Ye algorithm for linear programming problems is bounded by a polynomial in m and n for any right-hand side and objective coefficient vectors when A is randomly generated in this way. As a corollary of the close relation between _A and (A), we show that the same bound holds for E(ln(A)). Received: September 1998 / Accepted: September 2000?Published online January 17, 2001     

Discrete -convex extremal distributions: Theory and applications

Given a nondegenerate moment space with s fixed moments, explicit formulas for the discrete s-convex extremal distribution have been derived for s=1,2,3 (see [M. Denuit, Cl. Lefèvre, Some new classes of stochastic order relations among arithmetic random variables, with applications in actuarial sciences, Insurance Math. Econom. 20 (1997) 197–214]). If s=4, only the maximal distribution is known (see [M. Denuit, Cl. Lefèvre, M. Mesfioui, On s-convex stochastic extrema for arithmetic risks, Insurance Math. Econom. 25 (1999) 143–155]). This work goes beyond this limitation and proposes a method for deriving explicit expressions for general nonnegative integer s. In particular, we derive explicitly the discrete 4-convex minimal distribution. For illustration, we show how this theory allows one to bound the probability of extinction in a Galton–Watson branching process. The results are also applied to derive bounds for the probability of ruin in the compound binomial and Poisson insurance risk models.     

A trust region method based on interior point techniques for nonlinear programming

An algorithm for minimizing a nonlinear function subject to nonlinear inequality constraints is described. It applies sequential quadratic programming techniques to a sequence of barrier problems, and uses trust regions to ensure the robustness of the iteration and to allow the direct use of second order derivatives. This framework permits primal and primal-dual steps, but the paper focuses on the primal version of the new algorithm. An analysis of the convergence properties of this method is presented. Received: May 1996 / Accepted: August 18, 2000?Published online October 18, 2000     

A new inexact alternating directions method for monotone variational inequalities

The alternating directions method (ADM) is an effective method for solving a class of variational inequalities (VI) when the proximal and penalty parameters in sub-VI problems are properly selected. In this paper, we propose a new ADM method which needs to solve two strongly monotone sub-VI problems in each iteration approximately and allows the parameters to vary from iteration to iteration. The convergence of the proposed ADM method is proved under quite mild assumptions and flexible parameter conditions. Received: January 4, 2000 / Accepted: October 2001?Published online February 14, 2002     

A stochastic programming model using an endogenously determined worst case risk measure for dynamic asset allocation

We present a new approach to asset allocation with transaction costs. A multiperiod stochastic linear programming model is developed where the risk is based on the worst case payoff that is endogenously determined by the model that balances expected return and risk. Utilizing portfolio protection and dynamic hedging, an investment portfolio similar to an option-like payoff structure on the initial investment portfolio is characterized. The relative changes in the expected terminal wealth, worst case payoff, and risk aversion, are studied theoretically and illustrated using a numerical example. This model dominates a static mean-variance model when the optimal portfolios are evaluated by the Sharpe ratio. Received: August 15, 1999 / Accepted: October 1, 2000?Published online December 15, 2000