Convexity of cubic function in positive domain with some negative coefficients

684 Views Asked by At

Question: Is there a way to maintain convexity when multiplying a convex function with a positive variable, when some coefficients are negative? (at least in the positive domain?)

Goal: Find global optimium in reasonable time

Problem details:

I had a convex model (linear objective function with convex quadratic constraint and a vector of variables, $\boldsymbol{x} \in\mathbb{R_{++}^n}$, with constant upper bounds $\boldsymbol{ub_x}\in\mathbb{R_{++}^n}$) that solved fine, i.e. found the global optimum in reasonable time.

Then, I multiplied some terms (incl. variables) by another variable, $z \in\mathbb{R_{++}}$, and lost convexity of both objective function and constraint. $$ y, z, ub_z,const_i\in \mathbb{R}_{++}, \boldsymbol{x}, \boldsymbol{ub_x}, \boldsymbol{c_2}\in \mathbb{R}^n_{++}, \boldsymbol{c_1}\in \mathbb{R}^n, \boldsymbol{C}\in \mathbb{R}^{n\times n} $$ Constraints: $$ 0 \ge y - const_1 * z * \bigg(\frac{1}{2}*\boldsymbol{x^T}*\boldsymbol{C}*\boldsymbol{x}+\boldsymbol{c_1^T}*\boldsymbol{x}*const_2\bigg) $$ $$ z\le ub_z,\boldsymbol{x} \le \boldsymbol{ub_x} $$ $\boldsymbol{C}$ is negative definite, thus the quadratic part of the constraint (in parenthesis) is concave. Without multiplying by $z$ this would make the constraint convex (negative sign in front of parenthesis).

I understand that, since elements of $\boldsymbol{C}$ and $\boldsymbol{c}$ can be negative, geometric programming is not an option.

After introducing $z$, the constraint becomes cubic, but no univariate cubic term exists. Also, the constraint is no longer convex.

Objective function: $$ obj.var. = const_3 * z + const_4 * y + z*\boldsymbol{c_2^T} *\boldsymbol{x} $$ Before introducing $z$, the objective function was linear and thus, convex. With $z$ its Hessian is indefinite, thus no more convex.

Sorry for the lengthy question and thanks for all help!