2014, 4(2): 141-150. doi: 10.3934/naco.2014.4.141

A weighted-path-following method for symmetric cone linear complementarity problems

1. 

Department of Mathematics, Azarbaijan Shahid Madani University, Tabriz, I.R., Iran

Received  June 2013 Revised  April 2014 Published  May 2014

In this paper a weighted-path-following interior-point algorithm for linear complementarity problem over symmetric cones is proposed that uses new search directions. The complexity results of the new algorithm derived and proved that the proposed algorithm has quadratically convergent with polynomial-time. We conclude that following the central path yields to the best iteration bound in this case as well.
Citation: Behrouz Kheirfam. A weighted-path-following method for symmetric cone linear complementarity problems. Numerical Algebra, Control & Optimization, 2014, 4 (2) : 141-150. doi: 10.3934/naco.2014.4.141
References:
[1]

M. Achache, A weighted-path-following method for the linear complementarity problem,, Studia Univ. Babes-Bolyai, (2004), 61.   Google Scholar

[2]

Z. Darvay, New interior-point algorithms in linear programming,, Adv. Model. Optim., 5 (2003), 51.   Google Scholar

[3]

J. Ding and T. Y. Li, An algorithm based on weighted logarithmic barrier functions for linear complementarity problems,, Arabian Journal for Science and Engineering, 15 (1990), 679.   Google Scholar

[4]

J. Faraut and A. Korányi, Analysis on Symmetric Cones,, Oxford Mathematical Monographs, (1994).   Google Scholar

[5]

L. Faybusovich, A Jordan-algebraic approach to potential-reduction algorithms,, Mathematicsche Zeitschrift, 239 (2002), 117.  doi: 10.1007/s002090100286.  Google Scholar

[6]

L. Faybusovich, Linear systems in Jordan algebras and primal-dual interior-point algorithms,, J. Comput. Appl. Math., 86 (1997), 149.  doi: 10.1016/S0377-0427(97)00153-2.  Google Scholar

[7]

L. Faybusovich, Euclidean Jordan algebras and interior-point algorithms,, Positivity, 1 (1997), 331.  doi: 10.1023/A:1009701824047.  Google Scholar

[8]

O. Güler, Barrier functions in interior-point methods,, Math. Oper. Res., 21 (1996), 860.  doi: 10.1287/moor.21.4.860.  Google Scholar

[9]

B. Jansen, C. Roos, T. Terlaky and J.-Ph. Vial, Primal-dual target-following algorithms for linear programming,, Anna. Oper. Res., 62 (1996), 197.  doi: 10.1007/BF02206817.  Google Scholar

[10]

B. Kheirfam, A full Nesterov-Todd step feasible weighted primal-dual interior-point algorithm for symmetric optimization,, J. Oper. Res. Soci. of China, 1 (2013), 467.   Google Scholar

[11]

M. Kojima, S. Shindoh and S. Hara, Interior-point methods for the monotone semidefinite linear complementarity problem in symmetric matrices,, SIAM J. Optim., 7 (1997), 86.  doi: 10.1137/S1052623494269035.  Google Scholar

[12]

G. Lesaja and C. Roos, Kernel-based interior-point methods for monotone linear complementarity problems over symmetric cones,, J. Optim. Theory Appl., 150 (2011), 444.  doi: 10.1007/s10957-011-9848-9.  Google Scholar

[13]

Y. E. Nesterov and M. J. Todd, Self-scaled barriers and interior-point methods for convex programming,, Math. Oper. Res., 22 (1997), 1.  doi: 10.1287/moor.22.1.1.  Google Scholar

[14]

Y. E. Nesterov, M. J. Todd, Primal-dual interior-point methods for self-scaled cones,, SIAM J. Optim., 8 (1998), 324.  doi: 10.1137/S1052623495290209.  Google Scholar

[15]

B. K. Rangarajan, Polynomial convergence of infeasible interior-point methods over symmetric cones,, SIAM J. Optim., 16 (2006), 1211.  doi: 10.1137/040606557.  Google Scholar

[16]

C. Roos and D. den Hertog, A polynomial method of approximate weighted centers for linear programming,, Technical Report 89-13, (1994), 89.   Google Scholar

[17]

S. H. Schmieta and F. Alizadeh, Extension of primal-dual interior-point algorithm to symmetric cones,, Math. Program., 96 (2003), 409.  doi: 10.1007/s10107-003-0380-z.  Google Scholar

[18]

S. H. Schmieta and F. Alizadeh, Associative and Jordan algebras and polynomial time interior-point algorithms for symmetric cones,, Math. Oper. Res., 26 (2001), 543.  doi: 10.1287/moor.26.3.543.10582.  Google Scholar

