A Full Nesterov-Todd Step Infeasible Interior-point Method for Symmetric Optimization in the Wider Neighborhood of the Central Path
AbstractIn this paper, an improved Interior-Point Method (IPM) for solving symmetric optimization problems is presented. Symmetric optimization (SO) problems are linear optimization problems over symmetric cones. In particular, the method can be efficiently applied to an important instance of SO, a Controlled Tabular Adjustment (CTA) problem which is a method used for Statistical Disclosure Limitation (SDL) of tabular data. The presented method is a full Nesterov-Todd step infeasible IPM for SO. The algorithm converges to ε-approximate solution from any starting point whether feasible or infeasible. Each iteration consists of the feasibility step and several centering steps, however, the iterates are obtained in the wider neighborhood of the central path in comparison to the similar algorithms of this type which is the main improvement of the method. However, the currently best known iteration bound known for infeasible short-step methods is still achieved.
Anjos M.F., Lasserre, J.B.: Handbook on Semidefinite, Conic and Polynomial Optimization: Theory, Algorithms, Software and Applications. International Series in Operational Research and Management Science. Volume 166, Springer, New York, USA (2012)
Castro, J.: Minimum-distance controlled perturbation methods for large-scale tabular data protection. European J. Oper. Res., 171, 39-52 (2006)
Castro, J., Gonzalez, J.A.: Assessing the information loss of controlled adjustment methods in two-way tables. Privacy in Statistical Databases 2014, LNCS, 8744, 79-88 (2014)
Castro, J., Gonzalez, J.A.: A fast CTA method without complicating binary decisions. Documents of the Joint UNECE/ Eurostat Work Session on Statistical Data Confidentiality, Statistics Canada, Ottawa, 1-7 (2013)
Castro, J., Gonzalez, J.A.: A multiobjective LP approach for controlled tabular adjustment in statistical disclosure control. Working paper, Department of Statistics and Operations Research, Universitat Politecnica de Catalunya (2014)
Dandekar, R. A., Cox, L.H.: Synthetic tabular Data: an alternative to complementary cell suppression. Manuscript, Energy Information Administration, U.S. (2002)
Faraut, J., Koranyi, A.: Analysis on Symmetric Cones, Oxford University Press, New York, USA (1994)
Faybusovich L.: Euclidean Jordan algebras and interior-point algorithms. Positivity 1, 331-35 (1997)
Faybusovich L.: A Jordan-algebraic approach to potential-reduction algorithms. Math. Z. 239(1), 117-129 (2002)
Gu, G., Mansouri, H., Zangiabadi, M., Bai, Y.Q., Roos, C.: Improved full-Newton step O(nL) infeasible interior-point method for linear optimization. J. Optim. Theory Appl. 145(2), 271-288 (2010)
Gu, G., Zangiabadi, M., Roos, C.: Full Nesterov-Todd step infeasible interior-point method for symmetric optimization. European J. Oper. Res. 214(3), 473-484 (2011)
Guler, O.: Barrier functions in interior-point methods. Math. Oper. Res. 21(4), 860-885 (1996)
Lesaja, G., Castro, J., Oganian, A.: Second Order Cone formulation of Continuous CTA Model. Lecture Notes in Computer Science 9867, Springer., 41-53, (2016)
Liu, C.H., Liu, H.W., Liu, X.Z.: Polynomial convergence of second-order mehrotra type predictor-corrector algorithms over symmetric cones. J. Optim. Theory Appl. 154(3), 949-965 (2012)
Liu H.W., Yang X.M., Liu C.H.: A new wide neighborhood primal-dual infeasible interior-point method for symmetric cone programming, J. Optim. Theory Appl. 158(3), 796-815 (2013)
Muramatsu, M.: On a commutative class of search directions for linear programming over symmetric cones. J. Optim. Theory Appl. 112(3), 595-625 (2002)
Nesterov Y.E., Todd M.J.: Self-scaled barriers and interior-point methods for convex programming. Math. Oper. Res. 22(1), 1-42 (1997)
Nesterov Y.E., Todd M.J.: Primal-dual interior-point methods for self-scaled cones. SIAM J. Optim. 8(2), 324-364 (1998)
Rangarajan, B.K.: Polynomial convergence of infeasible-interior-point methods over symmetric cones. SIAM J. Optim. 16(4), 1211-1229 (2006)
Roos, C.: A full-Newton step O(n) infeasible interior-point algorithm for linear optimization. SIAM J. Optim. 16(4), 1110-1136 (2006)
Roos C., Terlaky T., Vial J.-Ph.: Theory and Algorithms for Linear Optimization: An Interior-Point Approach. John Wiley & Sons, Chichester, UK (1997)
Schmieta, S.H., Alizadeh, F.: Extension of primal-dual interior-point algorithms to symmetric cones. Math. Program. 96(3), 409-438 (2003)
Vieira, M.V.C.: Jordan algebraic approach to symmetric optimization. Ph.D thesis, Electrical Engineering, Mathematics and Computer Science, Delft University of Technology, The Netherlands (2007)
Wang, G.Q., Bai, Y.Q.: A new full Nesterov-Todd step primal-dual path-following interior-point algorithm for symmetric optimization. J. Optim. Theory Appl. 154(3), 966-985 (2012)
Wang, G.Q., Kong, L.C., Tao, J.Y., Lesaja G.: Improved complexity analysis of full Nesterov-Todd step feasible interior-point method for symmetric optimization. J. Optim. Theory Appl. 166(2), 588-604, (2015)
Wright, S.J.: Primal-Dual Interior-Point Methods. SIAM, Philadelphia (1996)
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).