How to solve a minimization problem of conjugates?


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.


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


The whole code is actually very simple as follows.

%%% main.m %%%


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

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

%%% F.m %%%

function f = F(lambda)

n = length(lambda);

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

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



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 ?


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:

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.


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