I would like to write a constraint as follows, where $x,y>0$ are optimization variables, and $a,b,c,d,A$ are positive constants. How to make it a convex constraint?
\begin{equation} \frac{{ax}}{{\ln (b + cy)}} + dx \le A \end{equation}
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
3
The constraint is not convex, and is not transformable to a convex constraint without substantively changing it.
The additive linear term $dx$ is irrelevant to convexity. So let's ignore it and look at the simple case of $a = b = c = 1$. The Hessian of $\frac{{ax}}{{\ln (b + cy)}}$ at $x = y = 1$ has one positive and one negative eigenvalue. Hence $\frac{{ax}}{{\ln (b + cy)}}$ is neither convex nor concave. Therefore the constraint is not convex. In order for the constraint to be convex, that term would have to be convex, which it is not.
answered Jun 19, 2021 at 12:28
-
$\begingroup$ Thank you very much for your kind reply. The Hessian of the function you mentioned is calculated as follows:\begin{equation}\small \begin{aligned} \left[ \begin{array}{l} 0\\ - \frac{{ac}}{{{{\ln }^2}(b + cy)(b + cy)}} \end{array} \right. \left. \begin{array}{l} - \frac{{ac}}{{{{\ln }^2}(b + cy)(b + cy)}}\\ \frac{{a{c^2}x\left( {\ln \left( {cy + b} \right) + 2} \right)}}{{{{\ln }^3}\left( {cy + b} \right){{\left( {cy + b} \right)}^2}}} \end{array} \right] \end{aligned} \end{equation} $\endgroup$ Jun 20, 2021 at 17:49
-
$\begingroup$ From it we know this function is concave. However it is not a convex constraint. Am I right? $\endgroup$ Jun 20, 2021 at 17:49
-
1$\begingroup$ A constraint is convex if all points satisfying the constraint is a convex set of points. For example, constraining (x, y, z) to be within a cube is a convex constraint because all points satisfying the constraint is a solid cube and a solid cube is convex. I think he mean the function is not concave and is not convex. Therefore, the function can't be the boundary of a convex set of points. Think about a parabola that opens upward (f(x) = x^2). The function is convex. All points (x, y) satisfying y > x^{2} is a convex set of points and f(x) is the boundary of that set of points. $\endgroup$ Jun 20, 2021 at 18:02
$\begingroup$
$\endgroup$
23
Transform the optimizing variables $x$ and $y$ in everything (the whole model) to $u = \frac{ax}{\ln(b + cy)}$ and $v = x$
Transformed constraint $u + dv \le A$ is linear.
Therefore, the transformed constraint in terms of $u$ and $v$ is convex.
-
$\begingroup$ Disclaimer: I have never done anything like this before. Don't be surprised if I make any mistake. I would be happy if anyone point out the mistakes though. $\endgroup$ Jun 20, 2021 at 19:20
-
$\begingroup$ Thank you very much! Your insights give me a further understanding of convex and Hessian. I have a further question about positive definite of hessian matrix: the positive definite of hessian matrix is discussed over $p,q\in \mathcal{R^2}$, can we discuss the convexity of constraints over a restricted domain? Could you please show me any example, websites or papers which uses the similar idea? Many thanks! According to your comments, if domain of a,b,c,d and A as well as the domain of x and y satisfy the additional constraints you provided, the constraint is convex in the restricted domain? $\endgroup$ Jun 20, 2021 at 23:53
-
$\begingroup$ The idea of convexity of a function $f$ over an convex open set $S$ is from the "mathematical methods for economic theory" link. I think some subsets of $\mathbb{R}^{2}$ are convex sets (e.g. all points within a triangle or a square that is within $\mathbb{R}^{2}$. $\endgroup$ Jun 21, 2021 at 0:28
-
$\begingroup$ Many transformation can change the convexity of a set of points/constraints. For example, a cube is convex but if you deform it by punching it, the result is probably no longer convex. Deforming the space (as in relativity) has the same effect. Therefore, you can't talk about convexity without considering the optimizing variables (or the coordinate system). $\endgroup$ Jun 21, 2021 at 0:34
-
1$\begingroup$ The proposed solution won't work for at least two reasons. First, it assumes that $x$ and $y$ can be recovered from $u$ and $v$. If the solver chooses $u=2$ and $v=0$, good luck solving for $y$. Second, it ignores the presence of $x$ and $y$ elsewhere in the model. So the solver will choose values for $u$, $v$, $x$ and $y$ and there is nothing requiring the chosen values of $u$ and $v$ (or at least $u$) to conform to the chosen values of $x$ and $y$. $\endgroup$– prubin ♦Jun 21, 2021 at 21:06