# 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:
The second argument must be positive or negative semidefinite.

Is there any possible way to avoid this error?

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.

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 %%%

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).

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: