On Complexity Analysis for Primal-Dual Interior-Point Methods for Optimization Problems with Conic Constraints
- Alternative Title
- 추제약식을 가지고 있는 최적화 문제를 위한 원-쌍대 내점기법에 대한 복잡성 분석에 관한 연구
- Abstract
- 본 연구에서는 추제약식을 가지고 있는 최적화 문제인 2계추 최적화 문제, 반정부호 최적화 문제, 셀프 스케일 최적화 문제(대칭추 최적화 문제)에 대한 원-쌍대 내점기법을 위한 새로운 복잡성(complexity)분석에 관한 결과를 얻었다.
첫째로, 2계추 최적화 문제에 대해서는 새로운 핵함수(kernel function) , 를 정의하여 이를 기초로 한 근접함수(proximity function)를 정의하여 large-update 원-쌍대 내점기법 알고리즘을 만들었고, 그것의 복잡성 분석을 하여 최악의 반복 바운드(worst-case iteration bound)가 임을 보였다.
둘째로, 반정부호 최적화 문제에 대해서는 새로운 핵함수 , 에 의해 근접함수를 정의하였다. 그 근접함수를 이용하여 우리는 반정부호 최적화 문제에 대한 large-update 원-쌍대 내점기법 알고리즘을 만들었고, 그것의 복잡성 분석을 하여 최악의 반복 바운드가 임을 보였다.
셋째로, 셀프-레귤러 근접함수 이론과 조르단 대수 (Jordan algebra) 이론을 사용하고 잘 알려진 셀프-레귤러 함수인 핵함수 에 의한 근접함수를 이용하여, 유클리디안 조르단 대수에서 정의되는 셀프 스케일 최적화 문제(대칭추 최적화 문제)를 위한 large-update 원-쌍대 내점기법에 대한 알고리즘을 만들었고, 복잡성 분석을 하여 최악의 반복 바운드가 유클리디안 조르단 대수의 계수(rank)가 일 때 임을 보였다.
- Issued Date
- 2010
- Awarded Date
- 2010. 2
- Type
- Dissertation
- Keyword
- Interior-Point Methods Second-order Cone Optimization Problem Semidefinite Optimization Problem Self-scaled Optimization Problem Proximity Function Search Directions Iteration bound
- Publisher
- 부경대학교
- Alternative Author(s)
- Choi, Bo Kyung
- Affiliation
- 부경대학교 대학원 응용수학과
- Department
- 대학원 응용수학과
- Advisor
- 이규명
- Table Of Contents
- Contents
Abstract (Korean) iii
1 Introduction 1
2 Second-order Cone Optimization Problem 6
2.1 Introduction 6
2.2 Proximity Functions and Search Directions 9
2.3 Algorithm and Complexity Analysis 20
2.3.1 Bound of the proximity function after the $\mu$-update 22
2.3.2 Determining a default step size 24
2.3.3 Decrease of the proximity function during an inner iteration 36
2.3.4 Iteration bound 38
3 Semidefinite Optimization Problem 41
3.1 Introduction 41
3.2 Proximity Functions and Search Directions 43
3.3 Algorithm and Complexity Analysis 48
3.3.1 Bound of the proximity function after the $\mu$-update 49
3.3.2 Determining a default step size 51
3.3.3 Decrease of the proximity function during an inner iteration 60
3.3.4 Iteration bound 61
4 Self-scaled Optimization Problem 64
4.1 Introduction 64
4.2 Proximity Functions and Search Directions 73
4.3 Algorithm and Complexity Analysis 77
4.3.1 Bound of the proximity function after the $\mu$-update 79
4.3.2 Determining a default step size 81
4.3.3 Decrease of the proximity function during an inner iteration 93
4.3.4 Iteration bound 94
4.4 Concluding Remarks 96
Appendix 98
References 100
- Degree
- Doctor
- Files in This Item:
-
-
There are no files associated with this item.
-
Items in Repository are protected by copyright, with all rights reserved, unless otherwise indicated.