Solving a large scale semi-definite logit model

This paper is concerned with an algorithm for solving a large scale semi-definite logit model which cannot be solved by an outer approximation (cutting plane) algorithm proposed earlier by one of the authors. Outer approximation algorithm can solve a problem with up to 10 financial attributes and 7,800 companies which is less than satisfactory from the viewpoint of failure discriminant analysis. The new algorithm can generate an approximately optimal solution for problems with over 14 attributes and 8,000 companies, by which the quality of failure discriminant analysis would be substantially improved.     

Estimation of failure probability using semi-definite logit model

We will propose a new and practical method for estimating the failure probability of a large number of small to medium scale companies using their balance sheet data. We will use the maximum likelihood method to estimate the best parameters of the logit function, where the failure intensity function in its exponent is represented as a convex quadratic function instead of a commonly used linear function. The reasons for using this type of function are : (i) it can better represent the observed nonlinear dependence of failure probability on financial attributes, (ii) the resulting likelihood function can be maximized using a cutting plane algorithm developed for nonlinear semi-definite programming problems.We will show that we can achieve better prediction performance than the standard logit model, using thousands of sample companies.Revised: December 2002,     

A new model and hybrid approach for large scale inventory routing problems

This paper studies an inventory routing problem (IRP) with split delivery and vehicle fleet size constraint. Due to the complexity of the IRP, it is very difficult to develop an exact algorithm that can solve large scale problems in a reasonable computation time. As an alternative, an approximate approach that can quickly and near-optimally solve the problem is developed based on an approximate model of the problem and Lagrangian relaxation. In the approach, the model is solved by using a Lagrangian relaxation method in which the relaxed problem is decomposed into an inventory problem and a routing problem that are solved by a linear programming algorithm and a minimum cost flow algorithm, respectively, and the dual problem is solved by using the surrogate subgradient method. The solution of the model obtained by the Lagrangian relaxation method is used to construct a near-optimal solution of the IRP by solving a series of assignment problems. Numerical experiments show that the proposed hybrid approach can find a high quality near-optimal solution for the IRP with up to 200 customers in a reasonable computation time.     

A parallel integer linear programming algorithm

The solution of large scale integer linear programming models is generally dependent, in some way, upon the branch and bound technique, which can be quite time consuming. This paper describes a parallel branch and bound algorithm which achieves super linear efficiency in solving integer linear programming models on a multiprocessor computer. The algorithm is used to solve the Haldi and IBM test problems as well as a system design model.     

有交货时间限制的大规模实用下料问题

研究的是有交货时间限制的单一原材料下料问题(规模较大).对于一维下料问题,本文得到一个有各自交货时间的模型.针对该模型提出一种新的算法:DP贪婪算法.计算结果是总用料800根即可完成需求任务,材料利用率为99.6%.对于二维下料问题,在一维的基础上建立了二维的求解模型,运用我们自己设计的降维思想结合一维的DP贪婪算法,给出解决该模型的算法.计算结果是总用料451块即可完成需求任务,材料利用率位99.2%.算法设计时考虑了普遍的情况,所以算法在解决大多数实际下料问题,特别是大规模下料问题时是切实有效的.     

Parallel multilevel solvers for the cardiac electro-mechanical coupling

We develop a parallel solver for the cardiac electro-mechanical coupling. The electric model consists of two non-linear parabolic partial differential equations (PDEs), the so-called Bidomain model, which describes the spread of the electric impulse in the heart muscle. The two PDEs are coupled with a non-linear elastic model, where the myocardium is considered as a nearly-incompressible transversely isotropic hyperelastic material. The discretization of the whole electro-mechanical model is performed by Q1 finite elements in space and a semi-implicit finite difference scheme in time. This approximation strategy yields at each time step the solution of a large scale ill-conditioned linear system deriving from the discretization of the Bidomain model and a non-linear system deriving from the discretization of the finite elasticity model. The parallel solver developed consists of solving the linear system with the Conjugate Gradient method, preconditioned by a Multilevel Schwarz preconditioner, and the non-linear system with a Newton–Krylov-Algebraic Multigrid solver. Three-dimensional parallel numerical tests on a Linux cluster show that the parallel solver proposed is scalable and robust with respect to the domain deformations induced by the cardiac contraction.     

