8
$\begingroup$

Anyone have an idea for a disciplined convex programming (DCP) representation of the concave function $x\sqrt{1-x}$, which is defined over the domain $[0,1]$?

The Taylor series about $x=0$ is $$x - \frac{x^2}{2} - \frac{x^3}{8} - \frac{x^4}{16} + O(x^5),$$ which is DCP. However, I'm trying to find a DCP representation for the function itself, preferably.

$\endgroup$
1
7
$\begingroup$

I think in convex functions and epigraphs, so I hope you don't mind me deriving a DCP representation of the inequality $$t \geq -x \sqrt{1-x},$$

on $x \in (-∞, 1]$, which I rewrite to $$t \geq (1-x) \sqrt{1-x} - \sqrt{1-x} = r^{3/2} - r^{1/2},\quad r = 1-x \geq 0.$$

It should now be easy to input into your DCP framework. In MOSEK, it could be represented using two power cones: $$ t \geq p - q,\quad p \geq |r|^{3/2},\quad |q| \leq \sqrt{r}.$$

$\endgroup$
1
  • 1
    $\begingroup$ Nice, $t \ge r^{3/2} - r^{1/2}, r = 1-x \ge 0.$ should go right into CVX, CVXPY, and CVXR. This should be the answer accepted by the OP. $\endgroup$ Jan 3 '20 at 13:33
6
$\begingroup$

This is possible purely under DCP. As you are interested in the interval $[0,1]$, rewrite your function as $$x\sqrt{1-x}=\exp\left(\ln x+\frac12\ln(1-x)\right),\quad x\in[0,1].$$ Then the following code

import cvxpy as cp
x = cp.Variable()
y = cp.exp(cp.log(x) + 0.5 * cp.log(1 - x))
print("x * sqrt(1 - x) curvature:", y.curvature)

gives QUASICONCAVE as desired.

$\endgroup$
6
$\begingroup$

I don't think you can represent this as a concave function in the (cvxpy-)DCP sense:

import cvxpy as cp
x=cp.Variable()
a=x*cp.sqrt(1-x)
a.curvature

'UNKNOWN'

However, you can represent it using DQCP (disciplined quasiconvex programming):

import cvxpy as cp
x=cp.Variable(pos=True)
a=x*cp.sqrt(1-x)
a.curvature

'QUASICONCAVE'

$\endgroup$
4
$\begingroup$

Does this appear in a context in your program such that it can be replaced with a strictly monotonically increasing function of itself? For example, if it is the only term in the objective function, or the only term on the LHS of a LHS >= constant constraint.

If so, this can be handled as a weighted-geometric mean, which actually represents $(x\sqrt{1-x})^{2/3}$.

In CVX (the original DCP tool), this can be done using the geo_mean function, as follows:

cvx_begin
variable x
maximize(geo_mean([x;1-x],1,[2;1]))
<add any constraints>
cvx_end

Internally, this geo_mean formulation is handled by CVX in a manner similar to @TheSimpliFire 's answer.

help geo_mean
 geo_mean   Geometric mean.
    Y=geo_mean(X), where X is a vector, computes the geometrix mean of X. If any
    of the elements of X are negative, then Y=-Inf. Otherwise, it is equivalent
    to Y=PROD(X).^(1/LENGTH(X)). All elements must be real.
 
    For matrices, geo_mean(X) is a row vector containing the geometric means of
    the columns. For N-D arrays, geo_mean(X) is an array of the geometric means
    taken along the first non-singleton dimension of X.
 
    geo_mean(X,DIM) takes the geometric mean along the dimension DIM of X.
 
    geo_mean(X,DIM,W), where W is a vector of nonnegative integers, computes a
    weighted geometric mean Y = PROD(X.^W)^(1/SUM(W)). This is more efficient
    than replicating the values of X W times. Note that W must be a vector,
    even if X is a matrix, and its length must be the same as SIZE(X,DIM).
 
    Disciplined convex programming information:
        geo_mean is concave  and nondecreasing; therefore, when used in CVX
        specifications, its argument must be concave.

EDIT: @Henrik Alsing Friberg's subsequent answer is better than mine. I showed how to represent the stated function to the 2/3 power (which would only be useful in the circumstances I described), whereas he showed how to represent the function as stated in the question.

$\endgroup$
1
  • $\begingroup$ Thanks Mark - This is very helpful. I should have been more explicit in my post. I am actually looking for a variable transformation that will allow me to represent $f = \sum(y_i^3)/\sum(y_i^2\sqrt{1-y_i^2})$ as a quasiconvex function. I need to preserve convexity in the numerator and concavity in the denominator. Your suggestion is spot on and I had not considered using geo_mean. Introducing the change of variables that $z_i = y_i^3$ presents an affine numerator and allows the denominator to be represented as sum(geo_mean([z_i;z_i^(1/3)-z_i])), which is concave. Very helpful and thanks. $\endgroup$ Dec 31 '19 at 4:20

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.