2
$\begingroup$

I am solving a set non-linear, optimization problems. I used Matlab optimization toolbox in addition to CVX. I am wondering if there is any reference that summarize the complexity of these algorithms, (or the major ones), as function of (among other):

  • number of variables,
  • number of constraints,
  • type of constraints etc.

It would be great if the reference is easy to follow, I mean does not assume very advanced knowledge in computer science or optimization theory, (I am not bad in both but cannot claim to be an expert).

$\endgroup$
8
$\begingroup$

You have to start by defining what you mean by the computational complexity of an optimization algorithm. In general, the optimal solution to an optimization problem might involve irrational numbers that can't be computed exactly in floating point arithmetic or even as the ratio of two integers with unlimited precision. Although computations are performed in limited precision floating point arithmetic, most analysis of convergence is done assuming exact computation with real numbers. Optimization algorithms are iterative algorithms that produce a sequence of solutions that converge to an optimal solution to the problem. Generally it is relatively easy to analyze the computational effort per iteration, so the focus is usually on the number of iterations required to obtain convergence to within a tolerance $\epsilon$.

Traditionally in nonlinear programming, algorithms were analyzed in terms of asymptotic rate of convergence of the iterates to an optimal solution. For example, if Newton's method is started sufficiently close to a minimum point $x^{*}$ of an unconstrained minimization problem, it has quadratic asymptotic convergence:

$ \lim_{k \rightarrow \infty} \frac{\| x^{k+1}-x^{*} \|}{\| x^{k}-x^{*} \|^{2}}=c < \infty. $

Other methods, such as steepest descent have linear asymptotic convergence

$ \lim_{k \rightarrow \infty} \frac{\| x^{k+1}-x^{*} \|}{\| x^{k}-x^{*} \|}=c < 1. $

In some cases it's possible to determine the rate constant $c$ for particular problems.

Other methods, such as the BFGS method have superlinear asymptotic convergence:

$ \lim_{k \rightarrow \infty} \frac{\| x^{k+1}-x^{*} \|}{\| x^{k}-x^{*} \|}=0. $

Results on the asymptotic convergence rate of an algorithm can be found in most textbooks on nonlinear optimization. A good reference is the book Numerical Optimization, 2nd ed. by Jorge Nocedal and Stephen J. Wright.

Asymptotic convergence rates aren't by themselves sufficient to bound the number of iterations required to obtain a solution within $\epsilon$ of optimal. In general, this is hard. Although you can compute a bound on the number of Newton's method iterations required to find the minimum of a general convex function, the bound depends on constants that aren't typically known. This is discussed in the book Convex Optimization by Stephen Boyd and Lieven Vandenberghe.

The book Interior-Point Polynomial Algorithms in Convex Programming by Yurii Nesterov and Arkadii Nemirovskii gives bounds on the number of iterations required by Newton's method for a special class of self concordant functions. This is applied to polynomial time interior point methods for linear, quadratic, second order cone, and semidefinite programming. Although this is a classic book, it's not an easy starting point. Nesterov's Introductory Lectures on Convex Optimization: A Basic Course would be a better place to start.

A typical result is that in a primal-dual method for linear programming $O(\sqrt{n}L)$ (where $n$ is the number of variables and $L$ is the size of the problem data) iterations are required in the worst case to obtain a solution that can be transformed easily into an optimal basic feasible solution. A good reference on this is the book Primal-Dual Interior-Point Methods by Stephen J. Wright.

You should know that the solvers (SDPT3, SeDuMi, glpk, and if you have the licenses, Mosek and Gurobi) used by CVX are primal-dual interior point codes that can solve linear programming, quadratic programming, second order cone programming, and semidefinite programming problems. The algorithms implemented in these solvers are based on worst-case polynomial time algorithms for LP, SOCP, and SDP mentioned above.

CVX transforms the problems that you give it into the standard LP/SOCP/SDP form used by these solvers and then the solver uses a primal-dual interior point method to solve the problem. Note that the problem that you wrote might be transformed into a standard form problem with many more variables or constraints than your original problem. The transformations perofrmed by CVX can be quite involved. One issue you need to consider is the size of the LP, SOCP, or SDP produced by CVX.

