Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Lets say we have a Quadratically Constrained Quadratic Program which we would like to optimize. The first step for many methods requires one to first find a point in the feasible region.

How can I answer the question "Is the feasible region non-empty?" If the answer is yes, I would like a witness obviously. I'm assuming this is possible in polynomial time if the problem is convex?

share|improve this question
    
I noticed a possible problem. The specific problem I was thinking of turned out not to be convex(my mistake), and the feasible set always would have had an empty interior. Both of those things seem to make it not possible in polynomial time. But I still would be interested in an answer to this question. –  Tim Seguine Sep 28 '11 at 19:17

1 Answer 1

up vote 0 down vote accepted

For feasibility, only the constraints matter, not the objective. One way to identify a feasible point (even if there exist no strictly feasible point), is to solve the feasibility problem $$ \min \ 0 \quad \text{subject to your constraints}. $$ Usually, this is not a much better-behaved problem than the original problem. An alternative is to minimize the infeasibility residual $$ \min \ \|\text{constraints}\|^2 $$ (assuming equality constraints). This is typically a nonlinear least-squares problem. Depending on the form of your constraints it can be solved more or less efficiently. If your original problem was feasible, this last one is a zero-residual least-squares problem and Gauss-Newton should converge quadratically.

That being said, note that many modern methods do not require an initial feasible point. I may be able to be more specific if you give more details on your problem.

share|improve this answer
    
This looks pretty helpful, but considering my comment on my original post: Can this work efficiently even if the feasible set is not convex? The problem is this: satisfy a linear equation system in n dimensions(possibly overdetermined) with the extra constraint that the solutions lie on a hypersphere of radius $\sqrt{n}$. –  Tim Seguine Nov 13 '11 at 15:04
    
@Tim The linear system is no problem. The hypersphere constraint is a nonconvex equality constraint. The problem is NP hard. –  Dominique Dec 7 '11 at 1:52
    
@Tim Just to add to my previous comment, if your quadratic constraint were to stay within a hypersphere, then this constraint could be written $\|x\|_M^2 \leq r^2$ for some $r > 0$ and you could use the truncated conjugate gradient method (assuming your objective is convex). See jstor.org/pss/2157277 I hope this helps. –  Dominique Dec 7 '11 at 13:50
    
That is what I thought. Thanks. –  Tim Seguine Dec 9 '11 at 15:27
    
I'd just like to add: Even though the problem that I was originally considering is intractable, your answer was very complete and nevertheless interesting and informative, and I intend to follow up on the references. –  Tim Seguine Dec 16 '11 at 18:31

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.