Opt. pb with "reciprocal" variable


(Mario Di Mauro) #1

Hi all…i’ve the following problem.
I’m trying to solve my opt. problem:

  cvx_begin;
    variable mou;
    minimize(sum(inv_pos(mou-lam)));
    subject to
    sum(inv_pos(mou))<=c;
    mou>lam;
 cvx_end

The problem is that i would that opt. variable could be 1/mou rather than mou. But, if i declare variable 1./mou, the code returns me an error.

So…if i pose t=1/mou and rewrite the optimization problem as:

  cvx_begin;
    variable t;
    minimize(sum(t.*inv_pos(lam-t))) 
    subject to
    sum(t)<=c
    lam.*t<1
cvx_end

the response is: “Cannot perform the operation: {real affine} .* {convex}”

Any help?


(Mark L. Stone) #2

The 2nd derivative of t/(lam - t) is 2*lam/(lam - t)^3 It is convex for values of t <= lam., So t*inv+pos(lam - t) is convex. But it can not be entered directly into CV as such because it is in violation of iis DCP rules.

I’m busy and lazy, so I’ll leave this for the wizard of conic reformulation, @Michal_Adamaszek, or another smart poster to handle.


(Mario Di Mauro) #3

thanks for your time Mark!
I don’t know about conic reformulation but, if you can give me some suggestions, i’ll try to deepen on my own.

P.s.: sorry for mistake…the obj fun is t/(1-lamt). But also in this case, we fall in the case you cited since the 2nd derivative is 2lam/(1-lam*t)^3 that is convex for t<=lam.

Mario


(Erling D.Andersen) #4

If we assume \lambda=1 and t\geq 0. Then define s=1-t. So the objective becomes

t/(1-t) = (1-s)/s=1/s -1

which works. The \lambda=1 can be achieved by changing the units of the variables. The t\geq 0 constraint seems to be needed.


(Mario Di Mauro) #5

Dear Erling, thanks for your intervention. Your proposal (variable change) seems to work even if the results are not in accordance with my expectation. I returned to my original problem (top of this post) by trying to minimize(sum(inv_pos(mou-lam)));

The problem is that, when i impose my constraint i observe a strange behavior (probably due to my scarce skill on cvx programming). Namely, the following two conditions that should be the same things, return different results.

  1. sum(inv_pos(mou))<=1/c;
  2. sum(mou)>=c;

Is there any reason?
Thx a lot.


(Erling D.Andersen) #6
  1. and 2) are NOT the same unless mou is a scalar. Can you prove they are the same?

(Mario Di Mauro) #7

i guess mou is a scalar (i declare it as mou and not as mou(n))


(Dinh) #8

If \mu is a scalar, there is no need for the sum in your obejctive function and constraints. Your objective function is then

\sum \frac{1}{\mu - \lambda} = \frac{1}{\mu - \lambda}

Then your problem is equivalent to

\min \frac{1}{\mu}

following the informal reasoning

\min \frac{1}{\mu - \lambda} = \max \mu-\lambda = \max \mu = \min \frac{1}{\mu} .

Your problem can thus be recast as a convex problem with the variable t, t = \mu^{-1}.


(Mario Di Mauro) #9

Hi! Yes, you’re right, the problem is vectorial with mu summing over an index.


(Dinh) #10

So if I understand well, your decision variable is finally a vector. Your problem is thus

\begin{array}{cl} \min_{\mu\in\mathbb{R}^n} & \sum_{i=1}^n \frac{1}{\mu_i-\lambda_i} \\ s.t. & \sum_{i=1}^n \frac{1}{\mu_i} \leq c \\ & \lambda_i < \mu_i \end{array}

If by any chance all your \lambda_i are positive, I can propose the following. Perform the change of variable t_i = 1/\mu_i, so that your problem is equivalent to

\begin{array}{cl} \min_{t\in\mathbb{R}^n} & \sum_{i=1}^n \frac{t_i}{1-\lambda_i t_i} \\ s.t. & \sum_{i=1}^n t_i \leq c \\ & 0 < t_i < 1/\lambda_i \end{array}

Introduce now the vector x, the problem is still equivalent to

\begin{array}{cl} \min_{t\in\mathbb{R}^n,x\in\mathbb{R}^n} & \sum_{i=1}^n x_i \\ s.t. & \sum_{i=1}^n t_i \leq c \\ & 0 < t_i < 1/\lambda_i \\ & 0 < x_i \\ & \frac{t_i}{1-\lambda_i t_i} \leq x_i \end{array}

