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

Previous Article
Continuity and stability of two-stage stochastic programs with quadratic continuous recourse
NACO Home
This Issue
Next Article

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

Abstract
Related Papers

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 & 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.
[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, (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. 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. 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.
[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.
[8]	L. Faybusovich, Euclidean Jordan algebras and interior-point algorithms,, Positivity, 1 (1997), 331. 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. 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. doi: 10.1007/s13160-012-0081-1.
[11]	Y. Nesterov, Towards non-symmetric conic optimization,, Optim. Method Softw., 27 (2012), 893. 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. 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. 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. 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. 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. 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. 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. 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.
[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.*
[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.*
[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.
[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.*
[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.

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.
[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, (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. 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. 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.
[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.
[8]	L. Faybusovich, Euclidean Jordan algebras and interior-point algorithms,, Positivity, 1 (1997), 331. 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. 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. doi: 10.1007/s13160-012-0081-1.
[11]	Y. Nesterov, Towards non-symmetric conic optimization,, Optim. Method Softw., 27 (2012), 893. 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. 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. 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. 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. 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. 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. 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. 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.
[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.*
[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.*
[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.
[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.*
[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.

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

American Institute of Mathematical Sciences