具有专用机与通用机的多组工件的Cmax问题

本文讨论了一类特殊的排序问题；具有专用机与通用机的多组工件的Ｃｍａｘ问题。文中给出了“ＬＰＴ－ＬＳＭＴ”算法，并对最差情况下的性能指标给出了严格的界。     

具有m台通用机的P∥Cmax问题的两种算法

本文讨论了具有二台专用机，ｍ台通用机的两组工件的Ｐ∥Ｃｍａｘ问题，提出了ＬＳＭＴ和ＭＬＰＴＦ一种近似算法，并分别分析了在最差情况下的性能指标的界 。     

两台平行机的实时到达在线排序

本文考虑一的的在线平行机排序模型－－实时到达在线问题,该模型中,工件是陆续到达的,工件的个数及到达时间是事先未知的,而且只有当工件到达,才知其加工时间,所求目标是使所有工件都加工完的时间达到最小,对两台平行机的情形,Ｃｈｅｎ与Ｖｅｓｔｊｅｎｓ给出近似比为３／２的线ＬＰＴ算法,并证明了不存在近似小于（５－√５）／２的算法,我们利用黄金分割数设计了一个 算法,其近似比不超过（１８－√５）／１１。     

求解界约束优化的一种新的非单调谱投影梯度法

本文给出求解界约束优化问题的一种新的非单调谱投影梯度算法. 该算法是将谱投影梯度算法与Zhang and Hager [SIAM Journal on Optimization,2004,4（4）：1043-1056]提出的非单调线搜索结合得到的方法. 在合理的假设条件下,证明了算法的全局收敛性.数值实验结果表明,与已有的界约束优化问题的谱投影梯度法比较,利用本文给出的算法求解界约束优化问题是有竞争力的.     

带单服务器的自由作业排序问题的启发式算法

研究带单服务器的自由作业排序问题,证明在只有两台机器且加工时间相同的情况下该问题是强NP-困难的,引入了求解该问题的启发式算法,证明该算法的紧界为5/4.在具有m台机器的情况下,给出相应的启发式算法,其紧界为2-3/(m+2).     

有上下界网络最大流与最小截问题

为了便于建立与有上下界网络最大流与最小截问题有关的决策支持系统，本文给出一个求有上下界网络最大流与最小截的数值算法，证明了算法的理论依据，并举例说明了算法在堵塞流理论中的应用。该算法能判定问题是否有可行解，在问题有可行解的情况下能求得问题的最优解。该算法具有易于编程实现、收敛性好等优点。数值实验表明该算法有较高的计算效率，可用于求解最小饱和流问题。     

P‖Cmin随机算法研究

本文研究了P‖Cmin的随机算法及其最坏情况界，我们给出了Pm‖Cmin在线排序问题新的随机上界，并给出了P2‖Cmin的最好随机算法，其最坏情况界为2／3。对P2‖Cmin已知工件加工时间递减半在线模型，我们给出了一最坏情况界为6／7的随机算法并证明了它为最好的。     

基于局部self-concordant障碍函数的全牛顿步多项式时间算法

由Nesterov和Nemirovski[4]创立的self-concordant障碍函数理论为解线性和凸优化问题提供了多项式时间内点算法.根据self-concordant障碍函数的参数,就可以分析内点算法的复杂性.在这篇文章中,我们介绍了基于核函数的局部self-concordant障碍函数,它在线性优化问题的中心路径及其邻域内满足self-concordant性质.通过求解此障碍函数的局部参数值,我们得到了求解线性规划问题的基于此局部Self-concordant障碍函数的纯牛顿步内点算法的理论迭代界.此迭代界与目前已知的最好的理论迭代界是一致的.     

解P_0非线性互补问题的光滑Levenberg-Marquardt方法

本文研究了一个P0非线性互补问题.利用信赖域技术获得了求解该问题的光滑Levenberg-Marquardt算法,该算法在一定条件下具有全局性.利用局部误差界还获得了该算法的超线性和二次收敛.数值结果表明该算法是有效的.     

一个解半正定规划问题的基于广义对数障碍函数的原始对偶内点算法

本文对经典对数障碍函数推广,给出了一个广义对数障碍函数.基于这个广义对数障碍函数设计了解半正定规划问题的原始-对偶内点算法.分析了该算法的复杂性,得到了一个理论迭代界,它与已有的基于经典对数障碍函数的算法的理论迭代界一致.同时,并给出了一个数值算例,阐明了函数的参数对算法运行时间的影响.     

New upper solution bounds of the discrete algebraic Riccati matrix equation

In this note, we present upper matrix bounds for the solution of the discrete algebraic Riccati equation (DARE). Using the matrix bound of Theorem 2.2, we then give several eigenvalue upper bounds for the solution of the DARE and make comparisons with existing results. The advantage of our results over existing upper bounds is that the new upper bounds of Theorem 2.2 and Corollary 2.1 are always calculated if the stabilizing solution of the DARE exists, whilst all existing upper matrix bounds might not be calculated because they have been derived under stronger conditions. Finally, we give numerical examples to demonstrate the effectiveness of the derived results.     

Trigonometric spline and spectral bounds for the solution of linear time-periodic systems

