• Previous Article
    Statistical mechanics approach for steady-state analysis in M/M/s queueing system with balking
  • JIMO Home
  • This Issue
  • Next Article
    Quantitative stability of the ERM formulation for a class of stochastic linear variational inequalities
doi: 10.3934/jimo.2021082
Online First

Online First articles are published articles within a journal that have not yet been assigned to a formal issue. This means they do not yet have a volume number, issue number, or page numbers assigned to them, however, they can still be found and cited using their DOI (Digital Object Identifier). Online First publication benefits the research community by making new scientific discoveries known as quickly as possible.

Readers can access Online First articles via the “Online First” tab for the selected journal.

A full-modified-Newton step $ O(n) $ infeasible interior-point method for the special weighted linear complementarity problem

1. 

School of Mathematics and Computing Science, Guilin University of Electronic Technology, Guilin 541004, China

2. 

School of Mathematics and Statistics, Wuhan University, Wuhan 430072, China

3. 

School of Mathematics and Information Science, North Minzu University, Yinchuan 750021, China

* Corresponding author: Zhongping Wan

Received  September 2020 Revised  February 2021 Early access April 2021

The weighted complementarity problem (wCP) can be applied to a large variety of equilibrium problems in science, economics and engineering. Since formulating an equilibrium problem as a wCP may lead to highly efficient algorithms for its numerical solution, wCP is a nontrivial generalization of the complementarity problem. In this paper we consider a special weighted linear complementarity problem (wLCP), which is the more general optimization of the Fisher market equilibrium problem. A full-modified-Newton infeasible interior-point method (IIPM) for the special wLCP is proposed. The algorithm reformulates the central path of the perturbed problem as an equivalent system of equations, and uses only full-Newton steps at each iteration, so-called a feasibility step (i.e., a full-modified-Newton step) and several usual centering steps. The polynomial complexity of the algorithm is as good as the best known iteration bound for these types of IIPMs in linear optimization.

Citation: 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, doi: 10.3934/jimo.2021082
References:
[1]

K. M. Anstreicher, Interior-point algorithms for a generalization of linear programming and weighted centring, Optim. Methods Softw., 27 (2012), 605-612.  doi: 10.1080/10556788.2011.644791.  Google Scholar

[2]

Y. BaiP. Ma and J. Zhang, A polynomial-time interior-point method for circular cone programming based on kernel functions, J. Ind. Manag. Optim., 12 (2016), 739-756.  doi: 10.3934/jimo.2016.12.739.  Google Scholar

[3]

J. -S. Chen, SOC Functions and their Applications, Springer, Singapore, 2019. doi: 10.1007/978-981-13-4077-2.  Google Scholar

[4]

X. ChiM. S. Gowda and J. Tao, The weighted horizontal linear complementarity problem on a Euclidean Jordan algebra, J. Global Optim., 73 (2019), 153-169.  doi: 10.1007/s10898-018-0689-z.  Google Scholar

[5] R. W. CottleJ.-S. Pang and R. E. Stone, The Linear Complementarity Problem, Academic Press, Boston, 1992.  doi: 10.1137/1.9780898719000.  Google Scholar
[6] S.-C. Fang and W. X. Xing, Linear Conic Programming: Theory and Applications, Science Press, Beijing, 2013.   Google Scholar
[7]

M. FukushimaZ.-Q. Luo and P. Tseng, Smoothing functions for second-order-cone complementarity problems, SIAM J. Optim., 12 (2002), 436-460.  doi: 10.1137/S1052623400380365.  Google Scholar

[8]

G. GuH. MansouriM. ZangiabadiY. Q. Bai and C. Roos, Improved full-Newton step $O(nL)$ infeasible interior-point method for linear optimization, J. Optim. Theory Appl., 145 (2010), 271-288.  doi: 10.1007/s10957-009-9634-0.  Google Scholar

[9]

N. Karmarkar, A new polynomial-time algorithm for linear programming, Combinatorica, 4 (1984), 373-395.  doi: 10.1007/BF02579150.  Google Scholar

[10]

