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.     

An algorithm for solving the indefinite least squares problem with equality constraints

An algorithm for computing the solution of indefinite least squares problems and of indefinite least squares problems with equality constrained is presented. Such problems arise when solving total least squares problems and in H ^∞-smoothing. The proposed algorithm relies only on stable orthogonal transformations reducing recursively the associated augmented matrix to proper block anti-triangular form. Some numerical results are reported showing the properties of the algorithm.     

An efficient generalized least squares algorithm for periodic trended regression with autoregressive errors

Time series data with periodic trends like daily temperatures or sales of seasonal products can be seen in periods fluctuating between highs and lows throughout the year. Generalized least squares estimators are often computed for such time series data as these estimators have minimum variance among all linear unbiased estimators. However, the generalized least squares solution can require extremely demanding computation when the data is large. This paper studies an efficient algorithm for generalized least squares estimation in periodic trended regression with autoregressive errors. We develop an algorithm that can substantially simplify generalized least squares computation by manipulating large sets of data into smaller sets. This is accomplished by coining a structured matrix for dimension reduction. Simulations show that the new computation methods using our algorithm can drastically reduce computing time. Our algorithm can be easily adapted to big data that show periodic trends often pertinent to economics, environmental studies, and engineering practices.     

On computing bounds for the least singular value of a triangular matrix

An algorithm for rapid computation of a lower bound for the least singular value of a triangular matrix is presented. It requiresO(N) operations whereN is the order of the matrix, and is based on the Perron-Frobenius theory of non-negative matrices. The input data are the diagonal elements and the off-diagonal elements of maximum modulus in each row.     

An algorithm based on QSVD for the quaternion equality constrained least squares problem

Numerical Algorithms - Quaternion equality constrained least squares (QLSE) problems have attracted extensive attention in the field of mathematical physics due to its applicability as an extremely...     

An algorithm and upper bounds for the weighted maximal planar graph problem

In this paper, we investigate the weighted maximal planar graph (WMPG) problem. Given a complete, edge-weighted, simple graph, the WMPG problem involves finding a subgraph with the highest sum of edge weights that is maximal planar, namely, it can be embedded in the plane without any of its edges intersecting, and no additional edge can be added to the subgraph without violating its planarity. We present a new integer linear programming (ILP) model for this problem. We then develop a cutting-plane algorithm to solve the WMPG problem based on the proposed ILP model. This algorithm enables the problem to be solved more efficiently than previously reported algorithms. New upper bounds are also provided, which are useful in evaluating the quality of heuristic solutions or in generating initial solutions for meta-heuristics. Computational results are reported for a set of 417 test instances of size varying from 6 to 100 nodes including 105 instances from the literature and 312 randomly generated instances. The computational results indicate that instances with up to 24 nodes can be solved optimally in reasonable computational time and the new upper bounds for larger instances significantly improve existing upper bounds.     

On optimal backward perturbation bounds for the linear least squares problem

Consider the linear least squares problem min _x ‖b?Ax‖₂ whereA is anm×n (m<n) matrix, andb is anm-dimensional vector. Lety be ann-dimensional vector, and let ηls(y) be the optimal backward perturbation bound defined by $$\eta _{LS} (y) = \inf \{ ||F||_F :y is a solution to \mathop {min}\limits_x ||b - (A + F)x||_2 \} .$$ . An explicit expression of ηls(y) (y≠0) has been given in [8]. However, if we define the optimal backward perturbation bounds ηmls(y) by $$\eta _{MLS} (y) = \inf \{ ||F||_F :y is the minimum 2 - norm solution to \mathop {min}\limits_x ||b - (A + F)x||_2 \} ,$$ , it may well be asked: How to derive an explicit expression of ηmls(y)? This note gives an answer. The main result is: Ifb≠0 andy≠0, then ηmls(y)=ηls (y).     

Interval algorithm for absolute value equations

