共查询到20条相似文献,搜索用时 31 毫秒
1.
《Journal of Computational and Applied Mathematics》2002,145(1):133-149
The problem of finding an such that Ax⩽b and x⩾0 arises in numerous contexts. We propose a new optimization method for solving this feasibility problem. After converting Ax⩽b into a system of equations by introducing a slack variable for each of the linear inequalities, the method imposes an entropy function over both the original and the slack variables as the objective function. The resulting entropy optimization problem is convex and has an unconstrained convex dual. If the system is consistent and has an interior solution, then a closed-form formula converts the dual optimal solution to the primal optimal solution, which is a feasible solution for the original system of linear inequalities. An algorithm based on the Newton method is proposed for solving the unconstrained dual problem. The proposed algorithm enjoys the global convergence property with a quadratic rate of local convergence. However, if the system is inconsistent, the unconstrained dual is shown to be unbounded. Moreover, the same algorithm can detect possible inconsistency of the system. Our numerical examples reveal the insensitivity of the number of iterations to both the size of the problem and the distance between the initial solution and the feasible region. The performance of the proposed algorithm is compared to that of the surrogate constraint algorithm recently developed by Yang and Murty. Our comparison indicates that the proposed method is particularly suitable when the number of constraints is larger than that of the variables and the initial solution is not close to the feasible region. 相似文献
2.
3.
Zusammenfassung Ein bekanntes Kriterium zur Erkennung redundanter Ungleichungen in einem linearen Ungleichungssystem wird in einer vereinfachten Form hergeleitet. Dieses Kriterium wird dann als Optimalitätskriterium in ein systematisches Verfahren zur Identifikation streng redundanter Ungleichungen eines linearen Ungleichungssystems bzw. eines Systems von Nebenbedingungen eines linearen Programms eingebaut. Das beschriebene Verfahren besteht im Grunde in der Minimierung von Schlupfvariablen über das Lösungspolyeder des ursprünglichen Ungleichungssystems. Ein kleines illustratives Beispiel mit vorzeichenunbeschränkten Variablen wird vorgeführt.
Summary A known criterion for redundant inequalities in a system of linear inequalities is derived in a simplified form. This criterion is then used as an optimality-criterion in the framework of a procedure for identifying of strictly redundant inequalities in a system of linear inequalities or in a system of constraints of a linear programming problem. The described method consists basically of the minimization of slack variables over the solution-polyhedron of the original system of inequalities. A small illustrative example is given with variables not constrained in sign.相似文献
4.
A. Chakrabarti 《Applied mathematics and computation》2009,211(2):459-466
This note is concerned with the problem of determining approximate solutions of Fredholm integral equations of the second kind. Approximating the solution of a given integral equation by means of a polynomial, an over-determined system of linear algebraic equations is obtained involving the unknown coefficients, which is finally solved by using the least-squares method. Several examples are examined in detail. 相似文献
5.
一类非线性波动方程的势对称分类 总被引:1,自引:0,他引:1
先给出了含有一个任意函数的线性波动方程的古典和势对称的完全分类.然后,在此基础上给出了含有两个任意函数的一类非线性波动方程的两种情形势对称分类,得到了该方程的新势对称.在处理对称群分类问题的难点-求解确定方程组时我们提出了微分形式吴方法算法,克服了以往难于处理的困难.在整个计算过程中反复使用了吴方法,吴方法起到了关键的作用. 相似文献
6.
A. V. Arutyunov E. V. Kruglova 《Computational Mathematics and Mathematical Physics》2006,46(4):537-540
A system of linear inhomogeneous inequalities is examined. An algorithm is presented for isolating all the consistent subsystems in this system that are maximal with respect to inclusion, and justification of this algorithm is given. A criterion for the consistency of a system of quadratic inhomogeneous equations and inequalities is proposed. 相似文献
7.
William Cook 《Operations Research Letters》1983,2(1):31-35
There are many useful operations, such as adding slack variables, taking scalar multiples of inequalities, and applying Fourier-Motzkin elimination, that can be performed on a linear system such that if the system defines an integer polyhedron then so does the derived system. The topic dealt with here is whether or not these operations also preserve total dual integrality of linear systems. 相似文献
8.
The ABS class for linear and nonlinear systems has been recently introduced by Abaffy, Broyden, Galantai and Spedicato. Here we consider various ways of applying these algorithms to the determination of the minimal euclidean norm solution of over-determined linear systems in the least squares sense. Extensive numerical experiments show that the proposed algorithms are efficient and that one of them usually gives better accuracy than standard implementations of the QR orthogonalization algorithm with Householder reflections. 相似文献
9.
赵金熙 《高等学校计算数学学报(英文版)》1994,(2)
We consider a class of ABS type algorithms for solving system of linear inequalities, where the number of inequalities does not exceed the number of variables. 相似文献
10.
Liu YangYanping Chen Xiaojiao TongChunlin Deng 《Applied mathematics and computation》2011,217(24):9855-9863
In this paper, a new smoothing Newton method is proposed for solving constrained nonlinear equations. We first transform the constrained nonlinear equations to a system of semismooth equations by using the so-called absolute value function of the slack variables, and then present a new smoothing Newton method for solving the semismooth equations by constructing a new smoothing approximation function. This new method is globally and quadratically convergent. It needs to solve only one system of unconstrained equations and to perform one line search at each iteration. Numerical results show that the new algorithm works quite well. 相似文献
11.
A. Orden 《Mathematical Programming》1971,1(1):137-152
A pivotal algebra algorithm is given and finite convergence shown for finding a vector which satisfies an arbitrary system of linear equations and/or inequalities. A modified form of the algorithm, obtained by introducing a redundant equation, is then shown to be a way to describe phase I of the simplex method without reference to artificial variables or an artificial objective function.The hypothesis is introduced that in each pivot stage each row of the tableau has equal probability of being chosen as the pivot row. Under this assumption the expected value of the ratio of the number of pivot stages to the number of rows should grow with the natural Log of the number of rows.Use of the algorithm in proving theorems of the alternative is indicated.This paper was presented at the 7th Mathematical Programming Symposium 1970, The Hague, The Netherlands. 相似文献
12.
Finding all vertices of a convex polyhedron 总被引:1,自引:0,他引:1
Summary The paper describes an algorithm for finding all vertices of a convex polyhedron defined by a system of linear equations and by non-negativity conditions for variables. The algorithm is described using terminology of the theory of graphs and it seems to provide a computationally effective method. An illustrative example and some experiences with computations on a computer are given. 相似文献
13.
S. Dias 《Nonlinear Analysis: Theory, Methods & Applications》2012,75(3):1219-1230
The Newton method is one of the most powerful tools used to solve systems of nonlinear equations. Its set-valued generalization, considered in this work, allows one to solve also nonlinear equations with geometric constraints and systems of inequalities in a unified manner. The emphasis is given to systems of linear inequalities. The study of the well-posedness of the algorithm and of its convergence is fulfilled in the framework of modern variational analysis. 相似文献
14.
Using the predicate language for ordered fields a class of problems referred to aslinear problems is defined. This class contains, for example, all systems of linear equations and inequalities, all linear programming problems, all integer programming problems with bounded variables, all linear complementarity problems, the testing of whether sets that are defined by linear inequalities are semilattices, all satisfiability problems in sentenial logic, the rank-computation of matrices, the computation of row-reduced echelon forms of matrices, and all quadratic programming problems with bounded variables. A single, one, algorithm, to which we refer as theUniversal Linear Machine, is described. It solves any instance of any linear problem. The Universal Linear Machine runs in two phases. Given a linear problem, in the first phase a Compiler running on a Turing Machine generates alinear algorithm for the problem. Then, given an instance of the linear problem, in the second phase the linear algorithm solves the particular instance of the linear problem. The linear algorithm is finite, deterministic, loopless and executes only the five ordered field operations — additions, multiplications, subtractions, divisions and comparisons. Conversely, we show that for each linear algorithm there is a linear problem which the linear algorithm solves uniquely. Finally, it is shown that with a linear algorithm for a linear problem, one can solve certain parametric instances of the linear problem.Research was supported in part by the National Science Foundation Grant DMS 92-07409, by the Department of Energy Grant DE-FG03-87-ER-25028, by the United States—Israel Binational Science Foundation Grant 90-00434 and by ONR Grant N00014-92-J1142.Corresponding author. 相似文献
15.
Spedicato Emilio Bodon Elena Xia Zunquan Mahdavi-Amiri Nezam 《Central European Journal of Operations Research》2010,18(1):73-95
ABS methods are a large class of algorithms for solving continuous and integer linear algebraic equations, and nonlinear continuous
algebraic equations, with applications to optimization. Recent work by Chinese researchers led by Zunquan Xia has extended
these methods also to stochastic, fuzzy and infinite systems, extensions not considered here. The work on ABS methods began
almost thirty years. It involved an international collaboration of mathematicians especially from Hungary, England, China
and Iran, coordinated by the university of Bergamo. The ABS method are based on the rank reducing matrix update due to Egerváry
and can be considered as the most fruitful extension of such technique. They have led to unification of classes of methods
for several problems. Moreover they have produced some special algorithms with better complexity than the standard methods.
For the linear integer case they have provided the most general polynomial time class of algorithms so far known; such algorithms
have been extended to other integer problems, as linear inequalities and LP problems, in over a dozen papers written by Iranian
mathematicians led by Nezam Mahdavi-Amiri. ABS methods can be implemented generally in a stable way, techniques existing to
enhance their accuracy. Extensive numerical experiments have shown that they can outperform standard methods in several problems.
Here we provide a review of their main properties, for linear systems and optimization. We also give the results of numerical
experiments on some linear systems. This paper is dedicated to Professor Egerváry, developer of the rank reducing matrix update,
that led to ABS methods. 相似文献
16.
This paper deals with the problem of absolute stability for a class of time-delay singular systems with sector-bounded nonlinearity. Both delay-independent and delay-dependent criteria are presented and formulated in the form of linear matrix inequalities (LMIs). Neither model transformation nor a bounding technique for cross-terms, nor a slack variable method is involved in obtaining the stability criteria. Numerical examples are given to show the effectiveness and improvements over some existing results. 相似文献
17.
E. Golpar-Raboky N. Mahdavi-Amiri 《Journal of Optimization Theory and Applications》2012,152(1):75-96
Classes of integer Abaffy–Broyden–Spedicato (ABS) methods have recently been introduced for solving linear systems of Diophantine
equations. Each method provides the general integer solution of the system by computing an integer solution and an integer
matrix, named Abaffian, with rows generating the integer null space of the coefficient matrix. The Smith normal form of a
general rectangular integer matrix is a diagonal matrix, obtained by elementary nonsingular (unimodular) operations. Here,
we present a class of algorithms for computing the Smith normal form of an integer matrix. In doing this, we propose new ideas
to develop a new class of extended integer ABS algorithms generating an integer basis for the integer null space of the matrix.
For the Smith normal form, having the need to solve the quadratic Diophantine equation, we present two algorithms for solving
such equations. The first algorithm makes use of a special integer basis for the row space of the matrix, and the second one,
with the intention of controlling the growth of intermediate results and making use of our given conjecture, is based on a
recently proposed integer ABS algorithm. Finally, we report some numerical results on randomly generated test problems showing
a better performance of the second algorithm in controlling the size of the solution. We also report the results obtained
by our proposed algorithm on the Smith normal form and compare them with the ones obtained using Maple, observing a more balanced
distribution of the intermediate components obtained by our algorithm. 相似文献
18.
Byeong-Chun Shin 《Applied Numerical Mathematics》2011,61(8):911-928
Differential equations with singular sources or discontinuous coefficients yield non-smooth or even discontinuous solutions. This problem is known as the interface problem. High-order numerical solutions suffer from the Gibbs phenomenon in that the accuracy deteriorates if the discontinuity is not properly treated. In this work, we use the spectral and radial basis function methods and present a least squares collocation method to solve the interface problem for one-dimensional elliptic equations. The domain is decomposed into multiple sub-domains; in each sub-domain, the collocation solution is sought. The solution should satisfy more conditions than the given conditions associated with the differential equations, which makes the problem over-determined. To solve the over-determined system, the least squares method is adopted. For the spectral method, the weighted norm method with different scaling factors and the mixed formulation are used. For the radial basis function method, the weighted shape parameter method is presented. Numerical results show that the least squares collocation method provides an accurate solution with high efficacy and that better accuracy is obtained with the spectral method. 相似文献
19.
This paper is concerned with the delay-dependent stability and robust stability criteria for linear systems with time-varying delay and norm-bounded uncertainties. Through constructing a general form of Lyapunov–Krasovskii functional, and using integral inequalities, some slack matrices and newly established convex combination condition in the calculation, the delay-dependent stability criteria are derived in terms of linear matrix inequalities. Numerical examples are given to illustrate the improvement on the conservatism of the delay bound over some reported results in the literature. 相似文献
20.
We consider an optimization reformulation approach for the generalized Nash equilibrium problem (GNEP) that uses the regularized
gap function of a quasi-variational inequality (QVI). The regularized gap function for QVI is in general not differentiable,
but only directionally differentiable. Moreover, a simple condition has yet to be established, under which any stationary
point of the regularized gap function solves the QVI. We tackle these issues for the GNEP in which the shared constraints
are given by linear equalities, while the individual constraints are given by convex inequalities. First, we formulate the
minimization problem involving the regularized gap function and show the equivalence to GNEP. Next, we establish the differentiability
of the regularized gap function and show that any stationary point of the minimization problem solves the original GNEP under
some suitable assumptions. Then, by using a barrier technique, we propose an algorithm that sequentially solves minimization
problems obtained from GNEPs with the shared equality constraints only. Further, we discuss the case of shared inequality
constraints and present an algorithm that utilizes the transformation of the inequality constraints to equality constraints
by means of slack variables. We present some results of numerical experiments to illustrate the proposed approach. 相似文献