共查询到20条相似文献,搜索用时 12 毫秒
1.
E. R. Avakov A. V. Arutyunov A. F. Izmailov 《Computational Mathematics and Mathematical Physics》2008,48(3):346-353
A new first-order sufficient condition for penalty exactness that includes neither the standard constraint qualification requirement nor the second-order sufficient optimality condition is proposed for optimization problems with equality constraints. 相似文献
2.
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 相似文献
3.
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 相似文献
4.
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 相似文献
5.
Asymptotic constraint qualifications and global error bounds for convex inequalities 总被引:2,自引:0,他引:2
Received October 26, 1996 / Revised version received October 1, 1997 Published online October 9, 1998 相似文献
6.
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 相似文献
7.
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 相似文献
8.
Error bounds for analytic systems and their applications 总被引:1,自引:0,他引:1
Using a 1958 result of Lojasiewicz, we establish an error bound for analytic systems consisting of equalities and inequalities defined by real analytic functions. In particular, we show that over any bounded region, the distance from any vectorx in the region to the solution set of an analytic system is bounded by a residual function, raised to a certain power, evaluated atx. For quadratic systems satisfying certain nonnegativity assumptions, we show that this exponent is equal to 1/2. We apply the error bounds to the Karush—Kuhn—Tucker system of a variational inequality, the affine variational inequality, the linear and nonlinear complementarity problem, and the 0–1 integer feasibility problem, and obtain new error bound results for these problems. The latter results extend previous work for polynomial systems and explain why a certain square-root term is needed in an error bound for the (monotone) linear complementarity problem.The research of this author is based on work supported by the Natural Sciences and Engineering Research Council of Canada under grant OPG0090391.The research of this author is based on work supported by the National Science Foundation under grants DDM-9104078 and CCR-9213739 and by the Office of Naval Research under grant 4116687-01. 相似文献
9.
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 相似文献
10.
Mihai Anitescu 《Mathematical Programming》2002,92(2):359-386
We analyze the convergence of a sequential quadratic programming (SQP) method for nonlinear programming for the case in which
the Jacobian of the active constraints is rank deficient at the solution and/or strict complementarity does not hold for some
or any feasible Lagrange multipliers. We use a nondifferentiable exact penalty function, and we prove that the sequence generated
by an SQP using a line search is locally R-linearly convergent if the matrix of the quadratic program is positive definite
and constant over iterations, provided that the Mangasarian-Fromovitz constraint qualification and some second-order sufficiency
conditions hold.
Received: April 28, 1998 / Accepted: June 28, 2001?Published online April 12, 2002 相似文献
11.
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 相似文献
12.
H. Hu 《Mathematical Programming》2000,88(2):277-284
This paper studies the existence of a uniform global error bound when a system of linear inequalities is under local arbitrary
perturbations. Specifically, given a possibly infinite system of linear inequalities satisfying the Slater’s condition and
a certain compactness condition, 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 the original system is bounded or its homogeneous system has
a strict solution.
Received: April 12, 1998 / Accepted: February 11, 2000?Published online July 20, 2000 相似文献
13.
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 相似文献
14.
Lagrangean dualization and subgradient optimization techniques are frequently used within the field of computational optimization
for finding approximate solutions to large, structured optimization problems. The dual subgradient scheme does not automatically
produce primal feasible solutions; there is an abundance of techniques for computing such solutions (via penalty functions,
tangential approximation schemes, or the solution of auxiliary primal programs), all of which require a fair amount of computational
effort.
We consider a subgradient optimization scheme applied to a Lagrangean dual formulation of a convex program, and construct,
at minor cost, an ergodic sequence of subproblem solutions which converges to the primal solution set. Numerical experiments
performed on a traffic equilibrium assignment problem under road pricing show that the computation of the ergodic sequence
results in a considerable improvement in the quality of the primal solutions obtained, compared to those generated in the
basic subgradient scheme.
Received February 11, 1997 / Revised version received June 19, 1998?Published online June 28, 1999 相似文献
15.
Consider the 2-matching problem defined on the complete graph, with edge costs which satisfy the triangle inequality. We prove
that the value of a minimum cost 2-matching is bounded above by 4/3 times the value of its linear programming relaxation,
the fractional 2-matching problem. This lends credibility to a long-standing conjecture that the optimal value for the traveling
salesman problem is bounded above by 4/3 times the value of its linear programming relaxation, the subtour elimination problem.
Received August 26, 1996 / Revised version received July 6, 1999? Published online September 15, 1999 相似文献
16.
A. L. Dontchev W. W. Hager K. Malanowski 《Numerical Functional Analysis & Optimization》2013,34(5-6):653-682
We examine convergence of the Euler approximation to a nonlinear optimal control problem subject to mixed state-control and pure state constraints. We prove that under smoothness, independence, controllability and coercivity conditions at a reference solution of the continuous problem, there exists a locally unique solution to the Euler approximation, for sufficiently fine discretization, which converges to the reference solution with rate proportional to the mesh size. 相似文献
17.
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 相似文献
18.
Alexander A. Georgiev 《Statistics & probability letters》1984,2(1):45-50
The problem of the estimation of functions and their derivatives from noisy observations is considered. The new kernel estimate is shown to be consistent in the mean square sense and an exact bound on the uniform mean squared error is given. An application to the system identification is discussed. 相似文献
19.
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 相似文献
20.
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 相似文献