3
$\begingroup$

For the following function, I am testing the convexity in $\lambda$. All parameters are in $\mathbb{R}^+$.

$$\frac{\left(- \lambda \left(b + \frac{p}{\beta}\right) + 1\right) \left(\left(1 + \frac{p}{\beta}\right) \left(b^{2} \lambda^{2} + \frac{2 b \lambda^{2} p}{\beta} + \frac{2 \lambda^{2} p}{\beta^{2}}\right) + \left(2 b \lambda \left(1 + \frac{p}{\beta}\right) + 2 \lambda p \left(\frac{1}{\beta} + \frac{1}{\beta^{2}}\right)\right) \left(- b \lambda + 1 - \frac{\lambda p}{\beta}\right)\right)}{2 \left(1 + \frac{p}{\beta}\right) \left(- b \lambda + 1 - \frac{\lambda p}{\beta}\right)^{2}}$$

I used Sympy to see the second derivative with respect to $\lambda$ as follows.

$$- \frac{\beta \left(b^{2} \beta^{2} + 2 b \beta p + 2 p\right)}{b^{3} \beta^{3} \lambda^{3} - 3 b^{2} \beta^{3} \lambda^{2} + 3 b^{2} \beta^{2} \lambda^{3} p + 3 b \beta^{3} \lambda - 6 b \beta^{2} \lambda^{2} p + 3 b \beta \lambda^{3} p^{2} - \beta^{3} + 3 \beta^{2} \lambda p - 3 \beta \lambda^{2} p^{2} + \lambda^{3} p^{3}}$$

Since there are lots of terms, it is not easy to understand whether it is $\geq 0$ or not. I set some values for $b$, $\beta$, and $p$ to see how it goes. When $p$ is very small (e.g., $p=0.00001$), $\beta = 0.021$, and $b=0.0021$, it seems to be convex. But, is there any way to make sure convexity (if true) without setting values to other parameters?

Update:

I also have a condition for the domain of the parameters: $\frac{\lambda \left(b + \frac{p}{\beta}\right)}{1 + \frac{p}{\beta}}<1$.

Update2:

Based on the answer, I minimized the second derivative subject to non-negativity constraint and the condition with the following code.

from pyomo.environ import *

m= ConcreteModel('Convexity')

m.lmbda = Var(domain=NonNegativeReals)
m.beta = Var(domain=NonNegativeReals)
m.b = Var(domain=NonNegativeReals)
m.p = Var(domain=NonNegativeReals)

m.OBJ = Objective(expr = (-m.beta*(m.b**2*m.beta**2 
+ 2*m.b*m.beta*m.p + 2*m.p)/
                         (m.b**3*m.beta**3*m.lmbda**3 - 
                        3*m.b**2*m.beta**3*m.lmbda**2 + 
                          3*m.b**2*m.beta**2*m.lmbda**3*m.p + 
                        3*m.b*m.beta**3*m.lmbda 
                        - 6*m.b*m.beta**2*m.lmbda**2*m.p 
                        + 3*m.b*m.beta*m.lmbda**3*m.p**2 
                          - m.beta**3 + 3*m.beta**2*m.lmbda*m.p 
                        - 3*m.beta*m.lmbda**2*m.p**2 + m.lmbda**3*m.p**3)), 
                        sense=minimize)

def Traffic(m):
    return ((m.lmbda*(m.b+m.p/m.beta))/(1+m.p/m.beta) <= 0.99999999999)

m.AxbConstraint = Constraint(rule=Traffic)

opt = SolverFactory('ipopt', tee=True)
print(opt.solve(m))

The output log and the objective value is as follows:

Problem: 
- Lower bound: -inf
  Upper bound: inf
  Number of objectives: 1
  Number of constraints: 1
  Number of variables: 4
  Sense: unknown
Solver: 
- Status: ok
  Message: Ipopt 3.11.1\x3a Optimal Solution Found
  Termination condition: optimal
  Id: 0
  Error rc: 0
  Time: 0.18944215774536133
Solution: 
- number of solutions: 0
  number of solutions displayed: 0

Objective Value: 3.302498039268864e-09
$\endgroup$

1 Answer 1

5
$\begingroup$

Proving convexity is a global optimisation problem. In this case you are fortunate in that there is only one variable in your function so you can get the second derivative analytically.

The practical way to get an answer for this is to define ranges for all your parameters (which will now be variables), and solve the second derivative formula as a global optimisation problem, subject to your parameter constraint.

Any decent global optimisation solver should solve this instantly - if the solution is greater than zero, you have your answer for that parameter range.

From a theoretical point of view, that function is only positive iff the denominator is negative, which is not true in general, but might be true for specific ranges of $\lambda$ and your parameters.

$\endgroup$
9
  • $\begingroup$ That is a good idea! Basically, I will minimize the second derivative subject to the constraint and the non-negativity. If the objective value is $\geq 0$, the function is convex. Otherwise (i.e., objective value is $-\infty$), the function is concave. If all I am saying is true, how can I know if this function is neither convex nor concave? $\endgroup$
    – tcokyasar
    Apr 23, 2020 at 1:14
  • $\begingroup$ Your convexity would be indeterminate if the second derivative curve crosses zero, i.e., it changes sign. So, $min(der2)>0$ for convexity, $max(der2) < 0$ for concavity, and $der2=0$ at a point that is neither stationary nor vertex to prove that it is neither. $\endgroup$ Apr 23, 2020 at 1:20
  • $\begingroup$ I updated the question with my implementation. There is one problem with this solution which is the 'strictly less than' condition. I had to relax this condition by replacing it with $\leq 0.99999999999$. When I used $\leq 1$ the obj. val. was $3.302498039269579e-09$ which is almost the same. Can you please help me with the interpretation of these findings? $\endgroup$
    – tcokyasar
    Apr 23, 2020 at 1:42
  • 1
    $\begingroup$ You need a global optimisation solver to be certain, because IPOPT might have simply converged to an infeasible point and your second derivative function will definitely be non-convex in the parametric space. If you want one that you can use for free, try COUENNE or our own Octeract Engine. $\endgroup$ Apr 23, 2020 at 2:07
  • 1
    $\begingroup$ Yep, that is correct, you showed that it changes sign! $\endgroup$ Apr 23, 2020 at 3:48

Your Answer

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

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