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

1 Answer 1

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$
1
  • $\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, 2017 at 16:06

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .