13
$\begingroup$

I have a constraint that I believe to be convex and not affine which I think means that I can implement a relaxation. I will first define the full constraint, and then build up my (informal) reasoning as to why I think it's convex. Hopefully the holes in my thinking can be pointed out and corrected.

$$ X_{t} = \frac{ Y_{t-1}^2 }{Y_{t-1}^2 + a^2}Z_{t-1}, \quad t=1,2,\dots,T \tag1 $$ $$ X_t,Y_t,Z_t \ge 0, $$ $$ X_0, Y_0, Z_0, \alpha \gt 0 $$

Argument 1: A quadratic polynomial is convex, so if the constraint was simply $ X_{t} = Y_{t-1}^2$ then the constraint would be convex.

Argument 2: By a similar extension, $ X_{t} = Y_{t-1}^2 + \alpha^2 $ would be convex.

Argument 3: The ratio of two convex functions, call it $F_{t-1}$, should also be convex.

Argument 4: If $F_{t-1}$ is convex, then multiplying $F_{t-1}$ by a continuous linear variable would not impose any non-convexity issues.

Conclusion: The original constraint is convex but not affine and as such we can apply a relaxation to change the problem into:

$$ X_{t} \le \frac{ Y_{t-1}^2 }{Y_{t-1}^2 + a^2}Z_{t-1}, \quad t=1,2,\dots,T \tag1 $$

$\endgroup$
  • $\begingroup$ Even though your argument is not correct, there is still a possibility to obtain a convex formulation. You could substitute all your $X_t$ variables using the equality constraints that you showed us. If you are (really) lucky, it might be that your problem is convex after the substitutions. $\endgroup$ – Kevin Dalmeijer Oct 16 '19 at 3:20
18
$\begingroup$

Arguments 3 and 4 are incorrect. The Right-Hand Side (RHS) is not convex. Even if it were, setting a nonlinear equality with either side non-affine is non-convex. As the final coup de grace, even if the RHS were convex, an inequality, {affine expression} $\le$ {convex RHS}, is going the wrong direction to be convex.

I suggest you study sections 2.3 and especially 3.2, both named "Operations that preserve convexity" of Convex Optimization, by Boyd and Vandenberghe which is freely available at the linked website of one of the authors.

$\endgroup$
  • 3
    $\begingroup$ Thank you for the resource! Always appreciate your guidance on the forums. $\endgroup$ – GrayLiterature Oct 15 '19 at 16:57
  • $\begingroup$ Boyd also recommends (jokingly?) to work on this problem in two ways, simultaneously: While you try to prove convexity on paper, you run a program that samples two random points, and checks the convexity of the function at their midpoint, potentially providing a counter-example. $\endgroup$ – Robert Schwarz Oct 16 '19 at 8:41
13
$\begingroup$

Counterexamples to your arguments:

Argument 1: Only affine equality constraints are convex, $x = y^2$ is not convex.

Argument 3: Take $f(x) = x^4$ and $g(x) = x$. Both are convex, but the ratio $h(x) = \frac{x^4}{x} $ is not.

Argument 4: Let $f(x) = x$, and $y \in \mathbb{R}$. $f$ is convex, but $g(x, y) = yf(x) = xy$ is not.

$\endgroup$

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.