共查询到10条相似文献,搜索用时 93 毫秒
1.
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 相似文献
2.
A trust region and affine scaling interior point method for nonconvex minimization with linear inequality constraints 总被引:12,自引:0,他引:12
A trust region and affine scaling interior point method (TRAM) is proposed for a general nonlinear minimization with linear
inequality constraints [8]. In the proposed approach, a Newton step is derived from the complementarity conditions. Based
on this Newton step, a trust region subproblem is formed, and the original objective function is monotonically decreased.
Explicit sufficient decrease conditions are proposed for satisfying the first order and second order necessary conditions.?The
objective of this paper is to establish global and local convergence properties of the proposed trust region and affine scaling
interior point method. It is shown that the proposed explicit decrease conditions are sufficient for satisfy complementarity,
dual feasibility and second order necessary conditions respectively. It is also established that a trust region solution is
asymptotically in the interior of the proposed trust region subproblem and a properly damped trust region step can achieve
quadratic convergence.
Received: January 29, 1999 / Accepted: November 22, 1999?Published online February 23, 2000 相似文献
3.
A new method for derivative-free optimization is presented. It is designed for solving problems in which the objective function
is smooth and the number of variables is moderate, but the gradient is not available. The method generates a model that interpolates
the objective function at a set of sample points, and uses trust regions to promote convergence. The step-generation subproblem
ensures that all the iterates satisfy a geometric condition and are therefore adequate for updating the model. The sample
points are updated using a scheme that improves the accuracy of the interpolation model when needed. Two versions of the method
are presented: one using linear models and the other using quadratic models. Numerical tests comparing the new approach with
established methods for derivate-free optimization are reported.
Received: October 2000 / Accepted: August 2001?Published online October 26, 2001 相似文献
4.
Failure of global convergence for a class of interior point methods for nonlinear programming 总被引:6,自引:0,他引:6
Using a simple analytical example, we demonstrate that a class of interior point methods for general nonlinear programming,
including some current methods, is not globally convergent. It is shown that those algorithms produce limit points that are
neither feasible nor stationary points of some measure of the constraint violation, when applied to a well-posed problem.
Received: December 1999 / Accepted: May 2000?Published online August 18, 2000 相似文献
5.
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 相似文献
6.
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 相似文献
7.
On maximization of quadratic form over intersection of ellipsoids with common center 总被引:2,自引:2,他引:0
We demonstrate that if A
1,...,A
m
are symmetric positive semidefinite n×n matrices with positive definite sum and A is an arbitrary symmetric n×n matrix, then the relative accuracy, in terms of the optimal value, of the semidefinite relaxation of the optimization program is not worse than . It is shown that this bound is sharp in order, as far as the dependence on m is concerned, and that a~feasible solution x to (P) with can be found efficiently. This somehow improves one of the results of Nesterov [4] where bound similar to (*) is established
for the case when all Ai are of rank 1.
Received August 13, 1998 / Revised version received May 25, 1999? Published online September 15, 1999 相似文献
8.
M. S. Babynin V. G. Zhadan 《Computational Mathematics and Mathematical Physics》2008,48(10):1746-1767
The linear semidefinite programming problem is examined. A primal interior point method is proposed to solve this problem. It extends the barrier-projection method used for linear programs. The basic properties of the proposed method are discussed, and its local convergence is proved. 相似文献
9.
n . The method is based on Rockafellar’s proximal point algorithm and a cutting-plane technique. At each step, we use an approximate
proximal point pa(xk) of xk to define a vk∈∂εkf(pa(xk)) with εk≤α∥vk∥, where α is a constant. The method monitors the reduction in the value of ∥vk∥ to identify when a line search on f should be used. The quasi-Newton step is used to reduce the value of ∥vk∥. Without the differentiability of f, the method converges globally and the rate of convergence is Q-linear. Superlinear
convergence is also discussed to extend the characterization result of Dennis and Moré. Numerical results show the good performance
of the method.
Received October 3, 1995 / Revised version received August 20, 1998
Published online January 20, 1999 相似文献
10.
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 相似文献