How to solve a minimization problem of conjugates?


#1

I would like to solve a minimization problem of convex conjugates defined by the well-known Legendre-Fenchel transformation.

For example, a simple problem can be given as:

Minimize w.r.t. lambda Maximize w.r.t. x : lambda’x - 1/2norm(x)^2
subject to some interval constraint of lambda : a <= lambda <= b

This is actually a convex program w.r.t. lambda because the function of lambda:
"Maximize w.r.t. x : lambda’x - 1/2norm(x)^2 "
is the conjugate of quadratic functions, whose closed form is exactly given as 1/2*norm(lambda)^2.

However, CVX returns the error:
cvx/quad_form (line_230)
The second argument must be positive or negative semidefinite.

Is there any possible way to avoid this error?


(Mark L. Stone) #2

This is confusing. Is x CVX variable? If so, you can write the 2nd term of the objective function as
-0.5 * sum_square(x)
If not, it can be eliminated from the problem, unless it comes into play somewhere you haven’t shown.
If lambda and x are both CVX variavbles,
lambada' * x
is a non-convex (indefinite) term which will not be accepted by CVX.


#3

I am sorry that my explanation regarding that is insufficient.
Actually, both lambda and x are CVX variable, but the whole program consists of the nest of two convex programs as follows.

The first one is:
Minimize F(lambda) subject to a <= lambda <= b

In this program, “lambda” is only the CVX variable.

Here, the function F(lambda) comes from the result of another convex program:
Maximize lambda’x - 1/2norm(x)^2

In this program, “x” is the only CVX variable while “lambda” is dealt with as a constant.

The second program corresponds to the Legendre-Fenchel transformation, which yields the convex function w.r.t. “lambda”.
In this case, its closed form is given as F(lambda)=1/2*norm(lambda)^2.

But, in a general case (i.e., the convex function “1/2*norm(x)^2” is replaced with a general convex function of “x”), such a closed form cannot be written down though the resultant
F(lambda) = max (w.r.t. x) lambda’*x - G(x)
is always convex w.r.t. lambda, where G(x) is a given convex function w.r.t. x.

In fact, the second program is successfully solved by CVX, where “lambda” is considered as a constant.
However, the first program cannot run due to the above error.


(Mark L. Stone) #4

You are still leaving too much to the imagination. Please show the complete MATLAB and CVX code for everything


#5

The whole code is actually very simple as follows.

%%% main.m %%%

clc;

n=1;
A = [eye(n); -eye(n)];
b = [1ones(n,1); 1ones(n,1)];

cvx_begin
variable lambda(n);
minimize( F(lambda) );
subject to
A*lambda <= b;
cvx_end

%%% F.m %%%

function f = F(lambda)

n = length(lambda);

cvx_begin
variable x(n);
maximize (lambda’*x - 0.5 * sum_square(x));
cvx_end

optx = x;
optf = lambda’*optx - 0.5 * sum_square(optx);

f=optf;
end

%%%%%%%%%%%%%%%%%%%%%

main.m solves the first convex program.
F.m solves the second, which gives the convex function w.r.t. lambda.

In this simple case, the function “F.m” returns the value of 0.5*sum_square(lambda).


(Mark L. Stone) #6

Have you read http://web.cvxr.com/cvx/doc/advanced.html#new-functions-via-partially-specified-problems ?


#7

Yes, I know and read the partial minimization, but the Legendre-Fenchel transformation is different from it:

I found that CVX cannot accept the term “lambda’*x” which can be evaluated as a nonconvex bilinear term:
http://web.cvxr.com/cvx/doc/dcp.html#scalar-quadratic-forms

I think the CVX in general cannot accept the Legendre-Fenchel transformation due to this operation…


(Mark L. Stone) #8

Wait for mcg to come along and see what he says. He should know one way or another.


(Michael C. Grant) #9

I’m afraid you’re trying to be more clever with CVX than it was designed to be. There are many constructs, conjugates among them, that cannot be represented according to DCP rules.


#10

Thank you for your reply. I’ll try to find another way to do it.