[19]

J. F. Sturm, Similarity and other spectral relations for symmetric cones,, Algebra Appl., 312 (2000), 135.  doi: 10.1016/S0024-3795(00)00096-3.  Google Scholar

[20]

M. V. C. Vieira, Jordan Algebraic Approach to Symmetric Optimization,, Ph.D. Thesis, (2007).   Google Scholar

[21]

G. Q. Wang and Y. Q. Bai, A new full Nesterov-Todd step primal-dual path-following interior-point algorithm for symmetric optimization,, J. Optim. Theory Appl., 154 (2012), 966.  doi: 10.1007/s10957-012-0013-x.  Google Scholar

show all references

References:
[1]

M. Achache, A weighted-path-following method for the linear complementarity problem,, Studia Univ. Babes-Bolyai, (2004), 61.   Google Scholar

[2]

Z. Darvay, New interior-point algorithms in linear programming,, Adv. Model. Optim., 5 (2003), 51.   Google Scholar

[3]

J. Ding and T. Y. Li, An algorithm based on weighted logarithmic barrier functions for linear complementarity problems,, Arabian Journal for Science and Engineering, 15 (1990), 679.   Google Scholar

[4]

J. Faraut and A. Korányi, Analysis on Symmetric Cones,, Oxford Mathematical Monographs, (1994).   Google Scholar

[5]

L. Faybusovich, A Jordan-algebraic approach to potential-reduction algorithms,, Mathematicsche Zeitschrift, 239 (2002), 117.  doi: 10.1007/s002090100286.  Google Scholar

[6]

L. Faybusovich, Linear systems in Jordan algebras and primal-dual interior-point algorithms,, J. Comput. Appl. Math., 86 (1997), 149.  doi: 10.1016/S0377-0427(97)00153-2.  Google Scholar

[7]

L. Faybusovich, Euclidean Jordan algebras and interior-point algorithms,, Positivity, 1 (1997), 331.  doi: 10.1023/A:1009701824047.  Google Scholar

[8]

O. Güler, Barrier functions in interior-point methods,, Math. Oper. Res., 21 (1996), 860.  doi: 10.1287/moor.21.4.860.  Google Scholar

[9]

B. Jansen, C. Roos, T. Terlaky and J.-Ph. Vial, Primal-dual target-following algorithms for linear programming,, Anna. Oper. Res., 62 (1996), 197.  doi: 10.1007/BF02206817.  Google Scholar

[10]

B. Kheirfam, A full Nesterov-Todd step feasible weighted primal-dual interior-point algorithm for symmetric optimization,, J. Oper. Res. Soci. of China, 1 (2013), 467.   Google Scholar

[11]

M. Kojima, S. Shindoh and S. Hara, Interior-point methods for the monotone semidefinite linear complementarity problem in symmetric matrices,, SIAM J. Optim., 7 (1997), 86.  doi: 10.1137/S1052623494269035.  Google Scholar

[12]

G. Lesaja and C. Roos, Kernel-based interior-point methods for monotone linear complementarity problems over symmetric cones,, J. Optim. Theory Appl., 150 (2011), 444.  doi: 10.1007/s10957-011-9848-9.  Google Scholar

[13]

Y. E. Nesterov and M. J. Todd, Self-scaled barriers and interior-point methods for convex programming,, Math. Oper. Res., 22 (1997), 1.  doi: 10.1287/moor.22.1.1.  Google Scholar

[14]

Y. E. Nesterov, M. J. Todd, Primal-dual interior-point methods for self-scaled cones,, SIAM J. Optim., 8 (1998), 324.  doi: 10.1137/S1052623495290209.  Google Scholar

[15]

B. K. Rangarajan, Polynomial convergence of infeasible interior-point methods over symmetric cones,, SIAM J. Optim., 16 (2006), 1211.  doi: 10.1137/040606557.  Google Scholar

[16]

C. Roos and D. den Hertog, A polynomial method of approximate weighted centers for linear programming,, Technical Report 89-13, (1994), 89.   Google Scholar

[17]

S. H. Schmieta and F. Alizadeh, Extension of primal-dual interior-point algorithm to symmetric cones,, Math. Program., 96 (2003), 409.  doi: 10.1007/s10107-003-0380-z.  Google Scholar

[18]

S. H. Schmieta and F. Alizadeh, Associative and Jordan algebras and polynomial time interior-point algorithms for symmetric cones,, Math. Oper. Res., 26 (2001), 543.  doi: 10.1287/moor.26.3.543.10582.  Google Scholar

[19]

J. F. Sturm, Similarity and other spectral relations for symmetric cones,, Algebra Appl., 312 (2000), 135.  doi: 10.1016/S0024-3795(00)00096-3.  Google Scholar

