Maximizing linear function over convex set


(Mtuk) #1

Given a convex function cost(x), we wish to solve the following:
cvx_begin quiet
cvx_precision best
variables x(d) c(d)
maximize(x’ * c)
subject to
cost(x) <= 1;
c <= ones(2,1);
-ones(2,1) <= c;
cvx_end

However the following fails and the error is given by the following statement:

Error using cvx/quad_form (line 230)
The second argument must be positive or negative semidefinite.

Error in * (line 261)
[ z2, success ] = quad_form( xx, P, Q, R );

My intentions is to find a point which cost(x) = 1 and my wish is to maximize the l1 norm of such point, i.e. find the point with maximal l1 norm such that cost(x) == 1.

Is there any way to fix this? Can it be done?

Please do advise and thanks in advance.

P.s. For simplicity, let cost(x) = norm(P*x,2) where P is nxd matrix.


(Mark L. Stone) #2

The error message is from taking the inner product of two CVX variables, which is a non-convex objective, not a linear objective. If you can;t overcome this, then CVX is not an appropriate tool for your model.

The constraint norm(Px,2) <= 1 would be o.k., but norm(Px,2) == 1 is non-convex and would be rejected by CVX.

I don;t see an l1 norm of x being maximized, unless you’re trying to do some dual norm thing, in which case I don’t think you have it right. Maximizing an l1, or any other, norm is non-convex, and therefore not possible in CVX unless you can accomplish it using binary or integer variables to handle the non-convexity.