3
$\begingroup$

Why is the optimization problem

$\textrm{minimize} ~f_0(x)$

equivalent to

$\textrm{minimize} ~~t \\ s.t. ~~ f_0(x)\leq t$

but not equivalent to the following?

$\textrm{minimize} ~~t \\ s.t. ~~ t=f_0(x)$

I found this example in Boyd's book and although he doesn't deny that the first and third minimization problems could be equivalent, it doesn't explicitly say so either? I'm wondering why he's using an inequality instead of an equality as a constraint?

$\endgroup$
7
  • 2
    $\begingroup$ Of course the equality version is equivalent. I guess the point of the inequality version is that you can more easily get a starting point for one of the various successive improvement methods. If you insist on equality, you're not giving those methods much of a chance to play. $\endgroup$
    – quasi
    Apr 5, 2017 at 6:34
  • $\begingroup$ On reflection, there's really no advantage, either way. So perhaps, just author's choice. $\endgroup$
    – quasi
    Apr 5, 2017 at 6:53
  • 4
    $\begingroup$ @quasi There is an important advantage in the case when $f_0$ is convex, because then the epigraph form problem is a convex optimization problem, whereas the equality constrained version is a nonconvex problem. $\endgroup$
    – littleO
    Apr 5, 2017 at 8:12
  • 1
    $\begingroup$ Just my two cents: the epigraph form is equivalent to the original problem provided that $f_0$ is lower semicontinuous. These equivalences are explained nicely in the book Optimization Models by G. Calafiore and L. El Ghaoui, Cambridge University Press [Section 8.3.4] $\endgroup$
    – Pantelis Sopasakis
    Dec 23, 2017 at 16:29
  • 1
    $\begingroup$ Agree with @littleO, when $f_0$ is not affine, the problem stated in the third approach may not be a convex problem, where equality constraint functions are required to be affine; however, the problem stated in the second approach is still a standard convex problem, as we only require inequality constant functions to be convex. $\endgroup$
    – Jake ZHANG Shiyu
    Oct 1, 2021 at 15:09

1 Answer 1

Reset to default
7
$\begingroup$

Suppose the original standard form of an optimization problem is:

$$\min~~f_0(\mathbf{x})\\ \text{s.t. } ~f_i(\mathbf{x}) \leq 0, i=1,...,m \\~~~~~~~ h_j(\mathbf{x}) = 0, j=1,...,p $$

in which $f_i$ for $i=1,...,m$ are inequality constraint functions and $h_j$ for $j=1,...,p$ are equality constraint functions. For a convex optimization problem, $f_0(\mathbf{x})$ and $f_i$ for $i=1,...,m$ are convex functions and $h_j$ for $j=1,...,p$ are affine functions.

Now, for the equivalent epigraph representation of the original problem in standard form, we use the corresponding constraint in inequality form, we have: $$\min ~~t \\ \text{s.t.} ~~ f_0(\mathbf{x}) - t\leq 0 \\ \qquad f_i(\mathbf{x}) \leq 0, i=1,...,m \\~~~~~~~ h_j(\mathbf{x}) = 0, j=1,...,p.$$ Assume the original problem is a convex optimization problem. To provide the original problem in epigraph standard representation, but preserving the problem to be in convex form, it needs to add an inequality constraint function $f_0(\mathbf{x}) - t$ which is convex in $(\mathbf{x},t)$; this inequality corresponds to the $\mathbf{epi} ~f_0$, here, is a convex set. So, the problem in the equivalent epigraph representation is still in a standard convex optimization problem form. Furthermore, for straightforward and meaningful analysis of a problem, also designing an efficient algorithm, different equivalent representation of a problem can be used.

Note: $f$ is convex if and only if $\textbf{epi} ~f$ is convex set.

$\endgroup$
8
  • 2
    $\begingroup$ No need for all the bold face here but good answer ;-) $\endgroup$
    – Michael Grant
    Apr 5, 2017 at 15:06
  • $\begingroup$ Thanks @MichaelGrant for your notice; I just applied your comment as much as possible. :) $\endgroup$
    – Amin
    Apr 5, 2017 at 15:32
  • $\begingroup$ @stephen Why is there an inequality sign for your equality constraints $h_j(x)$? $\endgroup$
    – Teodorism
    Apr 6, 2017 at 10:36
  • $\begingroup$ That was a typo; thanks @Teodorism for your notice, corrected. $\endgroup$
    – Amin
    Apr 6, 2017 at 11:14
  • $\begingroup$ @Stephen Please, correct me if I'm wrong. You're basically saying because in the definition of the standard form (of a convex optimization problem), we only allow affine equalities, we use $f_0(x)−t\leq 0$ instead of $f_0(x)−t=0$? Otherwise, if we'd lifted the 'affineness' requirement from the definition, we could've used $f_0(x)−t=0$? $\endgroup$
    – Teodorism
    Apr 6, 2017 at 11:25

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.