首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 15 毫秒
1.
It has been shown [8] that numerous interior-point algorithms for linear programming (LP) generate solution sequences that converge to strict complementarity solutions, or interior solutions on the optimal face. In this note we further establish a theoretical base for Gay's test (Gay, 1989) to identify the optimal face, and develop a new termination procedure to obtain an exact solution on the optimal face. We also report some numerical results for solving a set of LP test problems, each of which has a highly degenerate and unbounded optimal face.Research supported in part by NSF Grant DDM-8922636, The Iowa Business School Summer Grant, and the Interdisciplinary Research Grant of the University of Iowa Center for Advanced Studies.  相似文献   

2.
Algorithms for nonlinear programming and variational inequality problems are, in general, only guaranteed to converge in the limit to a Karush-Kuhn-Tucker point, in the case of nonlinear programs, or to a solution in the case of variational inequalities. In this paper, we derive sufficient conditions for nonlinear programs with convex feasible sets such that any convergent algorithm can be modified, by adding a convex subproblem with a linear objective function, to guarantee finite convergence in a generalized sense. When the feasible set is polyhedral, the subproblem is a linear program and finite convergence is obtained. Similar results are also developed for variational inequalities.The research of the first author was supported in part by the Office of Naval Research under Contract No. N00014-86-K-0173.The authors are indebted to Professors Olvi Mangasarian, Garth McCormick, Jong-Shi Pang, Hanif Sherali, and Hoang Tuy for helpful comments and suggestions and to two anonymous referees for constructive remarks and for bringing to their attention the results in Refs. 13 and 14.  相似文献   

3.
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.   相似文献   

4.
Starting from a recent result on generalized quasivariational inequalities, we derive a general theorem concerning the qualitative properties of the fixed-point set of certain multifunctions. Then, we apply our result to the problem of the existence of periodic solutions for a linear control system with the property that the final value lies on the relative boundary of the corresponding attainable set.This research was presented during the 19th Course of the International School of Mathematics G. Stampacchia, Variational Inequalities and Network Equilibrium Problems, Erice, Italy, June 1994.  相似文献   

5.
The auxiliary problem principle has been proposed by the first author as a framework to describe and analyze iterative algorithms such as gradient as well as decomposition/coordination algorithms for optimization problems (Refs. 1–3) and variational inequalities (Ref. 4). The key assumption to prove the global and strong convergence of such algorithms, as well as of most of the other algorithms proposed in the literature, is the strong monotony of the operator involved in the variational inequalities. In this paper, we consider variational inequalities defined over a product of spaces and we introduce a new property of strong nested monotony, which is weaker than the ordinary overall strong monotony generally assumed. In some sense, this new concept seems to be a minimal requirement to insure convergence of the algorithms alluded to above. A convergence theorem based on this weaker assumption is given. Application of this result to the computation of Nash equilibria can be found in another paper (Ref. 5).This research has been supported by the Centre National de la Recherche Scientifique (ATP Complex Technological Systems) and by the Centre National d'Etudes des Télécommunications (Contract 83.5B.034.PAA).  相似文献   

6.
The conventional procedure for folding a system of linear inequalities based on the Fourier-Chernikov algorithm is supplemented with techniques for eliminating redundant inequalities, which considerably counteracts the increase in the system dimension. Exact and approximate methods are proposed, which are brought to algorithmic form and software implementation. Numerical results are discussed.  相似文献   

7.
In this paper, we deal with primal-dual interior point methods for solving the linear programming problem. We present a short-step and a long-step path-following primal-dual method and derive polynomial-time bounds for both methods. The iteration bounds are as usual in the existing literature, namely iterations for the short-step variant andO(nL) for the long-step variant. In the analysis of both variants, we use a new proximity measure, which is closely related to the Euclidean norm of the scaled search direction vectors. The analysis of the long-step method depends strongly on the fact that the usual search directions form a descent direction for the so-called primal-dual logarithmic barrier function.This work was supported by a research grant from Shell, by the Dutch Organization for Scientific Research (NWO) Grant 611-304-028, by the Hungarian National Research Foundation Grant OTKA-2116, and by the Swiss National Foundation for Scientific Research Grant 12-26434.89.  相似文献   

8.
Comparisons are made between the expected gain of a prophet (an observer with complete foresight) and the maximal expected gain of a gambler (using only non-anticipating stopping times) observing a sequence of independent, uniformly bounded random variables where a non-negative fixed cost is charged for each observation. Sharp universal bounds are obtained under various restrictions on the cost and the length of the sequence. For example, it is shown for X1, X2, … independent, [0, 1]-valued random variables that for all c ≥ 0 and all n ≥ 1 that E(max1 ≤ jn(Xjjc)) − supt Tn E(Xttc) ≤ 1/e, where Tn is the collection of all stopping times t which are less than or equal to n almost surely.  相似文献   

9.
This paper discusses plausible explanations of the somewhat folkloric, ‘tailing off’ convergence behavior of the Dantzig-Wolfe decomposition algorithm for linear programs. Is is argued that such beahvior may be used to numerical inaccuracy. Procedures to identify and mitigate such difficulties are outlined.  相似文献   

