共查询到20条相似文献,搜索用时 46 毫秒
1.
Martin Gugat 《Mathematical Programming》2000,88(2):255-275
The feasible set of a convex semi–infinite program is described by a possibly infinite system of convex inequality constraints.
We want to obtain an upper bound for the distance of a given point from this set in terms of a constant multiplied by the
value of the maximally violated constraint function in this point. Apart from this Lipschitz case we also consider error bounds
of H?lder type, where the value of the residual of the constraints is raised to a certain power.?We give sufficient conditions
for the validity of such bounds. Our conditions do not require that the Slater condition is valid. For the definition of our
conditions, we consider the projections on enlarged sets corresponding to relaxed constraints. We present a condition in terms
of projection multipliers, a condition in terms of Slater points and a condition in terms of descent directions. For the Lipschitz
case, we give five equivalent characterizations of the validity of a global error bound.?We extend previous results in two
directions: First, we consider infinite systems of inequalities instead of finite systems. The second point is that we do
not assume that the Slater condition holds which has been required in almost all earlier papers.
Received: April 12, 1999 / Accepted: April 5, 2000?Published online July 20, 2000 相似文献
2.
H. Hu 《Journal of Global Optimization》2003,25(2):237-242
This paper studies the existence of a uniform global error bound when a convex inequality g 0, where g is a closed proper convex function, is perturbed. The perturbation neighborhoods are defined by small arbitrary perturbations of the epigraph of its conjugate function. Under certain conditions, 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 g satisfies the Slater condition and the solution set is bounded or its recession function satisfies the Slater condition. The results are used to derive lower bounds on the distance to ill-posedness. 相似文献
3.
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 相似文献
4.
The strong conical hull intersection property and bounded linear regularity are properties of a collection of finitely many
closed convex intersecting sets in Euclidean space. These fundamental notions occur in various branches of convex optimization
(constrained approximation, convex feasibility problems, linear inequalities, for instance). It is shown that the standard
constraint qualification from convex analysis implies bounded linear regularity, which in turn yields the strong conical hull
intersection property. Jameson’s duality for two cones, which relates bounded linear regularity to property (G), is re-derived
and refined. For polyhedral cones, a statement dual to Hoffman’s error bound result is obtained. A sharpening of a result
on error bounds for convex inequalities by Auslender and Crouzeix is presented. Finally, for two subspaces, property (G) is
quantified by the angle between the subspaces.
Received October 1, 1997 / Revised version received July 21, 1998? Published online June 11, 1999 相似文献
5.
We obtain local estimates of the distance to a set defined by equality constraints under assumptions which are weaker than
those previously used in the literature. Specifically, we assume that the constraints mapping has a Lipschitzian derivative,
and satisfies a certain 2-regularity condition at the point under consideration. This setting directly subsumes the classical
regular case and the twice differentiable 2-regular case, for which error bounds are known, but it is significantly richer
than either of these two cases. When applied to a certain equation-based reformulation of the nonlinear complementarity problem,
our results yield an error bound under an assumption more general than b-regularity. The latter appears to be the weakest assumption under which a local error bound for complementarity problems
was previously available. We also discuss an application of our results to the convergence rate analysis of the exterior penalty
method for solving irregular problems.
Received: February 2000 / Accepted: November 2000?Published online January 17, 2001 相似文献
6.
Satoru Fujishige 《Mathematical Programming》2000,88(1):217-220
U. Faigle and W. Kern have recently extended the work of their earlier paper and of M. Queyranne, F. Spieksma and F. Tardella
and have shown that a dual greedy algorithm works for a system of linear inequalities with {:0,1}-coefficients defined in
terms of antichains of an underlying poset and a submodular function on the set of ideals of the poset under some additional
condition on the submodular function.?In this note we show that Faigle and Kern’s dual greedy polyhedra belong to a class
of submodular flow polyhedra, i.e., Faigle and Kern’s problem is a special case of the submodular flow problem that can easily
be solved by their greedy algorithm.
Received: February 1999 / Accepted: December 1999?Published online February 23, 2000 相似文献
7.
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 相似文献
8.
Song Xu 《Mathematical Programming》2000,87(3):501-517
We propose an infeasible non-interior path-following method for nonlinear complementarity problems with uniform P-functions. This method is based on the smoothing techniques introduced by Kanzow. A key to our analysis is the introduction
of a new notion of neighborhood for the central path which is suitable for infeasible non-interior path-following methods.
By restricting the iterates in the neighborhood of the central path, we provide a systematic procedure to update the smoothing
parameter and establish the global linear convergence of this method. Some preliminary computational results are reported.
Received: March 13, 1997 / Accepted: December 17, 1999?Published online February 23, 2000 相似文献
9.
On the superlinear convergence of the variable metric proximal point algorithm using Broyden and BFGS matrix secant updating 总被引:2,自引:0,他引:2
In previous work, the authors provided a foundation for the theory of variable metric proximal point algorithms in Hilbert
space. In that work conditions are developed for global, linear, and super–linear convergence. This paper focuses attention
on two matrix secant updating strategies for the finite dimensional case. These are the Broyden and BFGS updates. The BFGS
update is considered for application in the symmetric case, e.g., convex programming applications, while the Broyden update
can be applied to general monotone operators. Subject to the linear convergence of the iterates and a quadratic growth condition
on the inverse of the operator at the solution, super–linear convergence of the iterates is established for both updates.
These results are applied to show that the Chen–Fukushima variable metric proximal point algorithm is super–linearly convergent
when implemented with the BFGS update.
Received: September 12, 1996 / Accepted: January 7, 2000?Published online March 15, 2000 相似文献
10.
The stable admissions polytope– the convex hull of the stable assignments of the university admissions problem – is described by a set of linear inequalities.
It depends on a new characterization of stability and arguments that exploit and extend a graphical approach that has been
fruitful in the analysis of the stable marriage problem.
Received: April 10, 1998 / Accepted: June 3, 1999?Published online January 27, 2000 相似文献
11.
This paper is about set packing relaxations of combinatorial optimization problems associated with acyclic digraphs and linear orderings, cuts and multicuts, and set
packings themselves. Families of inequalities that are valid for such a relaxation as well as the associated separation routines
carry over to the problems under investigation.
Received: September 1997 / Accepted: November 1999?Published online June 8, 2000 相似文献
12.
Self-regular functions and new search directions for linear and semidefinite optimization 总被引:11,自引:0,他引:11
In this paper, we introduce the notion of a self-regular function. Such a function is strongly convex and smooth coercive on its domain, the positive real axis. We show that any
such function induces a so-called self-regular proximity function and a corresponding search direction for primal-dual path-following
interior-point methods (IPMs) for solving linear optimization (LO) problems. It is proved that the new large-update IPMs enjoy
a polynomial ?(n
log) iteration bound, where q≥1 is the so-called barrier degree of the kernel function underlying the algorithm. The constant hidden in the ?-symbol depends
on q and the growth degree p≥1 of the kernel function. When choosing the kernel function appropriately the new large-update IPMs have a polynomial ?(lognlog) iteration bound, thus improving the currently best known bound for large-update methods by almost a factor . Our unified analysis provides also the ?(log) best known iteration bound of small-update IPMs. At each iteration, we need to solve only one linear system. An extension
of the above results to semidefinite optimization (SDO) is also presented.
Received: March 2000 / Accepted: December 2001?Published online April 12, 2002 相似文献
13.
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 相似文献
14.
Sien Deng 《Mathematical Programming》1998,83(1-3):263-276
In this paper several types of perturbations on a convex inequality system are considered, and conditions are obtained for
the system to be well-conditioned under these types of perturbations, where the well-conditionedness of a convex inequality
system is defined in terms of the uniform boundedness of condition numbers under a set of perturbations. It is shown that
certain types of perturbations can be used to characterize the well-conditionedness of a convex inequality system, in which
either the system has a bounded solution set and satisfies the Slater condition or an associated convex inequality system,
which defines the recession cone of the solution set for the system, satisfies the Slater condition. Finally, sufficient conditions
are given for the existence of a global error bound for an analytic system. It is shown that such a global error bound always
holds for any inequality system defined by finitely many convex analytic functions when the zero vector is in the relative
interior of the domain of an associated convex conjugate function. 相似文献
15.
Based on the authors’ previous work which established theoretical foundations of two, conceptual, successive convex relaxation
methods, i.e., the SSDP (Successive Semidefinite Programming) Relaxation Method and the SSILP (Successive Semi-Infinite Linear Programming)
Relaxation Method, this paper proposes their implementable variants for general quadratic optimization problems. These problems
have a linear objective function c
T
x to be maximized over a nonconvex compact feasible region F described by a finite number of quadratic inequalities. We introduce two new techniques, “discretization” and “localization,”
into the SSDP and SSILP Relaxation Methods. The discretization technique makes it possible to approximate an infinite number
of semi-infinite SDPs (or semi-infinite LPs) which appeared at each iteration of the original methods by a finite number of
standard SDPs (or standard LPs) with a finite number of linear inequality constraints. We establish:?•Given any open convex set U containing F, there is an implementable discretization of the SSDP (or SSILP) Relaxation Method
which generates a compact convex set C such that F⊆C⊆U in a finite number of iterations.?The localization technique is for the cases where we are only interested in upper bounds on the optimal objective value (for
a fixed objective function vector c) but not in a global approximation of the convex hull of F. This technique allows us to generate a convex relaxation of F that is accurate only in certain directions in a neighborhood of the objective direction c. This cuts off redundant work to make the convex relaxation accurate in unnecessary directions. We establish:?•Given any positive number ε, there is an implementable localization-discretization of the SSDP (or SSILP) Relaxation Method
which generates an upper bound of the objective value within ε of its maximum in a finite number of iterations.
Received: June 30, 1998 / Accepted: May 18, 2000?Published online September 20, 2000 相似文献
16.
In this paper we study the properties of the analytic central path of a semidefinite programming problem under perturbation
of the right hand side of the constraints, including the limiting behavior when the central optimal solution, namely the analytic
center of the optimal set, is approached. Our analysis assumes the primal-dual Slater condition and the strict complementarity
condition. Our findings are as follows. First, on the negative side, if we view the central optimal solution as a function
of the right hand side of the constraints, then this function is not continuous in general, whereas in the linear programming
case this function is known to be Lipschitz continuous. On the positive side, compared with the previous conclusion we obtain
a (seemingly) paradoxical result: on the central path any directional derivative with respect to the right hand side of the
constraints is bounded, and even converges as the central optimal solution is approached. This phenomenon is possible due
to the lack of a uniform bound on the derivatives with respect to the right hand side parameters. All these results are based
on the strict complementarity assumption. Concerning this last property we give an example. In that example the set of right
hand side parameters for which the strict complementarity condition holds is neither open nor closed. This is remarkable since
a similar set for which the primal-dual Slater condition holds is always open.
Received: April 2, 1998 / Accepted: January 16, 2001?Published online March 22, 2001 相似文献
17.
The General Routing Problem (GRP) is the problem of finding a minimum cost route for a single vehicle, subject to the condition that the vehicle visits
certain vertices and edges of a network. It contains the Rural Postman Problem, Chinese Postman Problem and Graphical Travelling Salesman Problem as special cases. We describe a cutting plane algorithm for the GRP based on facet-inducing inequalities and show that it
is capable of providing very strong lower bounds and, in most cases, optimal solutions.
Received: November 1998 / Accepted: September 2000?Published online March 22, 2001 相似文献
18.
Manuel A. Nunez 《Mathematical Programming》2002,91(2):375-390
Given a data instance of a convex program, we provide a collection of conic linear systems such that the data instance is
ill-posed if and only if at least one of those systems is satisfied. This collection of conic linear systems is derived from
a characterization of the boundary of the set of primal and dual feasible data instances associated with the given convex
program.
Received: September 1998 / Accepted: August 2000?Published online October 26, 2001 相似文献
19.
Portfolio optimization problem under concave transaction costs and minimal transaction unit constraints 总被引:9,自引:0,他引:9
We will propose a branch and bound algorithm for calculating a globally optimal solution of a portfolio construction/rebalancing
problem under concave transaction costs and minimal transaction unit constraints. We will employ the absolute deviation of
the rate of return of the portfolio as the measure of risk and solve linear programming subproblems by introducing (piecewise)
linear underestimating function for concave transaction cost functions. It will be shown by a series of numerical experiments
that the algorithm can solve the problem of practical size in an efficient manner.
Received: July 15, 1999 / Accepted: October 1, 2000?Published online December 15, 2000 相似文献
20.
Alberto Calabri 《Annali di Matematica Pura ed Applicata》2002,181(4):365-387
Following the ideas of Castelnuovo and Enriques, we classify the birational equivalence classes of double planes which are
rational or ruled surfaces. In order to do this, we prove that the vanishing of the m-adjoint linear system to the branch curve of the canonical resolution of a double plane, for m≥2, is a necessary and sufficient condition for the ruledness of the double plane.
Received: May 18, 2000?Published online: October 30, 2002
Partially supported by E.C. project EAGER, contract n. HPRN-CT-2000-00099 相似文献