M. KojimaS. Mizuno and T. Noma, Limiting behavior of trajectories generated by a continuation method for monotone complementarity problems, Math. Oper. Res., 15 (1990), 662-675.  doi: 10.1287/moor.15.4.662.  Google Scholar

[11]

L. KongN. Xiu and J. Han, The solution set structure of monotone linear complementarity problems over second-order cone, Oper. Res. Lett., 36 (2008), 71-76.  doi: 10.1016/j.orl.2007.03.009.  Google Scholar

[12]

H. LiuX. Yang and C. Liu, A new wide neighborhood primal-dual infeasible-interior-point method for symmetric cone programming, J. Optim. Theory Appl., 158 (2013), 796-815.  doi: 10.1007/s10957-013-0303-y.  Google Scholar

[13]

N. Lu and Z.-H. Huang, A smoothing Newton algorithm for a class of non-monotonic symmetric cone linear complementarity problems, J. Optim. Theory Appl., 161 (2014), 446-464.  doi: 10.1007/s10957-013-0436-z.  Google Scholar

[14]

F. A. Potra, Weighted complementarity problems-a new paradigm for computing equilibria, SIAM J. Optim., 22 (2012), 1634-1654.  doi: 10.1137/110837310.  Google Scholar

[15]

F. A. Potra, Sufficient weighted complementarity problems, Comput. Optim. Appl., 64 (2016), 467-488.  doi: 10.1007/s10589-015-9811-z.  Google Scholar

[16]

L. QiD. Sun and G. Zhou, A new look at smoothing Newton methods for nonlinear complementarity problems and box constrained variational inequalities, Math. Program., 87 (2000), 1-35.  doi: 10.1007/s101079900127.  Google Scholar

[17]

C. Roos, A full-Newton step $O(n)$ infeasible interior-point algorithm for linear optimization, SIAM J. Optim., 16 (2006), 1110-1136. doi: 10.1137/050623917.  Google Scholar

[18]

C. Roos, T. Terlaky and J. -Ph. Vial, Theory and Algorithms for Linear Optimization. An Interior-Point Approach, John Wiley & Sons, Chichester, 1997.  Google Scholar

[19]

J. Tang, A variant nonmonotone smoothing algorithm with improved numerical results for large-scale LWCPs, Comput. Appl. Math., 37 (2018), 3927-3936.  doi: 10.1007/s40314-017-0554-6.  Google Scholar

[20]

G. Q. WangC. J. Yu and K. L. Teo, A full-Newton step feasible interior-point algorithm for $P_{*}(\kappa)$-linear complementarity problems, J. Global Optim., 59 (2014), 81-99.  doi: 10.1007/s10898-013-0090-x.  Google Scholar

[21]

J. WuL. Zhang and Y. Zhang, A smoothing Newton method for mathematical programs governed by second-order cone constrained generalized equations, J. Glob. Optim., 55 (2013), 359-385.  doi: 10.1007/s10898-012-9880-9.  Google Scholar

[22]

Y. XuL. Zhang and J. Zhang, A full-modified-Newton step infeasible interior-point algorithm for linear optimization, J. Ind. Manag. Optim., 12 (2016), 103-116.  doi: 10.3934/jimo.2016.12.103.  Google Scholar

[23]

Y. Ye, Inteior Point Algorithms, Theory and Analysis, John Wiley & Sons, New York, 1997. doi: 10.1002/9781118032701.  Google Scholar

[24]

Y. Ye, A path to the Arrow-Debreu competitive market equilibrium, Math. Program., 111 (2008), 315-348.  doi: 10.1007/s10107-006-0065-5.  Google Scholar

[25]

J. Zhang, A smoothing Newton algorithm for weighted linear complementarity problem, Optim. Lett., 10 (2016), 499-509.  doi: 10.1007/s11590-015-0877-4.  Google Scholar

[26]

L. Zhang and Y. Xu, A full-Newton step interior-point algorithm based on modified Newton direction, Oper. Res. Lett., 39 (2011), 318-322.  doi: 10.1016/j.orl.2011.06.006.  Google Scholar

show all references

References:
[1]

