Some non-interior path-following methods based on a scaled central path for linear complementarity problems

In this paper we present some non-interior path-following methods for linear complementarity problems. Instead of using the standard central path we use a scaled central path. Based on this new central path, we first give a feasible non-interior path-following method for linear complementarity problems. And then we extend it to an infeasible method. After proving the boundedness of the neighborhood, we prove the convergence of our method. Another point we should present is that we prove the local quadratic convergence of feasible method without the assumption of strict complementarity at the solution.     

Dependence of locally linear embedding on the regularization parameter

This paper deals with a method, called locally linear embedding (LLE). It is a nonlinear dimensionality reduction technique that computes low-dimensional, neighborhood-preserving embeddings of high-dimensional data and attempts to discover a nonlinear structure (including manifolds) in high-dimensional data. In practice, the nonlinear manifold learning methods are applied in image processing, text mining, etc. The implementation of the LLE algorithm is fairly straightforward, because the algorithm has only two control parameters: the number of neighbors of each data point and the regularization parameter. The mapping quality is quite sensitive to these parameters. In this paper, we propose a new way of selecting a regularization parameter of a local Gram matrix.     

A shape and topology optimization technique for solving a class of linear complementarity problems in function space

A shape and topology optimization driven solution technique for a class of linear complementarity problems (LCPs) in function space is considered. The main motivating application is given by obstacle problems. Based on the LCP together with its corresponding interface conditions on the boundary between the coincidence or active set and the inactive set, the original problem is reformulated as a shape optimization problem. The topological sensitivity of the new objective functional is used to estimate the “topology” of the active set. Then, for local correction purposes near the interface, a level set based shape sensitivity technique is employed. A numerical algorithm is devised, and a report on numerical test runs ends the paper.     

Semismooth Newton Schwarz iterative methods for the linear complementarity problem

Semismooth Newton method is an effective method for solving a nonsmooth equation, which arises from a reformulation of the complementarity problem. Under appropriate conditions, we verify the monotone convergence of the method. We also present semismooth Newton Schwarz iterative methods for the nonsmooth equation. Under suitable conditions, the methods exhibit monotone and superlinear convergence properties.     

Outer Approximation Method Incorporating a Quadratic Approximation for a DC Programming Problem

In this paper, we propose an outer approximation method using two quadratic functions approximating the constraint functions of a DC programming problem. By analyzing the relation among the eigenvectors of the Hessian matrices of the constraint functions, the search direction for a feasible solution of the problem is determined. Moreover, to avoid line searches along similar directions, we incorporate a penalty function method in the algorithm.     

Representation for the W-weighted Drazin inverse of linear operators

In this paper we study the W-weighted Drazin inverse of the bounded linear operators between Banach spaces and its representation theorem. Based on this representation, utilizing the spectral theory of Banach space operators, we derive an approximating expression of the W-weighted Drazin inverse and an error bound. Also, a perturbation theorem for the W-weighted Drazin inverse is uniformly obtained from the representation theorem.     

On the order of a non-abelian representation group of a slim dense near hexagon

In this paper we study the possible orders of a non-abelian representation group of a slim dense near hexagon. We prove that if the representation group R of a slim dense near hexagon S is non-abelian, then R is a 2-group of exponent 4 and |R|=2 ^β , 1+NPdim(S)≤β≤1+dimV(S), where NPdim(S) is the near polygon embedding dimension of S and dimV(S) is the dimension of the universal representation module V(S) of S. Further, if β=1+NPdim(S), then R is necessarily an extraspecial 2-group. In that case, we determine the type of the extraspecial 2-group in each case. We also deduce that the universal representation group of S is a central product of an extraspecial 2-group and an abelian 2-group of exponent at most 4. This work was partially done when B.K. Sahoo was a Research Fellow at the Indian Statistical Institute, Bangalore Center with NBHM fellowship, DAE Grant 39/3/2000-R&D-II, Govt. of India.     

Linear transformations to decrease computational requirements of solving some known linear programming models

Imposing additional weight restrictions increases the degeneracy and computational complexity of solving Data Envelopment Analysis (DEA) models, a known class of linear programming models. In this paper some linear transformations to reduce these problems are provided.     

Stability and accuracy functions in a coalition game with bans,linear payoffs and antagonistic strategies

A coalition game with a finite number of players in which initial coefficients of linear payoff functions are subject to perturbations is considered. For any efficient solution which may appear in the game, appropriate measures of the quality are introduced. These measures correspond to the so-called stability and accuracy functions defined earlier for efficient solutions of a generic multiobjective combinatorial optimization problem with Pareto and lexicographic optimality principles. Various properties of such functions are studied. Maximum norms of perturbations for which an efficient in sense of equilibrium solution preserves the property of being efficient are calculated.     

An updated survey on the linear ordering problem for weighted or unweighted tournaments

In this paper, we survey some results, conjectures and open problems dealing with the combinatorial and algorithmic aspects of the linear ordering problem. This problem consists in finding a linear order which is at minimum distance from a (weighted or not) tournament. We show how it can be used to model an aggregation problem consisting of going from individual preferences defined on a set of candidates to a collective ranking of these candidates.     

Optimal linear estimator of origin-destination flows with redundant data

