# American Institute of Mathematical Sciences

2015, 5(2): 211-231. doi: 10.3934/naco.2015.5.211

## Primal-dual interior-point algorithms for convex quadratic circular cone optimization

 1 Department of Mathematics, Shanghai University, Shanghai 200444, China, China 2 College of Fundamental Studies, Shanghai University of Engineering Science, Shanghai 201620

Received  December 2014 Revised  May 2015 Published  June 2015

In this paper we focus on a class of special nonsymmetric cone optimization problem called circular cone optimization problem, which has a convex quadratic function as the objective function and an intersection of a non-self-dual circular cone and linear equations as the constraint condition. Firstly we establish the algebraic relationships between the circular cone and the second-order cone and translate the original problem from the circular cone optimization problem to the second-order cone optimization problem. Then we present kernel-function based primal-dual interior-point algorithms for solving this special circular cone optimization and derive the iteration bounds for large- and small-update methods. Finally, some preliminary numerical results are provided to demonstrate the computational performance of the proposed algorithms.
Citation: Yanqin Bai, Xuerui Gao, Guoqiang Wang. Primal-dual interior-point algorithms for convex quadratic circular cone optimization. Numerical Algebra, Control & Optimization, 2015, 5 (2) : 211-231. doi: 10.3934/naco.2015.5.211
##### References:
 [1] F. Alizadeh and D. Goldfard, Second-order cone programming,, Math. Program., 95 (2003), 3. doi: 10.1007/s10107-002-0339-5. Google Scholar [2] M. F. Anjos and J. B. Lasserre, Handbook on Semidefinite, Conic and Polynomial Optimization: Theory, Algorithms, Software and Applications,, Internat. Ser. Oper. Res. Management Sci., 166 (2012). doi: 10.1007/978-1-4614-0769-0. Google Scholar [3] Y. Q. Bai, Kernel Function-Based Interior-Point Algorithms for Conic Optimization,, Science Press, (2010). Google Scholar [4] Y. Q. Bai, M. El Ghami and C. Roos, A comparative study of kernel functions for primal-dual interior-point algorithms in linear optimization,, SIAM J. Optim., 15 (2004), 101. doi: 10.1137/S1052623403423114. Google Scholar [5] Y. Q. Bai, G. Q. Wang and C. Roos, Primal-dual interior-point algorithms for second-order cone optimization based on kernel functions,, Nonlinear Anal., 70 (2009), 3584. doi: 10.1016/j.na.2008.07.016. Google Scholar [6] S. P. Boyd and B. Wegbreit, Fast computation of optimal contact forces,, IEEE Trans. Robot., 23 (2007), 1117. Google Scholar [7] Y. L. Chang, C. Y. Yang and J. S. Chen, Smooth and nonsmooth analysis of vector-valued functions associated with circular cones,, Nonlinear Anal., 85 (2013), 160. doi: 10.1016/j.na.2013.01.017. Google Scholar [8] L. Faybusovich, Euclidean Jordan algebras and interior-point algorithms,, Positivity, 1 (1997), 331. doi: 10.1023/A:1009701824047. Google Scholar [9] G. Gu, M. Zangiabadi and C. Roos, Full Nesterov-Todd step interior-point method for symmetric optimization,, European J. Oper. Res., 214 (2011), 473. doi: 10.1016/j.ejor.2011.02.022. Google Scholar [10] Y. Matsukawa and A. Yoshise, A primal barrier function Phase I algorithm for nonsymmetric conic optimization problems,, Jpn. J. Ind. Appl. Math., 29 (2012), 499. doi: 10.1007/s13160-012-0081-1. Google Scholar [11] Y. Nesterov, Towards non-symmetric conic optimization,, Optim. Method Softw., 27 (2012), 893. doi: 10.1080/10556788.2011.567270. Google Scholar [12] J. Peng, C. Roos and T. Terlaky., A new class of polynomial primal-dual interior-point methods for second-order cone optimization based on self-regular proximities,, SIAM J. Optim., 13 (2002), 179. doi: 10.1137/S1052623401383236. Google Scholar [13] C. Roos, T. Terlaky and J.-Ph. Vial, Theory and Algorithms for Linear Optimization: An Interior-Point Approach,, John Wiley & Sons, (1997). Google Scholar [14] S. H. Schmieta and F. Alizadeh, Extension of primal-dual interior-point algorithms to symmetric cones,, Math. Program., 96 (2003), 409. doi: 10.1007/s10107-003-0380-z. Google Scholar [15] A. Skajaa and Y. Y. Ye, A homogeneous interior-point algorithm for nonsymmetric convex conic optimization,, Math. Program., 150 (2015), 391. doi: 10.1007/s10107-014-0773-1. Google Scholar [16] G. Q. Wang and Y. Q. Bai, A primal-dual path-following interior-point algorithm for second-order cone optimization with full Nesterov-Todd step,, Appl. Math. Comput., 215 (2009), 1047. doi: 10.1016/j.amc.2009.06.034. Google Scholar [17] G. Q. Wang and Y. Q. Bai, Primal-dual interior-point algorithm for convex quadratic semidefinite optimization,, Nonlinear Anal., 71 (2009), 3389. doi: 10.1016/j.na.2009.01.241. Google Scholar [18] G. Q. Wang and D. T. Zhu, A unified kernel function approach to primal-dual interior-point algorithms for convex quadratic SDO,, Numer. Algorithms, 57 (2011), 537. doi: 10.1007/s11075-010-9444-3. Google Scholar [19] Y. N. Wang, N. H. Xiu and J. Y. Han, On cone of nonsymmetric positive semidefinite matrices,, Linear Algebra Appl., 433 (2010), 718. doi: 10.1016/j.laa.2010.03.042. Google Scholar [20] A. Yoshise and Y. Matsukawa, On optimization over the doubly nonnegative cone,, Proceedings of 2010 IEEE Multi-Conference on Systems and Control, (2010), 13. Google Scholar [21] M. Zangiabadi, G. Gu and C. Roos, A full Nesterov-Todd step infeasible interior-point method for second-order cone optimization,, J. Optim. Theory Appl., 158 (2013), 816. doi: 10.1007/s10957-013-0278-8. Google Scholar [22] J. C. Zhou and J. S. Chen, The vector-valued functions associated with circular cones,, Abstr. Appl. Anal., 2014 (2014). doi: 10.1155/2014/603542. Google Scholar [23] J. C. Zhou and J. S. Chen, Properties of circular cone and spectral factorization associated with circular cone,, J. Nonlinear Convex Anal., 14 (2013), 807. Google Scholar [24] J. C. Zhou, J. S. Chen and H. F. Hung, Circular cone convexity and some inequalities associated with circular cones,, J. Inequal. Appl., 2013 (2013). doi: 10.1186/1029-242X-2013-571. Google Scholar [25] J. C. Zhou, J. S. Chen and B. S. Mordukhovich, Variational analysis of circular cone programs,, Optim., 64 (2014), 113. doi: 10.1080/02331934.2014.951043. Google Scholar

