Robust linear optimization under general norms

We explicitly characterize the robust counterpart of a linear programming problem with uncertainty set described by an arbitrary norm. Our approach encompasses several approaches from the literature and provides guarantees for constraint violation under probabilistic models that allow arbitrary dependencies in the distribution of the uncertain coefficients.     

A new formulation of some discrete-time stochastic-parameter state estimation problems

Linear unbiased full-order state estimation problem for discrete-time models with stochastic parameters and additive finite energy type disturbance signals is reformulated in terms of linear matrix inequalities. Two estimation problems that are considered are the design for mean-square bounded estimation error and the design for the mean-square stochastic version of the suboptimal H_∞ estimator. These two designs are shown to apply to both the estimation with random sensor delay and estimation under observation uncertainty.     

Test sets for integer programs

In this paper I discuss various properties of the simplicial complex of maximal lattice free bodies associated with a matrixA. If the matrix satisfies some mild conditions, and isgeneric, the edges of the complex form the minimal test set for the family of integer programs obtained by selecting a particular row ofA as the objective function, and using the remaining rows to impose constraints on the integer variables.     

Volumetric path following algorithms for linear programming

We consider the construction of small step path following algorithms using volumetric, and mixed volumetric-logarithmic, barriers. We establish quadratic convergence of a volumetric centering measure using pure Newton steps, enabling us to use relatively standard proof techniques for several subsequently needed results. Using a mixed volumetric-logarithmic barrier we obtain an O(n ^1/4 m ^1/4 L) iteration algorithm for linear programs withn variables andm inequality constraints, providing an alternative derivation for results first obtained by Vaidya and Atkinson. In addition, we show that the same iteration complexity can be attained while holding the work per iteration to O(n ² m), as opposed to O(nm ²), operations, by avoiding use of the true Hessian of the volumetric barrier. Our analysis also provides a simplified proof of self-concordancy of the volumetric and mixed volumetric-logarithmic barriers, originally due to Nesterov and Nemirovskii. This paper was first presented at the 1994 Faculty Research Seminar “Optimization in Theory and Practice”, at the University of Iowa Center for Advanced Studies.     

再论Pedoe不等式的高维推广及应用

本文对欧氏空间E~n中的两个n维单形,给出了著名的Pedoe不等式的一个实质性推广,并讨论了它的应用.     

一类非线性拟变分不等式

本文利用伪单调算子理论研究如下变分不等式问题：求ｘ∈Ｍ，使得〈Ａｘ，ｙ－ｘ〉＋〈Ｇｘ，ｙ－ｘ〉≥〈ｆ，ｙ－ｘ〉，?ｙ∈Ｍ．并将所得结果应用于拟线性椭圆型边值问题的求解．     

Inequalities based on a generalization of concavity

The concept of concavity is generalized to functions, , satisfying order differential inequalities, , and homogeneous two-point boundary conditions, , for some . A piecewise polynomial, which bounds the function, , below, is constructed, and then is employed to obtain that , where max and denotes the supremum norm. An analogous inequality for a related Green's function is also obtained. These inequalities are useful in applications of certain cone theoretic fixed point theorems.

     

一类基于广义梯度的求解非线性互补问题的算法

1 引言非线性互补问题(下称NCP)的应用十分广泛,自本世纪六十年代以来,人们对这一问题解的存在唯一性、灵敏度分析、算法与应用等方面进行深入的研究,取得很大的进展。关于NCP的解法通常是将其化为序列线性互补问题,而对线性问题则有若干现成算法,如Lemke算法。但一般说来,此类方法工作量大,效果也难以令人满意。J.S.Pang于七十年代提出了B-可微算法,即将NCP转化为一个B-可微函数的零点问题。近年来提出的一些算法大多属于此类方法。 本文提出的算法也属于B-可微算法,虽同是从广义梯度出发,但不同的是,我们不是通过二次规划而是通过线性规划来获得搜寻方向。由于所涉及的线性规划问题特别的简单,我们可以很快而方便地求得其解,所以算法简易可行,速度较快。     

A Convex Envelope Formula for Multilinear Functions

Convex envelopes of multilinear functions on a unit hypercube arepolyhedral. This well-known fact makes the convex envelopeapproximation very useful in the linearization of non-linear 0–1programming problems and in global bilinear optimization. This paperpresents necessary and sufficient conditions for a convex envelope to be apolyhedral function and illustrates how these conditions may be used inconstructing of convex envelopes. The main result of the paper is a simpleanalytical formula, which defines some faces of the convex envelope of amultilinear function. This formula proves to be a generalization of the wellknown convex envelope formula for multilinear monomial functions.     

A cone programming approach to the bilinear matrix inequality problem and its geometry

We discuss an approach for solving the Bilinear Matrix Inequality (BMI) based on its connections with certain problems defined over matrix cones. These problems are, among others, the cone generalization of the linear programming (LP) and the linear complementarity problem (LCP) (referred to as the Cone-LP and the Cone-LCP, respectively). Specifically, we show that solving a given BMI is equivalent to examining the solution set of a suitably constructed Cone-LP or Cone-LCP. This approach facilitates our understanding of the geometry of the BMI and opens up new avenues for the development of the computational procedures for its solution. Research supported in part by the National Science Foundation under Grant CCR-9222734.