×

Improving solver success in reaching feasibility for sets of nonlinear constraints. (English) Zbl 1278.90381

Summary: Whether a given nonlinear solver can reach a feasible point for a set of nonlinear constraints depends heavily on the initial point provided. We develop a range of computationally cheap constraint consensus algorithms that move from a given initial point to a better final point that is then passed to the nonlinear solver. Empirical tests show that this added step greatly improves the success rate of various nonlinear solvers in reaching feasibility, and reduces the effort they expend in doing so. We also develop a new initial point placement heuristic for use when an initial point is not provided by the modeller. Empirical tests show much improved performance for this new heuristic, both alone and in conjunction with the constraint consensus algorithms.

MSC:

90C30 Nonlinear programming
65K05 Numerical mathematical programming methods
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Drud, A.S., CONOPT—a large scale GRG code, ORSA journal on computing, 6, 207-216, (1994) · Zbl 0806.90113
[2] Lawrence, C.T.; Tits, A.L., A computationally efficient feasible sequential quadratic programming algorithm, SIAM journal on optimization, 11, 4, 1092-1118, (2001) · Zbl 1035.90105
[3] Lasdon, L.S., Optimization theory for large systems, (1970), Macmillan Company New York · Zbl 0224.90038
[4] Rardin, R.L., Optimization in operations research, (1998), Prentice Hall Upper Saddle River, NJ, USA
[5] Wright, S.J., Primal-dual interior point methods, (1997), SIAM Press Philadelphia, PA · Zbl 0863.65031
[6] Chinneck, J.W., The constraint consensus method for finding approximately feasible points in nonlinear programs, INFORMS journal on computing, 16, 3, 255-265, (2003) · Zbl 1239.90096
[7] Censor, Y.; Gordon, D.; Gordon, R., Component averaging: an efficient iterative parallel algorithm for large and sparse unstructured problems, Parallel computing, 27, 777-808, (2001) · Zbl 0972.68189
[8] Elwakeil, O.A.; Arora, J.S., Methods for finding feasible points in constrained optimization, AIAA journal, 33, 1715-1719, (1995) · Zbl 0862.73040
[9] Chen, X.B.; Kostreva, M.M., Global convergence analysis of algorithms for finding feasible points in norm-relaxed MFD, Journal of optimization theory and applications, 100, 2, 287-309, (1999) · Zbl 0915.90234
[10] Gertz M, Nocedal J, Sartenaer A. A starting-point strategy for nonlinear interior methods. Report OTC 2003/4, Optimization Technology Center, Northwestern University, Evanston, IL, USA, March 2003. · Zbl 1087.90084
[11] Murtagh BA, Saunders MA. MINOS 5.4 User’s guide. Report SOL 83-20R. Systems Optimization Laboratory, Stanford University (revised February 1995); 1983. See \(\langle\)http://www.sbsi-sol-optimize.com/⟩.
[12] Censor, Y.; Zenios, S.A., Parallel optimization: theory, algorithms, and applications, (1997), Oxford University Press New York · Zbl 0945.90064
[13] Bongartz, I.; Conn, A.R.; Gould, N.; Toint, P.L., CUTE: constrained and unconstrained testing environment, ACM transactions on mathematical software, 21, 1, 123-160, (1995), See \(\langle\)http://www.sor.princeton.edu/\(\sim\)rvdb/ampl/nlmodels/cute/index.html⟩ for CUTE models in AMPL format · Zbl 0886.65058
[14] Fourer, R.; Gay, D.M.; Kernighan, B., AMPL: a modeling language for mathematical programming, (2003), Thomson Brooks/Cole Pacific Grove, CA, USA
[15] Gill PE, Murray W, Saunders MA. SNOPT: an SQP algorithm for large-scale constrained optimization. Report SOL 97-3. Systems Optimization Laboratory, Stanford University, 1997. See \(\langle\)http://www.sbsi-sol-optimize.com/⟩. · Zbl 1210.90176
[16] Waltz RA, Nocedal J. KNITRO User’s manual. Technical report OTC 2003/05. Optimization Technology Center, Northwestern University, Evanston, IL, USA, April 2003. See \(\langle\)http://www.ziena.com/knitro.html⟩.
[17] Spellucci, P., An SQP method for general nonlinear programs using only equality constrained subproblems, Mathematical programming, 82, 3, 413-448, (1998) · Zbl 0930.90082
[18] Gould, NIM.; Leyffer, S.; Toint, PhL., A multidimensional filter algorithm for nonlinear equations and nonlinear least squares, SIAM journal of optimization, 15, 17-38, (2004) · Zbl 1075.65075
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.