Formulating optimization problems in standard quadratic form

177 Views Asked by At

I've been studying optimization theory for a while and I'm interested in finding out the solution to the following problem. Suppose we have a regression problem in the form of:

$$\quad y^k = \beta_0 + \beta_1 x + \beta_2 x^2 - u^k, \quad k=1,...K$$

With the following constraints:

\begin{equation} \label{eq5} \begin{split} min \sum_{k=1}^{K} u_k^2\\ s.t.\qquad u^k &\geq 0, \quad k=1,...K\\ \beta_0& \leq 0\\ \beta_1,\beta_2 & \geq 0 \end{split} \end{equation}

How do we translate such an optimization problem in a standard quadratic form?

\begin{equation} \begin{split} min(\frac{1}{2}x^TQx+c^Tx)\\ s.t.\quad A^Tx\leq b \\ \end{split} \end{equation}

Thank you in advance

1

There are 1 best solutions below

0
On BEST ANSWER

I assume your regression problem is $$y_k = \beta_0 + \beta_1x_k + \beta_2x_k^2-u_k.$$

Let column vectors $\beta = (\beta_0, \beta_1, \beta_2)'$ and $v_k = (1, x_k, x_k^2)'$, we can rewrite the objective for this regression model as \begin{align*} & \sum_{k=1}^K u_k^2 = \sum_{k=1}^K \left(\beta_0 + \beta_1x_k + \beta_2x_k^2-y_k\right)^2 \\ = & \sum_{k=1}^K\left(v_k^\prime\beta - y_k\right)^2 = \sum_{k=1}^K\left(v_k^\prime\beta\right)^2-2y_kv_k^\prime\beta + y_k^2 \\ = & \sum_{k=1}^K\beta'v_kv_k^\prime\beta - \sum_{k=1}^K2y_kv_k^\prime\beta + \sum_{k=1}^Ky_k^2 \end{align*} Note $\sum y_k^2$ is a constant and can be dropped freely in the objective function. Let $Q = 2\sum_{k=1}^Kv_kv_k^\prime$, $c = -2\sum_{k=1}^Ky_kv_k$, there is the standard quadratic program form $$\min_{\beta} \frac12\beta^\prime Q\beta + c'\beta.$$ Now let's look at the constraints, $\beta_0 \le 0$, $\beta_1 \ge 0$, and $\beta_2\ge 0$ can be written as $A_0^\prime\beta \le b_0$ where matrix $A_0$ is $$A_0 = \left(\begin{matrix}1 & 0 & 0\\ 0 & -1 & 0 \\ 0 & 0 & -1\end{matrix}\right)$$ and $b_0^\prime = (0,0,0)$. Each of $u_k \ge 0$ can be written as $-v_k^\prime\beta \le -y_k$. Combining all constraints together, we have $A^\prime\beta \le b$ where \begin{matrix} A & = & (A_0 &-v_1 &-v_2 & \cdots &-v_K) \\ b^\prime & = & (b_0^\prime & -y_1& -y_2 & \cdots & -y_K) \end{matrix}

In fact, the constraint $u_k\ge0$ is quite unusual. Usually, the estimation error is centered at 0, in your case, it is certainly not centered at 0. Also, with that set of constraints, you may run into feasibility problem.