On Tutte polynomial expansion formulas in perspectives of matroids and oriented matroids

We introduce the active partition of the ground set of an oriented matroid perspective (or morphism, or quotient, or strong map) on a linearly ordered ground set. The reorientations obtained by arbitrarily reorienting parts of the active partition share the same active partition. This yields an equivalence relation for the set of reorientations of an oriented matroid perspective, whose classes are enumerated by coefficients of the Tutte polynomial, and a remarkable partition of the set of reorientations into Boolean lattices, from which we get a short direct proof of a 4-variable expansion formula for the Tutte polynomial in terms of orientation activities. This formula was given in the last unpublished preprint by Michel Las Vergnas; the above equivalence relation and notion of active partition generalize a former construction in oriented matroids by Michel Las Vergnas and the author; and the possibility of such a proof technique in perspectives was announced in the aforementioned preprint. We also briefly highlight how the 5-variable expansion of the Tutte polynomial in terms of subset activities in matroid perspectives comes in a similar way from the known partition of the power set of the ground set into Boolean lattices related to subset activities (and we complete the proof with a property which was missing in the literature). In particular, the paper applies to matroids and oriented matroids on a linearly ordered ground set, and applies to graph and directed graph homomorphisms on a linearly ordered edge-set.     

考虑偏差值的中立型区间交叉效率研究

在不确定性环境下,当决策单元(DMU)的投入产出数据为区间数形式时,为解决决策单元之间既不是合作也不是竞争关系时的交叉评价问题,本文提出一种中立型区间交叉效率模型。从所有被评价者的角度出发解决评价权重的选取问题,以决策单元投入得分的平均偏差与产出得分的平均偏差之和最小化为目标,建立决策单元在最佳和最差两种生产状态下的中立型区间交叉效率模型。在本文提出的中立型模型视角下,DMU的投入得分平均偏差和产出得分平均偏差之和达到最小。算例结果表明该中立型区间交叉效率模型的有效性,解决了不确定性环境下的交叉评价问题,保证评价的客观公正,更加符合现实。     

Low Mach number limit of inviscid Hookean elastodynamics

The low Mach number limit of inviscid Hookean elastodynamic equations is rigorously proved in bounded domain, whole space and periodic domain, respectively. The uniform existence of smooth solutions and convergence results as the Mach number tends to zero are obtained in three different domains.     

On stability concepts in nonlinear programming

Kojima's strong stability of stationary solutions can be characterized by means of first and second order terms. We treat the problem whether there is a characterization of the stability concept allowing perturbations of the objective function only, keeping the feasible set unchanged. If the feasible set is a convex polyhedron, then there exists a characterization which is in fact weaker than that one of strong stability. However, in general it appears that data of first and second order do not characterize that kind of stability. As an interpretation we have that the strong stability is the only concept of stability which both admits a characterization and works for large problem classes.Supported by the Deutsche Forschungsgemeinschaft, Graduiertenkolleg Analyse und Konstruktion in der Mathematik.Partial support under Support Center for Advanced Telecommunications Technology Research.     

Dynamic complexity of optimal paths and discount factors for strongly concave problems

We study the relationship between the dynamical complexity of optimal paths and the discount factor in general infinite-horizon discrete-time concave problems. Given a dynamic systemx _t+1=h(x _t ), defined on the state space, we find two discount factors 0 < ^{* **} < 1 having the following properties. For any fixed discount factor 0 < < ^*, the dynamic system is the solution to some concave problem. For any discount factor ^** < < 1, the dynamic system is not the solution to any strongly concave problem. We prove that the upper bound ^** is a decreasing function of the topological entropy of the dynamic system. Different upper bounds are also discussed.This research was partially supported by MURST, National Group on Nonlinear dynamics in Economics and Social Sciences. The author would like to thank two anonymous referees for helpful comments and suggestions.     

The Newton modified barrier method for QP problems