K. M. Anstreicher, Interior-point algorithms for a generalization of linear programming and weighted centring, Optim. Methods Softw., 27 (2012), 605-612.  doi: 10.1080/10556788.2011.644791.  Google Scholar

[2]

Y. BaiP. Ma and J. Zhang, A polynomial-time interior-point method for circular cone programming based on kernel functions, J. Ind. Manag. Optim., 12 (2016), 739-756.  doi: 10.3934/jimo.2016.12.739.  Google Scholar

[3]

J. -S. Chen, SOC Functions and their Applications, Springer, Singapore, 2019. doi: 10.1007/978-981-13-4077-2.  Google Scholar

[4]

X. ChiM. S. Gowda and J. Tao, The weighted horizontal linear complementarity problem on a Euclidean Jordan algebra, J. Global Optim., 73 (2019), 153-169.  doi: 10.1007/s10898-018-0689-z.  Google Scholar

[5] R. W. CottleJ.-S. Pang and R. E. Stone, The Linear Complementarity Problem, Academic Press, Boston, 1992.  doi: 10.1137/1.9780898719000.  Google Scholar
[6] S.-C. Fang and W. X. Xing, Linear Conic Programming: Theory and Applications, Science Press, Beijing, 2013.   Google Scholar
[7]

M. FukushimaZ.-Q. Luo and P. Tseng, Smoothing functions for second-order-cone complementarity problems, SIAM J. Optim., 12 (2002), 436-460.  doi: 10.1137/S1052623400380365.  Google Scholar

[8]

G. GuH. MansouriM. ZangiabadiY. Q. Bai and C. Roos, Improved full-Newton step $O(nL)$ infeasible interior-point method for linear optimization, J. Optim. Theory Appl., 145 (2010), 271-288.  doi: 10.1007/s10957-009-9634-0.  Google Scholar

[9]

N. Karmarkar, A new polynomial-time algorithm for linear programming, Combinatorica, 4 (1984), 373-395.  doi: 10.1007/BF02579150.  Google Scholar

[10]

M. KojimaS. Mizuno and T. Noma, Limiting behavior of trajectories generated by a continuation method for monotone complementarity problems, Math. Oper. Res., 15 (1990), 662-675.  doi: 10.1287/moor.15.4.662.  Google Scholar

[11]

L. KongN. Xiu and J. Han, The solution set structure of monotone linear complementarity problems over second-order cone, Oper. Res. Lett., 36 (2008), 71-76.  doi: 10.1016/j.orl.2007.03.009.  Google Scholar

[12]

H. LiuX. Yang and C. Liu, A new wide neighborhood primal-dual infeasible-interior-point method for symmetric cone programming, J. Optim. Theory Appl., 158 (2013), 796-815.  doi: 10.1007/s10957-013-0303-y.  Google Scholar

[13]

N. Lu and Z.-H. Huang, A smoothing Newton algorithm for a class of non-monotonic symmetric cone linear complementarity problems, J. Optim. Theory Appl., 161 (2014), 446-464.  doi: 10.1007/s10957-013-0436-z.  Google Scholar

[14]

F. A. Potra, Weighted complementarity problems-a new paradigm for computing equilibria, SIAM J. Optim., 22 (2012), 1634-1654.  doi: 10.1137/110837310.  Google Scholar

[15]

F. A. Potra, Sufficient weighted complementarity problems, Comput. Optim. Appl., 64 (2016), 467-488.  doi: 10.1007/s10589-015-9811-z.  Google Scholar

[16]

L. QiD. Sun and G. Zhou, A new look at smoothing Newton methods for nonlinear complementarity problems and box constrained variational inequalities, Math. Program., 87 (2000), 1-35.  doi: 10.1007/s101079900127.  Google Scholar

[17]

C. Roos, A full-Newton step $O(n)$ infeasible interior-point algorithm for linear optimization, SIAM J. Optim., 16 (2006), 1110-1136. doi: 10.1137/050623917.  Google Scholar

[18]

C. Roos, T. Terlaky and J. -Ph. Vial, Theory and Algorithms for Linear Optimization. An Interior-Point Approach, John Wiley & Sons, Chichester, 1997.  Google Scholar

[19]

