Non-Convex Constraints for Classification Problems

Question

I am willing to create a hypothetical non-convex constraints for the purpose of practising nonlinear classification using an algorithm. I thought of such constraints in the form: $x^TAx + Bx leq c$.

I am curious if this qualifies for non-convex constraints, and if the matrices $A$ and $B$ are necessarily PSD. Or could I possibly have more than this constraints?

I would like if someone explains this or refers me to any text/paper I could read up. My Mathematics is kind of rusty at the moment.

Siong Thye Goh · Answer

Notice that constraint  of the form of $g(x) le c$ where $g$ is convex is convex.

To see this, consider $g(x_i) le c$, then for $lambda in (0,1)$,

$$g(lambda x_1 + (1-lambda)x_2) le lambda g(x_1) + (1-lambda) g(x_2) le lambda c + (1-lambda) c = c$$

To make it non-convex, let $A$ be negative definite or indefinite.

Non-Convex Constraints for Classification Problems

One Answer

Add your own answers!

Ask a Question