Formulation of Optimizer Problem

[Test User]

Hi,

I am attempting to use the optimizer command to pre-build my model but I seem to be having some issues with the solution not obeying the constraints. I may have called the function incorrectly.

Any help would be greatly appreciated.

yalmip('clear')
options = sdpsettings('solver','sedumi');

n = 2;
S = sdpvar(n, n, 'full');
t = sdpvar(1, n);
x = sdpvar(1, n);

Constraints = [x*S*x' <= 1, x >= 0.1, x <= 0.9];
Objective = -x*t';
P = optimizer(Constraints, Objective, options, {S, t}, x);

Then calling the model object,

S_a = [1.0, 0.5; 0.5, 1.0];
T = [1.0, 1.0];
P({S_a, T})

gives the solution,

[0.90, 0.90]

which does not satisfy the first constraint.

Calling optimize directly does seem to work fine,

optimize([x*S_a*x' <= 1, x>= 0.1, x <= 0.9], -x*T', options)
value(x)
ans = [0.5774, 0.5774]

Where have I gone wrong? Thank you.

[Test User]

Forgot to say,

yalmip('ver') = '20190425'

[Johan Löfberg]

The structure of the model cannot change. in your case it goes from an elementwise constraint, to a quadratic constraint that would require an SOCP once sedumi is supposed to be called. Hence, write it as an socp to begin with, i.e effectively norm(R_a*x) <=1 if you don't want to use low-level cone operator

[Test User]

Thank you very much for your reply Johan. Your advice has certainly helped me return a solution from the optimizer object.

By modifying the above such that,

Constraints = [norm(x*S,2) <= 1, x >= 0.1, x <= 0.9];

I now find that both

P({S_a, T})

and

optimize([norm(x*S_a,2) <= 1, x >= 0.1, x <= 0.9], -x*T', options)

return the same solution of,

[0.4714, 0.4714]

However, this is not the same as the solution returned by the previously mentioned,

optimize([x*S_a*x' <= 1, x>= 0.1, x <= 0.9], -x*T', options)

I apologise if I have missed something trivial, thank you again.

[Johan Löfberg]

you have now parameterized the problem in terms of a factor of S, hence, you should not call it S but, e.g., R as I did. And then you call the optimizer object with a factor of S (such as cholesky)

[Test User]

Thank you for both your time and advice. You are absolutely correct, my constraints set should have been modified to

norm(x*L,2) <= 1

where L is the lower triangular Cholesky decomposition of the symmetric matrix S_a.

This now works as expected,

P({chol(S_a,'lower'), T})

Where one to wish to extend the objective function to include an additional, either L1 or L2, norm term such as:

L = sdpvar(n, n, 'full');

t = sdpvar(1, n);
x = sdpvar(1, n);

b = sdpvar(1, n);

Constraints = [norm(x*L,2) <= 1, x >= 0.1, x <= 0.9];
Objective = -x*t' + norm(x - b, 1);
P = optimizer(Constraints, Objective, options, {L, t, b}, x);

would the above be your prefered method of implementation or would there be a numerically faster approach to solving the problem? What if instead the norm were a Euclidean norm instead?

Thank you once again.

[Johan Löfberg]

1-norm is LP-representable, but requires many more variables and constraints. Which one which leads to the fastest solve is up to the solver

If performance really is of absolute performance, you would not use a general solver for this problem, but a dedicated implementation