Iterative programming

(saeed ) #1

I have an iterative program in which there are some initial points that have to be updated in each iteration. in each of the iterations several cvx scalar and vector variables should be derived and some of them should be used in next iteration as initial points. i have used for loop for iterations and the program has a process like below. unfortunately I do not get desired points and in the second iteration the program gives an error. because some variables go in wrong range. I wanted see if my program procedure is ok or not.

> cvx_solver sedumi
> for i=1:Nmax
>     cvx_begin
>     variables z tb te wb we akstar(K) betta q(K)
>     variable v(L-NE) complex
>     minimize z
>     ((we0(i))/log(2))+((we-we0(i))/(we0(i)*log(2)))-te<=z %constraint 1
>     landa(i)=betta0(i)/tb0(i);
>     sigma=0;
>     for ii=1:K
>         if ii~=kstar
>             teta(ii,i)=akstar0(ii,i)/tb0(i);
>             sigma=sigma+.5*teta(ii,i)*tb^2+.5/teta(ii,i)*akstar(ii)^2;
>         end
>     end
>     sigma+.5*sigma2*landa(i)*tb^2+.5*sigma2/landa(i)*betta^2+sigma2*tb-wb<=z %constraint 2
>     for jj=1:K
>         if jj~=kstar
>             quad_over_lin(A1(:,:,kstar,jj)*v,q(jj))-akstar(jj)<=z  %constraint 3
>         end
>     end
>     Qphi=sqrtm(phi(:,:,kstar));
>     for k=1:K
>         Qphi_k(:,:,k)=sqrtm(phi(:,:,k));
>     end
>     norm(Qphi*v)-betta<=z %constraint 4
>     inv_pos(q)<=Psk %39k
>     expression sum_F_el(L)
>     for l=1:L
>         sum_F_el(l)=0;
>         for k=1:K
>             sum_F_el(l)=sum_F_el(l)+quad_over_lin(A3(:,:,k,l)*v,q(k));
>         end
>         sum_F_el(l)+sigma2*norm(Esqrt(:,:,l)*v)<=Ql;% constraint 11
>     end
>     %determining initiAL POINTS FOR NEXT ItERATION shown by index 0(i+1)
>     tb0(i+1)=tb;
>     we0(i+1)=we;

akstar0(:,i+1)=akstar;
betta0(i+1)=betta;
q0(:,i+1)=q;

end

(Mark L. Stone) #2

Not all iterative processes converge at all, let alone to the answer of the problem you want… So perhaps yours doesn’t converge, or only converges for certain starting values (i.e., initial points in first iteration). Have you tried starting the iteration with different starting values?

If some variables are going in a “wrong” range, you can consider adding constraints to prevent them from going to the wrong range.

(saeed ) #3

Dear mark,
I have tried different starting values but the problem was similar for all considered values. first, if you read the written program, was the overall procedure a correct procedure? I mean considering cvx programming in a for loop and letting the output variables as initial points for next i (next iteration)? second, haw can I add constraints while all constraints are specified in the problem?

(Mark L. Stone) #4

I don’t see cvx_end. Did it get lost when you copy and pasted into your post? Is anything else missing?

What is sum_F_el used for? You set it in a for loop, but I don’t see where it is used to “do” anything in your CVX program…

Have you looked at the solution status and CVX variable values at the conclusion of the first iteration, including making sure that there are no NaN values? Perhaps you should add some error checking after cvx_end (wherever it is).

Your setting of akstar0 , betta0 , and q0 to the values from the just ended cvx execution looks correct, presuming that they come after cvx_end . And also of course, that none of the CVX variables came out as NaN .

This should not be considered to be a complete list.

(saeed ) #5

thank you very much
yes, I missed cvx_end while copying the program into the post. I copied a part of program to show the procedure. sum_F_el (l) is used in one of the constraints.

sum_F_el(l)+sigma2*norm(Esqrt(:,:,l)*v)<=Ql;% constraint 11

is it right if I add some constraints to keep some of the variables in the correct range?

(Mark L. Stone) #6

You have to determine what is “right”. If they are valid constraints, then it is right to add them. If they are not valid constraints, then you are solving some problem other than what you want if you add them.

I suppose it might be possible to add constraints to keep the iterations out of trouble, and then remove them from a confirmatory iteration if they are not really “valid” for your problem.

In any event, unless you have a proof for your problem, you have no guarantee that you will have found the global optimum, and may not have even found a local optimum at the conclusion of the iteration.

(saeed ) #7

Ok dear mark
thank you for your time and answers
I’ll try to use your advices and may ask some more questions if needed.
regards

(saeed ) #8

Dear mark,
what options do we have to correct an optimization problem output when the problem seems well organized but the output is ‘‘Nan’’?

(Mark L. Stone) #9

What status is reported by the solver and CVX? You should try to find out why you are getting NaN. For instance, is the problem declared infeasible by CVX? If so, you need to diagnose why.

(saeed ) #10

for some initial points the status is failed and optval is Nan and for some it is infeasible. but I checked the program and it is written correctly based on a given problem in a paper. is it right to writhe a constraint like x'*A*x as norm(sqrtm(A)*x) in the cvx. since the below error was given after writing the original form x'*A*x. x is cvx variable and A may be not positive definite

Undefined function 'vec' for input arguments of type 'double'.
Error in cvx/quad_form (line 43)
v = vec( v );
Error in cvx/mtimes (line 261)
            [ z2, success ] = quad_form( xx, P, Q, R );
(Mark L. Stone) #11

If A is not positive definite, you will have changed the constraint to a different constraint. Presuming you had a constraint x’ * A * x <= some_number , you will have “succeeded” in transforming it into a different constraint which is accepted by CVX.

Example.:
A = -1 (the one by matrix).
x’ * A * x <=1 is -x^2 <= 1, i.e., x^2 >= -1, which does not constrain x at all.
norm(sqrtm(A)*x) <= 1 is norm(x) <= 1 , i.e., -1 <= x <= 1 .
So in this example, use of sqrtm actually added (or tightened) a constraint from the original non-convex formulation.

One other approach (it might wind up being terrible), is to linearize the constraint by using a constant x_0 instead of one of the x ‘s in x’ * A * x, and set an initial value of x_0, then update with with the optimal value of x from the previous iteration.

There is no guarantee any of this will converge at all, let alone to the right answer. Some solvers might work better than others (or maybe not), and if it converges, maybe it;s on;ly for a narrow range of initial values. You can consider inquiring with the paper author for more details of exactly what was done in the paper, including exact data sets, initial values, software versions, etc. It may be that the algorithm is not very robust.

(saeed ) #12

Ok, thank you very much for your explanations