共查询到20条相似文献,搜索用时 15 毫秒
1.
For the extended linear complementarity problem over an affine subspace, we first study some characterizations of (strong)
column/row monotonicity and (strong) R
0-property. We then establish global s-type error bound for this problem with the column monotonicity or R
0-property, especially for the one with the nondegeneracy and column monotonicity, and give several equivalent formulations
of such error bound without the square root term for monotone affine variational inequality. Finally, we use this error bound
to derive some properties of the iterative sequence produced by smoothing methods for solving such a problem under suitable
assumptions.
Received: May 2, 1999 / Accepted: February 21, 2000?Published online July 20, 2000 相似文献
2.
We consider stochastic programming problems with probabilistic constraints involving integer-valued random variables. The
concept of a p-efficient point of a probability distribution is used to derive various equivalent problem formulations. Next we introduce
the concept of r-concave discrete probability distributions and analyse its relevance for problems under consideration. These notions are
used to derive lower and upper bounds for the optimal value of probabilistically constrained stochastic programming problems
with discrete random variables. The results are illustrated with numerical examples.
Received: October 1998 / Accepted: June 2000?Published online October 18, 2000 相似文献
3.
François Oustry 《Mathematical Programming》2000,89(1):1-33
In this paper we present a nonsmooth algorithm to minimize the maximum eigenvalue of matrices belonging to an affine subspace
of n×n symmetric matrices. We show how a simple bundle method, the approximate eigenvalue method can be used to globalize the second-order method developed by M.L. Overton in the eighties and recently revisited in the
framework of the ?-Lagrangian theory. With no additional assumption, the resulting algorithm generates a minimizing sequence.
A geometrical and constructive proof is given. To prove that quadratic convergence is achieved asymptotically, some strict complementarity and non-degeneracy assumptions are needed. We also introduce new variants of bundle methods for semidefinite programming.
Received: February 9, 1998 / Accepted: May 2, 2000?Published online September 20, 2000 相似文献
4.
Solving large quadratic assignment problems on computational grids 总被引:10,自引:0,他引:10
Kurt Anstreicher Nathan Brixius Jean-Pierre Goux Jeff Linderoth 《Mathematical Programming》2002,91(3):563-588
The quadratic assignment problem (QAP) is among the hardest combinatorial optimization problems. Some instances of size n = 30 have remained unsolved for decades. The solution of these problems requires both improvements in mathematical programming
algorithms and the utilization of powerful computational platforms. In this article we describe a novel approach to solve
QAPs using a state-of-the-art branch-and-bound algorithm running on a federation of geographically distributed resources known
as a computational grid. Solution of QAPs of unprecedented complexity, including the nug30, kra30b, and tho30 instances, is
reported.
Received: September 29, 2000 / Accepted: June 5, 2001?Published online October 2, 2001 相似文献
5.
Diethard Klatte 《Mathematical Programming》2000,88(2):285-311
We analyze the local upper Lipschitz behavior of critical points, stationary solutions and local minimizers to parametric
C
1,1 programs. In particular, we derive a characterization of this property for the stationary solution set map without assuming
the Mangasarian–Fromovitz CQ. Moreover, conditions which also ensure the persistence of solvability are given, and the special
case of linear constraints is handled. The present paper takes pattern from [21] by continuing the approach via contingent
derivatives of the Kojima function associated with the given optimization problem.
Received: June 10, 1999 / Accepted: November 15, 1999?Published online July 20, 2000 相似文献
6.
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 相似文献
7.
A new look at smoothing Newton methods for nonlinear complementarity problems and box constrained variational inequalities 总被引:17,自引:0,他引:17
In this paper we take a new look at smoothing Newton methods for solving the nonlinear complementarity problem (NCP) and the
box constrained variational inequalities (BVI). Instead of using an infinite sequence of smoothing approximation functions,
we use a single smoothing approximation function and Robinson’s normal equation to reformulate NCP and BVI as an equivalent
nonsmooth equation H(u,x)=0, where H:ℜ
2n
→ℜ
2n
, u∈ℜ
n
is a parameter variable and x∈ℜ
n
is the original variable. The central idea of our smoothing Newton methods is that we construct a sequence {z
k
=(u
k
,x
k
)} such that the mapping H(·) is continuously differentiable at each z
k
and may be non-differentiable at the limiting point of {z
k
}. We prove that three most often used Gabriel-Moré smoothing functions can generate strongly semismooth functions, which
play a fundamental role in establishing superlinear and quadratic convergence of our new smoothing Newton methods. We do not
require any function value of F or its derivative value outside the feasible region while at each step we only solve a linear system of equations and if
we choose a certain smoothing function only a reduced form needs to be solved. Preliminary numerical results show that the
proposed methods for particularly chosen smoothing functions are very promising.
Received June 23, 1997 / Revised version received July 29, 1999?Published online December 15, 1999 相似文献
8.
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 相似文献
9.
We give some sufficient conditions for proper lower semicontinuous functions on metric spaces to have error bounds (with exponents).
For a proper convex function f on a normed space X the existence of a local error bound implies that of a global error bound. If in addition X is a Banach space, then error bounds can be characterized by the subdifferential of f. In a reflexive Banach space X, we further obtain several sufficient and necessary conditions for the existence of error bounds in terms of the lower Dini
derivative of f.
Received: April 27, 2001 / Accepted: November 6, 2001?Published online April 12, 2002 相似文献
10.
Conditions ensuring the applicability of cutting-plane methods for solving variational inequalities 总被引:1,自引:0,他引:1
Let VIP(F,C) denote the variational inequality problem associated with the mapping F and the closed convex set C. In this paper we introduce weak conditions on the mapping F that allow the development of a convergent cutting-plane framework for solving VIP(F,C). In the process we introduce, in a natural way, new and useful notions of generalized monotonicity for which first order
characterizations are presented.
Received: September 25, 1997 / Accepted: March 2, 1999?Published online July 20, 2000 相似文献
11.
We describe an O(n
4
hmin{logU,n
2logn}) capacity scaling algorithm for the minimum cost submodular flow problem. Our algorithm modifies and extends the Edmonds–Karp
capacity scaling algorithm for minimum cost flow to solve the minimum cost submodular flow problem. The modification entails
scaling a relaxation parameter δ. Capacities are relaxed by attaching a complete directed graph with uniform arc capacity
δ in each scaling phase. We then modify a feasible submodular flow by relaxing the submodular constraints, so that complementary
slackness is satisfied. This creates discrepancies between the boundary of the flow and the base polyhedron of a relaxed submodular
function. To reduce these discrepancies, we use a variant of the successive shortest path algorithm that augments flow along
minimum cost paths of residual capacity at least δ. The shortest augmenting path subroutine we use is a variant of Dijkstra’s
algorithm modified to handle exchange capacity arcs efficiently. The result is a weakly polynomial time algorithm whose running
time is better than any existing submodular flow algorithm when U is small and C is big. We also show how to use maximum mean cuts to make the algorithm strongly polynomial. The resulting algorithm is the
first capacity scaling algorithm to match the current best strongly polynomial bound for submodular flow.
Received: August 6, 1999 / Accepted: July 2001?Published online October 2, 2001 相似文献
12.
For an edge-weighted graph G with n vertices and m edges, we present a new deterministic algorithm for computing a minimum k-way cut for k=3,4. The algorithm runs in O(n
k-1
F(n,m))=O(mn
k
log(n
2
/m)) time and O(n
2) space for k=3,4, where F(n,m) denotes the time bound required to solve the maximum flow problem in G. The bound for k=3 matches the current best deterministic bound ?(mn
3) for weighted graphs, but improves the bound ?(mn
3) to O(n
2
F(n,m))=O(min{mn
8/3,m
3/2
n
2}) for unweighted graphs. The bound ?(mn
4) for k=4 improves the previous best randomized bound ?(n
6) (for m=o(n
2)). The algorithm is then generalized to the problem of finding a minimum 3-way cut in a symmetric submodular system.
Received: April 1999 / Accepted: February 2000?Published online August 18, 2000 相似文献
13.
Separation is of fundamental importance in cutting-plane based techniques for Integer Linear Programming (ILP). In recent decades, a considerable research effort has been devoted to the definition of effective separation procedures
for families of well-structured cuts. In this paper we address the separation of Chvátal rank-1 inequalities in the context
of general ILP’s of the form min{c
T
x:Ax≤b,x integer}, where A is an m×n integer matrix and b an m-dimensional integer vector. In particular, for any given integer k we study mod-k cuts of the form λ
T
Ax≤⌊λ
T
b⌋ for any λ∈{0,1/k,...,(k−1)/k}
m
such that λ
T
A is integer. Following the line of research recently proposed for mod-2 cuts by Applegate, Bixby, Chvátal and Cook [1] and
Fleischer and Tardos [19], we restrict to maximally violated cuts, i.e., to inequalities which are violated by (k−1)/k by the given fractional point. We show that, for any given k, such a separation requires O(mn min{m,n}) time. Applications to both the symmetric and asymmetric TSP are discussed. In particular, for any given k, we propose an O(|V|2|E
*|)-time exact separation algorithm for mod-k cuts which are maximally violated by a given fractional (symmetric or asymmetric) TSP solution with support graph G
*=(V,E
*). This implies that we can identify a maximally violated cut for the symmetric TSP whenever a maximally violated (extended) comb inequality exists. Finally, facet-defining mod-k cuts for the symmetric and asymmetric TSP are studied.
Received May 29, 1997 / Revised version received May 10, 1999?Published online November 9, 1999 相似文献
14.
Masayuki Shida 《Mathematical Programming》2000,88(1):193-210
We study the local change of the generalized index, which is a modification of the Morse index and the stationary index, for
the multiparametric optimization. Under the Regular Value Condition, the change of the generalized index around a triplet
(x,v,t) is locally bounded by the dimension of the parameter vector t, where x is a variable vector and v a vector of the Lagrange multiplier space. We also discuss the local change of the generalized index around a pair (x,t).
Received: March 27, 1998 / Accepted: January 29, 2000?Published online April 20, 2000 相似文献
15.
Bernd Kummer 《Mathematical Programming》2000,88(2):313-339
We show that, even for monotone directionally differentiable Lipschitz functionals on Hilbert spaces, basic concepts of generalized
derivatives identify only particular pseudo regular (or metrically regular) situations. Thus, pseudo regularity of (multi-)
functions will be investigated by other means, namely in terms of the possible inverse functions. In this way, we show how
pseudo regularity for the intersection of multifunctions can be directly characterized and estimated under general settings
and how contingent and coderivatives may be modified to obtain sharper regularity conditions. Consequences for a concept of
stationary points as limits of Ekeland points in nonsmooth optimization will be studied, too.
Received: May 20, 1999 / Accepted: February 15, 2000?Published online July 20, 2000 相似文献
16.
Error bounds for proximal point subproblems and associated inexact proximal point algorithms 总被引:1,自引:0,他引:1
We study various error measures for approximate solution of proximal point regularizations of the variational inequality problem,
and of the closely related problem of finding a zero of a maximal monotone operator. A new merit function is proposed for
proximal point subproblems associated with the latter. This merit function is based on Burachik-Iusem-Svaiter’s concept of
ε-enlargement of a maximal monotone operator. For variational inequalities, we establish a precise relationship between the
regularized gap function, which is a natural error measure in this context, and our new merit function. Some error bounds
are derived using both merit functions for the corresponding formulations of the proximal subproblem. We further use the regularized
gap function to devise a new inexact proximal point algorithm for solving monotone variational inequalities. This inexact
proximal point method preserves all the desirable global and local convergence properties of the classical exact/inexact method,
while providing a constructive error tolerance criterion, suitable for further practical applications. The use of other tolerance
rules is also discussed.
Received: April 28, 1999 / Accepted: March 24, 2000?Published online July 20, 2000 相似文献
17.
Martin Skutella 《Mathematical Programming》2002,91(3):493-514
In the single source unsplittable min-cost flow problem, commodities must be routed simultaneously from a common source vertex
to certain destination vertices in a given graph with edge capacities and costs; the demand of each commodity must be routed
along a single path so that the total flow through any edge is at most its capacity. Moreover, the total cost must not exceed
a given budget. This problem has been introduced by Kleinberg [7] and generalizes several NP-complete problems from various
areas in combinatorial optimization such as packing, partitioning, scheduling, load balancing, and virtual-circuit routing.
Kolliopoulos and Stein [9] and Dinitz, Garg, and Goemans [4] developed algorithms improving the first approximation results
of Kleinberg for the problem of minimizing the violation of edge capacities and for other variants. However, known techniques
do not seem to be capable of providing solutions without also violating the cost constraint. We give the first approximation
results with hard cost constraints. Moreover, all our results dominate the best known bicriteria approximations. Finally,
we provide results on the hardness of approximation for several variants of the problem.
Received: August 23, 2000 / Accepted: April 20, 2001?Published online October 2, 2001 相似文献
18.
Paul Tseng 《Mathematical Programming》2000,88(1):183-192
The classes of P-, P
0-, R
0-, semimonotone, strictly semimonotone, column sufficient, and nondegenerate matrices play important roles in studying solution
properties of equations and complementarity problems and convergence/complexity analysis of methods for solving these problems.
It is known that the problem of deciding whether a square matrix with integer/rational entries is a P- (or nondegenerate) matrix is co-NP-complete. We show, through a unified analysis, that analogous decision problems for the other matrix classes are also co-NP-complete.
Received: April 1999 / Accepted: March 1, 2000?Published online May 12, 2000 相似文献
19.
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 相似文献
20.
Model selection for regression on a fixed design 总被引:1,自引:0,他引:1
Yannick Baraud 《Probability Theory and Related Fields》2000,117(4):467-493
We deal with the problem of estimating some unknown regression function involved in a regression framework with deterministic
design points. For this end, we consider some collection of finite dimensional linear spaces (models) and the least-squares
estimator built on a data driven selected model among this collection. This data driven choice is performed via the minimization
of some penalized model selection criterion that generalizes on Mallows' C
p
. We provide non asymptotic risk bounds for the so-defined estimator from which we deduce adaptivity properties. Our results
hold under mild moment conditions on the errors. The statement and the use of a new moment inequality for empirical processes
is at the heart of the techniques involved in our approach.
Received: 2 July 1997 / Revised version: 20 September 1999 / Published online: 6 July 2000 相似文献