Is it possible to “solve” iterative (convex/non-convex) optimization problems via learning (one-shot)?

Question

I posted a following question in MSE, but I think it should be posted here in MO. Since I don't know how to transfer the post from MSE to MO, I have pasted the question below. Thank you in advance and looking for your comments/suggestions.

My question is two fold:

(1) Is it possible to "solve" (iterative convex/non-convex) optimization problems via learning (e.g., regression / classification) with an objective to "solve" (in some sense) the problem in "one-shot"?

(2) If the above answer is affirmative, do you have any preferred methods or papers that you can suggest or refer to?

---

ADD:

Let's consider a following convex optimization whose solution is obtained iteratively via some solver (e.g., CVX).

\begin{aligned} & \underset{\mathbf{x} \in \mathbb{R}^n}{\text{minimize}} & & \left\| \mathbf{y} - \mathbf{x} \right\|_2^2 %\\ & \text{subject to} & & \mathbf{A} \mathbf{x} \leq \mathbf{b} \ ,\\ %&&& X \succeq 0. \end{aligned} where the inequality constraint is element-wise. The matrix $\mathbf{A} \in \mathbb{R}^{m \times n}$, vector $\mathbf{b} \geq 0\in \mathbb{R}_{+}^{m}$, and the vector $\mathbf{y} \in \mathbb{R}^{n}$ are given/known. Also, $n > m$, and $n$ can be a very large value.

Question is: can we utilize some "learning" to "predict" the optimal solution (non-iteratively)?

---

I found some papers, e.g., Link, that attempt to solve the optimization problems utilizing "learning" (e.g., neural networks). Does anyone have any feeling about this? I will try to dig into this more in the future, but would be happy to hear your experience if any.

Answer 1

Solve the unconstrained least squares problem in "one-shot", for example by QR or SVD (if not too big), if you consider that to be "one-shot". Then if the optimal $x$ to the unconstrained least squares problem satisfies $A x \le b$, it is optimal for the original constrained problem; if not, you have not solved the original problem in one-shot.

Of course it is possible to solve the original constrained problem in one-shot if the one-shot consists of querying an oracle which can solve such problems. The only difficulty from a practical engineering perspective is that you may not have such an oracle available - I don't happen to.

The question title mentions convex/non-convex. But the only the problem you displayed is convex, and is a linearly constrained linear least squares problem, which can also be viewed as being a convex Quadratic Programming (QP) problem. Or it can be transformed into an equivalent Second Order Cone Problem (SOCP) via epigraph reformulation, which may be numerically advantageous from a robustness standpoint.

$min_{t.x} t$

s.t. $\|y-x\|_2 \le t, A x \le b$

Such linear inequality constrained linear least squares problems, linear inequality constrained QPs, and SOCPs are not solved in "one-shot", as you seem to define shot.

If $y$ were a nonlinear function of $x$, then you would have a linearly constrained nonlinear least squares problem which might be non-convex.

There are specialized, efficient, and robust numerical optimization solvers available for linearly constrained linear least squares, (linear inequality constrained) QPs, and for SOCPs.

The way you have written the problem, the condition number of the Hessian of the objective function is 1, so there is no harm in squaring the condition number of the problem via explicit QP formulation. More generally, there is harm in squaring the condition number via explicit QP formulation, though. In such case, a change of variables via Cholesky faotrization can be introduced such that the objective Hessian of the transformed problem is the Identity matrix (as is apparently the case in your problem to begin with), and a matrix equality constraint added defining the transformation.

Answer 2

The specific problem you gave has the property that for every given data $(A,b,y)$ there is exactly one $x$ that solves the problem. Hence, there a solution map $(A,b,y) \mapsto x$ mapping $\mathbb{R}^{m\times n}\times\mathbb{R}^m\times\mathbb{R}^n\to\mathbb{R}^n$. By the universal approximation theorem, you can approximate this map on a compact subset by a neural network with just one layer. I guess that this theoretical result is of no practical relevance, but I may be wrong.