Affine scaling algorithm fails for semidefinite programming

In this paper, we introduce an affine scaling algorithm for semidefinite programming (SDP), and give an example of a semidefinite program such that the affine scaling algorithm converges to a non-optimal point. Both our program and its dual have interior feasible solutions and unique optimal solutions which satisfy strict complementarity, and they are non-degenerate everywhere.     

关系模式关键字的一个求解算法

本文给出了关系数据库模式中求解关键字的一个算法。算法很简洁并且对于[1]定义的一大类问题,执行时间是多项式级的。     

A hybrid genetic algorithm-heuristic for a two-dimensional orthogonal packing problem

In this paper we address a two-dimensional (2D) orthogonal packing problem, where a fixed set of small rectangles has to be placed on a larger stock rectangle in such a way that the amount of trim loss is minimized. The algorithm we propose hybridizes a placement procedure with a genetic algorithm based on random keys. The approach is tested on a set of instances taken from the literature and compared with other approaches. The computation results validate the quality of the solutions and the effectiveness of the proposed algorithm.     

An algorithm for the linear complementarity problem with upper and lower bounds

In this paper, we adapt the octahedral simplicial algorithm for solving systems of nonlinear equations to solve the linear complementarity problem with upper and lower bounds. The proposed algorithm generates a piecewise linear path from an arbitrarily chosen pointz ⁰ to a solution point. This path is followed by linear programming pivot steps in a system ofn linear equations, wheren is the size of the problem. The starting pointz ⁰ is left in the direction of one of the 2 ⁿ vertices of the feasible region. The ray along whichz ⁰ is left depends on the sign pattern of the function value atz ⁰. The sign pattern of the linear function and the location of the points in comparison withz ⁰ completely govern the path of the algorithm.This research is part of the VF-Program Equilibrium and Disequilibrium in Demand and Supply, approved by the Netherlands Ministry of Education, Den Haag, The Netherlands.     

Recursive solution of linear-quadratic Nash games for weakly interconnected systems

A recursive method is developed for the solution of coupled algebraic Riccati equations and corresponding linear Nash strategies of weakly interconnected systems. It is shown that the given algorithm converges to the exact solution with the rate of convergence ofO(²), where is a small coupling parameter. In addition, only low-order systems are involved in algebrdic computations; the amount of computations required does not grow per iteration and no analyticity assumption is imposed on the system coefficients.This work was supported by Rutgers University Research Council under Grant No. 2-02188.     

Minimum concave cost production system: A further generalization of multi-echelon model

We will consider a concave minimization problem associated with a series production system in which raw material is processed inm consecutive facilities. The products at some facility are either sent to the next facility or stocked in the warehouse. The amount of demand for the final products during periodi, i = 1,,n, are known in advance. Our problem is to minimize the sum of processing, holding and backlogging cost, all of which are assumed to be concave.The origin of this model is the classical economic lot size problem of Wagner and Whitin and was extensively studied by Zangwill. This model is very important from the theoretical as well as practical point of view and this is one of the very rare instances in which polynomial time algorithm has been constructed for concave minimization problems.The purpose of this paper is to extend the model further to the situation in which time lag is associated with processing at each facility. We will propose an efficient O(n ⁴ m) algorithm for this class of problems.     

Multivariate calibration of near infrared spectra by orthogonal WAVElet correction using a genetic algorithm

Orthogonal WAVElet correction (OWAVEC) is a pre-processing method aimed at simultaneously accomplishing two essential needs in multivariate calibration, signal correction and data compression, by combining the application of an orthogonal signal correction algorithm to remove information unrelated to a certain response with the great potential that wavelet analysis has shown for signal processing. In the previous version of the OWAVEC method, once the wavelet coefficients matrix had been computed from NIR spectra and deflated from irrelevant information in the orthogonalization step, effective data compression was achieved by selecting those largest correlation/variance wavelet coefficients serving as the basis for the development of a reliable regression model. This paper presents an evolution of the OWAVEC method, maintaining the first two stages in its application procedure (wavelet signal decomposition and direct orthogonalization) intact but incorporating genetic algorithms as a wavelet coefficients selection method to perform data compression and to improve the quality of the regression models developed later. Several specific applications dealing with diverse NIR regression problems are analyzed to evaluate the actual performance of the new OWAVEC method. Results provided by OWAVEC are also compared with those obtained with original data and with other orthogonal signal correction methods.     

On the average length of lexicographic paths

A bound is given for the average length of a lexicographic path, a definition that is motivated by degeneracies encountered when using the randomized simplex method.     

Determining molecular structures and conformations directly from electron diffraction using a genetic algorithm.

A global optimization strategy, based upon application of a genetic algorithm (GA), is demonstrated as an approach for determining the structures of molecules possessing significant conformational flexibility directly from gas-phase electron diffraction data. In contrast to the common approach to molecular structure determination, based on trial-and-error assessment of structures available from quantum chemical calculations, the GA approach described here does not require expensive quantum mechanical calculations or manual searching of the potential energy surface of the sample molecule, relying instead upon simple comparison between the experimental and calculated diffraction pattern derived from a proposed trial molecular structure. Structures as complex as all-trans retinal and p-coumaric acid, both important chromophores in photosensing processes, may be determined by this approach. In the examples presented here, we find that the GA approach can determine the correct conformation of a flexible molecule described by 11 independent torsion angles. We also demonstrate applications to samples comprising a mixture of two distinct molecular conformations. With these results we conclude that applications of this approach are very promising in elucidating the structures of large molecules directly from electron diffraction data.