10.
Some projection algorithms are suggested for solving the system of generalized mixed variational inequalities, and the convergence of the proposed iterative methods are proved without any monotonicity assumption for the mappings in Banach spaces. Our theorems generalize some known results.  相似文献   

11.
Recently, Bombieri and Vaaler obtained an interesting adelic formulation of the first and the second theorems of Minkowski in the Geometry of Numbers and derived an effective formulation of the well-known “Siegel’s lemma” on the size of integral solutions of linear equations. In a similar context involving linearinequalities, this paper is concerned with an analogue of a theorem of Khintchine on integral solutions for inequalities arising from systems of linear forms and also with an analogue of a Kronecker-type theorem with regard to euclidean frames of integral vectors. The proof of the former theorem invokes Bombieri-Vaaler’s adelic formulation of Minkowski’s theorem.  相似文献   

12.
This paper points out some fatal errors in the equivalent formulations used in Noor 2011 [Noor MA. Projection iterative methods for solving some systems of general nonconvex variational inequalities. Applied Analysis. 2011;90:777–786] and consequently in Noor 2009 [Noor MA. System of nonconvex variational inequalities. Journal of Advanced Research Optimization. 2009;1:1–10], Noor 2010 [Noor MA, Noor KI. New system of general nonconvex variational inequalities. Applied Mathematics E-Notes. 2010;10:76–85] and Wen 2010 [Wen DJ. Projection methods for a generalized system of nonconvex variational inequalities with different nonlinear operators. Nonlinear Analysis. 2010;73:2292–2297]. Since these equivalent formulations are the main tools to suggest iterative algorithms and to establish the convergence results, the algorithms and results in the aforementioned articles are not valid. It is shown by given some examples. To overcome with the problems in these papers, we consider a new system of extended regularized nonconvex variational inequalities, and establish the existence and uniqueness result for a solution of the aforesaid system. We suggest and analyse a new projection iterative algorithm to compute the unique solution of the system of extended regularized nonconvex variational inequalities which is also a fixed point of a nearly uniformly Lipschitzian mapping. Furthermore, the convergence analysis of the proposed iterative algorithm under some suitable conditions is studied. As a consequence, we point out that one can derive the correct version of the algorithms and results presented in the above mentioned papers.  相似文献   

13.
This paper studies the existence of a uniform global error bound when a system of linear inequalities is under local arbitrary perturbations. Specifically, given a possibly infinite system of linear inequalities satisfying the Slater’s condition and a certain compactness condition, it is shown that for sufficiently small arbitrary perturbations the perturbed system is solvable and there exists a uniform global error bound if and only if the original system is bounded or its homogeneous system has a strict solution. Received: April 12, 1998 / Accepted: February 11, 2000?Published online July 20, 2000  相似文献   

14.
This paper shows how an existing algorithm, which is used in computer-aided design problems for solving a set of functional inequalities, may be modified by the inclusion of a Monte Carlo method to give a stochastic algorithm, which is easier to implement than its deterministic original and which solves the given set of functional inequalities almost surely.  相似文献   

15.
In this note, we show how branch-and-bound methods previously proposed for solving broad classes of multiextremal global optimization problems can be applied for solving systems of Lipschitzian equations and inequalities over feasible sets defined by various types of constraints. Some computational results are given.This research was accomplished while the second author was a fellow of the Alexander von Humboldt Foundation at the University of Trier, Trier, West Germany.  相似文献   

16.
We study the behavior of some polynomial interior-point algorithms for solving random linear programming (LP) problems. We show that the average number of iterations of these algorithms, coupled with a finite termination technique, is bounded above byO(n 1.5). The random LP problem is Todd’s probabilistic model with the standard Gauss distribution.  相似文献   

17.
A new approach is given for the analysis of random methods for detecting necessary constraints in systems of linear inequality constraints. This new approach directly accounts for the fact that two constraints are detected as necessary (hit) at each iteration of a random method. The significance of this two-hit analysis is demonstrated by comparing it with the usual one-hit analysis.  相似文献   

18.
A smoothing-type algorithm for solving system of inequalities   总被引:1,自引:0,他引:1  
In this paper we consider system of inequalities. By constructing a new smoothing function, the problem is approximated via a family of parameterized smooth equations. A Newton-type algorithm is applied to solve iteratively the smooth equations so that a solution of the problem concerned is found. We show that the algorithm is globally and locally quadratically convergent under suitable assumptions. Preliminary numerical results are reported.  相似文献   

19.
In this paper we consider systems of quasilinear elliptic variational inequalities, and prove the existence of minimal and maximal (in the set theoretical sense) solutions within some ordered interval of an appropriately defined pair of sub- and supersolutions. We show that the notion of sub- and supersolutions of variational inequalities introduced here is consistent with the usual notion of sub-supersolutions for (variational) equations. For weakly coupled quasimonotone systems of variational inequalities the existence of smallest and greatest solutions is proved.  相似文献   

20.
In this paper, we provide bounds for the expected value of the log of the condition number C(A) of a linear feasibility problem given by a n × m matrix A (Ref. 1). We show that this expected value is O(min{n, m log n}) if n > m and is O(log n) otherwise. A similar bound applies for the log of the condition number C R(A) introduced by Renegar (Ref. 2).  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号