Reduction of indefinite quadratic programs to bilinear programs

Indefinite quadratic programs with quadratic constraints can be reduced to bilinear programs with bilinear constraints by duplication of variables. Such reductions are studied in which: (i) the number of additional variables is minimum or (ii) the number of complicating variables, i.e., variables to be fixed in order to obtain a linear program, in the resulting bilinear program is minimum. These two problems are shown to be equivalent to a maximum bipartite subgraph and a maximum stable set problem respectively in a graph associated with the quadratic program. Non-polynomial but practically efficient algorithms for both reductions are thus obtaine.d Reduction of more general global optimization problems than quadratic programs to bilinear programs is also briefly discussed.     

Approximation theory for stochastic variational and Ky Fan inequalities in finite dimensions

The ideas of approximation and continuity have been extensively investigated both for optimization problems and variational inequalities. In this paper, we study approximation issues for a class of VIs, called Stochastic Variational Inequalities (SVIs), that arise, for example, in stochastic programming and portfolio choice problems. SVI problems are special cases of a more general class of problems that we will study first, called Stochastic Ky Fan Inequalities (SKFIs). We also analyze the role of monotonicity in the analysis of both SVIs and SKFIs. Our interest in these problems is motivated by recent research in the theory of portfolio choice for investors who are not classical expected utility maximizers.     

Roof duality for polynomial 0–1 optimization

The purpose of this note is to generalize the roof duality theory of Hammer, Hansen and Simeone to the case of polynomial 0–1 optimization (0-1PP). By reformulating 0-1PP and expanding some of their definitions, we show that most of the results for quadratic 0–1 problem (0-1QP) can be extended to the general polynomial case.     

Computing Karmarkar projections quickly

The paper presents a numerical method for computing the projections for Karmarkar's new algorithm for linear programming. The method is simple to implement, fully exploits sparsity, and appears in limited experimentation to have good stability properties. Preliminary numerical experience indicates that the method promises advantages over methods that refactor a matrix at every iteration.Research sponsored by the Air Force Office of Scientific Research, Air Force Systems Command, USAF under Grant AFOSR-86-0170. The US Government is authorized to reproduce and distribute reprints for Governmental purposes notwithstanding any copyright notation thereon.This work was initiated while the author was at the Graduate School of Administration, University of California, Davis, Davis, California.     

Directional derivatives of optimal value functions in mathematical programming

This note discusses the existence of the directional derivatives of the optimal value functions in a class of nonlinear programming problems and gives the expressions of the directional derivatives. In the study, it is not assumed that the optimal set at the point discussed is not empty. Many well-known results of this area can be derived as special cases of the main theorems of this note.This research was supported by the National Science Foundation of China. The authors would like to thank Professor A. V. Fiacco and the referees for their helpful suggestions.     

On confidence intervals from simulation of finite Markov chains

Consider a finite state irreducible Markov reward chain. It is shown that there exist simulation estimates and confidence intervals for the expected first passage times and rewards as well as the expected average reward, with 100% coverage probability. The length of the confidence intervals converges to zero with probability one as the sample size increases; it also satisfies a large deviations property.     

Some geometric results in semidefinite programming

The purpose of this paper is to develop certain geometric results concerning the feasible regions of Semidefinite Programs, called hereSpectrahedra.We first develop a characterization for the faces of spectrahedra. More specifically, given a pointx in a spectrahedron, we derive an expression for the minimal face containingx. Among other things, this is shown to yield characterizations for extreme points and extreme rays of spectrahedra. We then introduce the notion of an algebraic polar of a spectrahedron, and present its relation to the usual geometric polar.Support received under the grants: NSF-STC91-19999 (DIMACS) and Air Force grant F49620-93-1-0041 (RUTCOR).Support from the NSF grant ECS-9111548 is acknowledged.