共查询到20条相似文献,搜索用时 0 毫秒
1.
We present a framework for designing and analyzing primal-dual interior-point methods for convex optimization. We assume that a self-concordant barrier for the convex domain of interest and the Legendre transformation of the barrier are both available to us. We directly apply the theory and techniques of interior-point methods to the given good formulation of the problem (as is, without a conic reformulation) using the very usual primal central path concept and a less usual version of a dual path concept. We show that many of the advantages of the primal-dual interior-point techniques are available to us in this framework and therefore, they are not intrinsically tied to the conic reformulation and the logarithmic homogeneity of the underlying barrier function.Part of the research was done while the author was a Visiting Professor at the University of Waterloo.Research of this author is supported in part by a PREA from Ontario and by a NSERC Discovery Grant. Tel: (519) 888-4567 ext.5598, Fax: (519) 725-5441Mathematics Subject Classification (2000): 90C51, 90C25, 65Y20,90C28, 49D49 相似文献
2.
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. 相似文献
3.
Given a self-concordant barrier function for a convex set
, we determine a self-concordant barrier function for the conic hull
of
. As our main result, we derive an “optimal” barrier for
based on the barrier function for
. Important applications of this result include the conic reformulation of a convex problem, and the solution of fractional
programs by interior-point methods. The problem of minimizing a convex-concave fraction over some convex set can be solved
by applying an interior-point method directly to the original nonconvex problem, or by applying an interior-point method to
an equivalent convex reformulation of the original problem. Our main result allows to analyze the second approach showing
that the rate of convergence is of the same order in both cases. 相似文献
4.
Jean-Pierre Dussault Abdellatif Elafia 《Computational Optimization and Applications》2001,19(1):31-53
Since the pioneering work of Karmarkar, much interest was directed to penalty algorithms, in particular to the log barrier algorithm. We analyze in this paper the asymptotic convergence rate of a barrier algorithm when applied to non-linear programs. More specifically, we consider a variant of the SUMT method, in which so called extrapolation predictor steps allowing reducing the penalty parameter rk +1}k are followed by some Newton correction steps. While obviously related to predictor-corrector interior point methods, the spirit differs since our point of view is biased toward nonlinear barrier algorithms; we contrast in details both points of view. In our context, we identify an asymptotically optimal strategy for reducing the penalty parameter r and show that if rk+1=r
k
with < 8/5, then asymptotically only 2 Newton corrections are required, and this strategy achieves the best overall average superlinear convergence order (1.1696). Therefore, our main result is to characterize the best possible convergence order for SUMT type methods. 相似文献
5.
In this paper, we study the Riemannian length of the primal central path in a convex set computed with respect to the local
metric defined by a self-concordant function. Despite some negative examples, in many important situations, the length of
this path is quite close to the length of a geodesic curve. We show that in the case of a bounded convex set endowed with
a ν-self-concordant barrier, the length of the central path is within a factor O(ν
1/4) of the length of the shortest geodesic curve.
This paper presents research results of the Belgian Program on Interuniversity Poles of Attraction initiated by the Belgian
State, Prime Minister’s Office, Science Policy Programming. 相似文献
6.
This paper discusses self-concordant functions on smooth manifolds. In Euclidean space, such functions are utilized extensively
as barrier functions in interior-point methods for polynomial time optimization algorithms. Here, the self-concordant function
is carefully defined on a differential manifold in such a way that the properties of self-concordant functions in Euclidean
space are preserved. A Newton decrement is defined and analyzed for this class of functions. Based on this, a damped Newton
algorithm is proposed for the optimization of self-concordant functions. Under reasonable technical assumptions such as geodesic
completeness of the manifold, this algorithm is guaranteed to fall in any given small neighborhood of the optimal solution
in a finite number of steps. The existence and uniqueness of the optimal solution is also proved in this paper. Hence, the
optimal solution is a global one. Furthermore, it ensures a quadratic convergence within a neighborhood of the minimal point.
This neighborhood can be specified in terms of the Newton decrement. The computational complexity bound of the proposed approach
is also given explicitly. This complexity bound is shown to be of the order where is the desired precision. Some interesting optimization problems are given to illustrate the proposed concept and algorithm.
A part of the materials has been presented at 2004 Conference on Decision and Control 相似文献
7.
Michael J. Todd 《Mathematical Programming》1997,76(1):3-45
We provide a survey of interior-point methods for linear programming and its extensions that are based on reducing a suitable
potential function at each iteration. We give a fairly complete overview of potential-reduction methods for linear programming,
focusing on the possibility of taking long steps and the properties of the barrier function that are necessary for the analysis.
We then describe briefly how the methods and results can be extended to certain convex programming problems, following the
approach of Nesterov and Todd. We conclude with some open problems.
Research supported in part by NSF, AFOSR and ONR through NSF Grant DMS-8920550. Some of this work was done while the author
was on a sabbatical leave from Cornell University visiting the Department of Mathematics at the University of Washington. 相似文献
8.
Yu. Nesterov 《Mathematical Programming》1995,69(1-3):149-176
In this paper we establish the efficiency estimates for two cutting plane methods based on the analytic barrier. We prove that the rate of convergence of the second method is optimal uniformly in the number of variables. We present a modification of the second method. In this modified version each test point satisfies an approximate centering condition. We also use the standard strategy for updating approximate Hessians of the logarithmic barrier function. We prove that the rate of convergence of the modified scheme remains optimal and demonstrate that the number of Newton steps in the auxiliary minimization processes is bounded by an absolute constant. We also show that the approximate Hessian strategy significantly improves the total arithmetical complexity of the method. 相似文献
9.
A Lagrangian Dual Method with Self-Concordant Barriers for Multi-Stage Stochastic Convex Programming
Gongyun Zhao 《Mathematical Programming》2005,102(1):1-24
This paper presents an algorithm for solving multi-stage stochastic convex nonlinear programs. The algorithm is based on the Lagrangian dual method which relaxes the nonanticipativity constraints, and the barrier function method which enhances the smoothness of the dual objective function so that the Newton search directions can be used. The algorithm is shown to be of global convergence and of polynomial-time complexity.Mathematics Subject Classification (2000): 90C15, 90C51, 90C06, 90C25, 90C60Research is partially supported by NUS Academic Research Grant R-146-000-006-112 相似文献
10.
We develop an interior-point technique for solving quadratic programming problems in a Hilbert space. As an example, we consider an application of these results to the linear-quadratic control problem with linear inequality constraints. It is shown that the Newton step in this situation is basically reduced to solving the standard linear-quadratic control problem. 相似文献
11.
We consider the continuous trajectories of the vector field induced by the primal affine scaling algorithm as applied to linear programming problems in standard form. By characterizing these trajectories as solutions of certain parametrized logarithmic barrier families of problems, we show that these trajectories tend to an optimal solution which in general depends on the starting point. By considering the trajectories that arise from the Lagrangian multipliers of the above mentioned logarithmic barrier families of problems, we show that the trajectories of the dual estimates associated with the affine scaling trajectories converge to the so called centered optimal solution of the dual problem. We also present results related to asymptotic direction of the affine scaling trajectories. We briefly discuss how to apply our results to linear programs formulated in formats different from the standard form. Finally, we extend the results to the primal-dual affine scaling algorithm. 相似文献
12.
We describe a primal-dual interior point algorithm for linear programming problems which requires a total of
number of iterations, whereL is the input size. Each iteration updates a penalty parameter and finds the Newton direction associated with the Karush-Kuhn-Tucker system of equations which characterizes a solution of the logarithmic barrier function problem. The algorithm is based on the path following idea. 相似文献
13.
Inexact Interior-Point Method 总被引:2,自引:0,他引:2
S. Bellavia 《Journal of Optimization Theory and Applications》1998,96(1):109-121
In this paper, we introduce an inexact interior-point algorithm for a constrained system of equations. The formulation of the problem is quite general and includes nonlinear complementarity problems of various kinds. In our convergence theory, we interpret the inexact interior-point method as an inexact Newton method. This enables us to establish a global convergence theory for the proposed algorithm. Under the additional assumption of the invertibility of the Jacobian at the solution, the superlinear convergence of the iteration sequence is proved. 相似文献
14.
Durazzi C. Ruggiero V. Zanghirati G. 《Journal of Optimization Theory and Applications》2001,110(2):289-313
This paper concerns the use of iterative solvers in interior-point methods for linear and quadratic programming problems. We state an adaptive termination rule for the inner iterative scheme and we prove the global convergence of the obtained algorithm, exploiting the theory developed for inexact Newton methods. This approach is promising for problems with special structure on parallel computers. We present an application on Cray T3E/256 and SGI Origin 2000/64 arising in stochastic linear programming and robust optimization, where the constraint matrix is block-angular and extremely large. 相似文献
15.
Interior path following primal-dual algorithms. part II: Convex quadratic programming 总被引:4,自引:0,他引:4
We describe a primal-dual interior point algorithm for convex quadratic programming problems which requires a total of
number of iterations, whereL is the input size. Each iteration updates a penalty parameter and finds an approximate Newton direction associated with the Karush-Kuhn-Tucker system of equations which characterizes a solution of the logarithmic barrier function problem. The algorithm is based on the path following idea. The total number of arithmetic operations is shown to be of the order of O(n
3
L). 相似文献
16.
El-Alem M. M. El-Sayed S. El-Sobky B. 《Journal of Optimization Theory and Applications》2004,120(3):487-502
In this paper, a formulation for an interior-point Newton method of general nonlinear programming problems is presented. The formulation uses the Coleman-Li scaling matrix. The local convergence and the q-quadratic rate of convergence for the method are established under the standard assumptions of the Newton method for general nonlinear programming. 相似文献
17.
G. Alduncin 《Applied Mathematics and Optimization》1997,35(1):21-44
Iterative numerical algorithms for variational inequalities are systematically constructed from fixed-point problem characterizations
in terms of resolvent operators. The applied method is the one introduced by Gabay in [Ga], used here in the context of discrete
variational inequalities, and with the emphasis on mixed finite element models. The algorithms apply to nonnecessarily potential
problems, generalizing primal and mixed Uzawa and augmented Lagrangian-type algorithms. They are also identified with Euler
and operator splitting methods for the time discretization of evolution first-order problems. 相似文献
18.
A. Germani C. Manes P. Palumbo M. Sciandrone 《Journal of Optimization Theory and Applications》2006,131(3):347-364
A new iterative method to find the root of a nonlinear scalar function f is proposed. The method is based on a suitable Taylor polynomial model of order n around the current point x
k
and involves at each iteration the solution of a linear system of dimension n. It is shown that the coefficient matrix of the linear system is nonsingular if and only if the first derivative of f at x
k
is not null. Moreover, it is proved that the method is locally convergent with order of convergence at least n + 1. Finally, an easily implementable scheme is provided and some numerical results are reported. 相似文献
19.
Renato D. C. Monteiro Stephen J. Wright 《Computational Optimization and Applications》1994,3(2):131-155
Most asymptotic convergence analysis of interior-point algorithms for monotone linear complementarity problems assumes that the problem is nondegenerate, that is, the solution set contains a strictly complementary solution. We investigate the behavior of these algorithms when this assumption is removed.The work of this author was based on research supported by the National Science Foundation under grant DDM-9109404 and the Office of Naval Research under grant N00014-93-1-0234.The work of this author was based on research supported by the Office of Scientific Computing, U.S. Department of Energy, under Contract W-31-109-Eng-38. 相似文献
20.
Philip E. Gill Walter Murray Dulce B. Ponceleón Michael A. Saunders 《Mathematical Programming》1995,70(1-3):251-277
Many interior-point methods for linear programming are based on the properties of the logarithmic barrier function. After a preliminary discussion of the convergence of the (primal) projected Newton barrier method, three types of barrier method are analyzed. These methods may be categorized as primal, dual and primal—dual, and may be derived from the application of Newton's method to different variants of the same system of nonlinear equations. A fourth variant of the same equations leads to a new primal—dual method.In each of the methods discussed, convergence is demonstrated without the need for a nondegeneracy assumption or a transformation that makes the provision of a feasible point trivial. In particular, convergence is established for a primal—dual algorithm that allows a different step in the primal and dual variables and does not require primal and dual feasibility.Finally, a new method for treating free variables is proposed.Presented at the Second Asilomar Workshop on Progress in Mathematical Programming, February 1990, Asilomar, CA, United StatesThe material contained in this paper is based upon research supported by the National Science Foundation Grant DDM-9204208 and the Office of Naval Research Grant N00014-90-J-1242. 相似文献