Trust-region problems with linear inequality constraints: exact SDP relaxation,global optimality and robust optimization

The trust-region problem, which minimizes a nonconvex quadratic function over a ball, is a key subproblem in trust-region methods for solving nonlinear optimization problems. It enjoys many attractive properties such as an exact semi-definite linear programming relaxation (SDP-relaxation) and strong duality. Unfortunately, such properties do not, in general, hold for an extended trust-region problem having extra linear constraints. This paper shows that two useful and powerful features of the classical trust-region problem continue to hold for an extended trust-region problem with linear inequality constraints under a new dimension condition. First, we establish that the class of extended trust-region problems has an exact SDP-relaxation, which holds without the Slater constraint qualification. This is achieved by proving that a system of quadratic and affine functions involved in the model satisfies a range-convexity whenever the dimension condition is fulfilled. Second, we show that the dimension condition together with the Slater condition ensures that a set of combined first and second-order Lagrange multiplier conditions is necessary and sufficient for global optimality of the extended trust-region problem and consequently for strong duality. Through simple examples we also provide an insightful account of our development from SDP-relaxation to strong duality. Finally, we show that the dimension condition is easily satisfied for the extended trust-region model that arises from the reformulation of a robust least squares problem (LSP) as well as a robust second order cone programming model problem (SOCP) as an equivalent semi-definite linear programming problem. This leads us to conclude that, under mild assumptions, solving a robust LSP or SOCP under matrix-norm uncertainty or polyhedral uncertainty is equivalent to solving a semi-definite linear programming problem and so, their solutions can be validated in polynomial time.     

A shift‐adaptive meshfree method for solving a class of initial‐boundary value problems with moving boundaries in one‐dimensional domain

A new shift‐adaptive meshfree method for solving a class of time‐dependent partial differential equations (PDEs) in a bounded domain (one‐dimensional domain) with moving boundaries and nonhomogeneous boundary conditions is introduced. The radial basis function (RBF) collocation method is combined with the finite difference scheme, because, unlike with Kansa's method, nonlinear PDEs can be converted to a system of linear equations. The grid‐free property of the RBF method is exploited, and a new adaptive algorithm is used to choose the location of the collocation points in the first time step only. In fact, instead of applying the adaptive algorithm on the entire domain of the problem (like with other existing adaptive algorithms), the new adaptive algorithm can be applied only on time steps. Furthermore, because of the radial property of the RBFs, the new adaptive strategy is applied only on the first time step; in the other time steps, the adaptive nodes (obtained in the first time step) are shifted. Thus, only one small system of linear equations must be solved (by LU decomposition method) rather than a large linear or nonlinear system of equations as in Kansa's method (adaptive strategy applied to entire domain), or a large number of small linear systems of equations in the adaptive strategy on each time step. This saves a lot in time and memory usage. Also, Stability analysis is obtained for our scheme, using Von Neumann stability analysis method. Results show that the new method is capable of reducing the number of nodes in the grid without compromising the accuracy of the solution, and the adaptive grading scheme is effective in localizing oscillations due to sharp gradients or discontinuities in the solution. The efficiency and effectiveness of the proposed procedure is examined by adaptively solving two difficult benchmark problems, including a regularized long‐wave equation and a Korteweg‐de Vries problem. © 2016Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 32: 1622–1646, 2016     

A relaxed cutting plane method for semi-infinite semi-definite programming

In this paper, we develop two discretization algorithms with a cutting plane scheme for solving combined semi-infinite and semi-definite programming problems, i.e., a general algorithm when the parameter set is a compact set and a typical algorithm when the parameter set is a box set in the m-dimensional space. We prove that the accumulation point of the sequence points generated by the two algorithms is an optimal solution of the combined semi-infinite and semi-definite programming problem under suitable assumption conditions. Two examples are given to illustrate the effectiveness of the typical algorithm.     

