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

Predrag S. Stanimirović, Branislav Ivanov, Haifeng Ma, Dijana Mosić. A survey of gradient methods for solving nonlinear optimization. Electronic Research Archive, 2020, 28 (4) : 1573-1624. doi: 10.3934/era.2020115
[2]

Qiang Long, Xue Wu, Changzhi Wu. Non-dominated sorting methods for multi-objective optimization: Review and numerical comparison. Journal of Industrial & Management Optimization, 2021, 17 (2) : 1001-1023. doi: 10.3934/jimo.2020009
[3]

Shasha Hu, Yihong Xu, Yuhan Zhang. Second-Order characterizations for set-valued equilibrium problems with variable ordering structures. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020164
[4]

Liupeng Wang, Yunqing Huang. Error estimates for second-order SAV finite element method to phase field crystal model. Electronic Research Archive, 2021, 29 (1) : 1735-1752. doi: 10.3934/era.2020089
[5]

Ying Lv, Yan-Fang Xue, Chun-Lei Tang. Ground state homoclinic orbits for a class of asymptotically periodic second-order Hamiltonian systems. Discrete & Continuous Dynamical Systems - B, 2021, 26 (3) : 1627-1652. doi: 10.3934/dcdsb.2020176
[6]

Hua Chen, Yawei Wei. Multiple solutions for nonlinear cone degenerate elliptic equations. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020272
[7]

Liping Tang, Ying Gao. Some properties of nonconvex oriented distance function and applications to vector optimization problems. Journal of Industrial & Management Optimization, 2021, 17 (1) : 485-500. doi: 10.3934/jimo.2020117
[8]

Baoli Yin, Yang Liu, Hong Li, Zhimin Zhang. Approximation methods for the distributed order calculus using the convolution quadrature. Discrete & Continuous Dynamical Systems - B, 2021, 26 (3) : 1447-1468. doi: 10.3934/dcdsb.2020168
[9]

Xin Guo, Lexin Li, Qiang Wu. Modeling interactive components by coordinate kernel polynomial models. Mathematical Foundations of Computing, 2020, 3 (4) : 263-277. doi: 10.3934/mfc.2020010
[10]

Mohammed Abdulrazaq Kahya, Suhaib Abduljabbar Altamir, Zakariya Yahya Algamal. Improving whale optimization algorithm for feature selection with a time-varying transfer function. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 87-98. doi: 10.3934/naco.2020017
[11]

Yuyuan Ouyang, Trevor Squires. Some worst-case datasets of deterministic first-order methods for solving binary logistic regression. Inverse Problems & Imaging, 2021, 15 (1) : 63-77. doi: 10.3934/ipi.2020047
[12]

Gui-Qiang Chen, Beixiang Fang. Stability of transonic shock-fronts in three-dimensional conical steady potential flow past a perturbed cone. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 85-114. doi: 10.3934/dcds.2009.23.85
[13]

Bahaaeldin Abdalla, Thabet Abdeljawad. Oscillation criteria for kernel function dependent fractional dynamic equations. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020443
[14]

Philippe G. Ciarlet, Liliana Gratie, Cristinel Mardare. Intrinsic methods in elasticity: a mathematical survey. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 133-164. doi: 10.3934/dcds.2009.23.133
[15]

Xing-Bin Pan. Variational and operator methods for Maxwell-Stokes system. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3909-3955. doi: 10.3934/dcds.2020036
[16]

Min Xi, Wenyu Sun, Jun Chen. Survey of derivative-free optimization. Numerical Algebra, Control & Optimization, 2020, 10 (4) : 537-555. doi: 10.3934/naco.2020050
[17]

Weisong Dong, Chang Li. Second order estimates for complex Hessian equations on Hermitian manifolds. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020377
[18]

Gang Luo, Qingzhi Yang. The point-wise convergence of shifted symmetric higher order power method. Journal of Industrial & Management Optimization, 2021, 17 (1) : 357-368. doi: 10.3934/jimo.2019115
[19]

Xuefei He, Kun Wang, Liwei Xu. Efficient finite difference methods for the nonlinear Helmholtz equation in Kerr medium. Electronic Research Archive, 2020, 28 (4) : 1503-1528. doi: 10.3934/era.2020079
[20]

Xin Guo, Lei Shi. Preface of the special issue on analysis in data science: Methods and applications. Mathematical Foundations of Computing, 2020, 3 (4) : i-ii. doi: 10.3934/mfc.2020026

 Impact Factor: 

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences