0
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Hmm, I guess I played along those lines. It seems to be too good--I don't want to be so 'good' rather I want to allow some room such that $\ell_2$ norm ball is bit bigger. Does that make sense to you? $\endgroup$ – user550103 Aug 24 '18 at 15:15
  • $\begingroup$ It does. If your specialized solver is iterative, you do not have to wait until it converges. You can stop it as soon as its objective value drops below $\epsilon^2$. $\endgroup$ – Alex Shtof Aug 24 '18 at 21:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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