A full-Newton step infeasible interior point algorithm and its parameters analysis

Lipu Zhang; Yinghong Xu

doi:10.3934/jimo.2023148

Article Contents

2024, Volume 20, Issue 5: 1916-1933. Doi: 10.3934/jimo.2023148

This issue Previous Article Optimal dividend-penalty policies for a piecewise-deterministic compound Poisson risk model with transaction costs Next Article Convergence properties of stochastic proximal subgradient method in solving a class of composite optimization problems with cardinality regularizer

A full-Newton step infeasible interior point algorithm and its parameters analysis

Lipu Zhang^{1, 2, ,} and
Yinghong Xu^3,

1.
College of Media Engineering, Communication University of Zhejiang, Hangzhou 310018, China
2.
Key Lab of Film and TV Media Technology of Zhejiang Province, Hangzhou 310018, China
3.
Department of Mathematics, Zhejiang Sci-Tech University, Hangzhou 310018, China

^*Corresponding author: Lipu Zhang
^*Corresponding author: Lipu Zhang

Received: June 2023

Revised: October 2023

Early access: November 2023

Published: May 2024

This work is supported by the National Natural Science Foundation of China under the grant No. 11501513, 11871435, the Natural Science Foundation of Zhejiang Province under the grant No. LY18A010030.

Abstract / Introduction Full Text(HTML) Figure(0) / Table(6) Related Papers Cited by

Abstract

This article utilizes a simple univariate function to formulate the search direction for the full-Newton step and constructs a metric to estimate the distance between the iterative point and the central path. By doing so, it designs an infeasible interior point algorithm for linear optimization problems that employs only one kind of search step. As demonstrated in the complexity analysis, this straightforward univariate function proves to be highly beneficial in analyzing the algorithm. Additionally, we discuss the update parameters and threshold parameters of the algorithm, present three methods for parameter updates, and compare the efficiency of these three methods using numerical examples.

Keywords:

Mathematics Subject Classification: Primary: 90C05; Secondary: 90C51.

Citation:

Full Text(HTML)

Table 1. The comparison of kernel functions, metrics, and factors before the complexity results

The algorithm	Kernel Function	Metric	Complexity Factor
[16] with centality step	$ \frac{t^2-1}{2}-\log{t} $	$ \frac{1}{2}\\|v^{-1}-v\\| $	$ 16\sqrt{2}n $
[14]	$ \begin{cases} \frac{t^2 - 1}{2} - \frac{t^{1-p}-1}{p-1}&\text{if } p \in [0,1)\\\frac{t^2 - 1}{2} - \log(t)&\text{if } p = 1\end{cases} $	$ \frac{1}{2}\\|v^{-p}-v\\| $	$ 18.5\sqrt{2}n $
[7]	$ \frac{t^2-1}{2}-(1-\theta)\log{t} $	$ \frac{1}{2}\\|v^{-1}-v\\| $	$ 20n $
[21] with centrality step	$ (1-t)^2 $	$ \\|e-v\\| $	$ 36n $
[17] no centrality step	$ \frac{t^2-1}{2}-\log{t} $	$ \frac{1}{2}\\|v^{-1}-v\\| $	$ 8n $
[11]	$ \frac{\left(t-1\right)^2}{2}+\frac{\left(t-1\right)^2}{2t}+\frac{1}{8}{tan}^2\left(h\left(t\right)\right), h\left(t\right)=\frac{\pi\left(1-t\right)}{4t+2} $	$ \frac{1}{2}\\|v^{-1}-v\\| $	$ 22n $
[9]	$ \frac{t^2-1}{2}-\int_{1}^{t}{\frac{sinh(1)}{2sinh(v)}dy} $	$ \\|\frac{sinh(e)}{2sinh(v)}-\frac{v}{2}\\| $	$ 25\sqrt{2}n $

| Show Table

DownLoad: CSV

Table 2. Numerical results for Example 1 with small updates

iter	$ \theta $	$ \Psi_s(v) $	$ \mu $	gap
1	2.2222e-002	0.0000e+000	9.7778e-001	3.0000e+000
20	2.2222e-002	3.7527e-004	6.3797e-001	2.0014e+000
40	2.2222e-002	3.7585e-004	4.0701e-001	1.2769e+000
60	2.2222e-002	3.7688e-004	2.5966e-001	8.1465e-001
80	2.2222e-002	3.7761e-004	1.6566e-001	5.1974e-001
100	2.2222e-002	3.7805e-004	1.0569e-001	3.3158e-001
120	2.2222e-002	3.7831e-004	6.7425e-002	2.1154e-001
140	2.2222e-002	3.7847e-004	4.3015e-002	1.3496e-001
160	2.2222e-002	3.7857e-004	2.7443e-002	8.6101e-002
180	2.2222e-002	3.7863e-004	1.7508e-002	5.4931e-002
200	2.2222e-002	3.7867e-004	1.1169e-002	3.5044e-002
220	2.2222e-002	3.7870e-004	7.1258e-003	2.2357e-002
240	2.2222e-002	3.7871e-004	4.5461e-003	1.4263e-002
255	2.2222e-002	3.7872e-004	3.2452e-003	1.0182e-002

| Show Table

DownLoad: CSV

Table 3. Numerical results for Example 1 with adaptive updates

iter	$ \theta $	$ \Psi_s(v) $	$ \mu $	gap
1	1.1031e-001	0.0000e+000	8.8969e-001	3.0000e+000
10	8.9401e-002	6.3645e-003	3.8483e-001	1.3873e+000
20	8.9242e-002	6.4622e-003	1.5100e-001	5.4464e-001
30	8.9174e-002	6.5037e-003	5.9323e-002	2.1401e-001
40	8.9150e-002	6.5186e-003	2.3316e-002	8.4120e-002
50	8.9141e-002	6.5242e-003	9.1652e-003	3.3068e-002
60	8.9138e-002	6.5264e-003	3.6030e-003	1.3000e-002
62	8.9137e-002	6.5266e-003	2.9893e-003	1.0785e-002

| Show Table

DownLoad: CSV

Table 4. Numerical results for Example 1 with large updates

iter	$ \theta $	$ \Psi_s(v) $	$ \mu $	gap
1	2.5000e-001	0.0000e+000	7.5000e-001	3.0000e+000
5	2.5000e-001	5.6353e-002	2.3730e-001	1.2267e+000
10	2.5000e-001	6.0065e-002	5.6314e-002	2.9351e-001
15	2.5000e-001	6.0957e-002	1.3363e-002	6.9779e-002
20	2.5000e-001	6.1162e-002	3.1712e-003	1.6566e-002
21	2.5000e-001	6.1177e-002	2.3784e-003	1.2425e-002

| Show Table

DownLoad: CSV

Table 5. Numerical results for Example 2

density	$ m\times n $	iter$ _{ \rm{small}} $	iter$ _{ \rm{adaptiv}e} $	iter$ _{ \rm{large}} $
0.2	$ 10\times 100 $	19368	3260	57
0.2	$ 20\times 200 $	44089	6710	65
0.2	$ 30\times 300 $	65383	10939	66
0.2	$ 40\times 600 $	145394	23739	72
0.2	$ 100\times 1000 $	262429	42302	81
0.7	$ 40\times 200 $	46139	7970	70
0.7	$ 60\times 400 $	97467	16368	75
0.7	$ 80\times 600 $	156075	25291	79
0.7	$ 100\times 800 $	214607	34641	82
0.7	$ 150\times 1000 $	282358	45695	87

| Show Table

DownLoad: CSV

Table 6. Numerical results for Example 3

