A large-update primal-dual interior-point algorithm for second-order cone optimization based on a new proximity function. (English) Zbl 1397.90399
Summary: In this paper, we propose a large-update primal-dual interior-point algorithm for second-order cone optimization (SOCO) based on a class of kernel functions consisting of a trigonometric barrier term. The algorithm starts from a strictly feasible point and generates a sequence of points converging to an optimal solution of the problem. Using a simple analysis, we show that the algorithm has \(O(\sqrt{N}\log N \log \frac{N}{\epsilon})\) worst case iteration complexity for large-update primal-dual interior point methods which coincides with the so far best-known iteration bound for SOCO.
Keywords:
second-order cone optimization problem; primal-dual interior-point methods; kernel functionReferences:
| [1] | DOI: 10.1137/1.9781611970791 · doi:10.1137/1.9781611970791 |
| [2] | DOI: 10.1016/S0252-9602(06)60048-9 · Zbl 1092.90034 · doi:10.1016/S0252-9602(06)60048-9 |
| [3] | DOI: 10.1007/978-1-4613-3449-1_6 · doi:10.1007/978-1-4613-3449-1_6 |
| [4] | DOI: 10.1007/s10107-002-0349-3 · Zbl 1030.90137 · doi:10.1007/s10107-002-0349-3 |
| [5] | DOI: 10.1080/1055678021000045123 · Zbl 1032.90021 · doi:10.1080/1055678021000045123 |
| [6] | DOI: 10.1080/10556789908805766 · Zbl 0973.90526 · doi:10.1080/10556789908805766 |
| [7] | Tsuchiya T. A polynomial primal-dual path-following algorithm for second-order cone programming. Tokyo, Japan: The Institute of Statistical Mathematics; 1997. (Research Memorandum no. 649 ). |
| [8] | DOI: 10.1080/10556789908805750 · Zbl 0957.90129 · doi:10.1080/10556789908805750 |
| [9] | DOI: 10.1137/S1052623495290209 · Zbl 0922.90110 · doi:10.1137/S1052623495290209 |
| [10] | DOI: 10.1287/moor.23.4.769 · Zbl 0977.90052 · doi:10.1287/moor.23.4.769 |
| [11] | DOI: 10.1016/S0167-6377(99)00016-4 · Zbl 0941.90053 · doi:10.1016/S0167-6377(99)00016-4 |
| [12] | DOI: 10.1137/S0895479896298130 · Zbl 0891.65039 · doi:10.1137/S0895479896298130 |
| [13] | DOI: 10.1016/S0024-3795(98)10032-0 · Zbl 0946.90050 · doi:10.1016/S0024-3795(98)10032-0 |
| [14] | Wolkowicz H, Handbook of semidefinite programming. Theory, algorithms, and applications. International Series in Operations Research & Management Science 27 (2000) · Zbl 0951.90001 |
| [15] | Peng J, Self-regularity: a new paradigm for primal–dual interior-point algorithms (2002) · Zbl 1136.90045 |
| [16] | DOI: 10.1137/S1052623403423114 · Zbl 1077.90038 · doi:10.1137/S1052623403423114 |
| [17] | DOI: 10.1016/j.na.2008.07.016 · Zbl 1190.90275 · doi:10.1016/j.na.2008.07.016 |
| [18] | El Ghami M, Optim. Theory Decis. Mak. Oper. Res. Appl 31 pp 331– (2013) |
| [19] | Fathi-Hafshejani S, J. Appl. Math. Comput 48 pp 11– (2015) |
| [20] | DOI: 10.1007/s11075-012-9557-y · Zbl 1259.65091 · doi:10.1007/s11075-012-9557-y |
| [21] | DOI: 10.1142/S0217595909002250 · Zbl 1176.90453 · doi:10.1142/S0217595909002250 |
| [22] | DOI: 10.1016/j.cam.2013.04.039 · Zbl 1291.90313 · doi:10.1016/j.cam.2013.04.039 |
| [23] | DOI: 10.1007/s11075-013-9772-1 · Zbl 1300.65042 · doi:10.1007/s11075-013-9772-1 |
| [24] | Bai YQ, Appl. Math. Mech 23 pp 2027– (2007) |
| [25] | DOI: 10.1016/S0252-9602(08)60058-2 · Zbl 1174.90009 · doi:10.1016/S0252-9602(08)60058-2 |
| [26] | DOI: 10.1007/s10483-011-1435-x · Zbl 1220.90093 · doi:10.1007/s10483-011-1435-x |
| [27] | DOI: 10.1137/S105262349325771X · Zbl 0856.90075 · doi:10.1137/S105262349325771X |
| [28] | DOI: 10.1016/j.cam.2011.05.036 · Zbl 1242.90292 · doi:10.1016/j.cam.2011.05.036 |
| [29] | Adler I, Alizadeh F. Primal-dual interior point algorithms for convex quadratically constrained and semidefinite optimization problems. Brunswick (NJ): Rutger center for Operations Research; 1995. (Technical Report PRR,111-95). |
| [30] | DOI: 10.1016/S0377-0427(97)00153-2 · Zbl 0889.65066 · doi:10.1016/S0377-0427(97)00153-2 |
| [31] | DOI: 10.1287/moor.26.3.543.10582 · Zbl 1073.90572 · doi:10.1287/moor.26.3.543.10582 |
| [32] | DOI: 10.1007/s10957-013-0278-8 · Zbl 1274.90496 · doi:10.1007/s10957-013-0278-8 |
| [33] | Roos C, Theory and algorithms for linear optimization: an interior point approach (2005) |
| [34] | DOI: 10.1137/S1052623401398132 · Zbl 1036.90051 · doi:10.1137/S1052623401398132 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
