共查询到20条相似文献,搜索用时 15 毫秒
1.
theory. This approach also quantifies the size of permissible perturbations. We include a discussion of these results for
block diagonal semidefinite programs, of which linear programming is a special case.
Received November 26, 1995 / Revised version received November 1, 1998
Published online February 25, 1999 相似文献
2.
Received August 29, 1996 / Revised version received May 1, 1998 Published online October 21, 1998 相似文献
3.
Received May 28, 1996 / Revised version received May 1, 1998 Published online October 9, 1998 相似文献
4.
Walter Gómez Bofill 《Mathematical Programming》1999,86(3):649-659
The paper presents an interior embedding of nonlinear optimization problems. This embedding satisfies a sufficient condition
for the success of pathfollowing algorithms with jumps being applied to one-parametric optimization problems.?The one-parametric
problem obtained by the embedding is supposed to be regular in the sense of Jongen, Jonker and Twilt. This asumption is analyzed,
and its genericity is proved in the space of the original optimization problems.
Received May 20, 1997 / Revised version received October 6, 1998?Published online May 12, 1999 相似文献
5.
Metric regularity and quantitative stability in stochastic programs with probabilistic constraints 总被引:2,自引:0,他引:2
Received January 24, 1996 / Revised version received December 24, 1997 Published online October 21, 1998 相似文献
6.
Jan-J. Rückmann 《Mathematical Programming》1999,86(2):387-415
The paper deals with semi-infinite optimization problems which are defined by finitely many equality constraints and infinitely
many inequality constraints. We generalize the concept of strongly stable stationary points which was introduced by Kojima
for finite problems; it refers to the local existence and uniqueness of a stationary point for each sufficiently small perturbed
problem, where perturbations up to second order are allowed. Under the extended Mangasarian-Fromovitz constraint qualification
we present equivalent conditions for the strong stability of a considered stationary point in terms of first and second derivatives
of the involved functions. In particular, we discuss the case where the reduction approach is not satisfied.
Received June 30, 1995 / Revised version received October 9, 1998?
Published online June 11, 1999 相似文献
7.
A.S. Lewis 《Mathematical Programming》1999,84(1):1-24
Received October 28, 1996 / Revised version received January 28, 1998 Published online October 9, 1998 相似文献
8.
Martin Gugat 《Mathematical Programming》1999,85(3):643-653
The growth of the multipliers, when the parameter approaches such a critical parameter, is characterized by a parametric constraint
qualification which is introduced here. It is equivalent to a bound on the growth of the multipliers.
Received May 8, 1995 / Revised version received February 12, 1998
Published online February 25, 1999 相似文献
9.
In this paper we show that the cut does not need to go through the query point: it can be deep or shallow. The primal framework
leads to a simple analysis of the potential variation, which shows that the inequality needed for convergence of the algorithm
is in fact attained at the first iterate of the feasibility step.
Received July 3, 1996 / Revised version received July 11, 1997 Published online August 18, 1998 相似文献
10.
This paper concerns with convergence properties of the classical proximal point algorithm for finding zeroes of maximal monotone
operators in an infinite-dimensional Hilbert space. It is well known that the proximal point algorithm converges weakly to
a solution under very mild assumptions. However, it was shown by Güler [11] that the iterates may fail to converge strongly
in the infinite-dimensional case. We propose a new proximal-type algorithm which does converge strongly, provided the problem
has a solution. Moreover, our algorithm solves proximal point subproblems inexactly, with a constructive stopping criterion
introduced in [31]. Strong convergence is forced by combining proximal point iterations with simple projection steps onto
intersection of two halfspaces containing the solution set. Additional cost of this extra projection step is essentially negligible
since it amounts, at most, to solving a linear system of two equations in two unknowns.
Received January 6, 1998 / Revised version received August 9, 1999?Published online November 30, 1999 相似文献
11.
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 相似文献
12.
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 相似文献
13.
Krzysztof C. Kiwiel 《Mathematical Programming》1999,85(2):241-258
k } by taking xk to be an approximate minimizer of , where is a piecewise linear model of f constructed from accumulated subgradient linearizations of f, Dh is the D-function of a generalized Bregman function h and tk>0. Convergence under implementable criteria is established by extending our recent framework of Bregman proximal minimization,
which is of independent interest, e.g., for nonquadratic multiplier methods for constrained minimization. In particular, we
provide new insights into the convergence properties of bundle methods based on h=?|·|2.
Received September 18, 1997 / Revised version received June 30, 1998
Published online November 24, 1998 相似文献
14.
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 相似文献
15.
We present a construction which gives deterministic upper bounds for stochastic programs in which the randomness appears on
the right–hand–side and has a multivariate Gaussian distribution. Computation of these bounds requires the solution of only
as many linear programs as the problem has variables.
Received December 2, 1997 / Revised version received January 5, 1999? Published online May 12, 1999 相似文献
16.
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 相似文献
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.
M. Locatelli 《Mathematical Programming》1999,85(3):593-616
In this paper the problem of finding the global optimum of a concave function over a polytope is considered. A well-known
class of algorithms for this problem is the class of conical algorithms. In particular, the conical algorithm based on the
so called ω-subdivision strategy is considered. It is proved that, for any given accuracy ε>0, this algorithm stops in a finite
time by returning an ε-optimal solution for the problem, while it is convergent for ε=0.
Received January 24, 1996 / Revised version received December 9, 1998
Published online June 11, 1999 相似文献
19.
A class of affine-scaling interior-point methods for bound constrained optimization problems is introduced which are locally
q–superlinear or q–quadratic convergent. It is assumed that the strong second order sufficient optimality conditions at the
solution are satisfied, but strict complementarity is not required. The methods are modifications of the affine-scaling interior-point
Newton methods introduced by T. F. Coleman and Y. Li (Math. Programming, 67, 189–224, 1994). There are two modifications. One is a modification of the scaling matrix, the other one is the use of a
projection of the step to maintain strict feasibility rather than a simple scaling of the step. A comprehensive local convergence
analysis is given. A simple example is presented to illustrate the pitfalls of the original approach by Coleman and Li in
the degenerate case and to demonstrate the performance of the fast converging modifications developed in this paper.
Received October 2, 1998 / Revised version received April 7, 1999?Published online July 19, 1999 相似文献
20.
The bin packing problem is one of the classical NP-hard optimization problems. In this paper, we present a simple generic
approach for obtaining new fast lower bounds, based on dual feasible functions. Worst-case analysis as well as computational
results show that one of our classes clearly outperforms the previous best “economical” lower bound for the bin packing problem
by Martello and Toth, which can be understood as a special case. In particular, we prove an asymptotic worst-case performance
of 3/4 for a bound that can be computed in linear time for items sorted by size. In addition, our approach provides a general
framework for establishing new bounds.
Received: August 11, 1998 / Accepted: February 1, 2001?Published online September 17, 2001 相似文献