IEICE TRANSACTIONS on Fundamentals
A Priori Estimation of Newton Type Homotopy Method for Calculating an Optimal Solution of Convex Optimization Problem
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.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E78-A No.10 pp.1339-1344
- Publication Date
- 1995/10/25
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- Special Section PAPER (Special Section on Nonlinear Theory and Its Applications)
- Category
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Mitsunori MAKINO, "A Priori Estimation of Newton Type Homotopy Method for Calculating an Optimal Solution of Convex Optimization Problem" in IEICE TRANSACTIONS on Fundamentals,
vol. E78-A, no. 10, pp. 1339-1344, October 1995, doi: .
Abstract: 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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e78-a_10_1339/_p
Copy
@ARTICLE{e78-a_10_1339,
author={Mitsunori MAKINO, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={A Priori Estimation of Newton Type Homotopy Method for Calculating an Optimal Solution of Convex Optimization Problem},
year={1995},
volume={E78-A},
number={10},
pages={1339-1344},
abstract={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.},
keywords={},
doi={},
ISSN={},
month={October},}
Copy
TY - JOUR
TI - A Priori Estimation of Newton Type Homotopy Method for Calculating an Optimal Solution of Convex Optimization Problem
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1339
EP - 1344
AU - Mitsunori MAKINO
PY - 1995
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E78-A
IS - 10
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - October 1995
AB - 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.
ER -
English
