A full-Newton step interior-point algorithm for symmetric cone convex quadratic optimization

Previous Article
An integrated approach for selection of service vendors in service supply chain
JIMO Home
This Issue
Next Article
Optimal fleet composition via dynamic programming and golden section search

October 2011, 7(4): 891-906. doi: 10.3934/jimo.2011.7.891

A full-Newton step interior-point algorithm for symmetric cone convex quadratic optimization

Yanqin Bai ^1, and Lipu Zhang ^2,

1.	Department of Mathematics, Shanghai University, 99, Shangda Road, 200444, Shanghai
2.	Department of Mathematics, Shanghai University, Shanghai 200444, China

Received November 2009 Revised May 2011 Published August 2011

Abstract
Related Papers

In this paper, we present a full-Newton step primal-dual interior-point algorithm for solving symmetric cone convex quadratic optimization problem, where the objective function is a convex quadratic function and the feasible set is the intersection of an affine subspace and a symmetric cone lies in Euclidean Jordan algebra. The search directions of the algorithm are obtained from the modification of NT-search direction in terms of the quadratic representation in Euclidean Jordan algebra. We prove that the algorithm has a quadratical convergence result. Furthermore, we present the complexity analysis for the algorithm and obtain the complexity bound as $\left\lceil 2\sqrt{r}\log\frac{\mu^0 r}{\epsilon}\right\rceil$, where $r$ is the rank of Euclidean Jordan algebras where the symmetric cone lies in.

Keywords: complexity analysis., Euclidean Jordan algebras, full-Newton step, NT-search direction, symmetric cone.

Mathematics Subject Classification: 17C99, 90C25, 90C5.

Citation: Yanqin Bai, Lipu Zhang. A full-Newton step interior-point algorithm for symmetric cone convex quadratic optimization. Journal of Industrial and Management Optimization, 2011, 7 (4) : 891-906. doi: 10.3934/jimo.2011.7.891

References:

[1]	K. M. Anstreicher, D. den Hertog, C. Roos and T. Terlaky, A long-step barrier method for convex quadratic programming, Algorithmica, 10 (1993), 365-382. doi: 10.1007/BF01769704.
[2]	Y. Q. Bai, M. El Ghami and C. Roos, A comparative study of kernel function for primal-dual interior-point algorithms in linear optimization, SIAM J. Optim., 15 (2004), 101-128. doi: 10.1137/S1052623403423114.
[3]	S. Boyd and L. Vandenberghe, "Convex Optimization," Cambridge University Press, 2004.
[4]	J. Faraut and A. Korányi, "Analysis on Symmetric Cones," Oxford Mathematical Monographs, Oxford Science Publications, The Clarendon Press, Oxford University Press, New York, 1994.
[5]	L. Faybusovich, Linear systems in Jordan algebras and primal-dual interior-point algorithms, Special issue dedicated to William B. Gragg (Monterey, CA, 1996), J. Comput. Appl. Math., 86 (1997), 149-175. doi: 10.1016/S0377-0427(97)00153-2.
[6]	L. Faybusovich, A Jordan-algebraic approach to potential-reduction algorithms, Math. Z., 239 (2002), 117-129. doi: 10.1007/s002090100286.
[7]	R. D. C. Monteiro and I. Adler, Interior path following primal-dual algorithms, II: Convex quadratic programming, Math. Program., Ser. A, 44 (1989), 43-66.
[8]	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.
[9]	J. Peng, C. Roos and T. Terlaky, "Self-regularity: A New Paradigm for Primal-Dual Interior-Point Algorithms," Princeton Series in Applied Mathematics, Princeton University Press, Princeton, NJ, 2002.
[10]	C. Roos, T. Terlaky and J.-Ph. Vial, "Theory and Algorithms for Linear Optimization. An Interior Point Approach," Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons, Ltd., Chichester, 1997.
[11]	S. H. Schmieta and F. Alizadeh, Extension of primal-dual interior point algorithms to symmetric cones, Math. Program, Ser. A, 96 (2003), 409-438.
[12]	Changjun Yu, Kok Lay Teo, Liangsheng Zhang and Yanqin Bai, A new exact penalty function method for continuous inequality constrained optimization problems, Journal of Industrial and Management Optimization, 4 (2010), 895-910.
[13]	M. V. C. Vieira, "Jordan Algebraic Approach to Symmetric Optimization," Ph.D thesis, Delft University of Technology, 2007.

