On the extension of an arc-search interior-point algorithm for semidefinite optimization

Behrouz Kheirfam; Morteza Moslemi

doi:10.3934/naco.2018015

Article Contents

2018, Volume 8, Issue 2: 261-275. Doi: 10.3934/naco.2018015

This issue Previous Article Experiments with sparse Cholesky using a sequential task-flow implementation Next Article

On the extension of an arc-search interior-point algorithm for semidefinite optimization

Behrouz Kheirfam^1, , and
Morteza Moslemi^1,

1.
Department of Applied Mathematics, Azarbaijan Shahid Madani University, Tabriz, I. R. Iran

* Corresponding author: Behrouz Kheirfam
* Corresponding author: Behrouz Kheirfam

Received: May 31, 2017

Revised: February 28, 2018

Published: May 2018

Abstract Full Text(HTML) Figure(0) / Table(2) Related Papers Cited by

Abstract

This paper concerns an extension of the arc-search strategy that was proposed by Yang [26] for linear optimization to semidefinite optimization case. Based on the Nesterov-Todd direction as Newton search direction it is shown that the complexity bound of the proposed algorithm is of the same order as that of the corresponding algorithm for linear optimization. Some preliminary numerical results indicate that our primal-dual arc-search path-following method is promising for solving the semidefinite optimization problems.

Keywords:

Mathematics Subject Classification: 90C51.

Citation:

Full Text(HTML)

Table 1. Numerical results for Example 1

$\varepsilon$	MTYAlgor		NewAlgor
$\varepsilon$	Iter.	CPU	DGAP	Iter.	CPU	DGAP
$10^{-6}$	55	0.1882	$4.4981e^{-6}$	11	0.0729	$2.1703e^{-6}$
$10^{-8}$	73	0.2476	$4.7261e^{-8}$	13	0.0679	$9.6585e^{-9}$

| Show Table

DownLoad: CSV

Table 2. Numerical results for Example 2

