We have: $A \in \mathbb{R}^{n \times m}$ with independent columns, $y \in \mathbb{R}^n$. Moreover, $n \gg m$.

Consider the following problem, where the inequality is elementwise:

$$x^{\star} := \arg\min_x \| Ax - y \|_2 \,\, \text{subject to} \,\, Ax \leq y$$

Is it possible to compute $x^{\star}$ by an algorithm of time complexity polynomial in $m$ and space complexity $O(m^3)$ in the following sense:

  1. Read the matrix $A$ row by row and the vector $y$ element by element, constructing objects of size $O(m^3)$ on the go.
  2. Apply some algorithm polynomial in $m$ to the constructed objects, computing $x^\star$.
  • 1
    $\begingroup$ This is a standard inequality-constrained quadratic program (QP) $$\begin{array}{ll} \text{minimize} & \| \mathrm A \mathrm x - \mathrm y \|_2^2\\ \text{subject to} & \mathrm A \mathrm x \leq \mathrm y\end{array}$$ which can be solved using, say, MATLAB. Take a look at chapter 16 of Nocedal & Wright's Numerical Optimization ( home.agh.edu.pl/~pba/pdfdoc/Numerical_Optimization.pdf ) $\endgroup$ – Rodrigo de Azevedo Sep 19 '16 at 14:10
  • $\begingroup$ Of course, if $\mathrm y$ is in the column space of $\mathrm A$, then the linear system $\mathrm A \mathrm x = \mathrm y$ has a unique solution, and this unique solution satisfies the inequality constraints. In this case, the minimum is zero. $\endgroup$ – Rodrigo de Azevedo Sep 19 '16 at 14:16
  • $\begingroup$ @RodrigodeAzevedo Thanks. I clarified the part of the question dealing with the space constraint. The algorithms in the book do not meet these requirements because: in active set methods, the active set can be of size n; in primal-dual methods, the dual is of size n. $\endgroup$ – ziutek Sep 19 '16 at 15:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.