that is (1-\lambda_i t_i and x_i being positive)

\begin{array}{cl} \min_{t\in\mathbb{R}^n,x\in\mathbb{R}^n} & \sum_{i=1}^n x_i \\ s.t. & \sum_{i=1}^n t_i \leq c \\ & 0 < t_i < 1/\lambda_i \\ & 0 < x_i \\ & \frac{t_i}{x_i} \leq 1-\lambda_i t_i \end{array}

Since the t_i are positive, this is equivalent to

\begin{array}{cl} \min_{t\in\mathbb{R}^n,x\in\mathbb{R}^n} & \sum_{i=1}^n x_i \\ s.t. & \sum_{i=1}^n t_i \leq c \\ & 0 < t_i < 1/\lambda_i \\ & 0 < x_i \\ & \frac{t_i^2}{x_i} \leq t_i-\lambda_i t_i^2 \end{array}

which is convex.

From a coding point of view, I think that quadoverlin understands that the x_i should be positive. And you might prefer the constraint 1/t_i < \lambda_i using invpos.


(Erling D.Andersen) #11

If

\begin{array}{cl} \min & \sum_{i=1}^n \frac{1}{\mu_i-\lambda_i} \\ s.t. & \sum_{i=1}^n \frac{1}{\mu_i} \leq c \\ & 0 \leq \lambda_i \lt \mu_i \end{array}

is your problem then I would write

\begin{array}{cl} \min & \sum_{i=1}^n t_i \\ s.t. & \sum_{i=1}^n s_i \leq c \\ & (t_i;\mu_i-\lambda_i;\sqrt{2}) \in Q \\ & (s_i;\mu_i;\sqrt{2}) \in Q \\ & \end{array}

where Q is the 3 dimensional rotated quadratic cone. It gets rid of the issue with strict inequalities.
I use

Q=\{x:\, 2x_1x_2 \geq \|x_{3:n}\|^2,\, x_1,x_2 \geq 0 \}

You can use the rotated_lorentz function to do this. Something along the lines

(1,t_i,\mu_i-\lambda_i) \in rotated\_lorentz(3)

See under sets at http://cvxr.com/cvx/doc/funcref.html

Finally your problem is a bit crazy since there is an optimal solution such that \lambda_1=\lambda_2= \dots and \mu_1=\mu_2= \dots.


(Mario Di Mauro) #12

Marc,
thanks for your detailed reply.
Unluckily, cvx returns me errors for the last constraint (even if I try to eliminate quadratic form).


(Mario Di Mauro) #13

Erling,
thanks for your reply.
I’ve to deepen cone programming because, actually, i’m not able to “translate” in cvx your suggestion!


(Dinh) #14

Well if you don’t give us details, we can’t help you.


(Erling D.Andersen) #15

Note my post has been updated.


(Mark L. Stone) #16

I think the following will work to implement @Erling’s suggestion:
{1,t_i,mu_i - lambda_i} == rotated_lorentz(1)
and similarly for the other rotated quadratic cones.

Note that the argument of rotated_lorentz should be the dimension of the first element on the left-hand side, which in this case is 1, which has dimension 1.


(Mario Di Mauro) #17

Marc Dinh,
cvx errors for the last constraint:
inv_pos(x)(t.^2) <= t-lambda.(t.^2); --> Error using *
Inner matrix dimensions must agree.

or, alternatively:
t <= x - (lambda.*t.*x); --> invalid quadratic form(s): not a square.


(Mario Di Mauro) #18

Dear Erling,
I’ve noticed your updated response.

I didn’t catch a thing (i know it’s my fault about scarce skills in cvx programming): after substitution t_i=1/(\mu_i - \lambda_i), how can i declare \mu_i and \lambda_i in the rotated Lorentz expression? You maybe mean (1,t_i, \mu_i - \lambda_i) = (1, t_i , 1/t_i) ?


(Mario Di Mauro) #19

Mark Stone, thanks for your support. I’m trying to interpret Erling’s suggestion since i cannot understand if mu_i and lambda_i have to be expressed in function of t_i or declared as variables.


(Mark L. Stone) #20

I’m not sure I know the d9imension of your problem. Presuming mu is an n byy 1 vector and lambda is an n by 1 input vector:

variables t(n) mu(n)
for i = 1:n
  {1,t(i),mu(i) - lambda(i)} == rotated_lorentz(1)
end

plus the rest of your program.