共查询到20条相似文献,搜索用时 15 毫秒
1.
Inexact implicit methods for monotone general variational inequalities 总被引:32,自引:0,他引:32
Bingsheng He 《Mathematical Programming》1999,86(1):199-217
Solving a variational inequality problem is equivalent to finding a solution of a system of nonsmooth equations. Recently,
we proposed an implicit method, which solves monotone variational inequality problem via solving a series of systems of nonlinear
smooth (whenever the operator is smooth) equations. It can exploit the facilities of the classical Newton–like methods for
smooth equations. In this paper, we extend the method to solve a class of general variational inequality problems Moreover, we improve the implicit method to allow inexact solutions of the systems of nonlinear equations at each iteration.
The method is shown to preserve the same convergence properties as the original implicit method.
Received July 31, 1995 / Revised version received January 15, 1999? Published online May 28, 1999 相似文献
2.
A trust region method based on interior point techniques for nonlinear programming 总被引:15,自引:0,他引:15
An algorithm for minimizing a nonlinear function subject to nonlinear inequality constraints is described. It applies sequential
quadratic programming techniques to a sequence of barrier problems, and uses trust regions to ensure the robustness of the
iteration and to allow the direct use of second order derivatives. This framework permits primal and primal-dual steps, but
the paper focuses on the primal version of the new algorithm. An analysis of the convergence properties of this method is
presented.
Received: May 1996 / Accepted: August 18, 2000?Published online October 18, 2000 相似文献
3.
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 相似文献
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.
An interior Newton method for quadratic programming 总被引:2,自引:0,他引:2
We propose a new (interior) approach for the general quadratic programming problem. We establish that the new method has strong
convergence properties: the generated sequence converges globally to a point satisfying the second-order necessary optimality
conditions, and the rate of convergence is 2-step quadratic if the limit point is a strong local minimizer. Published alternative
interior approaches do not share such strong convergence properties for the nonconvex case. We also report on the results
of preliminary numerical experiments: the results indicate that the proposed method has considerable practical potential.
Received October 11, 1993 / Revised version received February 20, 1996
Published online July 19, 1999 相似文献
6.
Florian A. Potra 《Mathematical Programming》2001,91(1):99-115
Sufficient conditions are given for the Q-superlinear convergence of the iterates produced by primal-dual interior-point methods
for linear complementarity problems. It is shown that those conditions are satisfied by several well known interior-point
methods. In particular it is shown that the iteration sequences produced by the simplified predictor–corrector method of Gonzaga
and Tapia, the simplified largest step method of Gonzaga and Bonnans, the LPF+ algorithm of Wright, the higher order methods
of Wright and Zhang, Potra and Sheng, and Stoer, Wechs and Mizuno are Q-superlinearly convergent.
Received: February 9, 2000 / Accepted: February 20, 2001?Published online May 3, 2001 相似文献
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.
Roman A. Polyak 《Mathematical Programming》2002,92(2):197-235
We introduce an alternative to the smoothing technique approach for constrained optimization. As it turns out for any given
smoothing function there exists a modification with particular properties. We use the modification for Nonlinear Rescaling
(NR) the constraints of a given constrained optimization problem into an equivalent set of constraints.?The constraints transformation
is scaled by a vector of positive parameters. The Lagrangian for the equivalent problems is to the correspondent Smoothing
Penalty functions as Augmented Lagrangian to the Classical Penalty function or MBFs to the Barrier Functions. Moreover the
Lagrangians for the equivalent problems combine the best properties of Quadratic and Nonquadratic Augmented Lagrangians and
at the same time are free from their main drawbacks.?Sequential unconstrained minimization of the Lagrangian for the equivalent
problem in primal space followed by both Lagrange multipliers and scaling parameters update leads to a new class of NR multipliers
methods, which are equivalent to the Interior Quadratic Prox methods for the dual problem.?We proved convergence and estimate
the rate of convergence of the NR multipliers method under very mild assumptions on the input data. We also estimate the rate
of convergence under various assumptions on the input data.?In particular, under the standard second order optimality conditions
the NR method converges with Q-linear rate without unbounded increase of the scaling parameters, which correspond to the active
constraints.?We also established global quadratic convergence of the NR methods for Linear Programming with unique dual solution.?We
provide numerical results, which strongly support the theory.
Received: September 2000 / Accepted: October 2001?Published online April 12, 2002 相似文献
9.
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 相似文献
10.
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 相似文献
11.
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 相似文献
12.
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 相似文献
13.
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 相似文献
14.
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 相似文献
15.
In this paper, we propose a non-interior continuation method for solving generalized linear complementarity problems (GLCP)
introduced by Cottle and Dantzig. The method is based on a smoothing function derived from the exponential penalty function
first introduced by Kort and Bertsekas for constrained minimization. This smoothing function can also be viewed as a natural
extension of Chen-Mangasarian’s neural network smooth function. By using the smoothing function, we approximate GLCP as a
family of parameterized smooth equations. An algorithm is presented to follow the smoothing path. Under suitable assumptions,
it is shown that the algorithm is globally convergent and local Q-quadratically convergent. Few preliminary numerical results
are also reported.
Received September 3, 1997 / Revised version received April 27, 1999?Published online July 19, 1999 相似文献
16.
Sensitivity analysis in linear programming and semidefinite programming using interior-point methods
We analyze perturbations of the right-hand side and the cost parameters in linear programming (LP) and semidefinite programming
(SDP). We obtain tight bounds on the perturbations that allow interior-point methods to recover feasible and near-optimal
solutions in a single interior-point iteration. For the unique, nondegenerate solution case in LP, we show that the bounds
obtained using interior-point methods compare nicely with the bounds arising from using the optimal basis. We also present
explicit bounds for SDP using the Monteiro-Zhang family of search directions and specialize them to the AHO, H..K..M, and
NT directions.
Received: December 1999 / Accepted: January 2001?Published online March 22, 2001 相似文献
17.
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 相似文献
18.
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 相似文献
19.
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 相似文献
20.
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 相似文献