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