1
$\begingroup$

\begin{equation} \begin{split} \min_{x\in \mathbb{R}^n}\:f(x)=(1/2)x^{T}Q_0x+c_0^T x \end{split} \end{equation} s.t. $$ g_i(x)=\frac{1}{2}x^T Q_ix-lmax_i\leq0,i\in\{1,...,m/2\} $$ $$ g_i(x)=\frac{1}{2}x^T (-Q_i)x+lmin_i\leq0,i\in\{m/2,...,m\} $$ $$ h_j(x)=\frac{1}{2}x^T Q_jx+c_j^Tx+l_j=0,j\in\{1,...,m\} $$

Where all Q are sparse positive definite square matrices, for example, the first Q in constraint function is

\begin{equation} Q_1=2*sparse \begin{pmatrix} (1,1) & 1 & (1,4) & -1\\ (2,2) & 1 & (2,5) & -1\\ (3,3) & 1 & (3,6) & -1\\ (4,1) & -1 & (4,4) & 1\\ (5,2) & -1 & (5,5) & 1\\ (6,3) & -1 & (6,6) & 1\\ \end{pmatrix} \end{equation}

But note there are $-Q_i$ in the second inequality constraints, which makes it negative definite. So how does this affect the overall convergence, is there any way to treat it like a convex optimization problem since they are just so close?

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ Both the2nd and 3rd constraints make this problem highly nonconvex, and most likely hard. E.g., constraints of the form $x_i^2=1$ (which are a special case of your 3rd constraint) encode binary QPs ($x_i=\pm 1$), well known to be NP-hard in general... $\endgroup$
    – Suvrit
    Commented Jan 10, 2016 at 9:27
  • $\begingroup$ Thanks! But is there any difference between the constraints which has the form $x_i^2=1$ and the constraints which has the form $x_i^2+x_j^2=2$, 'cause the second form does not confine $x_i$ and $x_j$ within binary space anymore. And my third constraints are more like the second form.@Suvrit $\endgroup$
    – sjtupuzhao
    Commented Jan 10, 2016 at 13:08

0

Reset to default

You must log in to answer this question.