show all references

References:

[1]	K. M. Anstreicher, D. den Hertog, C. Roos and T. Terlaky, A long-step barrier method for convex quadratic programming, Algorithmica, 10 (1993), 365-382. doi: 10.1007/BF01769704.
[2]	Y. Q. Bai, M. El Ghami and C. Roos, A comparative study of kernel function for primal-dual interior-point algorithms in linear optimization, SIAM J. Optim., 15 (2004), 101-128. doi: 10.1137/S1052623403423114.
[3]	S. Boyd and L. Vandenberghe, "Convex Optimization," Cambridge University Press, 2004.
[4]	J. Faraut and A. Korányi, "Analysis on Symmetric Cones," Oxford Mathematical Monographs, Oxford Science Publications, The Clarendon Press, Oxford University Press, New York, 1994.
[5]	L. Faybusovich, Linear systems in Jordan algebras and primal-dual interior-point algorithms, Special issue dedicated to William B. Gragg (Monterey, CA, 1996), J. Comput. Appl. Math., 86 (1997), 149-175. doi: 10.1016/S0377-0427(97)00153-2.
[6]	L. Faybusovich, A Jordan-algebraic approach to potential-reduction algorithms, Math. Z., 239 (2002), 117-129. doi: 10.1007/s002090100286.
[7]	R. D. C. Monteiro and I. Adler, Interior path following primal-dual algorithms, II: Convex quadratic programming, Math. Program., Ser. A, 44 (1989), 43-66.
[8]	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.
[9]	J. Peng, C. Roos and T. Terlaky, "Self-regularity: A New Paradigm for Primal-Dual Interior-Point Algorithms," Princeton Series in Applied Mathematics, Princeton University Press, Princeton, NJ, 2002.
[10]	C. Roos, T. Terlaky and J.-Ph. Vial, "Theory and Algorithms for Linear Optimization. An Interior Point Approach," Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons, Ltd., Chichester, 1997.
[11]	S. H. Schmieta and F. Alizadeh, Extension of primal-dual interior point algorithms to symmetric cones, Math. Program, Ser. A, 96 (2003), 409-438.
[12]	Changjun Yu, Kok Lay Teo, Liangsheng Zhang and Yanqin Bai, A new exact penalty function method for continuous inequality constrained optimization problems, Journal of Industrial and Management Optimization, 4 (2010), 895-910.
[13]	M. V. C. Vieira, "Jordan Algebraic Approach to Symmetric Optimization," Ph.D thesis, Delft University of Technology, 2007.