J. Tang, A variant nonmonotone smoothing algorithm with improved numerical results for large-scale LWCPs, Comput. Appl. Math., 37 (2018), 3927-3936.  doi: 10.1007/s40314-017-0554-6.  Google Scholar

[20]

G. Q. WangC. J. Yu and K. L. Teo, A full-Newton step feasible interior-point algorithm for $P_{*}(\kappa)$-linear complementarity problems, J. Global Optim., 59 (2014), 81-99.  doi: 10.1007/s10898-013-0090-x.  Google Scholar

[21]

J. WuL. Zhang and Y. Zhang, A smoothing Newton method for mathematical programs governed by second-order cone constrained generalized equations, J. Glob. Optim., 55 (2013), 359-385.  doi: 10.1007/s10898-012-9880-9.  Google Scholar

[22]

Y. XuL. Zhang and J. Zhang, A full-modified-Newton step infeasible interior-point algorithm for linear optimization, J. Ind. Manag. Optim., 12 (2016), 103-116.  doi: 10.3934/jimo.2016.12.103.  Google Scholar

[23]

Y. Ye, Inteior Point Algorithms, Theory and Analysis, John Wiley & Sons, New York, 1997. doi: 10.1002/9781118032701.  Google Scholar

[24]

Y. Ye, A path to the Arrow-Debreu competitive market equilibrium, Math. Program., 111 (2008), 315-348.  doi: 10.1007/s10107-006-0065-5.  Google Scholar

[25]

J. Zhang, A smoothing Newton algorithm for weighted linear complementarity problem, Optim. Lett., 10 (2016), 499-509.  doi: 10.1007/s11590-015-0877-4.  Google Scholar

[26]

L. Zhang and Y. Xu, A full-Newton step interior-point algorithm based on modified Newton direction, Oper. Res. Lett., 39 (2011), 318-322.  doi: 10.1016/j.orl.2011.06.006.  Google Scholar

Figure 1.  The value of $ rb: = \|b-Ax\| $
Figure 2.  The value of $ rc:=\|c-A^{T}y-s\| $
Figure 3.  The value of $ rw: = \|\omega(t)-\omega\| $
Figure 4.  The value of $ rv: = \delta(v) $
Table 1.  Numerical results for the special wLCPs
Time(s) Iter $ t $ $ \delta(v) $
0.027 156 4.3155e-05 1.1389e-11
0.032 172 8.8496e-06 1.7788e-13
0.019 109 1.3410e-05 7.6732e-13
0.105 206 3.9157e-06 3.3555e-14
0.084 97 6.7376e-05 1.0484e-11
0.081 118 3.1367e-06 1.9156e-14
0.128 218 2.7493e-05 2.0044e-12
0.096 168 2.1576e-05 4.5414e-12
Time(s) Iter $ t $ $ \delta(v) $
0.027 156 4.3155e-05 1.1389e-11
0.032 172 8.8496e-06 1.7788e-13
0.019 109 1.3410e-05 7.6732e-13
0.105 206 3.9157e-06 3.3555e-14
0.084 97 6.7376e-05 1.0484e-11
0.081 118 3.1367e-06 1.9156e-14
0.128 218 2.7493e-05 2.0044e-12
0.096 168 2.1576e-05 4.5414e-12
[1]

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

[2]

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

[3]

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

[4]

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

[5]

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

[6]

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

[7]

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

[8]

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

[9]

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

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

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

[12]

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

[13]

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

[14]

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

[15]

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

[16]

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

[17]

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

[18]

Peili Li, Xiliang Lu, Yunhai Xiao. Smoothing Newton method for $ \ell^0 $-$ \ell^2 $ regularized linear inverse problem. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2021044

[19]

Fang Zeng, Pablo Suarez, Jiguang Sun. A decomposition method for an interior inverse scattering problem. Inverse Problems & Imaging, 2013, 7 (1) : 291-303. doi: 10.3934/ipi.2013.7.291

[20]

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

2020 Impact Factor: 1.801

Metrics

  • PDF downloads (93)
  • HTML views (220)
  • Cited by (0)

Other articles
by authors

[Back to Top]