3
$\begingroup$

I apologise for asking such a (trivial) question. But I am not sure how is called the following transformation.

Let us suppose that I have a generic feasibility problem \begin{align} & \underset{}{\text{find}} & & {x \in \mathbb{R}^n} \nonumber \\ & \text{subject to} & &f_1\left(x\right) \leq 0 \\ & & & f_2\left(x\right) \leq 0 , \end{align} where both functions are convex, i.e., $f_1(\cdot)$ and $f_2(\cdot)$.

However, I would like to convert such a feasibility problem to the following optimization problem \begin{align} & \underset{x \in \mathbb{R}^n, \delta \in \mathbb{R}}{\text{minimize}} & & {\delta} \nonumber \\ & \text{subject to} & &f_1\left(x\right) \leq \delta \\ & & & f_2\left(x\right) \leq 0 . \end{align}

Then, some basic questions:

  • What do you call the conversion of such a feasibility problem to a standard optimization problem?

  • Also, can you guarantee that the optimal solution of the latter is contained within the former, i.e., feasibility, problem?

$\endgroup$
2
$\begingroup$

As far as I know, the transformation of a feasibility problem into an optimization problem has no special name.

As for your second question, the short answer is yes. An optimal solution is a feasible solution which happens to give you the least value (in the case of minimization) of your objective function.

I offer a brief explanation of what is behind what you want to do. An optimization problem can be transformed into an equivalent problem for algorithmic purposes or just to get an explicit solution.

Consider the general convex program \begin{align} \min_x \ & \ f(x)\\ \text{s.t.} \ & \ g(x) \leq 0 \\ \ & \ h(x) =0, \end{align} then we can use the epigraph transformation, which gives the equivalent problem: \begin{align} \min_{x,t} \ & \ t\\ \text{s.t.} \ & \ f(x) \leq t \\ \ & \ g(x) \leq 0 \\ \ & \ h(x) =0. \end{align}

This transformation preserves convexity. (The epigraph of a function $f:\mathbb{R}^n \to \mathbb{R}$ is the set of points lying above its graph, i.e., $\text{epi}f = \{ (x,\mu) : x \in \mathbb{R}^n, \ \mu \in \mathbb{R}, \ f(x) \leq \mu \})$

In your case, as both $f_1$ and $f_2$ are convex, you can write your feasibility problem as the following optimization problem: \begin{align} \min_{x, \delta} \ & \ \delta \\ \text{s.t.} \ & \ f_1(x) \leq \delta \\ \ & \ f_2(x) \leq \delta \\ \ & \ 0 \leq \delta \end{align} where the last constraint is added to ensure that your problem is bounded (does not go to $- \infty$).

I hope you find this helpful.

$\endgroup$
  • $\begingroup$ Thanks, ConEd for the explanation! $\endgroup$ – learning Aug 31 at 18:42
0
$\begingroup$

In the two-phase simplex algorithm for linear programming, this is called Phase I.

In some nonlinear programming algorithms, this is called feasibility restoration.

$\endgroup$

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.