A polynomial-time interior-point method for circular cone programming based on kernel functions

Previous Article
The coordination of single-machine scheduling with availability constraints and delivery
JIMO Home
This Issue
Next Article
Resilience analysis for project scheduling with renewable resource constraint and uncertain activity durations

April 2016, 12(2): 739-756. doi: 10.3934/jimo.2016.12.739

A polynomial-time interior-point method for circular cone programming based on kernel functions

Yanqin Bai ^1, , Pengfei Ma ^2, and Jing Zhang ^2,

1.	Department of Mathematics, Shanghai University, Shanghai 200444
2.	Department of Mathematics, Shanghai University, Shanghai, 200444, China, China

Received May 2014 Revised March 2015 Published June 2015

Abstract
Related Papers

We present an interior-point method based on kernel functions for circular cone optimization problems, which has been found useful for describing optimal design problems of optimal grasping manipulation for multi-fingered robots. Since the well-known second order cone is a particular circular cone, we first establish an invertible linear mapping between a circular cone and its corresponding second order cone. Then we develop a kernel function based interior-point method to solve circular cone optimization in terms of the corresponding second order cone optimization problem. We derive the complexity bound of the interior-point method and conclude that circular cone optimization is polynomial-time solvable. Finally we illustrate the performance of interior-point method by a real-world quadruped robot example of optimal contact forces taken from the literature [10].

Keywords: interior-point methods, polynomial-time algorithm., Linear conic programming problem.

Mathematics Subject Classification: Primary: 90C25, 90C51; Secondary: 90C6.

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

References:

[1]	F. Alizadeh and D. Goldfarb, Second-order cone programming, Mathematical Programming Series B, 95 (2003), 3-51. doi: 10.1007/s10107-002-0339-5.
[2]	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 Journal on Optimization, 15 (2004), 101-128. doi: 10.1137/S1052623403423114.
[3]	Y. Q. Bai, G. Q. Wang and C. Roos, Primal-dual interior-point algorithms for second-order cone optimization based on kernel functions, Nonlinear Analysis: Theory, Methods & Applications, 70 (2009), 3584-3602. doi: 10.1016/j.na.2008.07.016.
[4]	Y. Q. Bai, Kernel Function-Based Interior-point Algorithms for Conic Optimization, Science Press, Beijing, 2010.
[5]	A. Ben-Tal and A. Nemirovski, Lectures on Modern Convex Optimization: Analysis, Algorithms and Engineering Applications, MPS/SIAM Series on Optimization, SIAM Publications, Philadelphia, 2001. doi: 10.1137/1.9780898718829.
[6]	I. Bomze, Copositive optimization-Recent developments and applications, European Journal of Operational Research, 216 (2012), 509-520. doi: 10.1016/j.ejor.2011.04.026.
[7]	I. Bomze, M. Dur and C. P. Teo, Copositive optimization, Mathematical Optimization Society Newsletter, Optima 89 (2012), 2-8. doi: 10.1007/978-0-387-74759-0_99.
[8]	P. H. Borgstrom, M. A. Batalin, G. Sukhatme, et al., Weighted barrier functions for computation of force distributions with friction cone constraints, Robotics and Automation (ICRA), 2010 IEEE International Conference on, IEEE, (2010), 785-792. doi: 10.1109/ROBOT.2010.5509833.
[9]	S. Boyd and L. Vandenberghe, Convex Optimization, Cambridge University Press, Cambridge, 2004. doi: 10.1017/CBO9780511804441.
[10]	S. Boyd and B. Wegbreit, Fast computation of optimal contact forces, IEEE Transactions on Robotics, 23 (2007), 1117-1132.
[11]	S. Burer, On the copositive representation of binary and continuous nonconvex quadratic programs, Mathematical Programming Series A, 120 (2009), 479-495. doi: 10.1007/s10107-008-0223-z.
[12]	Y. L. Chang, C. Y. Yang and J. S. Chen, Smooth and nonsmooth analyses of vector-valued functions associated with circular cones, Nonlinear Analysis: Theory, Methods and Applications, 85 (2013), 160-173. doi: 10.1016/j.na.2013.01.017.
[13]	J. S. Chen, X. Chen and P. Tseng, Analysis of nonsmooth vector-valued functions associated with second order cones, Mathematical Programming Series B, 101 (2004), 95-117. doi: 10.1007/s10107-004-0538-3.
[14]	S. C. Fang and W. X. Xing, Linear Conic Programming: Theory and Applications, Science Press, Beijing, 2013.
[15]	M. Fukushima, Z. Q. Luo and P. Tseng, Smoothing functions for second-order-cone complementarity problems, SIAM Journal on Optimization, 12 (2001), 436-460. doi: 10.1137/S1052623400380365.
[16]	O. Güler, Barrier functions in interior point methods, Mathematics of Operations Research, 21 (1996), 860-885. doi: 10.1287/moor.21.4.860.
[17]	C. H. Ko and J. S. Chen, Optimal grasping manipulation for multifingered robots using semismooth Newton method, em appear in Mathematical Problems in Engineering, 2013 (2013). Available from: http://math.ntnu.edu.tw/~jschen/Publications.html.
[18]	B. León, A. Morales and J. Sancho-Bru, Robot Grasping Foundations, In From Robot to Human Grasping Simulation, Springer International Publishing, (2014), 15-31.
[19]	Z. J. Li, S. Z. Sam Ge and S. B. Liu, Contact-force distribution optimization and control for quadruped robots using both gradient and adaptive neural networks, IEEE Transactions on Neural Networks and Learning Systems, 8 (2014), 1460-1473. doi: 10.1109/TNNLS.2013.2293500.
[20]	Y. Matsukawa and A. Yoshise, A primal barrier function Phase I algorithm for nonsymmetric conic optimization problems, Japan Journal of Industrial and Applied Mathematics, 29 (2012), 499-517. doi: 10.1007/s13160-012-0081-1.
[21]	A. Nemirovski, Advanced in convex optimization: Conic optimization, In International Congress of Mathematicians, 1 (2006), 413-444. doi: 10.4171/022-1/17.
[22]	Y. Nesterov, Towards nonsymmetric conic optimization, Optimization Methods and Software, 27 (2012), 893-917. doi: 10.1080/10556788.2011.567270.
[23]	Y. Nesterov and MJ. Todd, Primal-dual interior-point methods for self-scaled cones, SIAM Journal on Optimization, 8 (1998), 324-364. doi: 10.1137/S1052623495290209.
[24]	J. Peng, C. Roos and T. Terlaky, New primal-dual algorithms for second-order conic optimization based on self-regular proximities, SIAM Journal on Optimization, 13 (2002), 179-203. doi: 10.1137/S1052623401383236.
[25]	J. Renegar, A Mathematical View of Interior-Point Methods in Convex Optimization, MPS/SIAM Series on Optimization, SIAM Publications, Philadelphia, 2001. doi: 10.1137/1.9780898718812.
[26]	A. Skajaa and Y. Ye, Homogeneous interior-point algorithm for nonsymmetric convex conic optimization, To appear mathematical programming, (2014). Available from: http://link.springer.com/journal/10107/onlineFirst/page/1. doi: 10.1007/s10107-014-0773-1.
[27]	C. J. Yu, K. L. Teo, L. S. Zhang and Y. Q. Bai, A new exact penalty function method for continuous inequality constrained optimization problems, Journal of Industrial Management and Optimization, 6 (2010), 895-910. doi: 10.3934/jimo.2010.6.895.
[28]	C. J. Yu, K. L. Teo, L. S. Zhang and Y. Q. Bai, On a refinement of the convergence analysis for the new exact penalty function method for continuous inequality constrained optimization problem, Journal of Industrial Management and Optimization, 8 (2012), 485-491. doi: 10.3934/jimo.2012.8.485.
[29]	J. C. Zhou and J. S. Chen, Properties of circular cone and spectral factorization associated with circular cone, Journal of Nonlinear and Convex Analysis, 14 (2014), 807-816.

show all references

References:

[1]	F. Alizadeh and D. Goldfarb, Second-order cone programming, Mathematical Programming Series B, 95 (2003), 3-51. doi: 10.1007/s10107-002-0339-5.
[2]	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 Journal on Optimization, 15 (2004), 101-128. doi: 10.1137/S1052623403423114.
[3]	Y. Q. Bai, G. Q. Wang and C. Roos, Primal-dual interior-point algorithms for second-order cone optimization based on kernel functions, Nonlinear Analysis: Theory, Methods & Applications, 70 (2009), 3584-3602. doi: 10.1016/j.na.2008.07.016.
[4]	Y. Q. Bai, Kernel Function-Based Interior-point Algorithms for Conic Optimization, Science Press, Beijing, 2010.
[5]	A. Ben-Tal and A. Nemirovski, Lectures on Modern Convex Optimization: Analysis, Algorithms and Engineering Applications, MPS/SIAM Series on Optimization, SIAM Publications, Philadelphia, 2001. doi: 10.1137/1.9780898718829.
[6]	I. Bomze, Copositive optimization-Recent developments and applications, European Journal of Operational Research, 216 (2012), 509-520. doi: 10.1016/j.ejor.2011.04.026.
[7]	I. Bomze, M. Dur and C. P. Teo, Copositive optimization, Mathematical Optimization Society Newsletter, Optima 89 (2012), 2-8. doi: 10.1007/978-0-387-74759-0_99.
[8]	P. H. Borgstrom, M. A. Batalin, G. Sukhatme, et al., Weighted barrier functions for computation of force distributions with friction cone constraints, Robotics and Automation (ICRA), 2010 IEEE International Conference on, IEEE, (2010), 785-792. doi: 10.1109/ROBOT.2010.5509833.
[9]	S. Boyd and L. Vandenberghe, Convex Optimization, Cambridge University Press, Cambridge, 2004. doi: 10.1017/CBO9780511804441.
[10]	S. Boyd and B. Wegbreit, Fast computation of optimal contact forces, IEEE Transactions on Robotics, 23 (2007), 1117-1132.
[11]	S. Burer, On the copositive representation of binary and continuous nonconvex quadratic programs, Mathematical Programming Series A, 120 (2009), 479-495. doi: 10.1007/s10107-008-0223-z.
[12]	Y. L. Chang, C. Y. Yang and J. S. Chen, Smooth and nonsmooth analyses of vector-valued functions associated with circular cones, Nonlinear Analysis: Theory, Methods and Applications, 85 (2013), 160-173. doi: 10.1016/j.na.2013.01.017.
[13]	J. S. Chen, X. Chen and P. Tseng, Analysis of nonsmooth vector-valued functions associated with second order cones, Mathematical Programming Series B, 101 (2004), 95-117. doi: 10.1007/s10107-004-0538-3.
[14]	S. C. Fang and W. X. Xing, Linear Conic Programming: Theory and Applications, Science Press, Beijing, 2013.
[15]	M. Fukushima, Z. Q. Luo and P. Tseng, Smoothing functions for second-order-cone complementarity problems, SIAM Journal on Optimization, 12 (2001), 436-460. doi: 10.1137/S1052623400380365.
[16]	O. Güler, Barrier functions in interior point methods, Mathematics of Operations Research, 21 (1996), 860-885. doi: 10.1287/moor.21.4.860.
[17]	C. H. Ko and J. S. Chen, Optimal grasping manipulation for multifingered robots using semismooth Newton method, em appear in Mathematical Problems in Engineering, 2013 (2013). Available from: http://math.ntnu.edu.tw/~jschen/Publications.html.
[18]	B. León, A. Morales and J. Sancho-Bru, Robot Grasping Foundations, In From Robot to Human Grasping Simulation, Springer International Publishing, (2014), 15-31.
[19]	Z. J. Li, S. Z. Sam Ge and S. B. Liu, Contact-force distribution optimization and control for quadruped robots using both gradient and adaptive neural networks, IEEE Transactions on Neural Networks and Learning Systems, 8 (2014), 1460-1473. doi: 10.1109/TNNLS.2013.2293500.
[20]	Y. Matsukawa and A. Yoshise, A primal barrier function Phase I algorithm for nonsymmetric conic optimization problems, Japan Journal of Industrial and Applied Mathematics, 29 (2012), 499-517. doi: 10.1007/s13160-012-0081-1.
[21]	A. Nemirovski, Advanced in convex optimization: Conic optimization, In International Congress of Mathematicians, 1 (2006), 413-444. doi: 10.4171/022-1/17.
[22]	Y. Nesterov, Towards nonsymmetric conic optimization, Optimization Methods and Software, 27 (2012), 893-917. doi: 10.1080/10556788.2011.567270.
[23]	Y. Nesterov and MJ. Todd, Primal-dual interior-point methods for self-scaled cones, SIAM Journal on Optimization, 8 (1998), 324-364. doi: 10.1137/S1052623495290209.
[24]	J. Peng, C. Roos and T. Terlaky, New primal-dual algorithms for second-order conic optimization based on self-regular proximities, SIAM Journal on Optimization, 13 (2002), 179-203. doi: 10.1137/S1052623401383236.
[25]	J. Renegar, A Mathematical View of Interior-Point Methods in Convex Optimization, MPS/SIAM Series on Optimization, SIAM Publications, Philadelphia, 2001. doi: 10.1137/1.9780898718812.
[26]	A. Skajaa and Y. Ye, Homogeneous interior-point algorithm for nonsymmetric convex conic optimization, To appear mathematical programming, (2014). Available from: http://link.springer.com/journal/10107/onlineFirst/page/1. doi: 10.1007/s10107-014-0773-1.
[27]	C. J. Yu, K. L. Teo, L. S. Zhang and Y. Q. Bai, A new exact penalty function method for continuous inequality constrained optimization problems, Journal of Industrial Management and Optimization, 6 (2010), 895-910. doi: 10.3934/jimo.2010.6.895.
[28]	C. J. Yu, K. L. Teo, L. S. Zhang and Y. Q. Bai, On a refinement of the convergence analysis for the new exact penalty function method for continuous inequality constrained optimization problem, Journal of Industrial Management and Optimization, 8 (2012), 485-491. doi: 10.3934/jimo.2012.8.485.
[29]	J. C. Zhou and J. S. Chen, Properties of circular cone and spectral factorization associated with circular cone, Journal of Nonlinear and Convex Analysis, 14 (2014), 807-816.

