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

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

[3]

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

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

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

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

[9]

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

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

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

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

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

[14]

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

[15]

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

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

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

[18]

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

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

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

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

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

[23]

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

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

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

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

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.

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

[3]

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

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

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

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

[9]

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

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

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

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

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

[14]

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

[15]

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

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

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

[18]

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

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

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

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

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

[23]

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

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

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

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

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 and 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 and 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 and 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 and 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 and Optimization, 2015, 5 (1) : 37-46. doi: 10.3934/naco.2015.5.37

[6]

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

[7]

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

[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 and Optimization, 2015, 5 (2) : 101-113. doi: 10.3934/naco.2015.5.101

[9]

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

[10]

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

[11]

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

[12]

Behrouz Kheirfam. A weighted-path-following method for symmetric cone linear complementarity problems. Numerical Algebra, Control and Optimization, 2014, 4 (2) : 141-150. doi: 10.3934/naco.2014.4.141

[13]

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

[14]

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 and Management Optimization, 2011, 7 (1) : 53-66. doi: 10.3934/jimo.2011.7.53

[15]

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

[16]

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

[17]

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

[18]

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

[19]

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

[20]

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

2020 Impact Factor: 1.801

Metrics

  • PDF downloads (426)
  • HTML views (474)
  • Cited by (0)

Other articles
by authors

[Back to Top]