2
$\begingroup$

Is there a solution to find the global optimum of a convex function , subject to non convex constraints?

For example:

$\min x_1^2 + x_2^2$

subject to

$x_2 + x_1^2 \geq 2$

$x_2 - x_1^2 \leq 3$

constraints

It's only an example; I am looking for a general method to find the optimal point in any convex function with non-convex constraints

$\endgroup$
  • $\begingroup$ What inequality constraints define the feasible region? $\endgroup$ – Rodrigo de Azevedo Feb 20 '17 at 22:58
1
$\begingroup$

The two constraints here are actually both convex, which you can see by drawing out the shape and observing that circles (and lunes) are convex. Alternatively, you know that $x_1^2 + x_2^2$ is a convex function, so $(x_1 - 1)^2 + (x_2 - 1)^2$ is a convex function, and hence the inequality $(x_1 - 1)^2 + (x_2 - 1)^2 \leq 3$ is a convex region.

Also by drawing the regions out, you can see that the origin is included in the feasible set, and $(0, 0)$ clearly minimises $x_1^2 + x_2^2$, so the minimum is $0$.

$\endgroup$
  • $\begingroup$ I think i have chosen an incorrect example for my question, in general have can we solve a convext function subject to non-convex constraints? $\endgroup$ – Hojjatollah Bakhtiyari Kiya Feb 20 '17 at 20:23
  • $\begingroup$ @B.Mehta I disagree, the feasible region is not convex: If you draw a line segment between the bottom left "corner" and bottom right "corner", it passes through points that are not in the feasible set, therefore it is not convex. $\endgroup$ – Kuifje Feb 20 '17 at 23:20
  • $\begingroup$ @Kuifje The feasible region was originally the intersection of two circles, but has since been edited to a non-convex set, I agree. $\endgroup$ – B. Mehta Feb 20 '17 at 23:33
  • $\begingroup$ @B.Mehta: all righty then ! $\endgroup$ – Kuifje Feb 20 '17 at 23:49
  • $\begingroup$ @B.Mehta I changed the constraints to show that, I am not looking for the current problem's solution. I Only want to know if there exist a solution for non-convex constraints . $\endgroup$ – Hojjatollah Bakhtiyari Kiya Feb 21 '17 at 3:44

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.