show all references

##### References:
 [1] F. Alizadeh and D. Goldfard, Second-order cone programming,, Math. Program., 95 (2003), 3. doi: 10.1007/s10107-002-0339-5. Google Scholar [2] M. F. Anjos and J. B. Lasserre, Handbook on Semidefinite, Conic and Polynomial Optimization: Theory, Algorithms, Software and Applications,, Internat. Ser. Oper. Res. Management Sci., 166 (2012). doi: 10.1007/978-1-4614-0769-0. Google Scholar [3] Y. Q. Bai, Kernel Function-Based Interior-Point Algorithms for Conic Optimization,, Science Press, (2010). Google Scholar [4] Y. Q. Bai, M. El Ghami and C. Roos, A comparative study of kernel functions for primal-dual interior-point algorithms in linear optimization,, SIAM J. Optim., 15 (2004), 101. doi: 10.1137/S1052623403423114. Google Scholar [5] Y. Q. Bai, G. Q. Wang and C. Roos, Primal-dual interior-point algorithms for second-order cone optimization based on kernel functions,, Nonlinear Anal., 70 (2009), 3584. doi: 10.1016/j.na.2008.07.016. Google Scholar [6] S. P. Boyd and B. Wegbreit, Fast computation of optimal contact forces,, IEEE Trans. Robot., 23 (2007), 1117. Google Scholar [7] Y. L. Chang, C. Y. Yang and J. S. Chen, Smooth and nonsmooth analysis of vector-valued functions associated with circular cones,, Nonlinear Anal., 85 (2013), 160. doi: 10.1016/j.na.2013.01.017. Google Scholar [8] L. Faybusovich, Euclidean Jordan algebras and interior-point algorithms,, Positivity, 1 (1997), 331. doi: 10.1023/A:1009701824047. Google Scholar [9] G. Gu, M. Zangiabadi and C. Roos, Full Nesterov-Todd step interior-point method for symmetric optimization,, European J. Oper. Res., 214 (2011), 473. doi: 10.1016/j.ejor.2011.02.022. Google Scholar [10] Y. Matsukawa and A. Yoshise, A primal barrier function Phase I algorithm for nonsymmetric conic optimization problems,, Jpn. J. Ind. Appl. Math., 29 (2012), 499. doi: 10.1007/s13160-012-0081-1. Google Scholar [11] Y. Nesterov, Towards non-symmetric conic optimization,, Optim. Method Softw., 27 (2012), 893. doi: 10.1080/10556788.2011.567270. Google Scholar [12] J. Peng, C. Roos and T. Terlaky., A new class of polynomial primal-dual interior-point methods for second-order cone optimization based on self-regular proximities,, SIAM J. Optim., 13 (2002), 179. doi: 10.1137/S1052623401383236. Google Scholar [13] C. Roos, T. Terlaky and J.-Ph. Vial, Theory and Algorithms for Linear Optimization: An Interior-Point Approach,, John Wiley & Sons, (1997). Google Scholar [14] S. H. Schmieta and F. Alizadeh, Extension of primal-dual interior-point algorithms to symmetric cones,, Math. Program., 96 (2003), 409. doi: 10.1007/s10107-003-0380-z. Google Scholar [15] A. Skajaa and Y. Y. Ye, A homogeneous interior-point algorithm for nonsymmetric convex conic optimization,, Math. Program., 150 (2015), 391. doi: 10.1007/s10107-014-0773-1. Google Scholar [16] G. Q. Wang and Y. Q. Bai, A primal-dual path-following interior-point algorithm for second-order cone optimization with full Nesterov-Todd step,, Appl. Math. Comput., 215 (2009), 1047. doi: 10.1016/j.amc.2009.06.034. Google Scholar [17] G. Q. Wang and Y. Q. Bai, Primal-dual interior-point algorithm for convex quadratic semidefinite optimization,, Nonlinear Anal., 71 (2009), 3389. doi: 10.1016/j.na.2009.01.241. Google Scholar [18] G. Q. Wang and D. T. Zhu, A unified kernel function approach to primal-dual interior-point algorithms for convex quadratic SDO,, Numer. Algorithms, 57 (2011), 537. doi: 10.1007/s11075-010-9444-3. Google Scholar [19] Y. N. Wang, N. H. Xiu and J. Y. Han, On cone of nonsymmetric positive semidefinite matrices,, Linear Algebra Appl., 433 (2010), 718. doi: 10.1016/j.laa.2010.03.042. Google Scholar [20] A. Yoshise and Y. Matsukawa, On optimization over the doubly nonnegative cone,, Proceedings of 2010 IEEE Multi-Conference on Systems and Control, (2010), 13. Google Scholar [21] M. Zangiabadi, G. Gu and C. Roos, A full Nesterov-Todd step infeasible interior-point method for second-order cone optimization,, J. Optim. Theory Appl., 158 (2013), 816. doi: 10.1007/s10957-013-0278-8. Google Scholar [22] J. C. Zhou and J. S. Chen, The vector-valued functions associated with circular cones,, Abstr. Appl. Anal., 2014 (2014). doi: 10.1155/2014/603542. Google Scholar [23] J. C. Zhou and J. S. Chen, Properties of circular cone and spectral factorization associated with circular cone,, J. Nonlinear Convex Anal., 14 (2013), 807. Google Scholar [24] J. C. Zhou, J. S. Chen and H. F. Hung, Circular cone convexity and some inequalities associated with circular cones,, J. Inequal. Appl., 2013 (2013). doi: 10.1186/1029-242X-2013-571. Google Scholar [25] J. C. Zhou, J. S. Chen and B. S. Mordukhovich, Variational analysis of circular cone programs,, Optim., 64 (2014), 113. doi: 10.1080/02331934.2014.951043. Google Scholar
 [1] Guoqiang Wang, Zhongchen Wu, Zhongtuan Zheng, Xinzhong Cai. Complexity analysis of primal-dual interior-point methods for semidefinite optimization based on a parametric kernel function with a trigonometric barrier term. Numerical Algebra, Control & Optimization, 2015, 5 (2) : 101-113. doi: 10.3934/naco.2015.5.101 [2] Yanqin Bai, Pengfei Ma, Jing Zhang. A polynomial-time interior-point method for circular cone programming based on kernel functions. Journal of Industrial & Management Optimization, 2016, 12 (2) : 739-756. doi: 10.3934/jimo.2016.12.739 [3] Siqi Li, Weiyi Qian. Analysis of complexity of primal-dual interior-point algorithms based on a new kernel function for linear optimization. Numerical Algebra, Control & Optimization, 2015, 5 (1) : 37-46. doi: 10.3934/naco.2015.5.37 [4] Yanqin Bai, Lipu Zhang. A full-Newton step interior-point algorithm for symmetric cone convex quadratic optimization. Journal of Industrial & Management Optimization, 2011, 7 (4) : 891-906. doi: 10.3934/jimo.2011.7.891 [5] Behrouz Kheirfam. A full Nesterov-Todd step infeasible interior-point algorithm for symmetric optimization based on a specific kernel function. Numerical Algebra, Control & Optimization, 2013, 3 (4) : 601-614. doi: 10.3934/naco.2013.3.601 [6] Liwei Zhang, Jihong Zhang, Yule Zhang. Second-order optimality conditions for cone constrained multi-objective optimization. Journal of Industrial & Management Optimization, 2018, 14 (3) : 1041-1054. doi: 10.3934/jimo.2017089 [7] Anurag Jayswala, Tadeusz Antczakb, Shalini Jha. Second order modified objective function method for twice differentiable vector optimization problems over cone constraints. Numerical Algebra, Control & Optimization, 2019, 9 (2) : 133-145. doi: 10.3934/naco.2019010 [8] Yi Zhang, Yong Jiang, Liwei Zhang, Jiangzhong Zhang. A perturbation approach for an inverse linear second-order cone programming. Journal of Industrial & Management Optimization, 2013, 9 (1) : 171-189. doi: 10.3934/jimo.2013.9.171 [9] Behrouz Kheirfam, Morteza Moslemi. On the extension of an arc-search interior-point algorithm for semidefinite optimization. Numerical Algebra, Control & Optimization, 2018, 8 (2) : 261-275. doi: 10.3934/naco.2018015 [10] Behrouz Kheirfam, Guoqiang Wang. An infeasible full NT-step interior point method for circular optimization. Numerical Algebra, Control & Optimization, 2017, 7 (2) : 171-184. doi: 10.3934/naco.2017011 [11] Xiaoni Chi, Zhongping Wan, Zijun Hao. Second order sufficient conditions for a class of bilevel programs with lower level second-order cone programming problem. Journal of Industrial & Management Optimization, 2015, 11 (4) : 1111-1125. doi: 10.3934/jimo.2015.11.1111 [12] Xiaoling Guo, Zhibin Deng, Shu-Cherng Fang, Wenxun Xing. Quadratic optimization over one first-order cone. Journal of Industrial & Management Optimization, 2014, 10 (3) : 945-963. doi: 10.3934/jimo.2014.10.945 [13] Ye Tian, Qingwei Jin, Zhibin Deng. Quadratic optimization over a polyhedral cone. Journal of Industrial & Management Optimization, 2016, 12 (1) : 269-283. doi: 10.3934/jimo.2016.12.269 [14] Ye Tian, Shu-Cherng Fang, Zhibin Deng, Wenxun Xing. Computable representation of the cone of nonnegative quadratic forms over a general second-order cone and its application to completely positive programming. Journal of Industrial & Management Optimization, 2013, 9 (3) : 703-721. doi: 10.3934/jimo.2013.9.703 [15] Xi-De Zhu, Li-Ping Pang, Gui-Hua Lin. Two approaches for solving mathematical programs with second-order cone complementarity constraints. Journal of Industrial & Management Optimization, 2015, 11 (3) : 951-968. doi: 10.3934/jimo.2015.11.951 [16] Yanhong Yuan, Hongwei Zhang, Liwei Zhang. A smoothing Newton method for generalized Nash equilibrium problems with second-order cone constraints. Numerical Algebra, Control & Optimization, 2012, 2 (1) : 1-18. doi: 10.3934/naco.2012.2.1 [17] Jae-Hong Pyo, Jie Shen. Normal mode analysis of second-order projection methods for incompressible flows. Discrete & Continuous Dynamical Systems - B, 2005, 5 (3) : 817-840. doi: 10.3934/dcdsb.2005.5.817 [18] Boshi Tian, Xiaoqi Yang, Kaiwen Meng. An interior-point $l_{\frac{1}{2}}$-penalty method for inequality constrained nonlinear optimization. Journal of Industrial & Management Optimization, 2016, 12 (3) : 949-973. doi: 10.3934/jimo.2016.12.949 [19] Yinghong Xu, Lipu Zhang, Jing Zhang. A full-modified-Newton step infeasible interior-point algorithm for linear optimization. Journal of Industrial & Management Optimization, 2016, 12 (1) : 103-116. doi: 10.3934/jimo.2016.12.103 [20] Shiyun Wang, Yong-Jin Liu, Yong Jiang. A majorized penalty approach to inverse linear second order cone programming problems. Journal of Industrial & Management Optimization, 2014, 10 (3) : 965-976. doi: 10.3934/jimo.2014.10.965

Impact Factor:

## Metrics

• PDF downloads (7)
• HTML views (0)
• Cited by (4)

## Other articlesby authors

• on AIMS
• on Google Scholar

[Back to Top]