A Full Nesterov-Todd Step Infeasible Interior-point Method for Symmetric Optimization in the Wider Neighborhood of the Central Path

Lesaja Goran; G.Q.  Wang; A. Oganian

doi:10.19139/soic-2310-5070-1175

Lesaja Goran Georgia Southern University, USA
G.Q. Wang Shanghai University of Engineering Science, China
A. Oganian National Center for Health Statistics, 3311 Toledo Rd, Hyattsville, MD, 20782, USA

DOI: https://doi.org/10.19139/soic-2310-5070-1175

Keywords: Interior-point methods; Euclidean Jordan algebras; Linear optimization over symmetric cones; Full Nesterov-Todd step; Polynomial complexity, Control tabular adjustment problem, Statistical Disclosure Limitation, Tabular data

Abstract

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

References

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)