共查询到20条相似文献,搜索用时 15 毫秒
1.
We consider the parametric programming problem (Q
p
) of minimizing the quadratic function f(x,p):=x
T
Ax+b
T
x subject to the constraint Cx≤d, where x∈ℝ
n
, A∈ℝ
n×n
, b∈ℝ
n
, C∈ℝ
m×n
, d∈ℝ
m
, and p:=(A,b,C,d) is the parameter. Here, the matrix A is not assumed to be positive semidefinite. The set of the global minimizers and the set of the local minimizers to (Q
p
) are denoted by M(p) and M
loc
(p), respectively. It is proved that if the point-to-set mapping M
loc
(·) is lower semicontinuous at p then M
loc
(p) is a nonempty set which consists of at most ?
m,n
points, where ?
m,n
= is the maximal cardinality of the antichains of distinct subsets of {1,2,...,m} which have at most n elements. It is proved also that the lower semicontinuity of M(·) at p implies that M(p) is a singleton. Under some regularity assumption, these necessary conditions become the sufficient ones.
Received: November 5, 1997 / Accepted: September 12, 2000?Published online November 17, 2000 相似文献
2.
This paper presents a polynomial-time dual simplex algorithm for the generalized circulation problem. An efficient implementation
of this algorithm is given that has a worst-case running time of O(m
2(m+nlogn)logB), where n is the number of nodes, m is the number of arcs and B is the largest integer used to represent the rational gain factors and integral capacities in the network. This running time
is as fast as the running time of any combinatorial algorithm that has been proposed thus far for solving the generalized
circulation problem.
Received: June 1998 / Accepted: June 27, 2001?Published online September 17, 2001 相似文献
3.
Given a linear transformation L:?
n
→?
n
and a matrix Q∈?
n
, where ?
n
is the space of all symmetric real n×n matrices, we consider the semidefinite linear complementarity problem SDLCP(L,?
n
+,Q) over the cone ?
n
+ of symmetric n×n positive semidefinite matrices. For such problems, we introduce the P-property and its variants, Q- and GUS-properties. For a matrix A∈R
n×n
, we consider the linear transformation L
A
:?
n
→?
n
defined by L
A
(X):=AX+XA
T
and show that the P- and Q-properties for L
A
are equivalent to A being positive stable, i.e., real parts of eigenvalues of A are positive. As a special case of this equivalence, we deduce a theorem of Lyapunov.
Received: March 1999 / Accepted: November 1999?Published online April 20, 2000 相似文献
4.
Polynomial convergence of primal-dual algorithms for the second-order cone program based on the MZ-family of directions 总被引:5,自引:0,他引:5
In this paper we study primal-dual path-following algorithms for the second-order cone programming (SOCP) based on a family
of directions that is a natural extension of the Monteiro-Zhang (MZ) family for semidefinite programming. We show that the
polynomial iteration-complexity bounds of two well-known algorithms for linear programming, namely the short-step path-following
algorithm of Kojima et al. and Monteiro and Adler, and the predictor-corrector algorithm of Mizuno et al., carry over to the
context of SOCP, that is they have an O( logε-1) iteration-complexity to reduce the duality gap by a factor of ε, where n is the number of second-order cones. Since the MZ-type family studied in this paper includes an analogue of the Alizadeh,
Haeberly and Overton pure Newton direction, we establish for the first time the polynomial convergence of primal-dual algorithms
for SOCP based on this search direction.
Received: June 5, 1998 / Accepted: September 8, 1999?Published online April 20, 2000 相似文献
5.
Summary. Let A be an n×m real matrix and consider the linear conic system
In [Cheung and Cucker 2001] a condition number 𝒞(A) for this system is defined. In this paper we let the coefficients of A be independent identically distributed random variables with standard Gaussian distribution and we estimate the moments of
the random variable ln𝒞(A). In particular, when n is sufficiently larger than m we obtain for its expected value E(ln𝒞(A))=max{ln m, ln ln n}+𝒪(1). Bounds for the expected value of the condition number introduced by Renegar [1994b, 1995a, 1995b] follow.
Received June 12, 2001 / Revised version received October 29, 2001 /
Published online November 27, 2002
RID="⋆"
ID="⋆" Partially supported by CERG grant City U 1085/02p.
Mathematics Subject Classification (1991): 65F35, 65K05 相似文献
6.
The Frattini Subalgebra of Restricted Lie Superalgebras 总被引:6,自引:0,他引:6
Liang Yun CHEN Dao Ji MENG Yong Zheng ZHANG 《数学学报(英文版)》2006,22(5):1343-1356
In the present paper, we study the Frattini subalgebra of a restricted Lie superalgebra (L, [p]). We show first that if L = A1 + A2 +… +An, then Фp(L) = Фp(A1) +Фp(A2) +…+Фp(An), where each Ai is a p-ideal of L. We then obtain two results: F(L) = Ф(L) = J(L) = L if and only if L is nilpotent; Fp(L) and F(L) are nilpotent ideals of L if L is solvable. In addition, necessary and sufficient conditions are found for Фp-free restricted Lie superalgebras. Finally, we discuss the relationships of E-p-restricted Lie superalgebras and E-restricted Lie superalgebras. 相似文献
7.
Levent Tunçel 《Mathematical Programming》1999,86(1):219-223
Given an m×n integer matrix A of full row rank, we consider the problem of computing the maximum of ∥B
-1
A∥2 where B varies over all bases of A. This quantity appears in various places in the mathematical programming literature. More recently, logarithm of this number
was the determining factor in the complexity bound of Vavasis and Ye’s primal-dual interior-point algorithm. We prove that
the problem of approximating this maximum norm, even within an exponential (in the dimension of A) factor, is NP-hard. Our proof is based on a closely related result of L. Khachiyan [1].
Received November 13, 1998 / Revised version received January 20, 1999? Published online May 12, 1999 相似文献
8.
The subgroups E(m,R) ⊗ E(n,R) ≤ H ≤ G = GL(mn,R) are studied under the assumption that the ring R is commutative and m, n ≥ 3. The group GL
m
⊗GL
n
is defined by equations, the normalizer of the group E(m,R) ⊗ E(n,R) is calculated, and with each intermediate subgroup H it is associated a uniquely determined lower level (A,B,C), where A,B,C are ideals in R such that mA,A
2 ≤ B ≤ A and nA,A
2 ≤ C ≤ A. The lower level specifies the largest elementary subgroup satisfying the condition E(m, n,R, A,B,C) ≤ H. The standard answer to this problem asserts that H is contained in the normalizer N
G
(E(m,n,R, A,B,C)). Bibliography: 46 titles. 相似文献
9.
This paper is concerned with classical concave cost multi-echelon production/inventory control problems studied by W. Zangwill
and others. It is well known that the problem with m production steps and n time periods can be solved by a dynamic programming algorithm in O(n
4
m) steps, which is considered as the fastest algorithm for solving this class of problems. In this paper, we will show that
an alternative 0–1 integer programming approach can solve the same problem much faster particularly when n is large and the number of 0–1 integer variables is relatively few. This class of problems include, among others problem
with set-up cost function and piecewise linear cost function with fewer linear pieces. The new approach can solve problems
with mixed concave/convex cost functions, which cannot be solved by dynamic programming algorithms. 相似文献
10.
U. Luther 《Annali di Matematica Pura ed Applicata》2003,182(2):161-200
We show that the representation theorem for classical approximation spaces can be generalized to spaces A(X,l
q
(ℬ))={f∈X:{E
n
(f)}∈l
q
(ℬ)} in which the weighted l
q
-space l
q
(ℬ) can be (more or less) arbitrary. We use this theorem to show that generalized approximation spaces can be viewed as real
interpolation spaces (defined with K-functionals or main-part K-functionals) between couples of quasi-normed spaces which satisfy certain Jackson and Bernstein-type inequalities. Especially,
interpolation between an approximation space and the underlying quasi-normed space leads again to an approximation space.
Together with a general reiteration theorem, which we also prove in the present paper, we obtain formulas for interpolation
of two generalized approximation spaces.
Received: December 6, 2001; in final form: April 2, 2002?Published online: March 14, 2003 相似文献
11.
Xia Chen 《Probability Theory and Related Fields》2000,116(1):89-123
Let {X
n
}
n
≥0 be a Harris recurrent Markov chain with state space E and invariant measure π. The law of the iterated logarithm and the law of weak convergence are given for the additive functionals
of the form
where ƒ is a real π-centered function defined on E. Some similar results are also obtained for additive functionals which are martingales associated with {X
n
}
n
≥0.
Received: 15 September 1998 / Revised version: 1 April 1999 相似文献
12.
An improved rounding method and semidefinite programming relaxation for graph partition 总被引:8,自引:0,他引:8
Given an undirected graph G=(V,E) with |V|=n and an integer k between 0 and n, the maximization graph partition (MAX-GP) problem is to determine a subset S⊂V of k nodes such that an objective function w(S) is maximized. The MAX-GP problem can be formulated as a binary quadratic program and it is NP-hard. Semidefinite programming
(SDP) relaxations of such quadratic programs have been used to design approximation algorithms with guaranteed performance
ratios for various MAX-GP problems. Based on several earlier results, we present an improved rounding method using an SDP
relaxation, and establish improved approximation ratios for several MAX-GP problems, including Dense-Subgraph, Max-Cut, Max-Not-Cut,
and Max-Vertex-Cover.
Received: March 10, 2000 / Accepted: July 13, 2001?Published online February 14, 2002 相似文献
13.
Luke B. Winternitz Stacey O. Nicholls André L. Tits Dianne P. O’Leary 《Computational Optimization and Applications》2012,51(3):1001-1036
Consider linear programs in dual standard form with n constraints and m variables. When typical interior-point algorithms are used for the solution of such problems, updating the iterates, using
direct methods for solving the linear systems and assuming a dense constraint matrix A, requires O(nm2)\mathcal{O}(nm^{2}) operations per iteration. When n≫m it is often the case that at each iteration most of the constraints are not very relevant for the construction of a good
update and could be ignored to achieve computational savings. This idea was considered in the 1990s by Dantzig and Ye, Tone,
Kaliski and Ye, den Hertog et al. and others. More recently, Tits et al. proposed a simple “constraint-reduction” scheme and
proved global and local quadratic convergence for a dual-feasible primal-dual affine-scaling method modified according to
that scheme. In the present work, similar convergence results are proved for a dual-feasible constraint-reduced variant of
Mehrotra’s predictor-corrector algorithm, under less restrictive nondegeneracy assumptions. These stronger results extend
to primal-dual affine scaling as a limiting case. Promising numerical results are reported. 相似文献
14.
Given an n × n symmetric possibly indefinite matrix A, a modified Cholesky algorithm computes a factorization of the positive definite matrix A + E, where E is a correction matrix. Since the factorization is often used to compute a Newton-like downhill search direction for an optimization
problem, the goals are to compute the modification without much additional cost and to keep A + E well-conditioned and close to A. Gill, Murray and Wright introduced a stable algorithm, with a bound of ||E||2 = O(n
2). An algorithm of Schnabel and Eskow further guarantees ||E||2 = O(n). We present variants that also ensure ||E||2 = O(n). Moré and Sorensen and Cheng and Higham used the block LBL
T
factorization with blocks of order 1 or 2. Algorithms in this class have a worst-case cost O(n
3) higher than the standard Cholesky factorization. We present a new approach using a sandwiched LTL
T
-LBL
T
factorization, with T tridiagonal, that guarantees a modification cost of at most O(n
2).
H.-r. Fang’s work was supported by National Science Foundation Grant CCF 0514213.
D. P. O’Leary’s work was supported by National Science Foundation Grant CCF 0514213 and Department of Energy Grant DEFG0204ER25655. 相似文献
15.
András A. Benczúr 《Mathematical Programming》1999,84(3):595-640
1 ,E2,..., such that ⋃i≤τEi optmially increases the connectivity by τ, for any integer τ. The main result of the paper is that this sequence of edge
sets can be divided into O(n) groups such that within one group, all Ei are basically the same. Using this result, we improve on the running time of edge connectivity augmentation, as well as we
give the first parallel (RNC) augmentation algorithm. We also present new efficient subroutines for finding the so-called
extreme sets and the cactus representation of min-cuts required in our algorithms. Augmenting the connectivity of hypergraphs
with ordinary edges is known to be structurally harder than that of ordinary graphs. In a weaker version when one exceptional
hyperedge is allowed in the augmenting edge set, we derive similar results as for ordinary graphs.
Received November 1995 / Revised version received July 1998
Published online March 16, 1999 相似文献
16.
A conic linear system is a system of the form?P(d): find x that solves b - Ax∈C
Y
, x∈C
X
,? where C
X
and C
Y
are closed convex cones, and the data for the system is d=(A,b). This system is“well-posed” to the extent that (small) changes in the data (A,b) do not alter the status of the system (the system remains solvable or not). Renegar defined the “distance to ill-posedness”,
ρ(d), to be the smallest change in the data Δd=(ΔA,Δb) for which the system P(d+Δd) is “ill-posed”, i.e., d+Δd is in the intersection of the closure of feasible and infeasible instances d’=(A’,b’) of P(·). Renegar also defined the “condition measure” of the data instance d as C(d):=∥d∥/ρ(d), and showed that this measure is a natural extension of the familiar condition measure associated with systems of linear
equations. This study presents two categories of results related to ρ(d), the distance to ill-posedness, and C(d), the condition measure of d. The first category of results involves the approximation of ρ(d) as the optimal value of certain mathematical programs. We present ten different mathematical programs each of whose optimal
values provides an approximation of ρ(d) to within certain constants, depending on whether P(d) is feasible or not, and where the constants depend on properties of the cones and the norms used. The second category of
results involves the existence of certain inscribed and intersecting balls involving the feasible region of P(d) or the feasible region of its alternative system, in the spirit of the ellipsoid algorithm. These results roughly state that
the feasible region of P(d) (or its alternative system when P(d) is not feasible) will contain a ball of radius r that is itself no more than a distance R from the origin, where the ratio R/r satisfies R/r≤c
1
C(d), and such that r≥ and R≤c
3
C(d), where c
1,c
2,c
3 are constants that depend only on properties of the cones and the norms used. Therefore the condition measure C(d) is a relevant tool in proving the existence of an inscribed ball in the feasible region of P(d) that is not too far from the origin and whose radius is not too small.
Received November 2, 1995 / Revised version received June 26, 1998?Published online May 12, 1999 相似文献
17.
In this paper we study three-color Ramsey numbers. Let K
i,j
denote a complete i by j bipartite graph. We shall show that (i) for any connected graphs G
1, G
2 and G
3, if r(G
1, G
2)≥s(G
3), then r(G
1, G
2, G
3)≥(r(G
1, G
2)−1)(χ(G
3)−1)+s(G
3), where s(G
3) is the chromatic surplus of G
3; (ii) (k+m−2)(n−1)+1≤r(K
1,k
, K
1,m
, K
n
)≤ (k+m−1)(n−1)+1, and if k or m is odd, the second inequality becomes an equality; (iii) for any fixed m≥k≥2, there is a constant c such that r(K
k,m
, K
k,m
, K
n
)≤c(n/logn), and r(C
2m
, C
2m
, K
n
)≤c(n/logn)
m/(m−1)
for sufficiently large n.
Received: July 25, 2000 Final version received: July 30, 2002
RID="*"
ID="*" Partially supported by RGC, Hong Kong; FRG, Hong Kong Baptist University; and by NSFC, the scientific foundations of
education ministry of China, and the foundations of Jiangsu Province
Acknowledgments. The authors are grateful to the referee for his valuable comments.
AMS 2000 MSC: 05C55 相似文献
18.
In a recent paper, the authors have proved results characterizing convexity-preserving maps defined on a subset of a not-necessarily
finite dimensional real vector space as projective maps. The purpose of this note is three-fold. First, we state a theorem
characterizing continuous, injective, convexity-preserving maps from a relatively open, connected subset of an affine subspace
of ℝ
m
into ℝ
n
as projective maps. This result follows from the more general results stated and proved in a coordinate-free manner in the
above paper, and is intended to be more accessible to researchers interested in optimization algorithms. Second, based on
that characterization theorem, we offer a characterization theorem for collinear scalings first introduced by Davidon in 1977
for deriving certain algorithms for nonlinear optimization, and a characterization theorem for projective transformations
used by Karmarkar in 1984 in his linear programming algorithm. These latter two theorems indicate that Davidon’s collinear
scalings and Karmarkar’s projective transformations are the only continuous, injective, convexity-preserving maps possessing
certain features that Davidon and Karmarkar respectively desired in the derivation of their algorithms. The proofs of these
latter two theorems utilize our characterization of continuous, injective, convexity-preserving maps in a way that has implications
to the choice of scalings and transformations in the derivation of optimization algorithms in general. The third purpose of
this note is to point this out.
Received: January 2000 / Accepted: November 2000?Published online January 17, 2001 相似文献
19.
The dynamical characteristics of scalar difference equations of the form?x
n
+1=f
1(x
n
−τ1)+f
2(x
n
−τ2), n=0,1,2,...,?are investigated. A necessary and sufficient condition is obtained for all positive solutions to be oscillatory
about a unique positive equilibrium point and sufficient criteria for the global attractivity of the equilibrium are established.
Also, the stability and periodicity of more general equations are studied via comparison with the corresponding properties
of an associated first-order non-linear equation.
Received: September 5, 2001; in final form: March 7, 2002?Published online: April 14, 2003 相似文献
20.
For a polytope in the [0,1]
n
cube, Eisenbrand and Schulz showed recently that the maximum Chvátal rank is bounded above by O(n
2logn) and bounded below by (1+ε)n for some ε>0. Chvátal cuts are equivalent to Gomory fractional cuts, which are themselves dominated by Gomory mixed integer
cuts. What do these upper and lower bounds become when the rank is defined relative to Gomory mixed integer cuts? An upper
bound of n follows from existing results in the literature. In this note, we show that the lower bound is also equal to n. This result still holds for mixed 0,1 polyhedra with n binary variables.
Received: March 15, 2001 / Accepted: July 18, 2001?Published online September 17, 2001 相似文献