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?

| cite | improve this question | |
$\endgroup$
  • 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 '17 at 6:34
  • $\begingroup$ On reflection, there's really no advantage, either way. So perhaps, just author's choice. $\endgroup$ – quasi Apr 5 '17 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 '17 at 8:12
  • $\begingroup$ I follow -- for the convex case, the inequality version yields a region of the form required by the standard methods. $\endgroup$ – quasi Apr 5 '17 at 9:06
  • 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 '17 at 16:29
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.

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ No need for all the bold face here but good answer ;-) $\endgroup$ – Michael Grant Apr 5 '17 at 15:06
  • $\begingroup$ Thanks @MichaelGrant for your notice; I just applied your comment as much as possible. :) $\endgroup$ – Amin Apr 5 '17 at 15:32
  • $\begingroup$ @stephen Why is there an inequality sign for your equality constraints $h_j(x)$? $\endgroup$ – Teodorism Apr 6 '17 at 10:36
  • $\begingroup$ That was a typo; thanks @Teodorism for your notice, corrected. $\endgroup$ – Amin Apr 6 '17 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 '17 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.