Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Phương pháp nội điểm điều hòa sơ cấp - đối cấp cho các chương trình bậc hai lồi
Tóm tắt
Các phương pháp nội điểm dưới dạng tăng cường cho lập trình tuyến tính và bậc hai lồi yêu cầu giải một chuỗi các hệ phương trình tuyến tính đối xứng không xác định, được sử dụng để suy diễn các hướng tìm kiếm. Thường thì cần có các biện pháp bảo vệ để xử lý các biến tự do hoặc Jacobian thiếu hạng. Chúng tôi đề xuất một khung nhất quán và lý do lý thuyết đi kèm để điều hòa các hệ phương trình tuyến tính này. Cách tiếp cận của chúng tôi có thể được hiểu là một sự điều hòa điểm gần đồng thời của các vấn đề sơ cấp và đối cấp. Việc điều hòa được gọi là chính xác để nhấn mạnh rằng, mặc dù các vấn đề đã được điều hòa, thuật toán khôi phục được một nghiệm của bài toán gốc, với các giá trị phù hợp của các tham số điều hòa.
Từ khóa
#phương pháp nội điểm #điều hòa sơ cấp - đối cấp #lập trình bậc hai lồi #hệ phương trình tuyến tính #Jacobian thiếu hạngTài liệu tham khảo
Altman A., Gondzio J.: Regularized symmetric indefinite systems in interior point methods for linear and quadratic optimization. Optim. Methods Softw. 11(12), 275–302 (1999)
Altman, A., Gondzio, J. Higher order primal dual method (2009). http://www.maths.ed.ac.uk/~gondzio/software/hopdm.html
Anjos M.F., Burer S.: On handling free variables in interior-point methods for conic linear optimization. SIAM J. Optim. 18(4), 1310–1325 (2007)
Armand, P., Benoist, J.: Uniform boundedness of the inverse of a jacobian matrix arising in regularized interior-point methods. Math. Program. (2011). doi:10.1007/s10107-011-0498-3
Bellavia S., Gondzio J., Morini B.: Regularization and preconditioning of KKT systems arising in nonnegative least-squares problems. Numer. Linear Algebra Appl. 16(1), 39–61 (2009). doi:10.1002/nla.610
Bunch J.R., Parlett B.N.: Direct methods for solving symmetric indefinite systems of linear equations. SIAM J. Numer. Anal. 8(4), 639–655 (1971)
Castro, J., Cuesta, J.: Quadratic regularizations in an interior-point method for primal block-angular problems. Math. Programm., 1–31 (2010). doi:10.1007/s10107-010-0341-2
Czyzyk, J., Mehrotra, S., Wagner, M., Wright, S.J.. PCx user guide version 1.1. Technical Report OTC 96/01, Optimization Technology Center, Evanston (1996). http://www.mcs.anl.gov/OTC/Tools/PCx
Fletcher R.: Practical Methods of Optimization, 2nd edn. Wiley, Chichester (1987)
Friedlander M.P., Leyffer S.: Global and finite termination of a two-phase augmented Lagrangian filter method for general quadratic programs. SIAM J. Sci. Comput. 30(4), 1706–1729 (2008). doi:10.1137/060669930
Friedlander M.P., Tseng P.: Exact regularization of convex programs. SIAM J. Optim. 18(4), 1326–1350 (2007). doi:10.1137/060675320
Gertz E.M., Wright S.J.: Object-oriented software for quadratic programming. ACM Trans. Math. Softw. 29(1), 58–81 (2003)
Gill, P.E., Murray, W., Ponceleón, D.B., Saunders, M.A.: Solving reduced KKT systems in barrier methods for linear and quadratic programming. Technical Report SOL 91-7, Systems Optimization Laboratory, Stanford University, Stanford (1991)
Gill P.E., Saunders M.A., Shinnerl J.R.: On the stability of Cholesky factorization for symmetric quasidefinite systems. SIAM J. Matrix Anal. Appl. 17(1), 35–46 (1996)
Gondzio, J.: Matrix-free interior point method. Comput. Optim. Appl., 1–24 (2011). doi:10.1007/s10589-010-9361-3
Gould N.I.M., Orban D., Toint P.L.: CUTEr and SifDec, a Constrained and Unconstrained Testing Environment, revisited. ACM Trans. Math. Softw. 29(4), 373–394 (2003)
Harwell Subroutine Library: A collection of Fortran codes for large-scale scientific computation. AERE Harwell Laboratory (2000). http://www.numerical.rl.ac.uk/hsl
Karypis G., Kumar V.: Multilevel k-way partitioning scheme for irregular graphs. J. Parallel Distrib. Comput. 48(1), 96–129 (1998)
Karypis G., Kumar V.: A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM J. Sci. Comput. 20(1), 359–392 (1999)
Kojima M., Megiddo N., Mizuno S.: A primal–dual infeasible-interior-point algorithm for linear programming. Math. Program. 61, 263–280 (1993)
Mangasarian O.L., Meyer R.R.: Nonlinear perturbation of linear programs. SIAM J. Control Optim. 17(6), 745–752 (1979)
Maros, I., Mészáros, C.: A repository of convex quadratic programming problems. Optim. Methods Softw. 11, 12, 671–681 (1999) (Special Issue on Interior Point Methods)
Mehrotra S.: On the implementation of a primal–dual interior-point method. SIAM J. Optim. 2(4), 575–601 (1992)
Mészáros C.: On free variables in interior point methods. Optim. Methods Softw. 9, 121–139 (1998)
Mittelmann, H.: http://plato.la.asu.edu/ftp/ampl_files/qpdataampl (2006)
Netlib. http://netlib.org/lp (2011)
Ng, E.G., Peyton, B.W.: Block sparse cholesky algorithms on advanced uniprocessor computers. SIAM J. Sci. Comput. 14(5), 1034–1056 (1993). doi:10.1137/0914063. http://link.aip.org/link/?SCE/14/1034/1
Oliveira A.R.L., Sorensen D.C.: A new class of preconditioners for large-scale linear systems from interior point methods for linear programming. Linear Algebra Appl. 394, 1–24 (2005)
Orban, D.: NLPy—a large-scale optimization toolkit in Python. Technical Report Cahier du GERAD G-2010-xx, GERAD, Montréal (2010). http://nlpy.sourceforge.net/.
Rockafellar R.T.: The multiplier method of Hestenes and Powell applied to convex programming. J. Optim. Theory Appl. 12, 555–562 (1973)
Rockafellar R.T.: Augmented Lagrangians and applications of the proximal point algorithm in convex programming. Math. Oper. Res. 1(2), 97–116 (1976)
Rusten, T., Winther, R.: A preconditioned iterative method for saddlepoint problems. SIAM J. Matrix Anal. Appl. 13(3), 887–904 (1992). doi:10.1137/0613054. http://link.aip.org/link/?SML/13/887/1
Saunders M.A.: Solution of sparse rectangular systems using LSQR and CRAIG. BIT 35, 588–604 (1995)
Saunders M.A.: Cholesky-based methods for sparse least squares: The benefits of regularization. In: Adams, L., Nazareth, J.L. (eds) Linear and Nonlinear Conjugate Gradient-Related Methods., pp. 92–100. SIAM, Philadelphia (1996)
Saunders, M.A.: PDCO: Primal–dual interior method for convex objectives (2010). http://www.stanford.edu/group/SOL/software/pdco.html
Saunders, M.A., Tomlin, J.A.: Solving regularized linear programs using barrier methods and KKT systems. SOL Report 96-4, Dept. of EESOR, Stanford University (1996)
Setiono R.: Interior proximal point algorithm for linear programs. J. Optim. Theory Appl. 74(3), 425–444 (1992)
Setiono R.: Interior dual proximal point algorithm for linear programs. Eur. J. Oper. Res. 77, 96–110 (1994)
Silvester, D., Wathen, A.: Fast iterative solution of stabilised Stokes systems part II: using general block preconditioners. SIAM J. Numer. Anal. 31(5), 1352–1367 (1994). doi:10.1137/0731070. http://link.aip.org/link/?SNA/31/1352/1
Vanderbei R.J.: Interior-point methods: algorithms and formulations.. ORSA J. Comput. 6(1), 32–34 (1994)
Vanderbei R.J.: Symmetric quasi-definite matrices. SIAM J. Optim. 5(1), 100–113 (1995)
Wright S.J.: Implementing proximal point methods for linear programming. J. Optim. Theory Appl. 65((3), 531–554 (1990)
Wright S.J.: Primal–Dual Interior-Point Methods. SIAM, Philadelphia (1997)