A Precedence Graph Algorithm for the Shop Scheduling Problem

This paper is concerned with the development of a precedence graph algorithm for solving certain combinatorial problems. This algorithm is applied mainly to job-shop scheduling problems; however, the extension of its applicability can be demonstrated by considering project scheduling, travelling salesman and explosion problems. The algorithm employs linear graphs to construct the quantified precedence matrix, a powerful criterion to resolve the conflict between the tied operations, and the use of a quasi-Boolean procedure to evaluate the obtained sequence.Considerable experimentation is conducted to evaluate the performance of the algorithm. Significant results pertaining to the quality of solution, the computation time and the number of iterations and conflicts encountered in obtaining a solution are given.     

基于异步次梯度法的LR算法及其在多阶段HFSP的应用

为降低求解复杂度和缩短计算时间,针对多阶段混合流水车间总加权完成时间问题,提出了一种结合异步次梯度法的改进拉格朗日松弛算法。建立综合考虑有限等待时间和工件释放时间的整数规划数学模型,将异步次梯度法嵌入到拉格朗日松弛算法中,从而通过近似求解拉格朗日松弛问题得到一个合理的异步次梯度方向,沿此方向进行搜索,逐渐降低到最优点的距离。通过仿真实验,验证了所提算法的有效性。对比所提算法与传统的基于次梯度法的拉格朗日松弛算法,结果表明,就综合解的质量和计算效率而言,所提算法能在较短的计算时间内获得更好的近优解,尤其是对大规模问题。     

一类含参数的分块对称矩阵的正定性及应用

首先给出一种判断分块对称矩阵正定的方法,提供了确定一组尽可能小的参数,使一类含参数的分块对称矩阵正定的简单算法,然后,将其结果用于研究线性定常大系统的分散镇定性,得到了一类可分散镇定的线性大系统,并给出了相应的分散镇定算法,同文献中提供的方法相比,该算法不仅扩大了所考虑的系统范围,而且不会引起过高的反馈增益,同时还简单易算。     

A meta-heuristic approach for solving the Urban Network Design Problem

This paper proposes an optimisation model and a meta-heuristic algorithm for solving the urban network design problem. The problem consists in optimising the layout of an urban road network by designing directions of existing roads and signal settings at intersections. A non-linear constrained optimisation model for solving this problem is formulated, adopting a bi-level approach in order to reduce the complexity of solution methods and the computation times. A Scatter Search algorithm based on a random descent method is proposed and tested on a real dimension network. Initial results show that the proposed approach allows local optimal solutions to be obtained in reasonable computation times.     

Airport noise modelling and aircraft scheduling so as to minimize community annoyance

A mathematical model of the annoyance created at an airport by aircraft operations is developed. The model incorporates population distribution considerations around an airport and the annoyance caused by aircraft noise. The objective function of this model corresponds to seeking to minimize total population annoyance created by all aircraft operations in a 24-hour period. Several factors are included in this model as constraint relationships. Aircraft operations by type and time period are upper bounded. Demand for flight services is incorporated by including lower bounds on the number of operations by type of aircraft, runway used and time period. Also upper bounds on the number of operations for each runway are included. The mathematical model as formulated is recognized as corresponding to a nonlinear integer mathematical programming problem.The solution technique selected makes use of a successive linear approximation optimization algorithm. An especially attractive feature of this solution algorithm is that it is capable of obtaining solutions to large problems. For example, it would be feasible to attempt the solution of problems involving several thousand variables and over 500 linear constraints. This suggested solution algorithm was implemented on a computer and computational results obtained for example problems.     

Mixed two‐grid finite difference methods for solving one‐dimensional and two‐dimensional Fitzhugh–Nagumo equations

