Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Phương Pháp Điểm Nội Đối Với Việc Hoàn Thành Xấp Xỉ Dương Bán Định
Tóm tắt
Cho một ma trận trọng số không âm, đối xứng H, chúng tôi nghiên cứu vấn đề tìm một ma trận Hermitian, dương bán định gần nhất với một ma trận Hermitian cho trước, A, theo trọng số H. Điều này mở rộng khái niệm về các bài toán hoàn thành ma trận chính xác ở chỗ, H
ij
=0 tương ứng với phần tử A
ij
không xác định (tự do), trong khi H
ij
lớn về giá trị tuyệt đối tương ứng với phần tử A
ij
được xác định xấp xỉ (cố định). Chúng tôi trình bày các điều kiện tối ưu, lý thuyết đối ngẫu và hai thuật toán điểm trong nguyên thủy-đối ngẫu. Do các yếu tố thưa thớt, thuật toán 'bước đối ngẫu trước' hiệu quả hơn cho một số lượng lớn các phần tử tự do, trong khi thuật toán 'bước nguyên thủy trước' hiệu quả hơn cho một số lượng lớn các phần tử cố định. Bao gồm có các bài kiểm tra số học minh họa hiệu suất và độ bền của các thuật toán.
Từ khóa
#ma trận dương bán định #ma trận Hermitian #thuật toán tối ưu #lý thuyết đối ngẫu #phương pháp điểm trong.Tài liệu tham khảo
F. Alizadeh, J.-P.A. Haeberly, and M.L. Overton, “Primal-dual interior-point methods for semidefinite programming: convergence rates, stability and numerical results,” Technical Report, Courant Institute of Mathematical Sciences, 1996, NYU Computer Science Dept. Technical Report 721.
W.W. Barrett, C.R. Johnson, and R. Loewy, “The real positive definite completion problem: cycle completability,” Memoirs of the American Mathematical Society, p. 71, 1996.
J.M. Borwein and H. Wolkowicz, “A simple constraint qualification in infinite dimensional programming,” Mathematical Programming, vol. 35, pp. 83-96, 1986.
J.M. Borwein and A. Lewis, “Partially finite convex programming, Part I, duality theory,” Mathematical Programming, vol. 57, pp. 15-48, 1992.
S. Boyd, L. El Ghaoui, E. Feron, and V. Balakrishnan, “Linear matrix inequalities in system and control theory,” Studies in Applied Mathematics, SIAM: Philadelphia, PA, vol. 15, June 1994.
H. Dym and I. Gohberg, “Extensions of band matrices with band inverses,” Linear Algebra and Its Applications, vol. 36, pp. 1-24, 1981.
W. Glunt, T. Hayden, C.R. Johnson, and P. Tarazaga, “Maximum determinant completions,” Technical Report, Dept. of Mathematics, College of William and Mary, Williamsburg, VA, 1994.
B. Grone, C. Johnson, E. Marques De Sa, and H. Wolkowicz, “Positive definite completions of partial Hermitian matrices,” Linear Algebra and Its Applications, vol. 58, pp. 109-124, 1984.
C. Helmberg, F. Rendl, R.J. Vanderbei, and H. Wolkowicz, “An interior point method for semidefinite programming,” SIAM Journal on Optimization, pp. 342-361, 1996. URL: ftp://orion.uwaterloo.ca/pub/henry/reports/sdp.ps.gz.
R.A. Horn and C.R. Johnson, Matrix Analysis, Cambridge University Press: New York, 1985.
C.R. Johnson and B. Kroschel, “Principal submatrices, geometric multiplicities, and structured eigenvectors,” SIAM Journal on Matrix Analysis and Applications, vol. 16, pp. 1004-1012, 1995.
C.R. Johnson and P. Tarazaga, “Approximate semidefinite matrices in a subspace,” Technical Report, Dept. of Mathematics, College of William and Mary, Williamsburg, VA, 1995, to appear in SIMAX.
M. Kojima, M. Shida, and S. Shindoh, “Reduction of monotone linear complementarity problems over cones to linear programs over cones,” Technical Report, Dept. of Information Sciences, Tokyo Institute of Technology, Tokyo, Japan, 1995.
M. Kojima, S. Shindoh, and S. Hara, “Interior-point methods for the monotone semidefinite linear complementarity problem in symmetric matrices,” SIAM J. Optim., vol. 7, no.1, pp. 86-125, 1997.
S. Kruk, M. Muramatsu, F. Rendl, R.J. Vanderbei, and H. Wolkowicz, “The Gauss-Newton direction in linear and semidefinite programming,” Technical Report in progress, University of Waterloo, Waterloo, Canada, 1997.
D.G. Luenberger, Optimization by Vector Space Methods, John Wiley, 1969.
J.R. Magnus and H. Neudecker, Matrix Differential Calculus, Wiley: New York, NY, 1988.
C.A. Micchelli, P.W. Smith, J. Swetits, and J.D.Ward, “Constrained l p approximation,” Journal of Constructive Approximation, vol. 1, pp. 93-102, 1985.
S. Mizuno, M.J. Todd, and Y. Ye, “On adaptive-step primal-dual interior-point algorithms for linear programming,” Mathematics of Operations Research, vol. 18, no.4, pp. 964-981, 1994.
J.J. Moreau, “Décomposition orthogonale d'un espace hilbertien selon deux co{ie190-01}es mutuellement polaires,” C.R. Acad. Sci. Paris, vol. 255, pp. 238-240, 1962.
Y.E. Nesterov and A.S. Nemirovsky, Interior Point Polynomial Algorithms in Convex Programming: Theory and Algorithms, SIAM Publications: SIAM, Philadelphia, USA, 1994.
M.L. Overton, “Large-scale optimization of eigenvalues,” SIAM J. Optimization, vol. 2, pp. 88-120, 1992.
P.W. Smith and H. Wolkowicz, “A nonlinear equation for linear programming,” Mathematical Programming, vol. 34, pp. 235-238, 1986.