[20]

M. V. C. Vieira, Jordan Algebraic Approach to Symmetric Optimization,, Ph.D. Thesis, (2007).   Google Scholar

[21]

G. Q. Wang and Y. Q. Bai, A new full Nesterov-Todd step primal-dual path-following interior-point algorithm for symmetric optimization,, J. Optim. Theory Appl., 154 (2012), 966.  doi: 10.1007/s10957-012-0013-x.  Google Scholar

[1]

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

[2]

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

[3]

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

[4]

Jie Zhang, Yue Wu, Liwei Zhang. A class of smoothing SAA methods for a stochastic linear complementarity problem. Numerical Algebra, Control & Optimization, 2012, 2 (1) : 145-156. doi: 10.3934/naco.2012.2.145

[5]

Fengming Ma, Yiju Wang, Hongge Zhao. A potential reduction method for the generalized linear complementarity problem over a polyhedral cone. Journal of Industrial & Management Optimization, 2010, 6 (1) : 259-267. doi: 10.3934/jimo.2010.6.259

[6]

Andrew E.B. Lim, John B. Moore. A path following algorithm for infinite quadratic programming on a Hilbert space. Discrete & Continuous Dynamical Systems - A, 1998, 4 (4) : 653-670. doi: 10.3934/dcds.1998.4.653

[7]

Mariantonia Cotronei, Tomas Sauer. Full rank filters and polynomial reproduction. Communications on Pure & Applied Analysis, 2007, 6 (3) : 667-687. doi: 10.3934/cpaa.2007.6.667

[8]

Martin Frank, Armin Fügenschuh, Michael Herty, Lars Schewe. The coolest path problem. Networks & Heterogeneous Media, 2010, 5 (1) : 143-162. doi: 10.3934/nhm.2010.5.143

[9]

Igor E. Pritsker and Richard S. Varga. Weighted polynomial approximation in the complex plane. Electronic Research Announcements, 1997, 3: 38-44.

[10]

Li-Xia Liu, Sanyang Liu, Chun-Feng Wang. Smoothing Newton methods for symmetric cone linear complementarity problem with the Cartesian $P$/$P_0$-property. Journal of Industrial & Management Optimization, 2011, 7 (1) : 53-66. doi: 10.3934/jimo.2011.7.53

[11]

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

[12]

Louis Caccetta, Ian Loosen, Volker Rehbock. Computational aspects of the optimal transit path problem. Journal of Industrial & Management Optimization, 2008, 4 (1) : 95-105. doi: 10.3934/jimo.2008.4.95

[13]

Tijana Levajković, Hermann Mena, Amjad Tuffaha. The stochastic linear quadratic optimal control problem in Hilbert spaces: A polynomial chaos approach. Evolution Equations & Control Theory, 2016, 5 (1) : 105-134. doi: 10.3934/eect.2016.5.105

[14]

Liuyang Yuan, Zhongping Wan, Jingjing Zhang, Bin Sun. A filled function method for solving nonlinear complementarity problem. Journal of Industrial & Management Optimization, 2009, 5 (4) : 911-928. doi: 10.3934/jimo.2009.5.911

[15]

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

[16]

Guoliang Xue, Weiyi Zhang, Tie Wang, Krishnaiyan Thulasiraman. On the partial path protection scheme for WDM optical networks and polynomial time computability of primary and secondary paths. Journal of Industrial & Management Optimization, 2007, 3 (4) : 625-643. doi: 10.3934/jimo.2007.3.625

[17]

Kohei Ueno. Weighted Green functions of nondegenerate polynomial skew products on $\mathbb{C}^2$. Discrete & Continuous Dynamical Systems - A, 2011, 31 (3) : 985-996. doi: 10.3934/dcds.2011.31.985

[18]

Kohei Ueno. Weighted Green functions of polynomial skew products on $\mathbb{C}^2$. Discrete & Continuous Dynamical Systems - A, 2014, 34 (5) : 2283-2305. doi: 10.3934/dcds.2014.34.2283

[19]

Alina Ostafe, Igor E. Shparlinski, Arne Winterhof. On the generalized joint linear complexity profile of a class of nonlinear pseudorandom multisequences. Advances in Mathematics of Communications, 2010, 4 (3) : 369-379. doi: 10.3934/amc.2010.4.369

[20]

Wei-Zhe Gu, Li-Yong Lu. The linear convergence of a derivative-free descent method for nonlinear complementarity problems. Journal of Industrial & Management Optimization, 2017, 13 (2) : 531-548. doi: 10.3934/jimo.2016030

 Impact Factor: 

Metrics

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

Other articles
by authors

[Back to Top]