The aim of this paper is to propose mixed two‐grid finite difference methods to obtain the numerical solution of the one‐dimensional and two‐dimensional Fitzhugh–Nagumo equations. The finite difference equations at all interior grid points form a large‐sparse linear system, which needs to be solved efficiently. The solution cost of this sparse linear system usually dominates the total cost of solving the discretized partial differential equation. The proposed method is based on applying a family of finite difference methods for discretizing the spatial and time derivatives. The obtained system has been solved by two‐grid method, where the two‐grid method is used for solving the large‐sparse linear systems. Also, in the proposed method, the spectral radius with local Fourier analysis is calculated for different values of h and Δt. The numerical examples show the efficiency of this algorithm for solving the one‐dimensional and two‐dimensional Fitzhugh–Nagumo equations. Copyright © 2016 John Wiley & Sons, Ltd.     

Classification of companies using maximal margin ellipsoidal surfaces

We recently proposed a data mining approach for classifying companies into several groups using ellipsoidal surfaces. This problem can be formulated as a semi-definite programming problem, which can be solved within a practical amount of computation time by using a state-of-the-art semi-definite programming software. It turned out that this method performs better for this application than earlier methods based on linear and general quadratic surfaces. In this paper we will improve the performance of ellipsoidal separation by incorporating the idea of maximal margin hyperplane developed in the field of support vector machine. It will be demonstrated that the new method can very well simulate the rating of a leading rating company of Japan by using up to 18 financial attributes of 363 companies. This paper is expected to provide another evidence of the importance of ellipsoidal separation approach in credit risk analysis.     

A cutting plane algorithm for semi-definite programming problems with applications to failure discriminant analysis

We will propose a new cutting plane algorithm for solving a class of semi-definite programming problems (SDP) with a small number of variables and a large number of constraints. Problems of this type appear when we try to classify a large number of multi-dimensional data into two groups by a hyper-ellipsoidal surface. Among such examples are cancer diagnosis, failure discrimination of enterprises. Also, a certain class of option pricing problems can be formulated as this type of problem. We will show that the cutting plane algorithm is much more efficient than the standard interior point algorithms for solving SDP.     

A multigrid compact finite difference method for solving the one‐dimensional nonlinear sine‐Gordon equation

The aim of this paper is to propose a multigrid method to obtain the numerical solution of the one‐dimensional nonlinear sine‐Gordon equation. The finite difference equations at all interior grid points form a large sparse linear system, which needs to be solved efficiently. The solution cost of this sparse linear system usually dominates the total cost of solving the discretized partial differential equation. The proposed method is based on applying a compact finite difference scheme of fourth‐order for discretizing the spatial derivative and the standard second‐order central finite difference method for the time derivative. The proposed method uses the Richardson extrapolation method in time variable. The obtained system has been solved by V‐cycle multigrid (VMG) method, where the VMG method is used for solving the large sparse linear systems. The numerical examples show the efficiency of this algorithm for solving the one‐dimensional sine‐Gordon equation. Copyright © 2014 John Wiley & Sons, Ltd.     

求解线性模型稳健参数估计的整数编码遗传算法

线性模型回归系数的一些稳健估计如LMS、LQS、LTS、LTA的应用越来越广泛,然而它们的精确计算依赖于NP难题,在遇到高维大规模数据集时不可能在较短时间内得到精确解.为尽快得到较高精度的近似解,提出了求解线性模型的稳健参数估计的整数编码遗传算法,通过计算机模拟试验验证了算法可以更快地找出全局最优解.     

模糊多目标半定规划

This paper first applies the fuzzy set theory to multi-objective semi-definite program-ming （MSDP）, and proposes the fuzzy multi-objective semi-definite programming （FMSDP） model whose optimal efficient solution is defined for the first time, too. By constructing a membership function, the FMSDP is translated to the MSDP. Then we prove that the optimal efficient solution of FMSDP is consistent with the efficient solution of MSDP and present the optimality condition about these programming. At last, we give an algorithm for FMSDP by introducing a new membership function and a series of transformation.