  We consider high dimensional random optimization problems where the dynamical
variables are subjected to non-convex excluded volume constraints. We focus on
the case in which the cost function is a simple quadratic cost and the excluded
volume constraints are modeled by a perceptron constraint satisfaction problem.
We show that depending on the density of constraints, one can have different
situations. If the number of constraints is small, one typically has a phase
where the ground state of the cost function is unique and sits on the boundary
of the island of configurations allowed by the constraints. In this case, there
is a hypostatic number of marginally satisfied constraints. If the number of
constraints is increased one enters a glassy phase where the cost function has
many local minima sitting again on the boundary of the regions of allowed
configurations. At the phase transition point, the total number of marginally
satisfied constraints becomes equal to the number of degrees of freedom in the
problem and therefore we say that these minima are isostatic. We conjecture
that by increasing further the constraints the system stays isostatic up to the
point where the volume of available phase space shrinks to zero. We derive our
results using the replica method and we also analyze a dynamical algorithm, the
Karush-Kuhn-Tucker algorithm, through dynamical mean-field theory and we show
how to recover the results of the replica approach in the replica symmetric
phase.
