Why are optimization algorithms defined in terms of other optimization problems?

Question

I am doing some research on optimization techniques for machine learning, but I am surprised to find large numbers of optimization algorithms are defined in terms of other optimization problems. I illustrate some examples in the following.

For example https://arxiv.org/pdf/1511.05133v1.pdf

Everything looks nice and good but then there is this $\text{argmin}_x$ in the $z^{k+1}$ update....so what is the algorithm that solves for the $\text{argmin}$? We don't know, and it doesn't say. So magically we are to solve another optimization problem which is find the minimizing vector so that the inner product is at minimum - how can this be done?

Take another example:https://arxiv.org/pdf/1609.05713v1.pdf

Everything looks nice and good until you hit that proximal operator in the middle of the algorithm, and what is the definition of that operator?

Boom:

Now pray tell, how do we solve this $\text{argmin}_x$ in the proximal operator? It doesn't say. In any case, that optimization problem looks hard (NP HARD) depending on what $f$ is.

Can someone please enlighten me as to:

1. Why are so many optimization algorithms defined in terms of other optimization problems?

(Wouldn't this be some sort of chicken and egg problem: to solve problem 1, you need to solve problem 2, using method of solving problem 3, which relies on solving problem ....)

2. How do you solve these optimization problems that are embedded in these algorithms? For example, $x^{k+1} = \text{argmin}_x \text{really complicated loss function}$, how to find the minimizer on the right hand side?

3. Ultimately, I am puzzled as to how these algorithms can be numerically implemented. I recognize that adding and multiplying vectors are easy operations in python, but what about $\text{argmin}_x$, is there some function (script) that magically gives you the minimizer to a function?

(Bounty: can anyone reference a paper for which the authors make clear the algorithm for the sub-problem embedded in the high level optimization algorithm?)

Answer 1

You are looking at top level algorithm flow charts. Some of the individual steps in the flow chart may merit their own detailed flow charts. However, in published papers having an emphasis on brevity, many details are often omitted. Details for standard inner optimization problems, which are considered to be "old hat" may not be provided at all.

The general idea is that optimization algorithms may require the solution of a series of generally easier optimization problems. It's not uncommon to have 3 or even 4 levels of optimization algorithms within a top level algorithm, although some of them are internal to standard optimizers.

Even deciding when to terminate an algorithm (at one of the hierarchial levels) may require solving a side optimization problem. For instance, a non-negatively constrained linear least squares problem might be solved to determine the Lagrange multipliers used to evaluate the KKT optimality score used to decide when to declare optimality.

If the optimization problem is stochastic or dynamic, there may be yet additional hierarchial levels of optimization.

Here's an example. Sequential Quadratic Programming (SQP). An initial optimization problem is treated by iteratively solving the Karush-Kuhn-Tucker optimality conditions, starting from an initial point with an objective which is a quadratic approximation of the Lagrangian of the problem, and a linearization of the constraints. The resulting Quadratic Program (QP) is solved. The QP which was solved either has trust region constraints, or a line search is conducted from the current iterate to the solution of the QP, which is itself an optimization problem, in order to find the next iterate. If a Quasi-Newton method is being used, an optimization problem has to be solved to determine the Quasi-Newton update to the Hessian of the Lagrangian - usually this is a closed form optimization using closed form formulas such as BFGS or SR1, but it could be a numerical optimization. Then the new QP is solved, etc. If the QP is ever infeasible, including to start, an optimization problem is solved to find a feasible point. Meanwhile, there may be one or two levels of internal optimization problems being called inside the QP solver. At the end of each iteration, a non-negative linear least squares problem might be solved to determine the optimality score. Etc.

If this is a mixed integer problem, then this whole shebang might be performed at each branching node, as part of a higher level algorithm. Similarly for a global optimizer - a local optimization problem is used to produce an upper bound on the globally optimal solution, then a relaxation of some constraints is done to produce a lower bound optimization problem. Thousands or even millions of "easy" optimization problems from branch and bound might be solved in order to solve one mixed integer or global optimization problem.

This should start to give you an idea.

Edit: In response to the chicken and egg question which was added to the question after my answer: If there's a chicken and egg problem, then it's not a well-defined practical algorithm. In the examples I gave, there is no chicken and egg. Higher level algorithm steps invoke optimization solvers, which are either defined or already exist. SQP iteratively invokes a QP solver to solve sub-problems, but the QP solver solves an easier problem, QP, than the original problem. If there is an even higher level global optimization algorithm, it may invoke an SQP solver to solve local nonlinear optimization subproblems, and the SQP solver in turn calls a QP solver to solve QP subproblems. No chiicken and egg.

Note: Optimization opportunities are "everywhere". Optimization experts, such as those developing optimization algorithms, are more likely to see these optimization opportunities, and view them as such, than the average Joe or Jane. And being algorithmically inclined, quite naturally they see opportunities for building up optimization algorithms out of lower-level optimization algorithms. Formulation and solution of optimization problems serve as building blocks for other (higher level) optimization algorithms.

Edit 2: In response to bounty request which was just added by the OP. The paper describing the SQP nonlinear optimizer SNOPT https://web.stanford.edu/group/SOL/reports/snopt.pdf specifically mentions the QP solver SQOPT, which is separately documented, as being used to solve QP subproblems in SNOPT.

Answer 2

I think a reference that my satisfy your desire is here. Go to section 4 - Optimisation in Modern Bayesian Computation.

TL;DR -they discuss proximal methods. One of the advantages of such methods is splitting - you can find a solution by optimizing easier subproblems. A lot of times (or, at least, sometimes) you may find in the literature a specialized algorithm to evaluate a specific proximal function. In their example, they do image denoising. One of the steps is a very successful and highly cited algorithm by Chambolle.

Answer 3

I like Mark's answer, but I though I would mention "Simulated Annealing", which basically can run on top of any optimization algorithm. At a high level it works like this:

It has a "temperature" parameter which starts hot. While hot it steps frequently away and (and further away) from the where the subordinate optimization algorithm points. As it cools it follows the advice of the subordinate algorithm more closely, and at zero it follows it to whatever local optimum it has then ended up at.

The intuition is that it will search the space widely at the beginning, looking for "better places" to look for optimums.

We know there is no real general solution to the local/global optimum problem. Every algorithm will have its blind spots, but hybrids like this seem to give better results in a lot of cases.

Answer 4

This is quite common in many optimization papers and it has to do with generality. The authors usually write the algorithms in this manner to show that they technically work for any function f. However, in practice, they are only useful for very specific functions where these sub-problems can be efficiently solved.

For example, and now I'm talking about the second algorithm only, whenever you see a proximal operator (which as you noted its another optimization problem that can be indeed very hard to solve) is usually implicit that it has a closed form solution in order for the algorithm to be efficient. This is so for many functions of interest in machine learning such as the l1-norm, group norms, and so on. In those cases you would replace the sub-problems for the explicit formula of the proximal operator, and there is no need for an algorithm to solve that problem.

As to why they are writen in this manner just note that if you were to come up with another function and wanted to apply that algorithm you would check, first, if the proximal has a closed form solution or can be computed efficiently. In that case you just plug in the formula into the algorithm and you are good to go. As mentioned before, this guarantees that the algorithm is general enough that can be applied to future function that may come up after the algorithm is first published, together with their proximal expressions of efficient algorithms to compute them.

Finally, as an example, take the classic FISTA algorithm original paper. They derive the algorithm for two very specific functions, the squared loss and the l1-norm. However, they note that it can be applied no any functions as long as they meet some pre-requisites, one of them being that the proximal of the regularized can be computed efficiently. This is not a theoretical requirement but a practical one.

This compartimentalization not only makes the algorithm general but also easier to analyze: as long as there exists algorithms for the sub-problems that have this properties, then the proposed algorithm will have this convergence rate or whatever.