For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
A Priori Estimation of Newton Type Homotopy Method for Calculating an Optimal Solution of Convex Optimization Problem
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 1995/10/25
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Nonlinear Theory and Its Applications)
homotopy method, convex programming, nonlinear programming, computational complexity, monotone operator, nonlinear system analysis,
Full Text: PDF>>
In this paper a priori estimation method is presented for calculating solution of convex optimization problems (COP) with some equality and/or inequality constraints by so-called Newton type homotopy method. The homotopy method is known as an efficient algorithm which can always calculate solution of nonlinear equations under a certain mild condition. Although, in general, it is difficult to estimate a priori computational complexity of calculating solution by the homotopy method. In the presented papers, a sufficient condition is considered for linear homotopy, under which an upper bound of the complexity can be estimated a priori. For the condition it is seen that Urabe type convergence theorem plays an important role. In this paper, by introducing the results, it is shown that under a certain condition a global minimum of COP can be always calculated, and that computational complexity of the calculation can be a priori estimated. Suitability of the estimation for analysing COP is also discussed.