Is it better to take the optimization variables from cvx and recompute the original non convex objective function instead of considering the cvx_optval

1

Hi,
I have non-convex maximization problem. I solved it using fmincon. I did convexification and solved it using cvx.
I compared fmincon output and cvx_optval. cvx_optval is higher than the objective value obtained from fmincon.

  1. Is this possible? I mean solving the approximated problem has to give lower values.
  2. Do I have to compare cvx_optval with fmincon output, or I have to compute the original objective function using the optimization variables obtained from cvx, then compare it with fmincon output?
    Note: cvx_optval is the value of the slack variable replacing the original objective function , as a part of the convexification.
2

The feasible set of a convexification is larger than the original, which means for a minimization problem the convexification would have lower value, for a maximization problem - higher.

cvx_optval should be equal to an objective you recompute yourself up to floating-point noise.

3

Thank you for your reply.
But you said that it will be higher, then you wrote that they have to be equal.
So I have not got the point here. I appreciate if you can clarify this. Below please find clarification of what i am doing.

The convex problem that I fed to cvx is :
P1: max t
subject to constraints

The original problem is
P2: max \sum (log2(1+f(x,y)) / \sum ( g(x,y))
subject to constraints

What I am getting from solving P1 using cvx are:

  • the cvx_optval which is the value of t
  • the original optimization variables x and y, and the slack variables that I added

What I am trying to do is to take x and y from cvx output and use them to recompute the objective function of P2

4

We must have confused ourselves about what you are asking.

Q1. After solving a CVX problem, does cvx_optval equal the objective value of that problem recomputed from variables? Yes.

Q2. Does a convexified optimization problem P1 have a higher objective value than the non-convex problem it relaxes P2. Yes.

Q3. Does the opt_value of the convexified problem P1 say anything about the objective in P2. No. P1 knows nothing about P2.

Of course there could be special cases where the convexified problem exactly recovers the optimal value of the non-convex original, but that is not a rule. That would depend on the details of what you are doing. Maybe you are not convexifying the problem in the classical sense I thought of, ie. forming a convex envelope, but just performing some other simple reformulation into a convex problem, in which case maybe it can be arranged so that they are equal. In any case it does not hurt to recompute the objective from scratch.

5

Thanks for your answer,
For Q1, No. This is my problem, is that cvx_optval which is the value of the slack variable t is not equal to the value I obtain, when I try taking all optimization variables from the output of cvx and inject them in my original non-convex objective function and recalculate it. The second value I get after recalculation is similar to the value I get from solving the original non convex problem using fmincon for example.

6

Then I think we agree. There is no reason why the optimal point of P1 should give the same optimal value in P1 and P2, as P1 is just a relaxation of P2.

I think maybe you would have to reveal the full problems with reproducible code to take this any further.