Boyd & Vandenberghe, problem 4.6 — can one replace $=$ with $\leq$?

Question

In problem 4.6 of Boyd & Vandenberghe's Convex Optimization, they ask under which condition the following problem can be converted into a standard convex optimization problem.

$\text{min. } f_0(x)$

$\text{s.t. } f_i(x)\leq 0, ~~ i \in \{1,2,\cdots m\}$

$h(x)=0$

where $f_0,f_i,h$ are convex functions.

It is known that for a standard convex optimization problem $h(x)$ should be an affine function. However, in the solution they say that if we can find a component $x_r$ such that the following properties are obeyed

1. $f_0(x)$ is monotonically increasing in $x_r$.

2. $f_1, f_2,\cdots f_m$ are nonincreasing in $x_r$.

3. $h$ is monotonically decreasing in $x_r$.

Then we can replace the equality sign in the above problem with $\leq$ sign.

My question is that if the functions follows the below properties in $x_r$

1. $f_0$ is decreasing.

2. $f_i$ is nonincreasing.

3. $h$ is increasing.

then "Can we replace the equality sign with $\leq$ sign in the above optimization problem?". Any help in this regard will be much appreciated. Thanks in advance.

Answer 1

Ok, I read the problem in more detail. This paragraph is important.

"Now suppose we can guarantee that at any optimal solution $x^*$ of the convex problem, we have $h(x^*) = 0$, i.e. the inequality $h(x)$ is always active at the solution. Then we can solve the nonconvex problem by solving the convex problem."

This paragraph basically means that we will change the problem, but it doesn't change the solution, so it's fine. So the problem now asks you to show that this condition $h(x^*) = 0$ always holds under the conditions they described.

• $f_0$ is monotonically increasing in $x_r$ -- this means that we want $x_r$ to be as small as possible in the solution.

• $f_i$, $i = 1,...,m$ nondecreasing in $x_r$: this means that as we force $x_r \to -\infty$, it can only help not violate the constraints.

• $h(x)$ is monotonically decreasing in $x_r$: this means that forcing $x_r$ to be smaller will actually increase the value of $h(x)$.

Since solutions always happen when you push all the indices as far as they can go, from the first point we know we are pushing $x_r$ to be small, the second point shows it doesn't violate the $f_i$ constraints, and the third constraint therefore must be tight at optimality.

There might be a way to do it using some fancy constraint qualification test as well, but I can't think of one off the top of my head.