DCP-compliant way to scale by sum(x)?


(Kaare Mikkelsen) #1

First, to hopefully demonstrate that I have done a lot of the groundwork already (at least as much as I was able), the following program already works:

lambda=0.1;

N=numel(b);

cvx_solver MOSEK
cvx_begin 
    variable x(N,1) binary
    minimize (lambda*(x'*A*x-Adiag'*x)-(1-lambda)*b'*X)
cvx_end

A is a positive semidefinite matrix, Adiag is the diagonal of A and b is a positive vector.
The above is a workable version of the problem, since by varying lambda I am able to weight the two terms differently. However, it annoys me that the first term (x’Ax) will grow (roughly) quadratically with sum(x), meaning that for most lambda-values, there will be a benefit to choosing x with many non-zero entries.
Is there a way to scale the first part of the objective with x, or something close to?

“(lambda*(x’Ax-Adiag’*x)/sum(x)-(1-lambda)*b’*X)” is convex (because x’Ax-Adiag’*x is convex, (1-lambda)*b’*X) is affine and sum(x) is concave), but I understand that it violates the no-product rule. Is there a way around this? I tried substituting with a scaled version of x (xScaled= x/sum(x)), which didn’t work, and neither does multiplying the second term by sum(x). Is there an accepted work-around?

I’ve already read through http://web.cvxr.com/cvx/doc/dcp.html and http://cvxr.com/cvx/doc/advanced.html, but I did not see an directly applicable suggestions?


(Mark L. Stone) #2

Presuming your input data is of the correct dimensions, then your objective function evaluates to a scalar and follows DCP rules, hence will be accepted by CVX.

As far as weighting terms, that is a modeling issue, not a CVX issue I have no idea what “real world” problem you are trying to solve, other than perhaps being a school assignment. You are responsible for modeling, but forum readers can help you reformulate your optimization problem to be accepted by CVX and to deal with other CVX issues.


(Kaare Mikkelsen) #3

I may have expressed myself in an unclear manner?

Indeed, the first bit of code is accepted by CVX, in fact it is running right now. I was including that part to avoid any questions regarding the properties of A, Adiag and b. The ‘original’ function is convex and DCP compliant.

The second one is also convex, but I understand that convexity does not guarantee DCP compliance.

I am asking whether there is a way to make the second function DCP compliant. In my experience, to solve issues such as this, one would have to explain what one is trying to accomplish, such that whoever is reading may be able to spot a different route to the goal. If I just wrote “how do I optimize (lambda*(x’ A x-Adiag’*x)/sum(x)-(1-lambda)*b’*X)”, then wouldn’t it be a lot harder for you (in case you actually wanted to help me, which it feels like you really don’t?) to understand what I’m trying to do, and what I have already done myself?

And why does the real world problem matter, if I can manage to express the issue in a relatively problem-independent manner? I would love for ‘forum readers to help me reformulate my optimization problem to be accepted by CVX’, that’s why I wrote the original question. I would think the discussion of my problem and any ultimate solution is a lot more useful to outsiders if the original question is not buried in unnecessary details about whatever real world problem prompted me to delve into this problem to begin with.


(Mark L. Stone) #4

If you don’t like the weighting of the terms in your objective function, that is a modeling issue.

If you have a convex optimization problem which you don’t know how to get accepted by CVX (or whether it can be accepted with a reformulation), that is a suitable topic for this forum.

If you have a convex program which is not accepted by CVX, then clearly show your code, preferably in a reproducible manner, complete with all input data. Make the problem dimensions small for illustrative purposes (for example, 3 by 1). So far, you showed one CVX code, which will be accepted presuming the inputs are of the correct dimensions.


(Kaare Mikkelsen) #5

OK, here is a minimal working example:

features=rand(100,10);
labels=round(rand(100,10));

temp=cov([features labels]);
A=temp(1:end-1,1:end-1);
Adiag=diag(A);
b=temp(1:end-1,end);

cvx_solver MOSEK

lambda=0.1;

N=numel(b);
% 
cvx_begin 
    variable X(N,1) binary
    variable Xscaled(N,1)
            minimize (lambda*(X'*A*X-Adiag'*X)/sum(X)-(1-lambda)*b'*X)
cvx_end

This returns the error:

Disciplined convex programming error:
    Cannot perform the operation: {convex} ./ {real affine}

It seems to be caused by the relationship between lambda*(X’AX-Adiag’*X) and 1/sum(X).
The function is on the form (convex-affine)/affine-affine, which means it is convex.
Is there a way to get this convex function accepted by CVX?


(Mark L. Stone) #6

convex/affine is not (necessarily) convex, and therefore neither is (convex-affine)/affine-affine.

Please read

Section 5.6 “Compositions” of CVX User’s Guide http://cvxr.com/cvx/doc/CVX.pdf

Section 3.2 “Operations that preserve convexity” of “Convex Optimization” by Boyd and Vandenberghe http://web.stanford.edu/~boyd/cvxbook/

Nowhere will you find a rule that convex/affine preserves convexity.

Given that X is a binary, perhaps there is some binary or integer modeling you can do to accomplish what you want - I don’t know.