A Priori Estimation of Newton Type Homotopy Method for Calculating an Optimal Solution of Convex Optimization Problem

Mitsunori MAKINO  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E78-A   No.10   pp.1339-1344
Publication Date: 1995/10/25
Online ISSN: 
DOI: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Nonlinear Theory and Its Applications)
Category: 
Keyword: 
homotopy method,  convex programming,  nonlinear programming,  computational complexity,  monotone operator,  nonlinear system analysis,  

Full Text: PDF(412.8KB)>>
Buy this Article




Summary: 
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.