[1]	Behrouz Kheirfam, Guoqiang Wang. An infeasible full NT-step interior point method for circular optimization. Numerical Algebra, Control and Optimization, 2017, 7 (2) : 171-184. doi: 10.3934/naco.2017011
[2]	Yu-Lin Chang, Chin-Yu Yang. Some useful inequalities via trace function method in Euclidean Jordan algebras. Numerical Algebra, Control and Optimization, 2014, 4 (1) : 39-48. doi: 10.3934/naco.2014.4.39
[3]	Shuang Chen, Li-Ping Pang, Dan Li. An inexact semismooth Newton method for variational inequality with symmetric cone constraints. Journal of Industrial and Management Optimization, 2015, 11 (3) : 733-746. doi: 10.3934/jimo.2015.11.733
[4]	Yinghong Xu, Lipu Zhang, Jing Zhang. A full-modified-Newton step infeasible interior-point algorithm for linear optimization. Journal of Industrial and Management Optimization, 2016, 12 (1) : 103-116. doi: 10.3934/jimo.2016.12.103
[5]	Li-Xia Liu, Sanyang Liu, Chun-Feng Wang. Smoothing Newton methods for symmetric cone linear complementarity problem with the Cartesian $P$/$P_0$-property. Journal of Industrial and Management Optimization, 2011, 7 (1) : 53-66. doi: 10.3934/jimo.2011.7.53
[6]	Behrouz Kheirfam. A full Nesterov-Todd step infeasible interior-point algorithm for symmetric optimization based on a specific kernel function. Numerical Algebra, Control and Optimization, 2013, 3 (4) : 601-614. doi: 10.3934/naco.2013.3.601
[7]	Xiaoni Chi, Zhongping Wan, Zijun Hao. A full-modified-Newton step $ O(n) $ infeasible interior-point method for the special weighted linear complementarity problem. Journal of Industrial and Management Optimization, 2021 doi: 10.3934/jimo.2021082
[8]	Golamreza Zamani Eskandani, Hamid Vaezi. Hyers--Ulam--Rassias stability of derivations in proper Jordan $CQ^{}$-algebras. Discrete and Continuous Dynamical Systems*, 2011, 31 (4) : 1469-1477. doi: 10.3934/dcds.2011.31.1469
[9]	M. P. de Oliveira. On 3-graded Lie algebras, Jordan pairs and the canonical kernel function. Electronic Research Announcements, 2003, 9: 142-151.
[10]	Xin-He Miao, Jein-Shan Chen. Error bounds for symmetric cone complementarity problems. Numerical Algebra, Control and Optimization, 2013, 3 (4) : 627-641. doi: 10.3934/naco.2013.3.627
[11]	Yuan Shen, Lei Ji. Partial convolution for total variation deblurring and denoising by new linearized alternating direction method of multipliers with extension step. Journal of Industrial and Management Optimization, 2019, 15 (1) : 159-175. doi: 10.3934/jimo.2018037
[12]	Feng Ma, Jiansheng Shu, Yaxiong Li, Jian Wu. The dual step size of the alternating direction method can be larger than 1.618 when one function is strongly convex. Journal of Industrial and Management Optimization, 2021, 17 (3) : 1173-1185. doi: 10.3934/jimo.2020016
[13]	Liping Tang, Xinmin Yang, Ying Gao. Higher-order symmetric duality for multiobjective programming with cone constraints. Journal of Industrial and Management Optimization, 2020, 16 (4) : 1873-1884. doi: 10.3934/jimo.2019033
[14]	Behrouz Kheirfam. A weighted-path-following method for symmetric cone linear complementarity problems. Numerical Algebra, Control and Optimization, 2014, 4 (2) : 141-150. doi: 10.3934/naco.2014.4.141
[15]	Yi Zhang, Liwei Zhang, Jia Wu. On the convergence properties of a smoothing approach for mathematical programs with symmetric cone complementarity constraints. Journal of Industrial and Management Optimization, 2018, 14 (3) : 981-1005. doi: 10.3934/jimo.2017086
[16]	Erik Carlsson, John Gunnar Carlsson, Shannon Sweitzer. Applying topological data analysis to local search problems. Foundations of Data Science, 2022 doi: 10.3934/fods.2022006
[17]	Peng Guo, Wenming Cheng, Yi Wang. A general variable neighborhood search for single-machine total tardiness scheduling problem with step-deteriorating jobs. Journal of Industrial and Management Optimization, 2014, 10 (4) : 1071-1090. doi: 10.3934/jimo.2014.10.1071
[18]	Charles Curry, Stephen Marsland, Robert I McLachlan. Principal symmetric space analysis. Journal of Computational Dynamics, 2019, 6 (2) : 251-276. doi: 10.3934/jcd.2019013
[19]	Yanhong Yuan, Hongwei Zhang, Liwei Zhang. A smoothing Newton method for generalized Nash equilibrium problems with second-order cone constraints. Numerical Algebra, Control and Optimization, 2012, 2 (1) : 1-18. doi: 10.3934/naco.2012.2.1
[20]	Matthias Gerdts, Stefan Horn, Sven-Joachim Kimmerle. Line search globalization of a semismooth Newton method for operator equations in Hilbert spaces with applications in optimal control. Journal of Industrial and Management Optimization, 2017, 13 (1) : 47-62. doi: 10.3934/jimo.2016003

2020 Impact Factor: 1.801

Tools

Metrics

Other articles
by authors

on AIMS
Yanqin Bai Lipu Zhang
on Google Scholar
Yanqin Bai Lipu Zhang

[Back to Top]