Given $\min \{a^Tx\mid x^TQx+2b^Tx+c\leq0\}$ and $Q\succ0$ find conditions for $Q,b,c$

226 Views Asked by At

Given $\min \{a^Tx\mid x^TQx+2b^Tx+c\leq0\}$ and $Q_{n\times n}\succ0,b\in\mathbb{R}^n,c\in\mathbb{R},a\in\mathbb{R}^n\backslash\{0\}$

  1. find conditions for $Q,b,c$ for which the problem is feasible
  2. find conditions for $Q,b,c$ for which KKT conditions are suffices
  3. find conditions for $Q,b,c$ for which KKT conditions are necessary

I thought maybe to look at $2b^Tx+c\leq0$ because $Q$ is positive but couldn't get more conditions from this inequality

2

There are 2 best solutions below

6
On BEST ANSWER

Let's check feasibility, the problem is infeasible only if, $$\ g(x) = x^TQx + 2b^Tx + c>0 \ \forall x $$ You can easily check $g(x) = x^TQx + 2b^Tx +c$ is convex. Let $x^*$ be the minima. For the problem to be feasible we need $g(x^*) \leq 0$. $$\ \nabla g(x^*)=2Qx +2b=0 \implies x^*=-Q^{-1}b $$ Setting $g(x^*)\leq0$, we get, $$\ c-b^TQ^{-1}b \leq 0 $$ Hence, we have this upper-bound on $c$ for the problem to be feasible. Note that we have assumed $Q$ to be a symmetric matrix. In case if its not, you can always replace $Q$ by $\frac{1}{2}(Q^T+Q)$. This won't change anything.

Since, both the objective and constraints are convex. KKT conditions suffice. But are they necessary? Can you figure it out?

Hint1: Are there points which violates the regularity conditions?
Hint2: Do we need $g(x^*) < 0$ for KKT?

0
On

Hint

Define $P={Q+Q^T\over 2}$. Then $P=P^T\succ 0$ and $$x^TPx=x^TQx$$also since $P=P^T$, Cholesky decomposition can be defined for it as $$P=LL^T$$where $L\succ 0$ is lower-triangular. By substitution we obtain $$x^TQx+2b^Tx+c=x^TLL^Tx+2b^T\underbrace{(L^T)^{-1}L^T}_{I}x+c$$which by defining $y=L^Tx$ and $b_1=L^{-1}b$, reduces to $$x^TQx+2b^Tx+c=y^Ty+2b_1^Ty+c=||y+b_1||^2+c-b_1^Tb_1$$ where $$b_1^Tb_1=b^T(L^T)^{-1}L^Tb=b^T(LL^T)^{-1}b=b^TQ^{-1}b$$Finally, your optimization problem is equivalent to this one: $$ {\min a^T(L^T)^{-1}y \\ \text{s.t.} \\ ||y+b_1||^2<b^TQ^{-1}b-c } $$

Remark

KKT conditions are sufficient only if the problem is convex.