[1]	Soodabeh Asadi, Hossein Mansouri. A Mehrotra type predictor-corrector interior-point algorithm for linear programming. Numerical Algebra, Control and Optimization, 2019, 9 (2) : 147-156. doi: 10.3934/naco.2019011
[2]	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
[3]	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
[4]	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
[5]	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
[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]	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]	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
[9]	Liming Sun, Li-Zhi Liao. An interior point continuous path-following trajectory for linear programming. Journal of Industrial and Management Optimization, 2019, 15 (4) : 1517-1534. doi: 10.3934/jimo.2018107
[10]	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
[11]	Qingsong Duan, Mengwei Xu, Liwei Zhang, Sainan Zhang. Hadamard directional differentiability of the optimal value of a linear second-order conic programming problem. Journal of Industrial and Management Optimization, 2021, 17 (6) : 3085-3098. doi: 10.3934/jimo.2020108
[12]	Terry Shue Chien Lau, Chik How Tan. Polynomial-time plaintext recovery attacks on the IKKR code-based cryptosystems. Advances in Mathematics of Communications, 2021 doi: 10.3934/amc.2020132
[13]	Yu-Hong Dai, Xin-Wei Liu, Jie Sun. A primal-dual interior-point method capable of rapidly detecting infeasibility for nonlinear programs. Journal of Industrial and Management Optimization, 2020, 16 (2) : 1009-1035. doi: 10.3934/jimo.2018190
[14]	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
[15]	Boshi Tian, Xiaoqi Yang, Kaiwen Meng. An interior-point $l_{\frac{1}{2}}$-penalty method for inequality constrained nonlinear optimization. Journal of Industrial and Management Optimization, 2016, 12 (3) : 949-973. doi: 10.3934/jimo.2016.12.949
[16]	Yibing Lv, Tiesong Hu, Jianlin Jiang. Penalty method-based equilibrium point approach for solving the linear bilevel multiobjective programming problem. Discrete and Continuous Dynamical Systems - S, 2020, 13 (6) : 1743-1755. doi: 10.3934/dcdss.2020102
[17]	Zheng-Hai Huang, Shang-Wen Xu. Convergence properties of a non-interior-point smoothing algorithm for the PNCP. Journal of Industrial and Management Optimization*, 2007, 3 (3) : 569-584. doi: 10.3934/jimo.2007.3.569
[18]	Vladimir Gaitsgory, Alex Parkinson, Ilya Shvartsman. Linear programming based optimality conditions and approximate solution of a deterministic infinite horizon discounted optimal control problem in discrete time. Discrete and Continuous Dynamical Systems - B, 2019, 24 (4) : 1743-1767. doi: 10.3934/dcdsb.2018235
[19]	Yanqun Liu. An exterior point linear programming method based on inclusive normal cones. Journal of Industrial and Management Optimization, 2010, 6 (4) : 825-846. doi: 10.3934/jimo.2010.6.825
[20]	Rong Hu, Ya-Ping Fang. A parametric simplex algorithm for biobjective piecewise linear programming problems. Journal of Industrial and Management Optimization, 2017, 13 (2) : 573-586. doi: 10.3934/jimo.2016032

2020 Impact Factor: 1.801

Tools

Metrics

Other articles
by authors

on AIMS
Yanqin Bai Pengfei Ma Jing Zhang
on Google Scholar
Yanqin Bai Pengfei Ma Jing Zhang

[Back to Top]