The Modified Barrier Functions (MBF) have elements of both Classical Lagrangians (CL) and Classical Barrier Functions (CBF). The MBF methods find an unconstrained minimizer of some smooth barrier function in primal space and then update the Lagrange multipliers, while the barrier parameter either remains fixed or can be updated at each step. The numerical realization of the MBF method leads to the Newton MBF method, where the primal minimizer is found by using Newton's method. This minimizer is then used to update the Lagrange multipliers. In this paper, we examine the Newton MBF method for the Quadratic Programming (QP) problem. It will be shown that under standard second-order optimality conditions, there is a ball around the primal solution and a cut cone in the dual space such that for a set of Lagrange multipliers in this cut cone, the method converges quadratically to the primal minimizer from any point in the aforementioned ball, and continues, to do so after each Lagrange multiplier update. The Lagrange multipliers remain within the cut cone and converge linearly to their optimal values. Any point in this ball will be called a hot start. Starting at such a hot start, at mostO(In In ^-1) Newton steps are sufficient to perform the primal minimization which is necessary for the Lagrange multiplier update. Here, >0 is the desired accuracy. Because of the linear convergence of the Lagrange multipliers, this means that onlyO(In ^-1)O(In In ^-1) Newton steps are required to reach an -approximation to the solution from any hot start. In order to reach the hot start, one has to perform Newton steps, wherem characterizes the size of the problem andC>0 is the condition number of the QP problem. This condition number will be characterized explicitly in terms of key parameters of the QP problem, which in turn depend on the input data and the size of the problem.Partially supported by NASA Grant NAG3-1397 and National Science Foundation Grant DMS-9403218.     

Chapter 15 DEA/AR analysis of the 1988–1989 performance of the Nanjing textiles corporation

This article employs new data envelopment analysis/assurance region (DEA/AR) methods to evaluate the efficiency of the 35 textile factories of the Nanjing Textiles Corporation (NTC), Nanjing, China. The returns to scale (RTS) of these factories were studied without assuming that the optimal DEA solutions were unique. All DMUs are identified with pointsE (Extreme Efficient),E (Efficient but not an extreme point) andF (Frontier but not efficient). We then further identify the nonfrontier DMUs with pointsNE, NE andNF according to whether they are projected onto a point inE, E, orF en route to evaluating their performances. All of the inefficient factories were in classNF and had unique optimal primal-dual solution pairs. Consequently, the solution pairs satisfy the strong complementary slackness condition (SCSC). Application of cone-ratio (CR) ARs reduced significantly the number of factories in classE, and showed that some AR-efficient factories were more flexible in adopting the mixture of central planning and market economies that China currently is trying to use. Also, linked-cone (LC) ARs were applied to measure maximum and minimum profit ratios. The SCSC multiplier space approach was utilized to analyze the sensitivity of the efficiency results to potential errors in the data with and without ARs. The results in this article suggest that collective units had a better performance than state-owned units in the two consecutive years analyzed.This paper was written while the author was at the School of Economics and Management, Southeast University, Nanjing 210018, P.R. China.     

The law of the solution to a nonlinear hyperbolicSPDE

Let { _s,t ,(s,t ₊ ² } be a white noise on ₊ ² . We consider the hyperbolic stochastic partial differential equation {ie863-3} The purpose of this paper is to study the law of the solution to this equation. We analyze the existence and smoothness of the density using the tools of Malliavin Calculus. Finally we prove a large deviation principle on the space of continuous functions, for the family of probabilities obtained by perturbation of the noise in the equation.This work has been partially supported by the grant of the DGICYT No. PB 930052 and the EU Science project CT 910459.     

Geometric indices and the Alexander polynomial of a knot

It is well-known that any Laurent polynomial satisfying and is the Alexander polynomial of a knot in . We show that can be realized by a knot which has the following properties simultaneously: (i) tunnel number 1; (ii) bridge index 3; and (iii) unknotting number 1.

     

Realization of fixed point sets

Letf:XX be a selfmap of a compact connected polyhedron, andA a nonempty closed subset ofX. In this paper, we shall deal with the question whether or not there is a mapg:XX homotopic tof such that the fixed point set Fixg ofg equalsA. We introduce a necessary condition for the existence of such a mapg. It is shown that this condition is easy to check, and hence some sufficient conditions are obtained.Partially supported by the Natural Science Foundation of Liaoning University.