Worst-case distribution analysis of stochastic programs

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.     

了本岛津产ICPl000型等离子体发射光谱仪的改造方法（软件部分）

提出了日本岛津1000型ICP改造后的软件设计方法，详细介绍了核心控制程序软件、服务程序框图和终端操作界面，阐明了标定放大系数、制作校准曲线的原理和方法。为该种大型精密光学仪器的改造做了有益的尝试。     

解线性规划问题的梯度投影法

本文叙述了一个求解线性规划问题的梯度投影法,导出了投影矩阵的递推公式,利用此公式可大大减少每次迭代所需的计算量。实例计算表明,本文给出的算法是一有效的算法,在某些方面它要优于Karmarkar算法和单纯形法。     

On the Glivenko-Cantelli problem in stochastic programming: Mixed-integer linear recourse

Expected recourse functions in linear two-stage stochastic programs with mixed-integer second stage are approximated by estimating the underlying probability distribution via empirical measures. Under mild conditions, almost sure uniform convergence of the empirical means to the original expected recourse function is established.     

Optimal objective function approximation for separable convex quadratic programming

We present an optimal piecewise-linear approximation method for the objective function of separable convex quadratic programs. The method provides guidelines on how many grid points to use and how to position them for a piecewise-linear approximation if the error induced by the approximation is to be bounded a priori.Corresponding author.     

The pivot and probe algorithm for solving a linear program

In [7] we defined acandidate constraint as one which, for at least one pivot step, contains a potential pivot, discovered that most constraints are never candidate, and devised a modification of the simplex method in which only constraints which are currently candidates are updated. In this paper we present another way to take advantage of this fact. We begin by solving a relaxed linear program consisting of the constraints of the original problem which are initially candidates. Its solution gives an upper bound to the value of the original problem. We also introduce the idea of a probe, that is, a line segment joining two vectors for the primal problem, one of which is primal feasible, and use it to identify a most violated constraint; at the same time this gives a lower bound to the objective value of the original problem. This violated constraint is added to the relaxed problem which is solved again, which gives a new upper bound etc. We present computational experience indicating that time savings of 50–80% over the simplex method can be obtained by this method, which we call PAPA, the Pivot and Probe Algorithm. This report was prepared as part of the activities of the Management Science Research Group, Carnegie-Mellon University, under Contract No. N00014-75-C-0621 NR 047-048 with the U.S. Office of Naval Research. Reproduction in whole or part is permitted for any purpose of the U.S. Government.     

A polynomially bounded algorithm for a singly constrained quadratic program

This paper presents a characterization of the solutions of a singly constrained quadratic program. This characterization is then used in the development of a polynomially bounded algorithm for this class of problems.     

Entropy in linear programs

This paper treats entropy constrained linear programs from modelling as well as computational aspects. The optimal solutions to linear programs with one additional entropy constraint are expressed in terms of Lagrange-multipliers. Conditions for uniqueness are given. Sensitivity and duality are studied. The Newton—Kantorovich method is used to obtain a locally convergent iterative procedure. Related problems based on maximum entropy or minimum information are discussed.     

Solving generalized equations via homotopies

Global Newton methods for computing solutions of nonlinear systems of equations have recently received a great deal of attention. By using the theory of generalized equations, a homotopy method is proposed to solve problems arising in complementarity and mathematical programming, as well as in variational inequalities. We introduce the concepts of generalized homotopies and regular values, characterize the solution sets of such generalized homotopies and prove, under boundary conditions similar to Smale’s [10], the existence of a homotopy path which contains an odd number of solutions to the problem. We related our homotopy path to the Newton method for generalized equations developed by Josephy [3]. An interpretation of our results for the nonlinear programming problem will be given.     

On the convergence of cutting plane algorithms for a class of nonconvex mathematical programs

We discuss the convergence of cutting plane algorithms for a class of nonconvex programs called the Generalized Lattice Point Problems (GLPP). A set of sufficient conditions which guarantee finite convergence are presented. Although these conditions are usually difficult to enforce in a practical implementation, they do illustrate the various factors that must be involved in a convergent rudimentary cutting plane algorithm. A striking example of nonconvergence (in which no subsequence converges to a feasible solution, even when seemingly strong cutting planes are used), is presented to show the effect of neglecting one such factor. We give an application of our analysis to problems with multiple choice constraints and finally discuss a modification of cutting plane algorithms so as to make finite convergence more readily implementable.