Suppose given a network endowed with a multiflow. We want to estimate some quantities connected with this multiflow, for instance the value of an s–t flow for one of the sources–sinks pairs s–t, but only measures on some arcs are available, at least on one s–t cocycle (set of arcs having exactly one endpoint in a subset X of vertices with s∈X and t?X). These measures, supposed to be unbiased, are random variables whose variances are known. How can we combine them optimally in order to get the best estimator of the value of the s–t flow?This question arises in practical situations when the OD matrix of a transportation network must be estimated. We will give a complete answer for the case when we deal with linear combinations, not only for the value of an s–t flow but also for any quantity depending linearly from the multiflow. Interestingly, we will see that the Laplacian matrix of the network plays a central role.     

Magnetically-Induced Buckling of a Whirling Conducting Rod with Applications to Electrodynamic Space Tethers

We study the effect of a magnetic field on the behaviour of a slender conducting elastic structure, motivated by stability problems of electrodynamic space tethers. Both static (buckling) and dynamic (whirling) instability are considered and we also compute post-buckling configurations. The equations used are the geometrically exact Kirchhoff equations. Magnetic buckling of a welded rod is found to be described by a surprisingly degenerate bifurcation, which is unfolded when both transverse anisotropy of the rod and angular velocity are considered. By solving the linearised equations about the (quasi-) stationary solutions, we find various secondary instabilities. Our results are relevant for current designs of electrodynamic space tethers and potentially for future applications in nano- and molecular wires.     

Symmetric modified AOR method to solve systems of linear equations

We propose a class of symmetric modified accelerated overrelaxation (SMAOR) methods for solving large sparse linear systems. The convergence region of the method has been investigated. Numerical examples indicate that the SMAOR method is better than other methods such as accelerated overrelaxation(AOR) and modified accelerated overrelaxation(MAOR) methods, since the spectral radius of iteration matrix in SMAOR method is less than that of the other methods. Also, we apply the method to solve a real boundary value problem.     

Remarks on a surplus-sharing rule from the Mishneh Torah

Rabbi Moshe ben Maimon (1135–1204), known as Moses Maimonides, ranks among the most distinguished philosophers of the Middle Ages. He is the renowned author of the Mishneh Torah, a comprehensive code of Jewish law. Book 12 (“Book of Acquisition”), Treatise 4 (“Agents and Partners”), of the Code of Maimonides is devoted in Chapter 4 to the allocation of the surplus from funds which a partnership invests in an indivisible input. The Rabbi’s case translates into a cooperative game where all intermediate coalitions are inessential. Standard axioms for cooperative-game solutions then suggest that the surplus be shared equally by the players, which is precisely the Maimonidean ruling. We show that this outcome can be preserved in spirit under much weaker assumptions on the worth of a game’s intermediate coalitions. We present results both for the nucleolus and the Shapley value of the underlying class of games.     

Tabu search for the linear ordering problem with cumulative costs

Given a matrix of weights, the Linear Ordering Problem (LOP) consists of finding a permutation of the columns and rows in order to maximize the sum of the weights in the upper triangle. This well known NP-complete problem can also be formulated on a complete weighted graph, where the objective is to find an acyclic tournament that maximizes the sum of arc weights. The variant of the LOP that we target here was recently introduced and adds a cumulative non-linear propagation of the costs to the sum of the arc weights. We first review the previous methods for the LOP and for this variant with cumulative costs (LOPCC) and then propose a heuristic algorithm for the LOPCC, which is based on the Tabu Search (TS) methodology. Our method achieves search intensification and diversification through the implementation of both short and long term memory structures. Our extensive experimentation with 224 instances shows that the proposed procedure outperforms existing methods in terms of solution quality and has reasonable computing-time requirements.     

Stability of a Turnpike Phenomenon for a Discrete-Time Optimal Control System

We study the structure of solutions of a discrete-time control system with a compact metric space of states X which arises in economic dynamics. This control system is described by a nonempty closed set Ω⊂X×X which determines a class of admissible trajectories (programs) and by a bounded upper semicontinuous objective function v:Ω→R ¹ which determines an optimality criterion. We are interested in turnpike properties of the approximate solutions which are independent of the length of the interval, for all sufficiently large intervals. In the present paper, we show that these turnpike properties are stable under perturbations of the objective function v.     

Isochronicity at infinity for a class of polynomial differential system

In this paper, we explore the problem of isochronicity at infinity for a class of polynomial differential system. The technique is based on taking infinity into the origin by means of a homeomorphism. Simultaneously, we derive a recursive algorithm to compute period constants at the origin of the transformed system. At the end, as an application of our algorithm, we study pseudo-isochronous center conditions at infinity for a class of septic system.     

Fourier Inversion of Distributions Supported by a Hypersurface

Let μ _Σ be the natural measure on R ^N (N≥3) supported by a compact oriented analytic hypersurface Σ, ψ a smooth function on R ^N and P(D) a differential operator in N variables of order m. We determine a sufficient condition on the number λ such that the Fourier integral of the distribution P(D)ψ μ _Σ be summable by Cesàro means of order λ to zero in a point outside the hypersurface. This condition depends on m and on the position of the point with respect to the caustic of the hypersurface.     

Suitability and managerial implications of a Master Surgical Scheduling approach

Operating room (OR) planning and scheduling is a popular and challenging subject within the operational research applied to health services research (ORAHS). However, the impact in practice is very limited. The organization and culture of a hospital and the inherent characteristics of its processes impose specific implementation issues that affect the success of planning approaches. Current tactical OR planning approaches often fail to account for these issues. Master surgical scheduling (MSS) is a promising approach for hospitals to optimize resource utilization and patient flows. We discuss the pros and cons of MSS and compare MSS with centralized and decentralized planning approaches. Finally, we address various implementation issues of MSS and discuss its suitability for hospitals with different organizational foci and culture.