• Previous Article
    Resilience analysis for project scheduling with renewable resource constraint and uncertain activity durations
  • JIMO Home
  • This Issue
  • Next Article
    The coordination of single-machine scheduling with availability constraints and delivery
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

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].
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. 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. 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, 70 (2009), 3584. doi: 10.1016/j.na.2008.07.016.

[4]

Y. Q. Bai, Kernel Function-Based Interior-point Algorithms for Conic Optimization,, Science Press, (2010).

[5]

A. Ben-Tal and A. Nemirovski, Lectures on Modern Convex Optimization: Analysis, Algorithms and Engineering Applications,, MPS/SIAM Series on Optimization, (2001). doi: 10.1137/1.9780898718829.

[6]

I. Bomze, Copositive optimization-Recent developments and applications,, European Journal of Operational Research, 216 (2012), 509. doi: 10.1016/j.ejor.2011.04.026.

[7]

I. Bomze, M. Dur and C. P. Teo, Copositive optimization,, Mathematical Optimization Society Newsletter, 89 (2012), 2. 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), 785. doi: 10.1109/ROBOT.2010.5509833.

[9]

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

[10]

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

[11]

S. Burer, On the copositive representation of binary and continuous nonconvex quadratic programs,, Mathematical Programming Series A, 120 (2009), 479. 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, 85 (2013), 160. 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. doi: 10.1007/s10107-004-0538-3.

[14]

S. C. Fang and W. X. Xing, Linear Conic Programming: Theory and Applications,, Science Press, (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. doi: 10.1137/S1052623400380365.

[16]

O. Güler, Barrier functions in interior point methods,, Mathematics of Operations Research, 21 (1996), 860. 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).

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

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

[21]

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

[22]

Y. Nesterov, Towards nonsymmetric conic optimization,, Optimization Methods and Software, 27 (2012), 893. 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. 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. doi: 10.1137/S1052623401383236.

[25]

J. Renegar, A Mathematical View of Interior-Point Methods in Convex Optimization,, MPS/SIAM Series on Optimization, (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). 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. 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. 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.

show all references

References:
[1]

F. Alizadeh and D. Goldfarb, Second-order cone programming,, Mathematical Programming Series B, 95 (2003), 3. 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. 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, 70 (2009), 3584. doi: 10.1016/j.na.2008.07.016.

[4]

Y. Q. Bai, Kernel Function-Based Interior-point Algorithms for Conic Optimization,, Science Press, (2010).

[5]

A. Ben-Tal and A. Nemirovski, Lectures on Modern Convex Optimization: Analysis, Algorithms and Engineering Applications,, MPS/SIAM Series on Optimization, (2001). doi: 10.1137/1.9780898718829.

[6]

I. Bomze, Copositive optimization-Recent developments and applications,, European Journal of Operational Research, 216 (2012), 509. doi: 10.1016/j.ejor.2011.04.026.

[7]

I. Bomze, M. Dur and C. P. Teo, Copositive optimization,, Mathematical Optimization Society Newsletter, 89 (2012), 2. 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), 785. doi: 10.1109/ROBOT.2010.5509833.

[9]

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

[10]

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

[11]

S. Burer, On the copositive representation of binary and continuous nonconvex quadratic programs,, Mathematical Programming Series A, 120 (2009), 479. 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, 85 (2013), 160. 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. doi: 10.1007/s10107-004-0538-3.

[14]

S. C. Fang and W. X. Xing, Linear Conic Programming: Theory and Applications,, Science Press, (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. doi: 10.1137/S1052623400380365.

[16]

O. Güler, Barrier functions in interior point methods,, Mathematics of Operations Research, 21 (1996), 860. 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).

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

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

[21]

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

[22]

Y. Nesterov, Towards nonsymmetric conic optimization,, Optimization Methods and Software, 27 (2012), 893. 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. 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. doi: 10.1137/S1052623401383236.

[25]

J. Renegar, A Mathematical View of Interior-Point Methods in Convex Optimization,, MPS/SIAM Series on Optimization, (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). 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. 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. 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.

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

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

[7]

Liming Sun, Li-Zhi Liao. An interior point continuous path-following trajectory for linear programming. Journal of Industrial & Management Optimization, 2018, 13 (5) : 1-18. doi: 10.3934/jimo.2018107

[8]

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

[9]

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

[10]

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

[11]

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, 2017, 13 (5) : 1-27. doi: 10.3934/jimo.2018190

[12]

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

[13]

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

[14]

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

[15]

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

[16]

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

[17]

Xiangtuan Xiong, Jinmei Li, Jin Wen. Some novel linear regularization methods for a deblurring problem. Inverse Problems & Imaging, 2017, 11 (2) : 403-426. doi: 10.3934/ipi.2017019

[18]

Ziran Yin, Liwei Zhang. Perturbation analysis of a class of conic programming problems under Jacobian uniqueness conditions. Journal of Industrial & Management Optimization, 2019, 15 (3) : 1387-1397. doi: 10.3934/jimo.2018100

[19]

Yue Zheng, Zhongping Wan, Shihui Jia, Guangmin Wang. A new method for strong-weak linear bilevel programming problem. Journal of Industrial & Management Optimization, 2015, 11 (2) : 529-547. doi: 10.3934/jimo.2015.11.529

[20]

Xin Zhang, Jie Wen, Qin Ni. Subspace trust-region algorithm with conic model for unconstrained optimization. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 223-234. doi: 10.3934/naco.2013.3.223

2018 Impact Factor: 1.025

Metrics

  • PDF downloads (10)
  • HTML views (0)
  • Cited by (4)

Other articles
by authors

[Back to Top]