0
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ The question is somewhat vague. A mildly better (but still too broad for this forum) version is "What characterizes those optimization problems for which one can find a quick convergence to (the desired) optimal points?". I think you will have to slice a piece off this and suggest to this forum a specific example or class of examples to consider. Gerhard "Not Ready To Eat Elephant" Paseman, 2018.10.30. $\endgroup$ – Gerhard Paseman Oct 30 '18 at 21:08
  • $\begingroup$ @GerhardPaseman: Thank you for your reply. I agree that the question was vague. Now, I have proposed an example that can be a starting point. What do you think about such problems? $\endgroup$ – user550103 Oct 31 '18 at 17:29
  • $\begingroup$ For the given example, I think one can use "theory" and "experience" to posit a solution vector and a means of finding it. However, I would not want to replace real intuition and experimentation with artificial substitutes. For this problem, I would predict x to be a scalar multiple of y which satisfies the constraint system, and then vary each coordinate of x in a way to decrease the distance while maintaining the constraint. Is that predictive enough for you? Gerhard "In Absence Of Closed-Form Solution" Paseman, 2018.10.31. $\endgroup$ – Gerhard Paseman Oct 31 '18 at 20:04
  • $\begingroup$ No, I am sorry and don't think this is enough. It sounds more numerical approach (which is again iterative method). $\endgroup$ – user550103 Oct 31 '18 at 20:14
  • 1
    $\begingroup$ Yes, for a relaxed notion of "solve" you can do this by "learning" -- without making any of those terms precise, there's not much more to say. Most likely what you are looking for in this question is a formulation that can make those terms precise..... $\endgroup$ – Suvrit Nov 4 '18 at 11:09
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you for your reply. So, can we generalize and say that one can solve via neural network those iterative convex problems which has a unique solution? If there are more solutions, will neural network not be able to learn the mapping? When would we need more layers? $\endgroup$ – user550103 Dec 17 '18 at 5:45

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.