The $O(\sqrt{n}L)$ iteration complexity bound hides a lot of detail in $L$. In particular, the number of linear constraints could be up to $n$ (an overdetermined problem wouldn't make any sense to consider) and the constraint matrix could be sparse or fully dense. The particular structure of the problem can make a huge difference in the work per iterations and this simply isn't accounted for in the complexity bound.

The major computation in each iteration of the primal-dual method is the construction and Cholesky factorization of a symmetric and positive definite matrix of size $m$ by $m$, where $m$ is the number of linear equality constraints. In the worst case, the Cholesky factorization could take $O(m^{3})$ time. This matrix is typically sparse in linear programming so the factorization is faster but it is often fully dense in semidefinite programming. Worst case complexity bounds aren't very relevant- this is all very problem specific. In practice, storage requirements for the large dense matrix are often more of an issue than time constraints. Some complexity analysis and computational results are reported in this paper by myself and Joseph Young.

However, it is generally the case that the work in each iteration of the primal-dual methods requires polynomial time that grows faster than linearly with the problem size. For really large-scale problems, polynomial time isn't good enough. Rather, the storage and time per iteration can be no more than linear in the size of the problem.

In recent years there has been a lot of interest in first order methods for large scale unconstrained convex optimization problems (and problems with extremely simple constraints such as $x \geq 0$.) These algorithms require no more than $O(n)$ storage and time per iteration.

The asymptotic convergence of these methods is typically linear or sublinear, but in practice no one performs enough iterations to obtain very accurate solutions. Rather, the algorithms are used to obtain solutions that might be accurate to no more than 3 or 4 digits.

In analyzing these first order methods for convex optimization, most authors focus on the number of iterations required to obtain a solution with an objective value with $\epsilon$ of the optimal solution. Various methods require $O(1/\epsilon^{2})$, $O(1/\epsilon)$, or $O(1/\sqrt{\epsilon})$ iterations for various problems. Nesterov's Introductory Lectures discusses this topic. Another recent reference is Convex Optimization Algorithms by Dimitri P. Bertsekas.

CVX does not make use of these newer first order methods. If you're finding that CVX can solve small instances of your problems but just won't handle larger instances, it might be that applying one of the first order methods to your problem would help you to solve the larger instances.

I'm afraid that all of these books that I've mentoned are at the level of research monographs or graduate level textbooks and might not be very accessible to you. This is a very technical subject.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you very much, that is quite helpful, I have taken course in numerical and optimization methods, but you connected both nicely. I was able to get some of these books. I will start looking at them soon. However, I am still wondering what impact does the constrains play here, (their number and functional structure), is it simply the number of iterations multiplied by the computational effort for evaluating each of the constraints? Do they impact the convergence rate? (do you think this problem discussed in the references that you listed? Thanks again $\endgroup$ – Burgh Apr 8 '17 at 2:01
  • $\begingroup$ I've expanded my answer to talk a bit about the work per iteration of polynomial time primal-dual interior point methods. Basically, this is very problem specific and worst case bounds aren't very useful. $\endgroup$ – Brian Borchers Apr 8 '17 at 4:47
  • $\begingroup$ Wow, great answer! Very useful overview. By the way, I think Boyd has been interested in making software like CVX except based on first-order methods and able to handle very large scale problems. $\endgroup$ – littleO Apr 8 '17 at 5:41
  • $\begingroup$ @BrianBorchers In a lot of times I see that the iteration being specified not in terms of the $\epsilon$ value, but in $k$. In other words, instead of seeing $\mathcal{O}(\frac{1}{\epsilon})$, a lot of authors tend to write $\mathcal{O}(\frac{1}{k})$, can you speak about this? $\endgroup$ – Bajie Jun 29 '17 at 21:05
  • 1
    $\begingroup$ You can specify either the number of iterations to meet a required accuracy ($O(1/\epsilon)$ or the accuracy that will be attained after $n$ iterations ($O(1/k)$. When $O(1/\sqrt{\epsilon})$ iterations are required to get an $\epsilon$ approximate solution, then the accuracy is $O(1/k^{2})$ after $k$ iterations. $\endgroup$ – Brian Borchers Jun 29 '17 at 23:17
0
$\begingroup$

I have a 0-1 second order cone (SOC) problem and I need to know the complexity of solving this problem?. I used cvx and the solver mosek to solve it. mosek uses branch and cut (B&C) method for 0-1 problems and Primal-Dual Interior-Point Methods for SOC problems?. The way I addressed this question is as following:

The 0-1 SOC problem can be solved using B&C method which has an exponential worst case complexity, i.e., O(2^n). At each node of B&C method, the relaxed problem is a SOC problem which can be solved using an primal-dual interior point method which has a polynomial-time complexity. However, I do not have an expression for the complexity of the interior point method yet. Assuming this complexity is O(n). Then, I can claim that the complexity of solving the 0-1 problem using B&C method is O(2^n) times O(n).

| cite | improve this answer | |
$\endgroup$

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.