Document Zbl 1259.65091

Primal-dual interior-point algorithm for semidefinite optimization based on a new kernel function with trigonometric barrier term. (English) Zbl 1259.65091

Numer. Algorithms 61, No. 4, 659-680 (2012).

The author analyzes large and small-update methods of a primal-dual interior-point algorithm based on a new kernel function with trigonometric barrier term for solving standard semidefinite optimization problems. The default step size of the algorithm is determined, and an upper bound to the decrease of the barrier function during an inner iteration is obtained. The iteration bounds for large and small-update method are established.

Reviewer: Hang Lau (Montréal)

Cited in 28 Documents

MSC:

65K05	Numerical mathematical programming methods
90C22	Semidefinite programming
90C51	Interior-point methods

Keywords:

kernel function; interior-point algorithm; semidefinite optimization; polynomial complexity; primal-dual method

Cite Review PDF

Full Text: DOI

References:

[1]	Bai, Y.Q., El Ghami, M., Roos, C.: A comparative study of kernel functions for primal-dual interior-point algorithms in linear optimization. SIAM J. Optim. 15(1), 101–128 (2004) · Zbl 1077.90038 · doi:10.1137/S1052623403423114
[2]	Bai, Y.Q., Guo, J., Roos, C.: A new kernel function yielding the best known iteration bounds for primal-dual interior-point algorithms. Acta Math. Sin., Engl. Ser. 25(12), 2169–2178 (2009) · Zbl 1184.90099 · doi:10.1007/s10114-009-6457-8
[3]	Bai, Y.Q., Roos, C.: A polynomial-time algorithm for linear optimization based a new simple kernel function. Optim. Methods Softw. 18(6), 631–646 (2003) · Zbl 1097.90031 · doi:10.1080/10556780310001639735
[4]	Bai, Y.Q., Lesaja, G., Roos, C., Wang, G.Q., El Ghami, M.: A class of large-update and small-update primal-dual interior-point algorithms for linear optimization. J. Optim. Theory Appl. 138(3), 341–359 (2008) · Zbl 1165.90564 · doi:10.1007/s10957-008-9389-z
[5]	Bai, Y.Q., El Ghami, M., Roos, C.: A new efficient large-update primal-dual interior-point method based on a finite barrier. SIAM J. Optim. 13(3), 766–782 (2003) · Zbl 1036.90051 · doi:10.1137/S1052623401398132
[6]	Bai, Y.Q., El Ghami, M., Roos, C.: Kernel function based algorithms for semidefinite optimization. Int. J. RAIRO-Oper. Res. 43(2), 189–199 (2009) · Zbl 1170.90455 · doi:10.1051/ro/2009011
[7]	De Klerk, E.: Aspects of Semidefinite Programming. Applied Optimization, vol. 65. Kluwer Academic, Dordrecht (2002) · Zbl 0991.90098
[8]	El Ghami, M., Guennoun, Z.A., Bouali, S., Steihaug, T.: Interior-point methods for linear optimization based on a kernel function with trigonmetric barrier term. J. Comput. Appl. Math. (2011). doi: 10.1016/j.cam.2011.05.036 · Zbl 1242.90292
[9]	El Ghami, M., Steihaug, T., Roos, C.: A generic primal-dual IPMS for semidefinite based on kernel functions. Optim. Methods Softw. 25(3), 387–403 (2010) · Zbl 1220.90081 · doi:10.1080/10556780903239048
[10]	Helmberg, C.: Simedefinite programming for combinatorial optimization. Technical Report 00-34, Konrad-Zuse-Zentrum für Informationstechink Berlin, Takustrabe 7, D-14195 Berlin (2000)
[11]	Horn, R.A., Johnson, C.R.: Topics in Matrix Analysis. Cambridge University Press, Cambridge (1991) · Zbl 0729.15001
[12]	Karmarkar, N.K.: A new polynomial-time algorithm for linear programming. Combinatorica 4, 375–395 (1984) · Zbl 0557.90065 · doi:10.1007/BF02579150
[13]	Kojima, M., Shida, M., Hara, S.: Interior point methods for the monotone semidefinite linear complementarity problem in symmetric matrices. SIAM J. Optim. 7, 86–125 (1997) · Zbl 0872.90098 · doi:10.1137/S1052623494269035
[14]	Mitrinović, D.S.: Analytic Inequalities. Springer, New York (1970) · Zbl 0199.38101
[15]	Nesterov, Y.E., Todd, M.J.: Self-scaled barriers and interior-point methods for convex programming. Math. Oper. Res. 22(1), 1–42 (1997) · Zbl 0871.90064 · doi:10.1287/moor.22.1.1
[16]	Nesterov, Y.E., Nemirovskii, A.S.: Interior point polynomial algorithms in convex programming. In: SIAM Stud. Appl. Math., vol. 13. SIAM, Philadelphia (1994) · Zbl 0824.90112
[17]	Peng, J., Roos, C., Terlaky, T.: Self-regular functions and new search directions for linear and semidefinite optimization. Math. Program. 93(1), 129–171 (2002) · Zbl 1007.90037 · doi:10.1007/s101070200296
[18]	Peng, J., Roos, C., Terlaky, T.: Self-Regularity: A New Paradigm for Primal-Dual Interior-Point Algorithms. Princeton University Press, Princeton (2002) · Zbl 1136.90045
[19]	Peng, J., Roos, C., Terlaky, T.: A new class of polynomial primal-dual methods for linear and semidefinite optimization. Eur. J. Oper. Res. 143, 234–256 (2002) · Zbl 1058.90037 · doi:10.1016/S0377-2217(02)00275-8
[20]	Qian, Z.G., Bai, Y.Q., Wang, G.Q.: Complexity analysis of interior-point algorithm based on a new kernel function for semidefinite optimization. J. Shanghai Univ. (Engl Ed). 12(5), 388–394 (2008) · Zbl 1174.90737 · doi:10.1007/s11741-008-0503-2
[21]	Roos, C., Terlaky, T., Vial, J.-Ph.: Theory and Algorithms for Linear Optimization. An Interior-Point Approach. Wiley, Chichester (1997) · Zbl 0954.65041
[22]	Todd, M.J.: A study of search directions in primal-dual interior-point methods for semidefinite programming. Optim. Methods Softw. 11, 1–46 (1999) · Zbl 0971.90109 · doi:10.1080/10556789908805745
[23]	Wang, G.Q., Bai, Y.Q.: Primal-dual interior-point algorithm for convex quadratic semi-definite optimization. Nonlinear Anal. 71, 3389–3402 (2009) · Zbl 1179.65074 · doi:10.1016/j.na.2009.01.241
[24]	Wang, G.Q., Bai, Y.Q., Roos, C.: Primal-dual interior-point algorithms for semidefinite optimization based on a simple kernel function. J. Math. Model. Algorithms 4(4), 409–433 (2005) · Zbl 1111.90083 · doi:10.1007/s10852-005-3561-3
[25]	Wolkowicz, H., Saigal, R., Vandenberghe, L.: Handbook of Semidefinite Programming, Theory, Algorithm, and Applications. Kluwer Academic, Dordrecht (2000) · Zbl 0951.90001

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.