1
$\begingroup$

Let $x \in {\mathbb R}^n$, and $f_0,f_1,\ldots f_m$ are convex functions on ${\mathbb R}^n$. Consider the following problem:

\begin{equation} (\mathrm{P1})~~~~~~~~~~~~~~~~~~ \begin{split} &\mathrm{minimize}~~~~~f_0(x)\\ &s.t.~~~~~~~~~~~~~~f_i(x) \leq 0,\quad i\in\{1,\ldots,m\} \end{split} \end{equation}

Then, can I solve (P1) by the following procedure?

Step 1: Solve $\mathrm{minimize}~f_0(x)$, and derive $x_1^*$.

Step 2: Judge if $x_1^*$ is feasible to the constraints in (P1), i.e., if $f_i(x_1^*) \leq 0$ for all $i \in \{1,\ldots,m\}$. If $x_1^*$ is feasible to them, then the minimizer of (P1) is $x_1^*$. Otherwise, we consider Step 3.

Step 3: Solve

\begin{equation} (\mathrm{P2})~~~~~~~~~~~~~~~~~~ \begin{split} &\mathrm{minimize}~~~~~f_0(x)\\ &s.t.~~~~~~~~~~~~~~f_i(x) = 0,\quad i\in\{1,\ldots,m\}, \end{split} \end{equation} and derive $x_2^*$. Then, $x_2^*$ is the optimal solution to (P1).

The algorithm above does not need any optimization technique in dealing with the inequality constraints. In step 1, we solve an unconstrained optimization problem. In step 2, we solve an optimization problem with equality constraints.

In my opinion, this algorithm can correctly return the optimal solution to (P1), since the global minimizer is either within the feasible region described by $f_i(x) \leq 0$ ($i \in \{1,\ldots,m\}$), or on the boundary of the feasible region. Am I right?

Thanks!

$\endgroup$
  • 1
    $\begingroup$ I guess P2 may be non convex in general. $\endgroup$ – AndreaCassioli Dec 9 '17 at 13:35
  • $\begingroup$ @AndreaCassioli You are right, and thanks very much for your comments. $\endgroup$ – Ryan Dec 9 '17 at 13:37
  • $\begingroup$ @AndreaCassioli How to close this problem without deleting it? $\endgroup$ – Ryan Dec 9 '17 at 13:40
  • 1
    $\begingroup$ You can't, really. But it is fine to leave it. $\endgroup$ – Michael Grant Dec 9 '17 at 21:32
  • $\begingroup$ @MichaelGrant Thanks for your help :-) $\endgroup$ – Ryan Dec 10 '17 at 2:09
2
$\begingroup$

This is an excellent question, almost always asked by our students. This approach has several major flaws:

  1. Solving equality constrained problems, unless the constraints are affine, is harder than inequality constrained problems. For example, the constraint $x^2 + y^2 - xy - y = 2$ is harder to handle than $x^2 + y^2 - xy -y \leq 2$
  2. It might happen that all optimal points $x^*$ satisfy some of the constraints with equality while others as strong inequalities. That is, for some $i$ we have $f_i(x^*) = 0$, while for other $i$ we have $f_i(x^*) < 0$. In that case, your algorithm will miss all optimal points.
$\endgroup$
  • $\begingroup$ Thanks very much for your answer! [+1] I completely agree with you. Firstly, non-affine equality contraints will make the problem harder in general. Secondly, this method will miss the optimal points who cannot make all constraints active. $\endgroup$ – Ryan Dec 10 '17 at 16:06

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.