Robust least squares solution of linear inequalities

Least squares solution of linear inequalities appears in many disciplines such as linear separability problems and inconsistency correction. In this paper we consider this problem with uncertainty in its data. Then we prove that its robust counterpart is equivalent to a second order conic linear optimization problem, which can be efficiently solved using interior point methods.     

Iterative solution of inconsistent systems of linear inequalities

In 1980 S.P. Han proposed a finitely terminating (in exact arithmetic) algorithm for solving an inconsistent system of linear inequalities in a least squares sense. This algorithm uses a singular value decomposition of a submatrix of the problem matrix on each iteration, making it impractical for all but only smaller problems. In this paper we show that a modification of Han's algorithm allows us to introduce an iterative approximation to the singular value decomposition solution. (© 2013 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

On stable least squares solution to the system of linear inequalities

The system of inequalities is transformed to the least squares problem on the positive ortant. This problem is solved using orthogonal transformations which are memorized as products. Author’s previous paper presented a method where at each step all the coefficients of the system were transformed. This paper describes a method applicable also to large matrices. Like in revised simplex method, in this method an auxiliary matrix is used for the computations. The algorithm is suitable for unstable and degenerate problems primarily.      

One condition for solution uniqueness and robustness of both l1-synthesis and l1-analysis minimizations

The ? ₁-synthesis model and the ? ₁-analysis model recover structured signals from their undersampled measurements. The solution of the former is a sparse sum of dictionary atoms, and that of the latter makes sparse correlations with dictionary atoms. This paper addresses the question: when can we trust these models to recover specific signals? We answer the question with a condition that is both necessary and sufficient to guarantee the recovery to be unique and exact and, in the presence of measurement noise, to be robust. The condition is one–for–all in the sense that it applies to both the ? ₁-synthesis and ? ₁-analysis models, to both constrained and unconstrained formulations, and to both the exact recovery and robust recovery cases. Furthermore, a convex infinity–norm optimization problem is introduced for numerically verifying the condition. A comprehensive comparison with related existing conditions is included.     

New methods for linear inequalities

The iterative method of Cimmino for solving linear equations is generalized to linear inequalities. We also present a Richardson-type iterative method for solving the inequality problem, which includes the generalized Cimmino scheme. Convergence proofs are provided.     

Surrogate methods for linear inequalities

Three algorithms are developed and validated for finding a pointx inR ⁿ that satisfies a given system of inequalities,Axb. A andb are a given matrix and a given vector inR ^m×n andR ^m , respectively, with the rows ofA assumed normalized. The algorithms are iterative and are based upon the orthogonal projection of an infeasible point onto the manifold of the bounding hyperplanes of some of the given constraints. The choice of the active constraints and the actual projection are accomplished through the use of surrogate constraints.This work was supported in part by the City University of New York Research Center. The author thanks Professor D. Goldfarb for suggesting the problem and also for his valuable literature information and time. The word surrogate was borrowed from one of his works.     

Boolean trends in linear inequalities

This is a short overview of some recent tendencies in the theory of linear inequalities that are evoked by Boolean valued analysis.     

On semi-infinite systems of linear inequalities

The ordered fieldR(M) consists of the realsR with a transcendentalM adjoined, which is larger than any realr ∈R. Given any semi-infinite matrix (s.i.m.) interpreted as linear inequalities:u ^tP_i≧c _i, ∀ _i ∈I, an arbitrary index set, it is also shown that the following are equivalent. (1) For every finiteJ ⊆I the systemu ^tP_i≧c _i,i ∈J is consistent, and (2) the s.i.m. has a solutionu ∈R(M) ⁿ. Some consequences for “duality gaps” are also given. These results were obtained as part of the activities of the Management Science Research Group and School of Urban and Public Affairs, Carnegie-Mellon University.     

Irreducibly inconsistent systems of linear inequalities

Irreducibly inconsistent systems of linear inequalities are considered from the point of view of applying simplex-like methods for investigation.We give necessary and sufficient conditions, for a system to be irreducibly inconsistent, which can be found by applying a simplex algorithm. Next we consider general inconsistent systems. The simplex method can be used to identify irreducibly inconsistent subsystem. Such subsystems can give structural insight in the inconsistency and are used in trying to make the overall system consistent. This can be done in an easy way e.g. by right-hand side manipulations. Finally the problem of finding a ‘cheapest’ way of doing this can be formulated and solved as an extended linear program.     

Dynamic system methods for solving mixed linear matrix inequalities and linear vector inequalities and equalities

A novel idea is proposed for solving a system of mixed linear matrix inequalities and linear vector inequalities and equalities. First, the problem is converted into an unconstrained minimization problem with a continuously differentiable convex objective function. Then, a continuous-time dynamic system and a discrete-time dynamic system are proposed for solving it. Under some mild conditions, the proposed dynamic systems are shown to be globally convergent to a solution of the problem. The merits of the methods refer to their simple numerical implementations and capability for handling nonstrict LMIs easily. In addition, the methods are promising in neural circuits realization, and therefore have potential applications in many online control problems. Several numerical examples are presented to illustrate the performance of the methods and substantiate the theoretical results.     

Projection with ε-depth and its application to the solution of homogeneous systems of linear inequalities

Translated from Issledovaniya po Prikladnoi Matematike, No. 8, pp. 18–22, 1980.     

Efficiently implementable iterative methods for linear elliptic variational inequalities with constraints on the gradient of solution

We construct and investigate a new iterative solution method for a finite-dimensional constrained saddle point problem. The results are applied to prove the convergence of different iterativemethods formesh approximations of variational inequalities with constraints on the gradient of solution. In particular, we prove the convergence of two-stage iterative methods. The main advantage of the proposed methods is the simplicity of their implementation. The numerical testing demonstrates high convergence rate of the methods.     

Sample-path solution of stochastic variational inequalities

Received July 30, 1997 / Revised version received June 4, 1998 Published online October 21, 1998     

Consistency of a linear system of inequalities

We show that a consistency check of a linear system of inequalitiesAxb reduces to check whetherQb0 for a certain matrixQ. It is a direct consequence of the Farkas-Minkowski theorem. Thus, when one has to check consistency for different values ofb, one need not run a numerical algorithm for eachb.On leave at the Electronics Research Laboratory of the University of California at Berkeley in a CNRS/NSF Exchange Program.