How to determine the existence of a solution to a system of homogenous quadratic inequalities and linear equalities?Let M1,…,MK be positive definite real symmetric matrices of dimension n. Let R be an m×n matrix with m&lt;n. Assume R has full row rank. Fix d∈Rm. Consider the system of inequalities/equalities for x∈Rn:xTMkx≤1,(k=1,…K)Rx=dIs there an efficient algorithm to determine whether a solution exists?

Question

How to determine the existence of a solution to a system of homogenous quadratic inequalities and linear equalities?Let M1,…,MK be positive definite real symmetric matrices of dimension n. Let R be an m×n matrix with m&amp;lt;n. Assume R has full row rank. Fix d∈Rm. Consider the system of inequalities/equalities for x∈Rn:xTMkx≤1,(k=1,…K)Rx=dIs there an efficient algorithm to determine whether a solution exists?

Trey Harrington · Accepted Answer

This problem can be solved by convex optimization. Define F(x)=|Rx−d|2 be the objective function, and let Φ={x:xTMkx≤1,k=1,…K}. Consider the problem(P)minxF(x):x∈ΦThe existence of a solution to the original problem above is equivalent to minxF(x)=0. This is minimization of a convex function F over a convex domain Φ. Since also Φ is non-empty (0∈Φ) we can initialize any convex optimizer at x0=0 and compute the global minimum for F to determine minF=0.

How to determine the existence of a solution to a system of homogenous quadratic inequalities and li

Answered question

Answer & Explanation

New Questions in Algebra I