If you are working on optimization with partial differential equations as constraints, you may be interested in the website
“OPTPDE – A Collection of Problems in PDE-Constrained Optimization”, http://www.optpde.net.
If you have developed an algorithm which can handle a certain class of optimization problems you need to do evaluations and tests on how well the method performs. To do so, you need well constructed test problems. This could be either problems where the optimal solution is known analytically our problems where the solution is known with a rigorous error bound obtained with a bullet-proof solver. Both things are not always easy to obtain and OPTPDE shall serve as a resource for such problems. It has been designed by Roland Herzog, Arnd Rösch, Stefan Ulbrich and Winnifried Wollner.
The generation of test instance for optimization problems seems quite important to me and indeed, several things can go wrong if this is not done right. Frequently, one sees tests for optimization routines on problems where the optimal solution is not known. Since there are usually different ways to express optimality conditions it is not always clear how to check for optimality; even more so, if you only check for “approximate optimality”, e.g. up to machine precision. A frequently observed effect is a kind of “trusted method bias”. By this I mean that an optimal solution is calculated by some trusted method and comparing the outcome of the tested routine with this solution. However, the trusted method uses some stopping criterion usually based on some specific set of formulations of optimality conditions and these can be different from what the new method has been tuned to. And most often, the stopping criteria do not give a rigorous error bound for the solution or the optimal objective value.
For sparse reconstruction problems, I dealt with this issue in “Constructing test instance for Basis Pursuit Denoising” (preprint available here) but I think this methodology could be used for other settings as well.
of a real vector space 
is convex if for any 
and ![{\lambda\in[0,1]}](http://s0.wp.com/latex.php?latex=%7B%5Clambda%5Cin%5B0%2C1%5D%7D&bg=ffffff&fg=000000&s=0 "{\lambda\in[0,1]}")
it holds that 
. 
for some 
in the dual space 
and 
). 
is convex if there is a convex function 
such that 
. 
from a real vector space into the real numbers is convex, if its epigraph 
is convex (as a subset of the vector space 
). 
which lie above the graph of the function and carries the same information as the function.
if one uses the right extension of the arithmetic and the obvious ordering, but we do not consider this in this post.)
with 
is also in the epigraph), and because the underlying vector space 
comes with an order in the second component, some of the definitions for convex sets from above have a specialized form:
and ![{\lambda\in [0,1]}](http://s0.wp.com/latex.php?latex=%7B%5Clambda%5Cin+%5B0%2C1%5D%7D&bg=ffffff&fg=000000&s=0 "{\lambda\in [0,1]}")
it holds that
of tuples 
it holds that
such that
be a set and let 
be a set of real valued function on 
is said to be 
such that
on a vector space by an arbitrary collection of real valued functions 
on a set. On sees immediately that for every function 
and any real number 
the function 
is 
is a subgradient of 
at 
, if for all 
it holds that 
or
if
we have
(without any additional structure) define a coupling function 
and define the 
-conjugate as
and 
. She proposed and analyzed smoothing methods, that is, to smooth the problem a bit to obtain a Lipschitz-continuous objective function 
, minimizing this and then gradually decreasing 
. This works, as she showed. If I remember correctly, she also treated “iteratively reweighted least squares” as I described in my 
-functions for non-convex functions. 
and not in 
.
-quasi-norm is replaced by functions of the form
, namely fulfilling a list of assumptions like
for 
(infinite slope at 
) and 
for 
(mild coercivity),
strictly convex on ![{]0,\infty[}](http://s0.wp.com/latex.php?latex=%7B%5D0%2C%5Cinfty%5B%7D&bg=ffffff&fg=000000&s=0 "{]0,\infty[}")
and 
for 
there is 
such that for 
it holds that 
, and
.
).
-norm. His talked is among the best planary talks I have ever attended and it was a great pleasure to listen to him. He carefully explained things and put them in perspective. In the case he skipped slides, he made me feel that I either did not miss an important thing, or understood them even though he didn’t show them He argued that it is not necessarily more expensive to use second order information in contrast to first order methods. Indeed, the 
-sparse solution of an 
system of equations. He formulated this as a feasibility-problem (well, 
the number of non-zero entries of 
. Then the problem of finding an 
is:
consists of just keeping the 
and 
of which you observe only the superposition of 
you observe
and 
-norms in the following manner: 
such that the residual (could also say “noise”) 
is also sparse. This differs from the common Basis Pursuit Denoising (BPDN) by the structure function for the residual (which is the squared 
-norm). This is due to the fact that in BPDN one usually assumes Gaussian noise which naturally lead to the squared 
is known.
, respectively. Assuming a kind of non-smoothness of 
convex in the first and concave in the second variable. The continuous Arrow-Hurwitz method consists of solving
and 
. For the case of 
he presented a nice analysis of the problem including convergence of the method to a solution of the primal problem and some a-posteriori estimates. This reminded me of 
this reads as
(replacing the subgradient step) and a feasibility operator 
(replacing the projection step). The algorithm then reads as
and noise 
. However, for the noise he assumed that it is given by
are kind of shape-functions which describe the “pattern of the noise” and the 
are samples of noise processes, following specific distributions (could be white noise realizations, impulsive noise or something else)-. He then formulated a variational method to identify the variables 
is not feasible. He used the primal-dual algorithm by Chambolle and Pock for this problem and showed that the method works well on real world problems.
(omitting regularity conditions which could be necessary to impose) depending on a parameter 
, 
solves~
. However, if the sparsity 
, which is a sharp lower bound on 
, and use non-asymptotic methods to bound the relative error of 
. These results also extend naturally to the problem of using linear measurements to estimate the rank of a positive semi-definite matrix, or the sparsity of a non-negative matrix. Finally, we show that if no structural assumption (such as non-negativity) is made on the signal 
cannot generally be estimated when 
. Similarly, measuring with Gaussian random vector you can obtain an estimate of 
.
with Lipschitz-differentiable 
to second order Newton-type methods. The abstract reads
is a convex but not necessarily differentiable function whose proximal mapping can be evaluated efficiently. We derive a generalization of Newton-type methods to handle such convex but nonsmooth objective functions. Many problems of relevance in high-dimensional statistics, machine learning, and signal processing can be formulated in composite form. We prove such methods are globally convergent to a minimizer and achieve quadratic rates of convergence in the vicinity of a unique minimizer. We also demonstrate the performance of such methods using problems of relevance in machine learning and high-dimensional statistics. 
(which results in 
) and decreases 
while tracking the (piecewise linear) solution path. Provable this reaches the Basis Pursuit solution for 
after crossing a finite number of breaks in the solution path. However, in our first experiments we used a final parameter of 
. And that was against our rules: We only considered solvers which (in theory) calculate the exact Basis Pursuit solution. Now we reran the calculations with 
which is maintained throughout the iterations.
always ended with an approximate solution accuracy (about 
) for all test instances (no matter what size, matrix type or number of nonzeros we used). That is a surprise because there is no formula which tells you in advance how accurate the Basis Pursuit denoising for a particular 
, a vector 
and a vector 
, that is, calculate a vector 
such that
-
-penalties, that is, studying the Tikhonov functional 
penalty term
we get 
.
leads to 
instead of 
.
since the growth of the 
. Then, 
is not at the place at which the second local minimum occurs. It is a little bit larger: In “
minimization for sparse solution of under determined linear systems
and a small 
and rewrite the 
![\displaystyle 0 = \alpha \Big[\frac{p}{q} (\epsilon + |x_i|^q)^{\frac{p}{q}-1} q \textup{sgn}(x_i) |x_i|^{q-1}\Big]_i + A^*(Ax-b)](http://s0.wp.com/latex.php?latex=%5Cdisplaystyle+0+%3D+%5Calpha+%5CBig%5B%5Cfrac%7Bp%7D%7Bq%7D+%28%5Cepsilon+%2B+%7Cx_i%7C%5Eq%29%5E%7B%5Cfrac%7Bp%7D%7Bq%7D-1%7D+q+%5Ctextup%7Bsgn%7D%28x_i%29+%7Cx_i%7C%5E%7Bq-1%7D%5CBig%5D_i+%2B+A%5E%2A%28Ax-b%29+&bg=ffffff&fg=000000&s=0 "\displaystyle 0 = \alpha \Big[\frac{p}{q} (\epsilon + |x_i|^q)^{\frac{p}{q}-1} q \textup{sgn}(x_i) |x_i|^{q-1}\Big]_i + A^*(Ax-b)")
is negative (which is also a reason for the introduction of the small 
we try to find 
by solving![\displaystyle 0 = \alpha \Big[\frac{p}{q} (\epsilon + |x_i^k|^q)^{\frac{p}{q}-1} q \textup{sgn}(x_i) |x_i|^{q-1}\Big]_i + A^*(Ax-b)](http://s0.wp.com/latex.php?latex=%5Cdisplaystyle+0+%3D+%5Calpha+%5CBig%5B%5Cfrac%7Bp%7D%7Bq%7D+%28%5Cepsilon+%2B+%7Cx_i%5Ek%7C%5Eq%29%5E%7B%5Cfrac%7Bp%7D%7Bq%7D-1%7D+q+%5Ctextup%7Bsgn%7D%28x_i%29+%7Cx_i%7C%5E%7Bq-1%7D%5CBig%5D_i+%2B+A%5E%2A%28Ax-b%29+&bg=ffffff&fg=000000&s=0 "\displaystyle 0 = \alpha \Big[\frac{p}{q} (\epsilon + |x_i^k|^q)^{\frac{p}{q}-1} q \textup{sgn}(x_i) |x_i|^{q-1}\Big]_i + A^*(Ax-b)")
-norm: Define (non-negative) weights 
an iterate 
which has the benefit that each iteration can be done by solving a linear system. However, for general 
each iteration is still a convex minimization problem. The paper “
and both papers deliver some theoretical results of the iteration. Indeed in both cases one can show (subsequential) convergence to a critical point.
, set 
and chose 
. This produced the following output (I plotted every fifth iteration):
for all 
gave 
small enough such that the method will pick the global minimizer. But wait—they do not say anything about initialization… What happens if we initialize with zero? I have to check…
into a separable Hilbert space.
in practice. However, I think that working directly in a separable Hilbert space is preferable since then one can be sure that the results will not depend on the dimension 
in any nasty way. 
to project back onto 
, i.e. we want to solve
. However, for these 
with Lipschitz constant 
and let 
be weakly lower semicontinuous and coercive. Furthermore let 
denote any solution of
it holds that
to both sides) that
. Now starts the hard part of the investigation: Under what circumstances do we get convergence and what are possible limits?
one gets that every subsequence of the iterates has a strong accumulation point which is a fixed point of the iteration for that particular 
. Well that’s good, but here’s the bad news: As long as 
we do not obtain the global minimizer. That’s for sure: Consider 
and any 
…
with 
(and another technical condition on the Lipschitz constant of 
and hence, satisfies necessary conditions for a global minimizer.
and 
with rational ![{]0,1[}](http://s0.wp.com/latex.php?latex=%7B%5D0%2C1%5B%7D&bg=ffffff&fg=000000&s=0 "{]0,1[}")
… Basically, Stefan was able to show this with the help of Gröbner bases and this has been my first contact with this nice theory. We hope to finalize our revision soon.
