共查询到20条相似文献,搜索用时 31 毫秒
1.
G. Still 《Mathematical Programming》2001,91(1):53-69
The discretization approach for solving semi-infinite optimization problems is considered. We are interested in the convergence
rate of the error between the solution of the semi-infinite problem and the solution of the discretized program depending
on the discretization mesh-size. It will be shown how this rate depends on whether the minimizer is strict of order one or
two and on whether the discretization includes boundary points of the index set in a specific way. This is done for ordinary
and for generalized semi-infinite problems.
Received: November 21, 2000 / Accepted: May 2001?Published online September 17, 2001 相似文献
2.
Global error bounds with fractional exponents 总被引:2,自引:0,他引:2
Using the partial order induced by a proper weakly lower semicontinuous function on a reflexive Banach space X we give a sufficient condition for f to have error bounds with fractional exponents. Application is given to identify the set of such exponents for quadratic
functions.
Received: August 20, 1999 / Accepted: March 20, 2000?Published online July 20, 2000 相似文献
3.
Reinhard John 《Mathematical Programming》2000,88(1):147-155
It is shown that pseudomonotone and quasimonotone maps can be characterized by a first order property provided they are regular.
This result extends the well known characterization of nonvanishing generalized monotone maps to an essentially larger class.
The paper supplements a recent contribution by Crouzeix and Ferland (1996) and solves a related open problem concerning homogeneous
excess demand functions which occur in general equilibrium theory.
Received: April 10, 1998 / Accepted: February 29, 2000?Published online April 20, 2000 相似文献
4.
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 相似文献
5.
Stephen M. Robinson 《Mathematical Programming》1999,86(1):41-50
This paper establishes a linear convergence rate for a class of epsilon-subgradient descent methods for minimizing certain
convex functions on ℝ
n
. Currently prominent methods belonging to this class include the resolvent (proximal point) method and the bundle method
in proximal form (considered as a sequence of serious steps). Other methods, such as a variant of the proximal point method
given by Correa and Lemaréchal, can also fit within this framework, depending on how they are implemented. The convex functions
covered by the analysis are those whose conjugates have subdifferentials that are locally upper Lipschitzian at the origin,
a property generalizing classical regularity conditions.
Received March 29, 1996 / Revised version received March 5, 1999? Published online June 11, 1999 相似文献
6.
Trade-off information related to Pareto optimal solutions is important in multiobjective optimization problems with conflicting
objectives. Recently, the concept of trade-off directions has been introduced for convex problems. These trade-offs are characterized
with the help of tangent cones. Generalized trade-off directions for nonconvex problems can be defined by replacing convex
tangent cones with nonconvex contingent cones. Here we study how the convex concepts and results can be generalized into a
nonconvex case. Giving up convexity naturally means that we need local instead of global analysis.
Received: December 2000 / Accepted: October 2001?Published online February 14, 2002 相似文献
7.
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 相似文献
8.
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 相似文献
9.
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 相似文献
10.
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 相似文献
11.
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 相似文献
12.
Linear Programming based lower bounds have been considered both for the general as well as for the symmetric quadratic assignment
problem several times in the recent years. Their quality has turned out to be quite good in practice. Investigations of the
polytopes underlying the corresponding integer linear programming formulations (the non-symmetric and the symmetric quadratic
assignment polytope) have been started during the last decade [34, 31, 21, 22]. They have lead to basic knowledge on these
polytopes concerning questions like their dimensions, affine hulls, and trivial facets. However, no large class of (facet-defining)
inequalities that could be used in cutting plane procedures had been found. We present in this paper the first such class
of inequalities, the box inequalities, which have an interesting origin in some well-known hypermetric inequalities for the
cut polytope. Computational experiments with a cutting plane algorithm based on these inequalities show that they are very
useful with respect to the goal of solving quadratic assignment problems to optimality or to compute tight lower bounds. The
most effective ones among the new inequalities turn out to be indeed facet-defining for both the non-symmetric as well as
for the symmetric quadratic assignment polytope.
Received: April 17, 2000 / Accepted: July 3, 2001?Published online September 3, 2001 相似文献
13.
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 相似文献
14.
We generalize the disjunctive approach of Balas, Ceria, and Cornuéjols [2] and devevlop a branch-and-cut method for solving
0-1 convex programming problems. We show that cuts can be generated by solving a single convex program. We show how to construct
regions similar to those of Sherali and Adams [20] and Lovász and Schrijver [12] for the convex case. Finally, we give some
preliminary computational results for our method.
Received January 16, 1996 / Revised version received April 23, 1999?Published online June 28, 1999 相似文献
15.
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 相似文献
16.
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 相似文献
17.
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 相似文献
18.
The alternating directions method (ADM) is an effective method for solving a class of variational inequalities (VI) when the
proximal and penalty parameters in sub-VI problems are properly selected. In this paper, we propose a new ADM method which
needs to solve two strongly monotone sub-VI problems in each iteration approximately and allows the parameters to vary from
iteration to iteration. The convergence of the proposed ADM method is proved under quite mild assumptions and flexible parameter
conditions.
Received: January 4, 2000 / Accepted: October 2001?Published online February 14, 2002 相似文献
19.
Optimality conditions for nonconvex semidefinite programming 总被引:9,自引:0,他引:9
Anders Forsgren 《Mathematical Programming》2000,88(1):105-128
This paper concerns nonlinear semidefinite programming problems for which no convexity assumptions can be made. We derive
first- and second-order optimality conditions analogous to those for nonlinear programming. Using techniques similar to those
used in nonlinear programming, we extend existing theory to cover situations where the constraint matrix is structurally sparse.
The discussion covers the case when strict complementarity does not hold. The regularity conditions used are consistent with
those of nonlinear programming in the sense that the conventional optimality conditions for nonlinear programming are obtained
when the constraint matrix is diagonal.
Received: May 15, 1998 / Accepted: April 12, 2000?Published online May 12, 2000 相似文献
20.
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 相似文献