排序方式: 共有5条查询结果,搜索用时 15 毫秒
1
1.
AP
*-geometric linear complementarity problem (P
*GP) as a generalization of the monotone geometric linear complementarity problem is introduced. In particular, it contains
the monotone standard linear complementarity problem and the horizontal linear complementarity problem. Linear and quadratic
programming problems can be expressed in a “natural” way (i.e., without any change of variables) asP
*GP. It is shown that the algorithm of Mizunoet al. [6] can be extended to solve theP
*GP. The extended algorithm is globally convergent and its computational complexity depends on the quality of the starting
points. The algorithm is quadratically convergent for problems having a strictly complementary solution.
The work of F. A. Potra was supported in part by NSF Grant DMS 9305760 相似文献
2.
J. L. Goffin 《Mathematical Programming》1982,22(1):93-103
A class of linear programs is given in which the relaxation method for inequalities, under the same operating rules as Khacian's method, is not polynomial in the length of the input. This result holds for any value of the relaxation parameter.This research was supported in part by the D.G.E.S. (Quebec), the N.S.E.R.C. of Canada under grant A 4152, and the S.S.H.R.C. of Canada. 相似文献
3.
Sung-Pil Hong 《Operations Research Letters》2007,35(6):739-742
We show that when the number of sources is constant the sparsest cut problem is solvable in polynomial time. 相似文献
4.
Jean-Louis Goffin 《Mathematical Programming》1984,30(2):147-162
The deepest, or least shallow, cut ellipsoid method is a polynomial (time and space) method which finds an ellipsoid, representable
by polynomial space integers, such that the maximal ellipsoidal distance relaxation method using this fixed ellipsoid is polynomial:
this is equivalent to finding a linear transforming such that the maximal distance relaxation method of Agmon, Motzkin and
Schoenberg in this transformed space is polynomial. If perfect arithmetic is used, then the sequence of ellipsoids generated
by the method converges to a set of ellipsoids, which share some of the properties of the classical Hessian at an optimum
point of a function; and thus the ellipsoid method is quite analogous to a variable metric quasi-Newton method.
This research was supported in part by the F.C.A.C. of Quebec, and the N.S.E.R.C. of Canada under Grant A 4152. 相似文献
5.
In this paper we introduce a primal-dual affine scaling method. The method uses a search-direction obtained by minimizing
the duality gap over a linearly transformed conic section. This direction neither coincides with known primal-dual affine
scaling directions (Jansen et al., 1993; Monteiro et al., 1990), nor does it fit in the generic primal-dual method (Kojima
et al., 1989). The new method requires
main iterations. It is shown that the iterates follow the primal-dual central path in a neighbourhood larger than the conventional
neighbourhood. The proximity to the primal-dual central path is measured by trigonometric functions. 相似文献
1