How to solve ${\text{find }} \mathbf{x}, \ \text{s.t. } f(\mathbf{x}) \leq 0 \ \ g(\mathbf{x}) \leq 0$ (without using generic solvers)?

Question

I am at a very beginner's level in the optimization domain. So, my apologies in advance, if I am asking trivial/stupid questions.

A generic minimization problem reads \begin{align} & \underset{\mathbf{x}}{\text{minimize}} & & \left\|\mathbf{z} - \mathbf{x}\right\|_2^2 \nonumber \\ & \text{subject to} & & g\left({\mathbf{x}}\right) \leq 0 \ , \end{align}

where the constraint $g(\cdot) \leq 0$ is convex.

This problem can equivalently be expressed as the projection onto a convex set $C = \left\{\mathbf{x} : \ g\left({\mathbf{x}}\right) \leq 0 \right\}$, i.e., \begin{align} & \underset{\mathbf{x}}{\text{minimize}} & & \left\|\mathbf{z} - \mathbf{x}\right\|_2^2 \nonumber \\ & \text{subject to} & & \mathbf{x} \in C \ . \end{align}

Suppose that I know the closed-form projection of this problem. So far so good.

Now, my problem is that I don't want to minimize $\left\|\mathbf{z} - \mathbf{x}\right\|_2^2$ but rather I want to meet some constraint. In other words, I pose the following feasibility problem: \begin{align} & \underset{}{\text{find}} & & {\mathbf{x}} \nonumber \\ & \text{subject to} & & \underbrace{\left\|\mathbf{z} - \mathbf{x}\right\|_2^2 - \epsilon }_{{f\left({\mathbf{x}}\right)}} \leq 0 \\ & & & g\left({\mathbf{x}}\right) \leq 0 . \end{align} Also, I don't want to use any generic optimization solvers, but rather utilize some "prox"-like operators and probably operator splitting techniques. Please suggest how to approach this problem. Also, I am not sure about the $\textrm{prox}_f(\cdot)$.

REMARK: The intention to "relax" (not the convexification sense) the constraint $\left\|\mathbf{z} - \mathbf{x}\right\|_2^2 \leq \epsilon$ is to allow some error, or geometerically to increase the size of the $\ell_2$ norm ball intentionally. I hope it makes sense you all.

Answer 1

I believe the answer is much simpler. Suppose, like you said, that you can solve the problem $\mu = \min_{\mathbf{x}} \{ \|\mathbf{x} - \mathbf{z} \|_2^2 : g(\mathbf{x}) \leq 0 \}$. The algorithm for solving your feasibility problem is very simple:

1. Compute $\mu$.
2. If $\mu> \epsilon$, your feasibility problem is infeasible. Otherwise, the optimal solution $\mathbf{x}^*$ you found is your feasible $\mathbf{x}$.

Note, that if your specialized solver for the projection problem is iterative and feasible in each iteration, you can stop it as soon as the objective value drops below $\epsilon$, since the current iterate is feasible for your feasibility problem.