American Institute of Mathematical Sciences

Advanced
  • 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

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 & 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.  Google Scholar

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

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

[4]

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

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

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

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

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

[9]

S. Boyd and L. Vandenberghe, Convex Optimization, Cambridge University Press, Cambridge, 2004. doi: 10.1017/CBO9780511804441.  Google Scholar

[10]

S. Boyd and B. Wegbreit, Fast computation of optimal contact forces, IEEE Transactions on Robotics, 23 (2007), 1117-1132. Google Scholar

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

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

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

[14]

S. C. Fang and W. X. Xing, Linear Conic Programming: Theory and Applications, Science Press, Beijing, 2013. Google Scholar

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

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

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

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

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

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

[21]

A. Nemirovski, Advanced in convex optimization: Conic optimization, In International Congress of Mathematicians, 1 (2006), 413-444. doi: 10.4171/022-1/17.  Google Scholar

[22]

Y. Nesterov, Towards nonsymmetric conic optimization, Optimization Methods and Software, 27 (2012), 893-917. doi: 10.1080/10556788.2011.567270.  Google Scholar

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

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

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

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

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

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

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

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.  Google Scholar

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

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

[4]

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

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

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

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

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

[9]

S. Boyd and L. Vandenberghe, Convex Optimization, Cambridge University Press, Cambridge, 2004. doi: 10.1017/CBO9780511804441.  Google Scholar

[10]

S. Boyd and B. Wegbreit, Fast computation of optimal contact forces, IEEE Transactions on Robotics, 23 (2007), 1117-1132. Google Scholar

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

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

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

[14]

S. C. Fang and W. X. Xing, Linear Conic Programming: Theory and Applications, Science Press, Beijing, 2013. Google Scholar

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

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

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

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

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

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

[21]

A. Nemirovski, Advanced in convex optimization: Conic optimization, In International Congress of Mathematicians, 1 (2006), 413-444. doi: 10.4171/022-1/17.  Google Scholar

[22]

Y. Nesterov, Towards nonsymmetric conic optimization, Optimization Methods and Software, 27 (2012), 893-917. doi: 10.1080/10556788.2011.567270.  Google Scholar

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

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

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

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

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

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

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

[1]

Soodabeh Asadi, Hossein Mansouri. A Mehrotra type predictor-corrector interior-point algorithm for linear programming. Numerical Algebra, Control & 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 & Management Optimization, 2016, 12 (1) : 103-116. doi: 10.3934/jimo.2016.12.103
[3]

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

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

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

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 & Management Optimization, 2021  doi: 10.3934/jimo.2021082
[7]

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

Liming Sun, Li-Zhi Liao. An interior point continuous path-following trajectory for linear programming. Journal of Industrial & Management Optimization, 2019, 15 (4) : 1517-1534. doi: 10.3934/jimo.2018107
[9]

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

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 & Management Optimization, 2021, 17 (6) : 3085-3098. doi: 10.3934/jimo.2020108
[11]

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

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 & Management Optimization, 2020, 16 (2) : 1009-1035. doi: 10.3934/jimo.2018190
[13]

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

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

Yibing Lv, Tiesong Hu, Jianlin Jiang. Penalty method-based equilibrium point approach for solving the linear bilevel multiobjective programming problem. Discrete & Continuous Dynamical Systems - S, 2020, 13 (6) : 1743-1755. doi: 10.3934/dcdss.2020102
[16]

Zheng-Hai Huang, Shang-Wen Xu. Convergence properties of a non-interior-point smoothing algorithm for the P*NCP. Journal of Industrial & Management Optimization, 2007, 3 (3) : 569-584. doi: 10.3934/jimo.2007.3.569
[17]

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 & Continuous Dynamical Systems - B, 2019, 24 (4) : 1743-1767. doi: 10.3934/dcdsb.2018235
[18]

Yanqun Liu. An exterior point linear programming method based on inclusive normal cones. Journal of Industrial & Management Optimization, 2010, 6 (4) : 825-846. doi: 10.3934/jimo.2010.6.825
[19]

Rong Hu, Ya-Ping Fang. A parametric simplex algorithm for biobjective piecewise linear programming problems. Journal of Industrial & Management Optimization, 2017, 13 (2) : 573-586. doi: 10.3934/jimo.2016032
[20]

Gurkan Ozturk, Mehmet Tahir Ciftci. Clustering based polyhedral conic functions algorithm in classification. Journal of Industrial & Management Optimization, 2015, 11 (3) : 921-932. doi: 10.3934/jimo.2015.11.921

2020 Impact Factor: 1.801

Tools

Metrics

  • PDF downloads (148)
  • HTML views (0)
  • Cited by (9)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences | Privacy Policy