0
$\begingroup$

Why do we have to have Quasi-convex Constraints for constrained maximisation? I think i'm missing something pretty simple as this feels like a basic question:

My current Logic: If both the objective function and constraint are Quasi-concave then:

  1. The optimal point still occurs where the gradients are a scalar of one another.
  2. When we increase our value of F, we are still increasing the value of G, so are constraint is meaningful.
  3. The objective function is still quasi-concave so we have a maximum.

Issues:

  1. Our feasible set i.e $G(\mathbf{x}) \le b$ is no longer convex... I guess i don't intuitively understand why this is an issue?

Example Diagram: I am just illustrating to myself, that we can still move along the contour of G, while increasing F, to reach an optimal point at the tangency. enter image description here

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

Consider the maximisation problem : $$\max_x f(x) \text{ s.t. } g(x) \leq c$$ Note that

  • If $f$ is quasi-concave and $g$ is quasi-convex, then the set of solutions to the above problem is either an empty or a non- empty convex set.
  • If $f$ is continuous, and $g(x) \leq c$ yields a compact constraint set then the solution set is non-empty.

For example:

  • $\displaystyle\max_{(x,y)\in\mathbb{R}^2_+} x+y \text{ s.t. } \sqrt{x} + \sqrt{y} \leq 1$. Herę $\sqrt{x} + \sqrt{y}$ is not quasi-convex and the set of solutions to the given problem is $\{(1,0), (0,1)\}$ which is not a convex set.
Improve this answer
$\endgroup$
5
  • $\begingroup$ Hi Amit, good to see you again so soon! Thanks for providing another answer, I'm not too clear on this one....With your final example you provide a solution which is not a convex set. But why do we need it to be a convex set? I'm still not clear intuitively what goes wrong if we have both a concave constraint and a concave objective function? $\endgroup$
    – CormJack
    Commented Feb 14, 2023 at 19:14
  • 1
    $\begingroup$ Consider the following modified problem: $\displaystyle\max_{(x,y)\in\mathbb{R}^2_+} 2x+y \text{ s.t. } \sqrt{x} + \sqrt{y} \leq 1$. This problem has a unique solution which is $(1,0)$. However, $(0,1)$ is also a "local" optimum i.e. If you're at $(0,1)$ and you try to move along the constraint boundary, the value of the objective will fall initially. So local optimality does not guarantee optimality. $\endgroup$
    – Amit
    Commented Feb 15, 2023 at 0:27
  • $\begingroup$ However if $f$ is quasi concave and $g$ is quasi-convex, local optimality guarantees optimality. This is certainly a desirable property if you want to write efficient programs to determine optimal solutions. $\endgroup$
    – Amit
    Commented Feb 15, 2023 at 0:27
  • $\begingroup$ I see, so we need it as a second oder condition to ensure globally? So we can still find local optimums if both constraint and objective function ore concave (or both convex) but we won't be assure that this is a global optimum? correct? Thanks for the input! $\endgroup$
    – CormJack
    Commented Feb 27, 2023 at 15:00
  • 1
    $\begingroup$ We need to compare all the local optimums to determine the global optimum in cases where either $f$ is not quasi-concave or $g$ is not quasi-convex. $\endgroup$
    – Amit
    Commented Feb 28, 2023 at 21:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.