×

zbMATH — the first resource for mathematics

Constraint consensus methods for finding strictly feasible points of linear matrix inequalities. (English) Zbl 06918317
Summary: We give algorithms for solving the strict feasibility problem for linear matrix inequalities. These algorithms are based on John Chinneck’s constraint consensus methods, in particular, the method of his original paper and the modified DBmax constraint consensus method from his paper with Ibrahim. Our algorithms start with one of these methods as “Phase 1.” Constraint consensus methods work for any differentiable constraints, but we take advantage of the structure of linear matrix inequalities. In particular, for linear matrix inequalities, the crossing points of each constraint boundary with the consensus ray can be calculated. In this way we check for strictly feasible points in “Phase 2” of our algorithms. We present four different algorithms, depending on whether the original (basic) or DBmax constraint consensus vector is used in Phase 1 and, independently, in Phase 2. We present results of numerical experiments that compare the four algorithms. The evidence suggests that one of our algorithms is the best, although none of them are guaranteed to find a strictly feasible point after a given number of iterations. We also give results of numerical experiments indicating that our best method compares favorably to a new variant of the method of alternating projections.
Reviewer: Reviewer (Berlin)
MSC:
90 Operations research, mathematical programming
Software:
SDPLIB; SeDuMi
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Todd, M. J., Semidefinite optimization, Acta Numerica, 10, 515-560, (2001) · Zbl 1105.65334
[2] Vandenberghe, L.; Boyd, S., Semidefinite programming, SIAM Review, 38, 1, 49-95, (1996) · Zbl 0845.65023
[3] Chinneck, J. W., The constraint consensus method for finding approximately feasible points in nonlinear programs, INFORMS Journal on Computing, 16, 3, 255-265, (2004) · Zbl 1239.90096
[4] Kearfott, R. B.; Dian, J., An iterative method for finding approximate feasible points, (2000), Lafayette, La, USA: Department of Mathematics, University of Southern Louisiana, Lafayette, La, USA
[5] Gahinet, P.; Nemirovski, A., The projective method for solving linear matrix inequalities, Mathematical Programming, 77, 163-190, (1997) · Zbl 0890.90142
[6] Rami, M. A.; Helmke, U.; Moore, J. B., A finite steps algorithm for solving convex feasibility problems, Journal of Global Optimization, 38, 1, 143-160, (2007) · Zbl 1180.90239
[7] Baang, D., Improved ellipsoid algorithm for LMI feasibility problems, International Journal of Control, Automation and Systems, 7, 6, 1015-1019, (2009)
[8] Censor, Y.; Zenios, S. A., Parallel Optimization: Theory, Algorithms, and Applications, (1997), New York, NY, USA: Oxford University Press, New York, NY, USA · Zbl 0945.90064
[9] Ibrahim, W.; Chinneck, J. W., Improving solver success in reaching feasibility for sets of nonlinear constraints, Computers & Operations Research, 35, 5, 1394-1411, (2008) · Zbl 1278.90381
[10] Borchers, B., SDPLIB 1.2, library of semidefinite programming test problems, Optimization Methods and Software, 11, 1–4, 683-690, (1999) · Zbl 0973.90522
[11] Jibrin, S., Generating uniform points on the boundary of bounded spectrahedron with applications to rank constrained linear matrix inequality problem, International Journal of Applied Mathematics & Engineering Sciences, 1, 1, 27-38, (2007)
[12] Caron, R. J.; Traynor, T.; Jibrin, S., Feasibility and constraint analysis of sets of linear matrix inequalities, INFORMS Journal on Computing, 22, 1, 144-153, (2010) · Zbl 1243.90172
[13] Overton, M. L.; Womersley, R. S., Optimality conditions and duality theory for minimizing sums of the largest eigenvalues of symmetric matrices, Mathematical Programming, 62, 2, 321-357, (1993) · Zbl 0806.90114
[14] Sturm, J., Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones, Optimization Methods and Software, 11-12, 625-653, (1999) · Zbl 0973.90526
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.