共查询到20条相似文献,搜索用时 15 毫秒
1.
《Optimization》2012,61(2):161-190
In the present article rather general penalty/barrier-methods (e.g. logarithmic barriers, SUMT, exponential penalties), which define a local continuously differentiable primal and dual path, are analyzed in case of strict local minima of nonlinear problems with inequality as well as equality constraints. In particular, the radius of convergence of Newton's method depending on the penalty/barrier-parameter is estimated. Unlike using self-concordance properties, the convergence bounds are derived by direct estimations of the solutions of the Newton equations. By means of the obtained results parameter selection rules are studied which guarantee the local convergence of the considered penalty/barrier-techniques with only a finite number of Newton steps at each parameter level. Numerical examples illustrate the practical behavior of the proposed class of methods. 相似文献
2.
A two-level decomposition method for nonconvex separable optimization problems with additional local constraints of general inequality type is presented and thoroughly analyzed in the paper. The method is of primal-dual type, based on an augmentation of the Lagrange function. Previous methods of this type were in fact three-level, with adjustment of the Lagrange multipliers at one of the levels. This level is eliminated in the present approach by replacing the multipliers by a formula depending only on primal variables and Kuhn-Tucker multipliers for the local constraints. The primal variables and the Kuhn-Tucker multipliers are together the higher-level variables, which are updated simultaneously. Algorithms for this updating are proposed in the paper, together with their convergence analysis, which gives also indications on how to choose penalty coefficients of the augmented Lagrangian. Finally, numerical examples are presented. 相似文献
3.
In this paper, we consider a primal-dual interior point method for solving nonlinear semidefinite programming problems. We propose primal-dual interior point methods based on the unscaled and scaled Newton methods, which correspond to the AHO, HRVW/KSH/M and NT search directions in linear SDP problems. We analyze local behavior of our proposed methods and show their local and superlinear convergence properties. 相似文献
4.
We prove a new local convergence property of some primal-dual methods for solving nonlinear optimization problems. We consider
a standard interior point approach, for which the complementarity conditions of the original primal-dual system are perturbed
by a parameter driven to zero during the iterations. The sequence of iterates is generated by a linearization of the perturbed
system and by applying the fraction to the boundary rule to maintain strict feasibility of the iterates with respect to the
nonnegativity constraints. The analysis of the rate of convergence is carried out by considering an arbitrary sequence of
perturbation parameters converging to zero. We first show that, once an iterate belongs to a neighbourhood of convergence
of the Newton method applied to the original system, then the whole sequence of iterates converges to the solution. In addition,
if the perturbation parameters converge to zero with a rate of convergence at most superlinear, then the sequence of iterates
becomes asymptotically tangent to the central trajectory in a natural way. We give an example showing that this property can
be false when the perturbation parameter goes to zero quadratically.
相似文献
5.
In this paper we analyze the rate of local convergence of the Newton primal-dual interior-point method when the iterates are
kept strictly feasible with respect to the inequality constraints.
It is shown under the classical conditions that the rate is q-quadratic when the functions associated to the binding inequality
constraints are concave. In general, the q-quadratic rate is achieved provided the step in the primal variables does not become
asymptotically orthogonal to any of the gradients of the binding inequality constraints. 相似文献
6.
《Optimization》2012,61(3):353-374
In the present paper some barrier and penalty methods (e.g. logarithmic barriers, SUMT, exponential penalties), which define a continuously differentiable primal and dual path, applied to linearly constrained convex problems are studied, in particular, the radius of convergence of Newton’s method depending on the barrier and penalty para-meter is estimated, Unlike using self-concordance properties the convergence bounds are derived by direct estimations of the solutions of the Newton equations. The obtained results establish parameter selection rules which guarantee the overall convergence of the considered barrier and penalty techniques with only a finite number of Newton steps at each parameter level. Moreover, the obtained estimates support scaling method which uses approximate dual multipliers as available in barrier and penalty methods 相似文献
7.
Superlinear and quadratic convergence of some primal-dual interior point methods for constrained optimization 总被引:6,自引:0,他引:6
This paper proves local convergence rates of primal-dual interior point methods for general nonlinearly constrained optimization
problems. Conditions to be satisfied at a solution are those given by the usual Jacobian uniqueness conditions. Proofs about
convergence rates are given for three kinds of step size rules. They are: (i) the step size rule adopted by Zhang et al. in
their convergence analysis of a primal-dual interior point method for linear programs, in which they used single step size
for primal and dual variables; (ii) the step size rule used in the software package OB1, which uses different step sizes for
primal and dual variables; and (iii) the step size rule used by Yamashita for his globally convergent primal-dual interior
point method for general constrained optimization problems, which also uses different step sizes for primal and dual variables.
Conditions to the barrier parameter and parameters in step size rules are given for each case. For these step size rules,
local and quadratic convergence of the Newton method and local and superlinear convergence of the quasi-Newton method are
proved.
A preliminary version of this paper was presented at the conference “Optimization-Models and Algorithms” held at the Institute
of Statistical Mathematics, Tokyo, March 1993. 相似文献
8.
Inexact Newton methods are variant of the Newton method in which each step satisfies only approximately the linear system (Ref. 1). The local convergence theory given by the authors of Ref. 1 and most of the results based on it consider the error terms as being provided only by the fact that the linear systems are not solved exactly. The few existing results for the general case (when some perturbed linear systems are considered, which in turn are not solved exactly) do not offer explicit formulas in terms of the perturbations and residuals. We extend this local convergence theory to the general case, characterizing the rate of convergence in terms of the perturbations and residuals.The Newton iterations are then analyzed when, at each step, an approximate solution of the linear system is determined by the following Krylov solvers based on backward error minimization properties: GMRES, GMBACK, MINPERT. We obtain results concerning the following topics: monotone properties of the errors in these Newton–Krylov iterates when the initial guess is taken 0 in the Krylov algorithms; control of the convergence orders of the Newton–Krylov iterations by the magnitude of the backward errors of the approximate steps; similarities of the asymptotical behavior of GMRES and MINPERT when used in a converging Newton method. At the end of the paper, the theoretical results are verified on some numerical examples. 相似文献
9.
Alexey F. Izmailov Alexey S. Kurennoy Mikhail V. Solodov 《Set-Valued and Variational Analysis》2013,21(1):17-45
While generalized equations with differentiable single-valued base mappings and the associated Josephy–Newton method have been studied extensively, the setting with semismooth base mapping had not been previously considered (apart from the two special cases of usual nonlinear equations and of Karush–Kuhn–Tucker optimality systems). We introduce for the general semismooth case appropriate notions of solution regularity and prove local convergence of the corresponding Josephy–Newton method. As an application, we immediately recover the known primal-dual local convergence properties of semismooth sequential quadratic programming algorithm (SQP), but also obtain some new results that complete the analysis of the SQP primal rate of convergence, including its quasi-Newton variant. 相似文献
10.
On the Global Convergence of a Modified Augmented Lagrangian Linesearch Interior-Point Newton Method for Nonlinear Programming 总被引:1,自引:0,他引:1
We consider a linesearch globalization of the local primal-dual interior-point Newton method for nonlinear programming introduced by El-Bakry, Tapia, Tsuchiya, and Zhang. The linesearch uses a new merit function that incorporates a modification of the standard augmented Lagrangian function and a weak notion of centrality. We establish a global convergence theory and present promising numerical experimentation. 相似文献
11.
Generalized stationary points of the mathematical program with equilibrium constraints (MPEC) are studied to better describe the limit points produced by interior point methods for MPEC. A primal-dual interior-point method is then proposed, which solves a sequence of relaxed barrier problems derived from MPEC. Global convergence results are deduced under fairly general conditions other than strict complementarity or the linear independence constraint qualification for MPEC (MPEC-LICQ). It is shown that every limit point of the generated sequence is a strong stationary point of MPEC if the penalty parameter of the merit function is bounded. Otherwise, a point with certain stationarity can be obtained. Preliminary numerical results are reported, which include a case analyzed by Leyffer for which the penalty interior-point algorithm failed to find a stationary point.Mathematics Subject Classification (1991):90C30, 90C33, 90C55, 49M37, 65K10 相似文献
12.
One motivation for the standard primal-dual direction used in interior-point methods is that it can be obtained by solving a least-squares problem. In this paper, we propose a primal-dual interior-point method derived through a modified least-squares problem. The direction used is equivalent to the Newton direction for a weighted barrier function method with the weights determined by the current primal-dual iterate. We demonstrate that the Newton direction for the usual, unweighted barrier function method can be derived through a weighted modified least-squares problem. The algorithm requires a polynomial number of iterations. It enjoys quadratic convergence if the optimal vertex is nondegenerate.The research of the second author was supported in part by ONR Grants N00014-90-J-1714 and N00014-94-1-0391. 相似文献
13.
基于Powell和Yuan所建议的近似Fetcher罚函数作为函数使用单调线搜索的技术,本文提供了一类正割方法解约束优化。在合理的条件下,证明了所提供的算法的整体收敛性和收敛速率。 相似文献
14.
Kärkkäinen T. Kunisch K. Tarvainen P. 《Journal of Optimization Theory and Applications》2003,119(3):499-533
Active set strategies for two-dimensional and three-dimensional, unilateral and bilateral obstacle problems are described. Emphasis is given to algorithms resulting from the augmented Lagrangian (i.e., primal-dual formulation of the discretized obstacle problems), for which convergence and rate of convergence are considered. For the bilateral case, modifications of the basic primal-dual algorithm are also introduced and analyzed. Finally, efficient computer realizations that are based on multigrid and multilevel methods are suggested and different aspects of the proposed techniques are investigated through numerical experiments. 相似文献
15.
The simplified Newton method, at the expense of fast convergence, reduces the work required by Newton method by reusing the initial Jacobian matrix. The composite Newton method attempts to balance the trade-off between expense and fast convergence by composing one Newton step with one simplified Newton step. Recently, Mehrotra suggested a predictor-corrector variant of primal-dual interior point method for linear programming. It is currently the interior-point method of the choice for linear programming. In this work we propose a predictor-corrector interior-point algorithm for convex quadratic programming. It is proved that the algorithm is equivalent to a level-1 perturbed composite Newton method. Computations in the algorithm do not require that the initial primal and dual points be feasible. Numerical experiments are made. 相似文献
16.
S. Volkwein 《Computational Optimization and Applications》2003,26(3):253-284
A Lagrange-Newton-SQP method is analyzed for the optimal control of the Burgers equation. Boundary controls are given, which are restricted by pointwise lower and upper bounds. The convergence of the method is proved in appropriate Banach spaces. This proof is based on a second-order sufficient optimality condition and the theory of Newton methods for generalized equations in Banach spaces. For the numerical realization a primal-dual active set strategy is applied. To illustrate the theoretical investigations, numerical examples are included. Moreover, a globalization technique for the SQP method is tested numerically. 相似文献
17.
《Operations Research Letters》2014,42(6-7):404-408
Resource allocation problems are usually solved with specialized methods exploiting their general sparsity and problem-specific algebraic structure. We show that the sparsity structure alone yields a closed-form Newton search direction for the generic primal-dual interior point method. Computational tests show that the interior point method consistently outperforms the best specialized methods when no additional algebraic structure is available. 相似文献
18.
Yu. Nesterov 《Mathematical Programming》1997,76(1):47-94
In this paper we analyze from a unique point of view the behavior of path-following and primal-dual potential reduction methods
on nonlinear conic problems. We demonstrate that most interior-point methods with
efficiency estimate can be considered as different strategies of minimizing aconvex primal-dual potential function in an extended primal-dual space. Their efficiency estimate is a direct consequence of large
local norm of the gradient of the potential function along a central path. It is shown that the neighborhood of this path
is a region of the fastest decrease of the potential. Therefore the long-step path-following methods are, in a sense, the
best potential-reduction strategies. We present three examples of such long-step strategies. We prove also an efficiency estimate
for a pure primal-dual potential reduction method, which can be considered as an implementation of apenalty strategy based on a functional proximity measure. Using the convex primal dual potential, we prove efficiency estimates for
Karmarkar-type and Dikin-type methods as applied to a homogeneous reformulation of the initial primal-dual problem. 相似文献
19.
Paul Armand Joël Benoist Dominique Orban 《Computational Optimization and Applications》2008,41(1):1-25
We introduce a framework in which updating rules for the barrier parameter in primal-dual interior-point methods become dynamic.
The original primal-dual system is augmented to incorporate explicitly an updating function. A Newton step for the augmented
system gives a primal-dual Newton step and also a step in the barrier parameter. Based on local information and a line search,
the decrease of the barrier parameter is automatically adjusted. We analyze local convergence properties, report numerical
experiments on a standard collection of nonlinear problems and compare our results to a state-of-the-art interior-point implementation.
In many instances, the adaptive algorithm reduces the number of iterations and of function evaluations. Its design guarantees
a better fit between the magnitudes of the primal-dual residual and of the barrier parameter along the iterations. 相似文献
20.
Yuying Li 《Computational Optimization and Applications》1998,10(3):219-242
The Weiszfeld algorithm for continuous location problems can be considered as an iteratively reweighted least squares method. It generally exhibits linear convergence. In this paper, a Newton algorithm with similar simplicity is proposed to solve a continuous multifacility location problem with the Euclidean distance measure. Similar to the Weiszfeld algorithm, the main computation can be solving a weighted least squares problem at each iteration. A Cholesky factorization of a symmetric positive definite band matrix, typically with a small band width (e.g., a band width of two for a Euclidean location problem on a plane) is performed. This new algorithm can be regarded as a Newton acceleration to the Weiszfeld algorithm with fast global and local convergence. The simplicity and efficiency of the proposed algorithm makes it particularly suitable for large-scale Euclidean location problems and parallel implementation. Computational experience suggests that the proposed algorithm often performs well in the absence of the linear independence or strict complementarity assumption. In addition, the proposed algorithm is proven to be globally convergent under similar assumptions for the Weiszfeld algorithm. Although local convergence analysis is still under investigation, computation results suggest that it is typically superlinearly convergent. 相似文献