Problems	$ m\times n $	iter$ _{ \rm{small}} $	iter$ _{ \rm{adaptive}} $	iter$ _{ \rm{large}} $
ADLITTLE	$ 56\times 138 $	53274	9008	91
AFIRO	$ 27\times 51 $	16030	2824	74
BLEND	$ 74\times 114 $	30295	5156	63
E226	$ 223\times 472 $	179609	29487	90
SC50A	$ 50\times 78 $	22495	3885	68
SCAGR7	$ 129\times 185 $	76312	12797	97
VTP-BASE	$ 198\times 347 $	140745	23241	95

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	S. Asadi and H. Mansouri, Polynomial interior-point algorithm for P * (κ) horizontal linear complementarity problems, Numer. Algorithms, 63 (2013), 385-398. doi: 10.1007/s11075-012-9628-0.
[2]	Y. Bai, C. Roos and M. El Ghami, A primal-dual interior-point method for linear optimization based on a new proximity function, Optim. Methods Softw., 6 (2002), 985-1008. doi: 10.1080/1055678021000090024.
[3]	Y. Bai, M. El Ghami and C. Roos, A New efficient large-update primal-dual interior-point method based on a finite barrier, SIAM J. Optim., 13 2002, 766-782. doi: 10.1137/S1052623401398132.
[4]	Y. Bai, M. Ghami and C. Roos, A comparative study of kernel functions for primal-dual interior-point algorithms in linear optimization, SIAM J. Optim., 15 (2004), 101-128. doi: 10.1137/S1052623403423114.
[5]	X. Chi, Z. Wan and Z. Hao, A full-modified-Newton step O(n) infeasible interior-point method for the special weighted linear complementarity problem, J. Ind. Manag. Optim., 4 (2022), 2579-2598. doi: 10.3934/jimo.2021082.
[6]	M. Ferris, O. Mangasarian and S. Wright, Linear Programming with MATLAB, Society for Industrial and Applied Mathematics, 2007. doi: 10.1137/1.9780898718775.
[7]	G. Gu, H. Mansouri, M. Zangiabadi, et al., 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.
[8]	G. Gu, M. Zangiabadi and C. Roos, Full Nesterov-Todd step infeasible interior-point method for symmetric optimization, Eur. J. Oper. Res., 3 (2011), 473-484. doi: 10.1016/j.ejor.2011.02.022.
[9]	S. Guerdouh, W. Chikouche and B. Kheirfam, A full-Newton step infeasible interior-point algorithm based on a kernel function with a new barrier term, J. Appl. Math. Comput., 69 (2023), 2935-2953. doi: 10.1007/s12190-023-01858-8.
[10]	L. Guerra, A class of new search directions for full-NT step feasible interior point method in semidefinite optimization, RAIRO-Oper. Res., 56 (2022), 3955-3971. doi: 10.1051/ro/2022192.
[11]	B. Kheirfam and M. Haghighi, A full-Newton step infeasible interior-point method based on a trigonometric kernel function without centering steps, Numer. Algorithms, 85 (2020), 59-75. doi: 10.1007/s11075-019-00802-x.
[12]	B. Kheirfam and N. Mahdavi-Amiri, An infeasible interior-point algorithm based on modified Nesterov and Todd directions for symmetric linear complementarity problem, Optimization, 64 (2015), 1577-1591. doi: 10.1080/02331934.2013.869877.
[13]	Z. Liu and W. Sun, A full-NT-step infeasible interior-point algorithm for SDP based on kernel functions, Appl. Math. Comput., 217 (2011), 4990-4999. doi: 10.1016/j.amc.2010.11.049.
[14]	Z. Liu, W. Sun and F. Tian, A full-Newton step infeasible interior-point algorithm for linear programming based on a kernel function, Appl. Math. Opt., 60 (2009), 237-251. doi: 10.1007/s00245-009-9069-x.
[15]	H. Mansouri, Full-Newton step infeasible interior-point algorithm for SDO problems, Kybernetika, 48 (2012), 907-923.
[16]	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.
[17]	C. Roos, An improved and simplified full-newton step O(n) infeasible interior-point method for linear optimization, SIAM J. Optim., 25 (2015), 102-114. doi: 10.1137/140975462.
[18]	C. Roos, T. Terlaky and J.-P. Vial, Interior Point Methods for Linear Optimization, Springer, 2006.
[19]	G. Wang, Y. Bai and C. Roos, Primal-dual interior-point algorithms for semidefinite optimization based on a simple kernel function, J. Math. Model Algorithm, 4 (2005), 409-433. doi: 10.1007/s10852-005-3561-3.
[20]	L. Zhang, Y. Bai and Y. Xu, A full-Newton step infeasible interior-point algorithm for monotone LCP based on a locally-kernel function, Numer. Algorithms, 61 (2012), 57-81. doi: 10.1007/s11075-011-9530-1.
[21]	L. Zhang and Y. Xu, A new infeasible interior-point algorithm with full step for linear optimization based on a simple function, Int. J. Comput. Math., 88 (2011), 3163-3185. doi: 10.1080/00207160.2011.597503.