Linear time-periodic systems arise whenever a nonlinear system is linearized about a periodic trajectory. Examples include anisotropic rotor-bearing systems and parametrically excited systems. The structure of the solution to linear time-periodic systems is known due to Floquet’s Theorem. We use this information to derive a new norm which yields two-sided bounds on the solution and in this norm vibrations of the solution are suppressed. The obtained results are a generalization for linear time-invariant systems. Since Floquet’s Theorem is non-constructive, the applicability of the aforementioned results suffers in general from an unknown Floquet normal form. Hence, we discuss trigonometric splines and spectral methods that are both equipped with rigorous bounds on the solution. The methodology differs systematically for the two methods. While in the first method the solution is approximated by trigonometric splines and the upper bound depends on the approximation quality, in the second method the linear time-periodic system is approximated and its solution is represented as an infinite series. Depending on the smoothness of the time-periodic system, we formulate two upper bounds which incorporate the approximation error of the linear time-periodic system and the truncation error of the series representation. Rigorous bounds on the solution are necessary whenever reliable results are needed, and hence they can support the analysis and, e.g., stability or robustness of the solution may be proven or falsified. The theoretical results are illustrated and compared to trigonometric spline bounds and spectral bounds by means of three examples that include an anisotropic rotor-bearing system and a parametrically excited Cantilever beam.     

Bounds for the solution set of linear complementarity problems

We give here bounds for the feasible domain and the solution norm of Linear Complementarity Problems (LCP). These bounds are motivated by formulating the LCP as a global quadratic optimization problem and are characterized by the eigenstructure of the corresponding matrix. We prove boundedness of the feasible domain when the quadratic problem is concave, and give easily computable bounds for the solution norm for the convex case. We also obtain lower and upper bounds for the solution norm of the general nonconvex problem.     

Corner singularities and boundary layers in a simple convection-diffusion problem

A singularly perturbed convection-diffusion problem posed on the unit square is considered. Its solution may have exponential and parabolic boundary layers, and corner singularities may also be present. Pointwise bounds on the solution and its derivatives are derived. The dependence of these bounds on the small diffusion coefficient, on the regularity of the data, and on the compatibility of the data at the corners of the domain are all made explicit. The bounds are derived by decomposing the solution into a sum of solutions of elliptic boundary-value problems posed on half-planes, then analyzing these simpler problems.     

Solution Bounds of the Continuous and Discrete Lyapunov Matrix Equations

A unified approach is proposed to solve the estimation problem for the solution of continuous and discrete Lyapunov equations. Upper and lower matrix bounds and corresponding eigenvalue bounds of the solution of the so-called unified algebraic Lyapunov equation are presented in this paper. From the obtained results, the bounds for the solutions of continuous and discrete Lyapunov equations can be obtained as limiting cases. It is shown that the eigenvalue bounds of the unified Lyapunov equation are tighter than some parallel results and that the lower matrix bounds of the continuous Lyapunov equation are more general than the majority of those which have appeared in the literature.     

Spectral Bounds on the Solution of Linear Time-Periodic Systems

Linear time-periodic systems arise whenever a nonlinear system is linearized about a periodic trajectory. Stability of the solution may be proven by rigorous bounds on the solution. The key idea of this paper is to derive Chebyshev projection bounds on the original system by solving an approximated system. Depending on the smoothness of the original function, we formulate two upper bounds. The theoretical results are illustrated and compared to trigonometric spline bounds by means of two examples which include an anisotropic rotor-bearing system. (© 2014 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Error analysis for convex separable programs: Bounds on optimal and dual optimal solutions

Computable lower and upper bounds on the optimal and dual optimal solutions of a nonlinear, convex separable program are obtained from its piecewise linear approximation. They provide traditional error and sensitivity measures and are shown to be attainable for some problems. In addition, the bounds on the solution can be used to develop an efficient solution approach for such programs, and the dual bounds enable us to determine a subdivision interval which insures the objective function accuracy of a prespecified level. A generalization of the bounds to certain separable, but nonconvex, programs is given and some numerical examples are included.     

离散时间代数Riccati方程的解矩阵的下界与上界

本文讨论离散时间代数Ｒｉｃｃａｔｉ方程ＡＴＸＡ－Ｘ－（ＡＴＸＢ＋Ｌ）（Ｒ＋ＢＴＸＢ）＾－１（ＬＴ＋ＢＴＸＡ）＋Ｑ＝０的唯一对称正定解的上界和下界。     

Sharpened bounds for corner singularities and boundary layers in a simple convection–diffusion problem

A singularly perturbed convection–diffusion problem posed on the unit square is considered. Its solution may have exponential and parabolic boundary layers, and corner singularities may also be present. Sharpened pointwise bounds on the solution and its derivatives are derived. The bounds improve bounds near an outflow corner of the problem that were derived in an earlier paper of the authors. Application is made to an error analysis of a finite element method for the problem.     

Improved componentwise verified error bounds for least squares problems and underdetermined linear systems

Recently Miyajima presented algorithms to compute componentwise verified error bounds for the solution of full-rank least squares problems and underdetermined linear systems. In this paper we derive simpler and improved componentwise error bounds which are based on equalities for the error of a given approximate solution. Equalities are not improvable, and the expressions are formulated in a way that direct evaluation yields componentwise and rigorous estimates of good quality. The computed bounds are correct in a mathematical sense covering all sources of errors, in particular rounding errors. Numerical results show a gain in accuracy compared to previous results.