Expressing an inequality constraint as a linear matrix inequality (LMI)

Question

I am trying to formulate an optimization problem as a semidefinite program (SDP). My optimization variable is $\mathbf x = [x_1, x_2, \dots, x_N]'$, where $\mathbf x$ is an $N \times 1$ vector, and one of my constraints is

$$\prod_{i=1}^{N} x_i \ge a$$

Can I express this inequality constraint as a linear matrix inequality (LMI)?

Answer 1

Yes, assuming the variables are non-negative, you can write this using a collection of LMIs, or even better/easier/more efficiently, as collection of second-order cone constraints. Using a modelling language such as cvx or YALMIP, you would typically implement this using a geometric mean operator (here the YALMIP version)

x = sdpvar(N,1);
Model = [geomean(x) >= a^(1/N)]

The basic idea is to recursively use constraints of the type $t^2 \leq y_1y_2$ which is SOCP-representable (and thus trivially LMI-representable) in a recursive fashion. As an example, $t \leq (x_1 x_2 x_3 x_4)^{1/4}$ can be written as $t^4 \leq x_1x_2x_3x_4$ which can be written as $t^2 \leq t_1 t_2$, $t_1^2 \leq x_1x_2, t_2^2\leq x_3x_4$ by introducing new variables. For vectors $x$ of length not a power of 2, the vector is padded with ones, and the strategy is applied.

For the (nasty) details, I recommend

Second-order cone programming. F. Alizadeh and D. Goldfarb. Mathematical Programming (Series B), 95(1):3-51, 2003