MINISTRY OF EDUCATION AND TRAINING MINISTRY OF NATIONAL DEFENCE
MILITARY TECHNICAL ACADEMY
TRAN HUNG CUONG
DC ALGORITHMS IN NONCONVEX
QUADRATIC PROGRAMMING AND
APPLICATIONS IN DATA CLUSTERING
DOCTORAL DISSERTATION MATHEMATICS
HANOI - 2021
MINISTRY OF EDUCATION AND TRAINING MINISTRY OF NATIONAL DEFENCE
MILITARY TECHNICAL ACADEMY
TRAN HUNG CUONG
DC ALGORITHMS IN NONCONVEX
QUADRATIC PROGRAMMING AND
APPLICATIONS IN DATA CLUSTERING
DOCTORAL DISSERTATION
Major: Mathematical Foundations for Informatics
Code: 9 46 01 10
RESEARCH SUPERVISIORS:
1. Prof. Dr.Sc. Nguyen Dong Yen
2. Prof. Dr.Sc. Pham The Long
HANOI - 2021
Confirmation
This dissertation was written on the basis of my research works carried out at
the Military Technical Academy, under the guidance of Prof. Nguyen Dong
Yen and Prof. Pham The Long. All the results presented in this dissertation
have got agreements of my coauthors to be used here.
February 25, 2021
The author
Tran Hung Cuong
i
Acknowledgments
I would like to express my deep gratitude to my advisor, Professor Nguyen
Dong Yen and Professor Pham The Long, for their careful and effective guid-
ance.
I would like to thank the board of directors of Military Technical Academy
for providing me with pleasant working conditions.
I am grateful to the leaders of Hanoi University of Industry, the Faculty of
Information Technology, and my colleagues, for granting me various financial
supports and/or constant help during the three years of my PhD study.
I am sincerely grateful to Prof. Jen-Chih Yao from Department of Applied
Mathematics, National Sun Yat-sen University, Taiwan, and Prof. Ching-
Feng Wen from Research Center for Nonlinear Analysis and Optimization,
Kaohsiung Medical University, Taiwan, for granting several short-termed
scholarships for my doctorate studies.
I would like to thank the following experts for their careful readings of this
dissertation and for many useful suggestions which have helped me to improve
the presentation: Prof. Dang Quang A, Prof. Pham Ky Anh, Prof. Le Dung
Muu, Assoc. Prof. Phan Thanh An, Assoc. Prof. Truong Xuan Duc Ha,
Assoc. Prof. Luong Chi Mai, Assoc. Prof. Tran Nguyen Ngoc, Assoc. Prof.
Nguyen Nang Tam, Assoc. Prof. Nguyen Quang Uy, Dr. Duong Thi Viet
An, Dr. Bui Van Dinh, Dr. Vu Van Dong, Dr. Tran Nam Dung, Dr. Phan
Thi Hai Hong, Dr. Nguyen Ngoc Luan, Dr. Ngo Huu Phuc, Dr. Le Xuan
Thanh, Dr. Le Quang Thuy, Dr. Nguyen Thi Toan, Dr. Ha Chi Trung, Dr.
Hoang Ngoc Tuan, Dr. Nguyen Van Tuyen.
I am so much indebted to my family for their love, support and encour-
agement, not only in the present time, but also in the whole my life. With
love and gratitude, I dedicate this dissertation to them.
ii
Contents
Acknowledgments ii
Table of Notations v
Introduction vii
Chapter 1. Background Materials 1
1.1 Basic Definitions and Some Properties ............. 1
1.2 DCA Schemes ........................... 4
1.3 General Convergence Theorem . . . . . . . . . . . . . . . . . . 8
1.4 Convergence Rates . . . . . . . . . . . . . . . . . . . . . . . . 11
1.5 Conclusions ............................ 13
Chapter 2. Analysis of an Algorithm in Indefinite Quadratic
Programming 14
2.1 Indefinite Quadratic Programs and DCAs ........... 15
2.2 Convergence and Convergence Rate of the Algorithm ..... 24
2.3 Asymptotical Stability of the Algorithm ............ 30
2.4 Further Analysis ......................... 36
2.5 Conclusions ............................ 40
Chapter 3. Qualitative Properties of the Minimum Sum-of-Squares
Clustering Problem 41
3.1 Clustering Problems ....................... 41
3.2 Basic Properties of the MSSC Problem ............. 44
3.3 The k-means Algorithm . . . . . . . . . . . . . . . . . . . . . 49
iii