On the Positivity of the Coefficients of a Certain Polynomial Defined by Two Positive Definite Matrices

It is shown that the polynomialp(t) = Tr[(A+tB)^m]has positive coefficients when m = 6 and A and B are any two 3-by-3 complex Hermitian positive definite matrices. This case is the first that is not covered by prior, general results. This problem arises from a conjecture raised by Bessis, Moussa, and Villani in connection with a long-standing problem in theoretical physics. The full conjecture, as shown recently by Lieb and Seiringer, is equivalent to p(t) having positive coefficients for any m and any two n-by-n positive definite matrices. We show that, generally, the question in the real case reduces to that of singular A and B, and this is a key part of our proof.     

Superlinear Convergence of a Newton-Type Algorithm for Monotone Equations

We consider the problem of finding solutions of systems of monotone equations. The Newton-type algorithm proposed in Ref. 1 has a very nice global convergence property in that the whole sequence of iterates generated by this algorithm converges to a solution, if it exists. Superlinear convergence of this algorithm is obtained under a standard nonsingularity assumption. The nonsingularity condition implies that the problem has a unique solution; thus, for a problem with more than one solution, such a nonsingularity condition cannot hold. In this paper, we show that the superlinear convergence of this algorithm still holds under a local error-bound assumption that is weaker than the standard nonsingularity condition. The local error-bound condition may hold even for problems with nonunique solutions. As an application, we obtain a Newton algorithm with very nice global and superlinear convergence for the minimum norm solution of linear programs.This research was supported by the Singapore-MIT Alliance and the Australian Research Council.     

信息熵增量最小化准则在供应链中的应用

本文研究了在考虑利润最大化准则和信息熵增量最小准则下，既能满足了利润最大化，又要增加利润可得性，销售商如何确定订购量的问题。数字实验表明：考虑双重准则得到的策略比仅考虑利润最大化准则得到的策略更好，可以使供应链、销售商及制造商都受益。     

IMPROVEMENT OF THE ALGORITHM PRINCIPLES FOR MINIMIZATION OF MULTI-OUTPUT FUNCTIONS

In this paper,the application of extraction principle for logic function minimiza-tion to multi-output case is studied.A defect in original algorithm in dealing with multi-outputextrema is made up,and on this base,three kinds of less-than terms in different conditions aredefined.In addition,three kinds of generalized definition of less-than terms are given,so as to findout more efficiently the covers with minimal number of terms and irredundant function outputs.This work makes the multi-output extraction principle closer to perfection.An algorithm basedon the work is presented.     

An efficient algorithm for solving the discrete minisum problem

For a simple nonsmooth minimization problem, the discrete minisum problem, an efficient hybrid method is presented. This method consists of an ‘inner algorithm’ (Newton method) for solving the necessary optimality conditions and a gradient-type ‘outer algorithm’. By this way we combine the large convergence area of the gradient technique with the fast final convergence of the Newton method.     

On the number of registers needed to evaluate arithmetic expressions

The question of how many temporary storage registers are needed to evaluate compiled arithmetic and masking expressions is discussed. It is assumed that any combination of left-to-right, right-to-left, top-to-bottom, and bottom-to-top techniques may be used to evaluate an expression, but that no factoring or re-arranging of the expression may occur. On this basis, the maximum number of registers needed to evaluate nonparenthesized expressions isN+1, withN the number of dyadic operator precedence levels. For parenthesized expressions with a maximum ofK nested parenthetical subexpressions, the maximum number of registers needed is (K+1)N+1.     

Local minima for indefinite quadratic knapsack problems

We consider the complexity of finding a local minimum for the nonconvex Quadratic Knapsack Problem. Global minimization for this example of quadratic programming is NP-hard. Moré and Vavasis have investigated the complexity of local minimization for the strictly concave case of QKP; here we extend their algorithm to the general indefinite case. Our main result is an algorithm that computes a local minimum in O(n(logn)²) steps. Our approach involves eliminating all but one of the convex variables through parametrization, yielding a nondifferentiable problem. We use a technique from computational geometry to address the nondifferentiable problem.Supported in part by the Applied Mathematical Sciences subprogram of the Office of Energy Research, Department of Energy, under contract W-31-109-Eng-38, in part by a Fannie and John Hertz Foundation graduate fellowship, and in part by Department of Energy grant DE-FG02-86ER25013.A000.     

不可微非线性规划的 L_1-精确罚函数法

本文提出求解不可微非线性不等式约束极小化问题的 L_1-精确罚函数算法。在有关函数为半光滑的假设下,给出了收敛性结果。     

On the convergence of a class of derivative-free minimization algorithms

A convergence analysis is presented for a general class of derivative-free algorithms for minimizing a functionf(x) for which the analytic form of the gradient and the Hessian is impractical to obtain. The class of algorithms accepts finite-difference approximation to the gradient, with stepsizes chosen in such a way that the length of the stepsize must meet two conditions involving the previous stepsize and the distance from the last estimate of the solution to the current estimate. The algorithms also maintain an approximation to the second-derivative matrix and require that the change inx made at each iteration be subject to a bound that is also revised automatically. The convergence theorems have the features that the starting pointx ¹ need not be close to the true solution andf(x) need not be convex. Furthermore, despite the fact that the second-derivative approximation may not converge to the true Hessian at the solution, the rate of convergence is still Q-superlinear. The theorry is also shown to be applicable to a modification of Powell's dog-leg algorithm.     

正例学习的一个启发式算法

本文基于多值逻辑函数极小化提出一种正例学习问题，并对这一正例学习问题给出一个启发式学习算法。同现存的示例学习方法相比，本文算法是基于演绎推理的，可对大量信息进行保真压缩，该算法具有简单，快速和易于实现的特点，本文用两个实例一焊接工艺自动设计知识获取和布尔函数极小化，将本算法同示例式归纳学习系统ＡＱ１５和布尔函数极小化系统ＳＷＴ进行了比较。