American Institute of Mathematical Sciences

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

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

Yanqin Bai 1, , Xuerui Gao 1, and  Guoqiang Wang 2,

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.
Keywords: circular cone optimization, large- and small-update methods, second-order cone optimization, polynomial complexity., Interior-point methods, Kernel function.
Mathematics Subject Classification: Primary: 90C05, 90C51; Secondary: 65K0.
Citation: Yanqin Bai, Xuerui Gao, Guoqiang Wang. Primal-dual interior-point algorithms for convex quadratic circular cone optimization. Numerical Algebra, Control and 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-51. doi: 10.1007/s10107-002-0339-5.

[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.

[3]

Y. Q. Bai, Kernel Function-Based Interior-Point Algorithms for Conic Optimization, Science Press, Beijing, 2010.

[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-128. doi: 10.1137/S1052623403423114.

[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-3602. doi: 10.1016/j.na.2008.07.016.

[6]

S. P. Boyd and B. Wegbreit, Fast computation of optimal contact forces, IEEE Trans. Robot., 23 (2007), 1117-1132.

[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-173. doi: 10.1016/j.na.2013.01.017.

[8]

L. Faybusovich, Euclidean Jordan algebras and interior-point algorithms, Positivity, 1 (1997), 331-357. doi: 10.1023/A:1009701824047.

[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-484. doi: 10.1016/j.ejor.2011.02.022.

[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-517. doi: 10.1007/s13160-012-0081-1.

[11]

Y. Nesterov, Towards non-symmetric conic optimization, Optim. Method Softw., 27 (2012) 893-917. doi: 10.1080/10556788.2011.567270.

[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-203. doi: 10.1137/S1052623401383236.

[13]

C. Roos, T. Terlaky and J.-Ph. Vial, Theory and Algorithms for Linear Optimization: An Interior-Point Approach, John Wiley & Sons, 1997.

[14]

S. H. Schmieta and F. Alizadeh, Extension of primal-dual interior-point algorithms to symmetric cones, Math. Program., 96 (2003), 409-438. doi: 10.1007/s10107-003-0380-z.

[15]

A. Skajaa and Y. Y. Ye, A homogeneous interior-point algorithm for nonsymmetric convex conic optimization, Math. Program., 150 (2015), 391-422. doi: 10.1007/s10107-014-0773-1.

[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-1061. doi: 10.1016/j.amc.2009.06.034.

[17]

G. Q. Wang and Y. Q. Bai, Primal-dual interior-point algorithm for convex quadratic semidefinite optimization, Nonlinear Anal., 71 (2009), 3389-3402. doi: 10.1016/j.na.2009.01.241.

[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-558. doi: 10.1007/s11075-010-9444-3.

[19]

Y. N. Wang, N. H. Xiu and J. Y. Han, On cone of nonsymmetric positive semidefinite matrices, Linear Algebra Appl., 433 (2010), 718-736. doi: 10.1016/j.laa.2010.03.042.

[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-19.

[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-858. doi: 10.1007/s10957-013-0278-8.

[22]

J. C. Zhou and J. S. Chen, The vector-valued functions associated with circular cones, Abstr. Appl. Anal., 2014 (2014), 21pages. doi: 10.1155/2014/603542.

[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-816.

[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), 17 pages. doi: 10.1186/1029-242X-2013-571.

[25]

J. C. Zhou, J. S. Chen and B. S. Mordukhovich, Variational analysis of circular cone programs, Optim., 64 (2014), 113-147. doi: 10.1080/02331934.2014.951043.

show all references

References:
[1]

F. Alizadeh and D. Goldfard, Second-order cone programming, Math. Program., 95 (2003), 3-51. doi: 10.1007/s10107-002-0339-5.

[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.

[3]

Y. Q. Bai, Kernel Function-Based Interior-Point Algorithms for Conic Optimization, Science Press, Beijing, 2010.

[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-128. doi: 10.1137/S1052623403423114.

[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-3602. doi: 10.1016/j.na.2008.07.016.

[6]

S. P. Boyd and B. Wegbreit, Fast computation of optimal contact forces, IEEE Trans. Robot., 23 (2007), 1117-1132.

[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-173. doi: 10.1016/j.na.2013.01.017.

[8]

L. Faybusovich, Euclidean Jordan algebras and interior-point algorithms, Positivity, 1 (1997), 331-357. doi: 10.1023/A:1009701824047.

[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-484. doi: 10.1016/j.ejor.2011.02.022.

[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-517. doi: 10.1007/s13160-012-0081-1.

[11]

Y. Nesterov, Towards non-symmetric conic optimization, Optim. Method Softw., 27 (2012) 893-917. doi: 10.1080/10556788.2011.567270.

[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-203. doi: 10.1137/S1052623401383236.

[13]

C. Roos, T. Terlaky and J.-Ph. Vial, Theory and Algorithms for Linear Optimization: An Interior-Point Approach, John Wiley & Sons, 1997.

[14]

S. H. Schmieta and F. Alizadeh, Extension of primal-dual interior-point algorithms to symmetric cones, Math. Program., 96 (2003), 409-438. doi: 10.1007/s10107-003-0380-z.

[15]

A. Skajaa and Y. Y. Ye, A homogeneous interior-point algorithm for nonsymmetric convex conic optimization, Math. Program., 150 (2015), 391-422. doi: 10.1007/s10107-014-0773-1.

[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-1061. doi: 10.1016/j.amc.2009.06.034.

[17]

G. Q. Wang and Y. Q. Bai, Primal-dual interior-point algorithm for convex quadratic semidefinite optimization, Nonlinear Anal., 71 (2009), 3389-3402. doi: 10.1016/j.na.2009.01.241.

[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-558. doi: 10.1007/s11075-010-9444-3.

[19]

Y. N. Wang, N. H. Xiu and J. Y. Han, On cone of nonsymmetric positive semidefinite matrices, Linear Algebra Appl., 433 (2010), 718-736. doi: 10.1016/j.laa.2010.03.042.

[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-19.

[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-858. doi: 10.1007/s10957-013-0278-8.

[22]

J. C. Zhou and J. S. Chen, The vector-valued functions associated with circular cones, Abstr. Appl. Anal., 2014 (2014), 21pages. doi: 10.1155/2014/603542.

[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-816.

[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), 17 pages. doi: 10.1186/1029-242X-2013-571.

[25]

J. C. Zhou, J. S. Chen and B. S. Mordukhovich, Variational analysis of circular cone programs, Optim., 64 (2014), 113-147. doi: 10.1080/02331934.2014.951043.

[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 and 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 and 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 and Optimization, 2015, 5 (1) : 37-46. doi: 10.3934/naco.2015.5.37
[4]

Ayache Benhadid, Fateh Merahi. Complexity analysis of an interior-point algorithm for linear optimization based on a new parametric kernel function with a double barrier term. Numerical Algebra, Control and Optimization, 2022  doi: 10.3934/naco.2022003
[5]

Lin Zhu, Xinzhen Zhang. Semidefinite relaxation method for polynomial optimization with second-order cone complementarity constraints. Journal of Industrial and Management Optimization, 2022, 18 (3) : 1505-1517. doi: 10.3934/jimo.2021030
[6]

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
[7]

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
[8]

Liwei Zhang, Jihong Zhang, Yule Zhang. Second-order optimality conditions for cone constrained multi-objective optimization. Journal of Industrial and Management Optimization, 2018, 14 (3) : 1041-1054. doi: 10.3934/jimo.2017089
[9]

Anurag Jayswala, Tadeusz Antczakb, Shalini Jha. Second order modified objective function method for twice differentiable vector optimization problems over cone constraints. Numerical Algebra, Control and Optimization, 2019, 9 (2) : 133-145. doi: 10.3934/naco.2019010
[10]

Yi Zhang, Yong Jiang, Liwei Zhang, Jiangzhong Zhang. A perturbation approach for an inverse linear second-order cone programming. Journal of Industrial and Management Optimization, 2013, 9 (1) : 171-189. doi: 10.3934/jimo.2013.9.171
[11]

Behrouz Kheirfam, Morteza Moslemi. On the extension of an arc-search interior-point algorithm for semidefinite optimization. Numerical Algebra, Control and Optimization, 2018, 8 (2) : 261-275. doi: 10.3934/naco.2018015
[12]

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
[13]

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 and Management Optimization, 2015, 11 (4) : 1111-1125. doi: 10.3934/jimo.2015.11.1111
[14]

Xiaoling Guo, Zhibin Deng, Shu-Cherng Fang, Wenxun Xing. Quadratic optimization over one first-order cone. Journal of Industrial and Management Optimization, 2014, 10 (3) : 945-963. doi: 10.3934/jimo.2014.10.945
[15]

Ye Tian, Qingwei Jin, Zhibin Deng. Quadratic optimization over a polyhedral cone. Journal of Industrial and Management Optimization, 2016, 12 (1) : 269-283. doi: 10.3934/jimo.2016.12.269
[16]

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 and Management Optimization, 2013, 9 (3) : 703-721. doi: 10.3934/jimo.2013.9.703
[17]

Xi-De Zhu, Li-Ping Pang, Gui-Hua Lin. Two approaches for solving mathematical programs with second-order cone complementarity constraints. Journal of Industrial and Management Optimization, 2015, 11 (3) : 951-968. doi: 10.3934/jimo.2015.11.951
[18]

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
[19]

Li Chu, Bo Wang, Jie Zhang, Hong-Wei Zhang. Convergence analysis of a smoothing SAA method for a stochastic mathematical program with second-order cone complementarity constraints. Journal of Industrial and Management Optimization, 2021, 17 (4) : 1863-1886. doi: 10.3934/jimo.2020050
[20]

Xin-He Miao, Kai Yao, Ching-Yu Yang, Jein-Shan Chen. Levenberg-Marquardt method for absolute value equation associated with second-order cone. Numerical Algebra, Control and Optimization, 2022, 12 (1) : 47-61. doi: 10.3934/naco.2021050

 Impact Factor: 

Tools

Metrics

  • PDF downloads (170)
  • HTML views (0)
  • Cited by (8)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy