
For FullText 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
Mitsunori MAKINO
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E78A
No.10
pp.13391344 Publication Date: 1995/10/25
Online ISSN:
DOI:
Print ISSN: 09168508 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)>>
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 socalled 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.

