How to work around a nonconvex constraint?

27 Views Asked by At

My objective function is

\begin{align} \text{minimize}_{\mathbf{x} \in \mathbb{R}^3} \quad & \mathbf{x}^T\mathbf{M}\mathbf{x} \\ \text{subject to }\quad & x_1 = 1\\ & x_3=x_1x_2=x_2 \end{align}

where \begin{equation} \mathbf{M} = \begin{bmatrix} M_{11} & M_{12} & M_{13} \\ M_{21} & M_{22} & M_{23} \\ M_{31} & M_{32} & M_{33} \\ \end{bmatrix}, \end{equation}

and

\begin{equation} \mathbf{x} = \begin{bmatrix} x_{1} \\ x_{2} \\ x_{3} \\ \end{bmatrix} \end{equation}

is a randomly generated symmetric positive definite matrix.

Objective function is convex but what about $x_3=x_2$ constraint? Any ideas about how to solve this.

1

There are 1 best solutions below

0
On

The constraint $x_2=x_3$ is convex, and indeed if we eliminate $x_1$ and let $x_2=x_3=x$ then the optimization problem is equivalent to $\min M_{11}+(M_{12}+M_{13}+M_{21}+M_{31})x+(M_{22}+M_{23}+M_{32}+M_{33})x^2$, meaning that if the quadratic term is negative then the problem is unbounded, and otherwise it can be solved analytically by completing the square.