A constrained optimization problem of the following form is given:

$ min \,\, f_1(x) \\ \text{subject to constraint}, \\ f_2(x) \leq f_2^*(x)$

Where $f_2^*(x)$ is the minimum of the convex function $f_2$ found earlier. So the function $f_1$ has to be minimized while keeping the value of function $f_2$ at the minimum found earlier. Both $f_1$ and $f_2$ are functions of the same variables $'x'$.

See Wikipedia: A-priori Optimization for more details.

I want to prove that the point where $f_2$ achieves it minimum, say $x_2^*$, will not be in general the optimal point of the constrained problem above. It seems obvious and intuitive but how does one prove it?

How does one in general prove that a point is not the minimum point of a constrained optimization problem and we can do better (find a point with lower function value)? I tried using KKT conditions to show that the point $x_2^*$ does not satisfy them and hence would not be an optimum point but couldn't get to the final conclusion. Could gradient based methods be used here? Even though it is an constrained problem.


1 Answer 1


If you can show that for any two functions $f_1$ and $f_2$ you can find a point, say $\tilde{x} \neq x_2^{*}$, such that $f_1(\tilde{x}) \leq f_1(x_2^{*})$, then you basically have shown that $x_2^{*}$ is not (in general) the optimal point of the problem.


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.