Equivalence of two linear programming relaxations for broadcast scheduling

A server needs to compute a broadcast schedule for n pages whose request times are known in advance. Outputting a page satisfies all outstanding requests for the page. The goal is to minimize the average waiting time of a client. In this paper, we show the equivalence of two apparently different relaxations that have been considered for this problem.     

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.     

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.     

线性同胚于星象函数的一族解析函数

本文定义了线性同胚于星象函数的－族解析函数Ａ（，α）．我们导出Ａ（α）中函数的积分表达式：借助算子理论研究Ａ（，α）族的包含关系并确定它的闭凸包、闭凸包的极值点和它的支撑点；利用一个阶微分从属证明关于实部的二个不等式．最后，我们还证明Ａ（，α）中函数的偏差定理．     

某些级数的无理性

本文证明了某些与二阶线性递推数列有关的无穷级数的和的无理性．特别，推广了某些与Ｆｉｂｏｎａｃｃｉ和Ｌｕｃａｓ数列有关的无理性结果     

THE ALGEBRAIC CRITERION OF UNCONDITIONAL STABILITY OF CONSTANT LINEAR SYSTEMS

1IntroductionandLemmasConsidern-dimentionalconstantlinearcontrolsystemwithdelaywhereA(1)=(ail))...,A(2)=(aj:))...,B(1)=(6j:))...,B(2)~(hi:))...,C=(oil)...areconstantmatrixesandX(t)~(xl(t),''5x.(t))',U(t)=(m(t),...9u.(t))',y(t)=(yi(t),'',y.(t))'arevector…     

增加试验数据对岭估计的均方误差的影响

在线性模型中,对于回归系数的岭估计和广义岭估计,本文给出了选择岭参数的条件,在此条件下,岭估计和广义岭估计不仅能改善LS估计,而且增加试验数据时,它们的均方误差都会减少。同时,本文将增加试验数据换成增加附加信息,从而讨论了附加信息对混合岭估计和混合广义岭估计的影响问题。     

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.     

Markov games with incomplete information

We consider zero-sum Markov games with incomplete information. Here, the second player is never informed about the current state of the underlying Markov chain. The existence of a value and of optimal strategies for both players is shown. In particular, we present finite algorithms for computing optimal strategies for the informed and uninformed player. The algorithms are based on linear programming results.