We investigate the absolute value equations Ax−|x| = b. Based on ɛ-inflation, an interval verification method is proposed. Theoretic analysis and numerical results show that the new proposed method is effective.     

Lower bounds for the absolute value of random polynomials on a neighborhood of the unit circle

Let where stands for a random choice of sign with equal probability. The first author recently showed that for any and most choices of sign, , provided is large. In this paper we show that the power is optimal. More precisely, for sufficiently small and large most choices of sign satisfy . Furthermore, we study the case of more general random coefficients and applications of our methods to complex zeros of random polynomials.

     

An algorithm for computing all solutions of an absolute value equation

Presented is an algorithm which in a finite (but exponential) number of steps computes all solutions of an absolute value equation Ax + B|x| = b (A, B square), or fails. Failure has never been observed for randomly generated data. The algorithm can also be used for computation of all solutions of a linear complementarity problem.     

Solving the minimal least squares problem subject to bounds on the variables

A computational procedure is developed for determining the solution of minimal length to a linear least squares problem subject to bounds on the variables. In the first stage, a solution to the least squares problem is computed and then in the second stage, the solution of minimal length is determined. The objective function in each step is minimized by an active set method adapted to the special structure of the problem.The systems of linear equations satisfied by the descent direction and the Lagrange multipliers in the minimization algorithm are solved by direct methods based on QR decompositions or iterative preconditioned conjugate gradient methods. The direct and the iterative methods are compared in numerical experiments, where the solutions are sought to a sequence of related, minimal least squares problems subject to bounds on the variables. The application of the iterative methods to large, sparse problems is discussed briefly.This work was supported by The National Swedish Board for Technical Development under contract dnr 80-3341.     

Estimation of optimal backward perturbation bounds for the linear least squares problem

In this paper a method of estimating the optimal backward perturbation bound for the linear least squares problem is presented. In contrast with the optimal bound, which requires a singular value decomposition, this method is better suited for practical use on large problems since it requiresO(mn) operations. The method presented involves the computation of a strict lower bound for the spectral norm and a strict upper bound for the Frobenius norm which gives a gap in which the optimal bounds for the spectral and the Frobenius norm must be. Numerical tests are performed showing that this method produces an efficient estimate of the optimal backward perturbation bound.     

Robust construction of regression models based on the generalized least absolute deviations method

We suggest a new method of robust construction of linear regression models, namely, the generalized least absolute deviations method. We give a theoretical justification of the method and consider its experimental approbation. Bibliography: 12 titles. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 328, 2005, pp. 236–250.     

Perturbation bounds for the linear least squares problem subject to linear inequality constraints

We study the effect on the solution to a linear least squares problem with linear inequality and equality constraints when the data defining the problem are perturbed. The existence and uniqueness of a solution are investigated. If the matrices involved have full rank, then a detailed bound is obtained by the duality theory for quadratic programming. Sufficient conditions are derived for an estimate of the perturbation in the solution to hold in terms of the largest perturbation in the data.     

Tighter bounds of the First Fit algorithm for the bin-packing problem

In this paper, we present improved bounds for the First Fit algorithm for the bin-packing problem. We prove for all lists L, and the absolute performance ratio of FF is at most .     

An algorithm for solving a linear two-point boundary value problem for an integrodifferential equation

family of algorithms for solving a linear two-point boundary value problem is constructed in terms of the data of the integrodifferential equation and the boundary condition involved. The convergence conditions for the algorithms are established, and necessary and sufficient conditions for the well-posedness of the problem are found.     

A hybrid global optimization algorithm for non-linear least squares regression

A hybrid global optimization algorithm is proposed aimed at the class of objective functions with properties typical of the problems of non-linear least squares regression. Three components of hybridization are considered: simplicial partition of the feasible region, indicating and excluding vicinities of the main local minimizers from global search, and computing the indicated local minima by means of an efficient local descent algorithm. The performance of the algorithm is tested using a collection of non-linear least squares problems evaluated by other authors as difficult global optimization problems.