Skip to main content
formatting, added tag
Source Link
YCor
  • 63.9k
  • 5
  • 187
  • 286

Solution to a Quadratically Constrained Quadratic Program (QCQP)quadratically constrained quadratic program with unit ball constraint

I am working on a Quadratically Constrained Quadratic Programquadratically constrained quadratic program (QCQP) of the form:$$ \min_{x} \quad \frac{1}{2} x^T P x + q^T x + r$$ $$ subject\ to \qquad x^{T}x \leq 1 $$$$ \text{subject to} \qquad x^{T}x \leq 1 $$

where $P \in S^{++}_{n}$ is a symmetric positive definite matrix, and $q \in \mathbb{R}^{n}$ is a given vector. I aim to show that the optimal solution $x^{*}$ satisfies:$$ x^{*}=-(P+ \lambda I)^{-1}q$$ where $ \lambda$ =$max\{ 0,\bar{\lambda}\}$$\max\{ 0,\bar{\lambda}\}$ and $\bar{\lambda}$ is the largest solution to the nonlinear equation:$$q^{T}(P+\lambda I)^{-2}q=1 $$ I tried solving this by using the necessary and sufficient conditions for the optimal solution:$$ x \ is \ optimal \ if \ and \ only \ if \ x \in X \ and \\ \nabla f_0(x)^T (y - x) \geq 0 \quad \text{for all} \quad y \in X. $$$$ x \text{ is optimal if and only if } x \in X \text{ and} \\ \nabla f_0(x)^T (y - x) \geq 0 \quad \text{for all} \quad y \in X. $$ But I wasn't able to make progress.Is there an alternative approach to solve this problem, or any hints on how to use the optimality conditions more effectively? Any suggestions would be greatly appreciated!

Solution to a Quadratically Constrained Quadratic Program (QCQP) with unit ball constraint

I am working on a Quadratically Constrained Quadratic Program (QCQP) of the form:$$ \min_{x} \quad \frac{1}{2} x^T P x + q^T x + r$$ $$ subject\ to \qquad x^{T}x \leq 1 $$

where $P \in S^{++}_{n}$ is a symmetric positive definite matrix, and $q \in \mathbb{R}^{n}$ is a given vector. I aim to show that the optimal solution $x^{*}$ satisfies:$$ x^{*}=-(P+ \lambda I)^{-1}q$$ where $ \lambda$ =$max\{ 0,\bar{\lambda}\}$ and $\bar{\lambda}$ is the largest solution to the nonlinear equation:$$q^{T}(P+\lambda I)^{-2}q=1 $$ I tried solving this by using the necessary and sufficient conditions for the optimal solution:$$ x \ is \ optimal \ if \ and \ only \ if \ x \in X \ and \\ \nabla f_0(x)^T (y - x) \geq 0 \quad \text{for all} \quad y \in X. $$ But I wasn't able to make progress.Is there an alternative approach to solve this problem, or any hints on how to use the optimality conditions more effectively? Any suggestions would be greatly appreciated!

Solution to a quadratically constrained quadratic program with unit ball constraint

I am working on a quadratically constrained quadratic program (QCQP) of the form:$$ \min_{x} \quad \frac{1}{2} x^T P x + q^T x + r$$ $$ \text{subject to} \qquad x^{T}x \leq 1 $$

where $P \in S^{++}_{n}$ is a symmetric positive definite matrix, and $q \in \mathbb{R}^{n}$ is a given vector. I aim to show that the optimal solution $x^{*}$ satisfies:$$ x^{*}=-(P+ \lambda I)^{-1}q$$ where $ \lambda$ =$\max\{ 0,\bar{\lambda}\}$ and $\bar{\lambda}$ is the largest solution to the nonlinear equation:$$q^{T}(P+\lambda I)^{-2}q=1 $$ I tried solving this by using the necessary and sufficient conditions for the optimal solution:$$ x \text{ is optimal if and only if } x \in X \text{ and} \\ \nabla f_0(x)^T (y - x) \geq 0 \quad \text{for all} \quad y \in X. $$ But I wasn't able to make progress.Is there an alternative approach to solve this problem, or any hints on how to use the optimality conditions more effectively? Any suggestions would be greatly appreciated!

Source Link

Solution to a Quadratically Constrained Quadratic Program (QCQP) with unit ball constraint

I am working on a Quadratically Constrained Quadratic Program (QCQP) of the form:$$ \min_{x} \quad \frac{1}{2} x^T P x + q^T x + r$$ $$ subject\ to \qquad x^{T}x \leq 1 $$

where $P \in S^{++}_{n}$ is a symmetric positive definite matrix, and $q \in \mathbb{R}^{n}$ is a given vector. I aim to show that the optimal solution $x^{*}$ satisfies:$$ x^{*}=-(P+ \lambda I)^{-1}q$$ where $ \lambda$ =$max\{ 0,\bar{\lambda}\}$ and $\bar{\lambda}$ is the largest solution to the nonlinear equation:$$q^{T}(P+\lambda I)^{-2}q=1 $$ I tried solving this by using the necessary and sufficient conditions for the optimal solution:$$ x \ is \ optimal \ if \ and \ only \ if \ x \in X \ and \\ \nabla f_0(x)^T (y - x) \geq 0 \quad \text{for all} \quad y \in X. $$ But I wasn't able to make progress.Is there an alternative approach to solve this problem, or any hints on how to use the optimality conditions more effectively? Any suggestions would be greatly appreciated!