$n\times m$	MTYAlgor			NewAlgor
$n\times m$	Iter.	CPU	Iter.	CPU
$10\times20$	97.2	3.4915	28.8	1.1028
$30\times30$	117.3	18.7385	32.3	5.9383
$25\times40$	116.2	67.5448	33.7	23.2533
$40\times20$	115.9	70.7626	33.1	24.0481
$50\times50$	136.7	179.9818	35.4	87.9356

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

	F. Alizadeh, Combinatorial Optimization with Interior-Point Methods and Semi-definite Matrices, Ph. D. thesis, Computer Science Department, University of Minnesota, Minneapolis, MN, 1991.
	F. Alizadeh , Interior-point methods in semidefinite programming with applications to combinatorial optimization, SIAM J. Optim., 5 (1995) , 13-51. doi: 10.1137/0805002.
	F. Alizadeh , J.A. Haeberly and M. L. Overton , Primal-dual interior-point methods for semidefinite programming: Convergence rates, stability and numerical results, SIAM J. Optim., 8 (1998) , 746-768. doi: 10.1137/S1052623496304700.
	S. Boyd, L. Ghoui, E. Feron and V. Balakrishnan, Linear Matrix Inequalities in System and Control Theory, SIAM, Philadelphia, PA, 1994. doi: 10.1137/1.9781611970777.
	E. De Klerk, Aspects of Semidefinite Programming: Interior Point Algorithms and Selected Applications, Kluwer Academic Publishers, Dordrecht, Netherlands, 2002. doi: 10.1007/b105286.
	D. Herbison-Evans, Solving quartics and cubics for graphics Technical Report, R94-487, Basser Department of Computer Science, University of Sydney, Sydney, Australia, 1994. doi: 10.1016/B978-0-12-543457-7.50009-7.
	B. Kheirfam , An arc-search interior point method in the $\mathcal{N}_{∞}^-$ neighborhood for symmetric optimization, Fundam. Inform., 146 (2016) , 255-269. doi: 10.3233/FI-2016-1385.
	M. Kojima , S. Shindoh and S. Hara , Interior-point methods for the monotone semidefinite linear complementarity problem in symmetric matrices, SIAM J. Optim., 7 (1997) , 86-125. doi: 10.1137/S1052623494269035.
	M. Kojima , M. Shida and S. Shindoh , Local convergence of predictor-corrector infeasible interior-point algorithm for SDPs and SDLCPs, Math. Program., 80 (1998) , 129-160. doi: 10.1007/BF01581723.
	Y. Li and T. Terlaky , A new class of large neighborhood path-following interior point algorithms for semidefinite optimization with $O(\sqrt{n}\log(\frac{{\rm tr}(X^0S^0)}{ε}))$ iteration complexity, SIAM J. Optim., 8 (2010) , 2853-2875. doi: 10.1137/080729311.
	H. W. Liu , C. H. Liu and X. M. Yang , New complexity analysis of a Mehrotra-type predictor-corrector algorithm for semidefinite programming, Optim. Methods Softw., 28 (2013) , 1179-1194. doi: 10.1080/10556788.2012.679270.
	S. Mizuno , M. J. Todd and Y. Ye , On adaptive-step primal-dual interior-point algorithms for linear programming, Math. Oper. Res., 18 (1993) , 964-981. doi: 10.1287/moor.18.4.964.
	R. D. C. Monteiro and I. Adler , Interior path following primal-dual algorithm. Part Ⅰ: linear programming, Math. Program., 44 (1989) , 27-41. doi: 10.1007/BF01587075.
	R. D. C. Monteiro , Polynomial convergence of primal-dual algorithms for semidefinite programming based on the Monteiro and Zhang family of directions, SIAM J. Optim., 8 (1998) , 797-812. doi: 10.1137/S1052623496308618.
	R. D. C. Monteiro and Y. Zhang , A unified analysis for a class of long-step primal-dual path-following interior-point algorithms for semidefinite programming, Math. Program., 81 (1998) , 281-299. doi: 10.1007/BF01580085.
	Y. E. Nesterov and A. S. Nemirovskii, Interior Point Polynomial Algorithms in Convex Programming. SIAM Studies in Applied Mathematics, Vol. 13 SIAM, Philadelphia, USA, 1994. doi: 10.1137/1.9781611970791.
	Y. E. Nesterov and M. J. Todd , Self-scaled barriers and interior-point methods for convex programming, Math. Oper. Res., 22 (1997) , 1-42. doi: 10.1287/moor.22.1.1.
	Y. E. Nesterov and M. J. Todd , Primal-dual interior point methods for self-scaled cones, SIAM J. Optim., 8 (1998) , 324-364. doi: 10.1137/S1052623495290209.
	F. A. Potra and R. Sheng , A superlinearly convergent primal-dual infeasible -interior-point algorithm for semidefinite programming, SIAM J. Optim., 8 (1998) , 1007-1028. doi: 10.1137/S1052623495294955.
	M. J. Todd , K. C. Toh and R. H. $T\ddot u\ddot unc\ddot u$ , On the Nesterov-Todd direction in semidefinite programming, SIAM J. Optim., 8 (1998) , 769-796. doi: 10.1137/S105262349630060X.
	S. Veeraraghavan and D. A. Mazziotti , Semidefinite programming formulation of linear-scaling electronic structure theories Artic, Phys. Rev. A, 92 (2015) , 215-220.
	H. Wolkowicz, R. Saigal and L. Vandenberghe, Handbook of Semidefinite Programming, International Series in Operations Research and Management Science (27) Kluwer Academic Publishers, Boston, MA, 2000. doi: 10.1007/978-1-4615-4381-7.
	S. Wright, Primal-Dual Interior-point Methods, SIAM, Philadelphia, 1997. doi: 10.1137/1.9781611971453.
	Y. Yang, Arc-search path-following interior-point algorithm for linear programming, Optimization online, 2009.
	Y. Yang , A polynomial arc-search interior-point algorithm for convex quadratic programming, Eur. J. Oper. Res., 215 (2011) , 25-38. doi: 10.1016/j.ejor.2011.06.020.
	Y. Yang , A polynomial arc-search interior-point algorithm for linear programming, J. Optim. Theory Appl., 158 (2013) , 859-873. doi: 10.1007/s10957-013-0281-0.
	X. Yang , Y. Zhang and H. Liu , A wide neighborhood infeasible-interior-point method with arc-search for linear programming, J. Appl. Math. Comput., 51 (2016) , 209-225. doi: 10.1007/s12190-015-0900-z.
	X. Yang , H. Liu and Y. Zhang , An arc-search infeasible-interior-point method for symmetric optimization in a wide neighborhood of the central path, Optim. Lett., 11 (2017) , 135-152. doi: 10.1007/s11590-016-0997-5.
	Y. Zhang , On extending primal-dual interior-point algorithms from linear programming to semidefinite programming, SIAM J. Optim., 8 (1998) , 365-386. doi: 10.1137/S1052623495296115.