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.
discrepancy term instead of the usual 
-one. He presented a path-following semismooth Newton method to solve the problem
almost everywhere. It seems to me that uniform noise would need a slightly different penalty but I don’t know which one – probably you do? Moreover, Christian presented the balancing principle to choose the regularization parameter (without knowledge about the noise level) and this was the first time I really got what it’s about. What one does here is, to choose 
such that (for some 
which only depends on 
, but not on the noise)
she calculated the solution of
, a positive integer 
be given. It is hard for NP under randomized polynomial-time reductions to check if 
is an RIP constant for 
is 
such that for all elements 
in the null space of 
is coNP-complete. Consequently, it is NP-hard to compute the null space constant of 
(if it is unique throughout) depends on 
in a piecewise linear way and converges to the solution of basis pursuit for 
. This leads to an algorithm for the solution of basis pursuit: Start with 
(for which the unique solution is 
), calculate the direction of the “solution path”, follow it until you reach a “break point”, calculate the next direction and so on until 
is 
is the number of entries in 
with a path with 
linear segments they try to construct an instance which has one more variable such that the number of linear segments in increased by a factor. Their result goes like this: 
have full rank and let 
be in the range of 
the regularization parameter which corresponds to the smallest kink in the path. Now choose 
and 
and 
by
and right hand side 
has 
linear segments. 
example and let it grow by one row and one column according to Theorem~![{A = [1]}](http://s0.wp.com/latex.php?latex=%7BA+%3D+%5B1%5D%7D&bg=ffffff&fg=000000&s=0 "{A = [1]}")
and ![{b=[1]}](http://s0.wp.com/latex.php?latex=%7Bb%3D%5B1%5D%7D&bg=ffffff&fg=000000&s=0 "{b=[1]}")
. To move to the next bigger example you can choose the next entry 
and we always choose 
for convenience. Moreover, you need the next 
, ![{A=[1]}](http://s0.wp.com/latex.php?latex=%7BA%3D%5B1%5D%7D&bg=ffffff&fg=000000&s=0 "{A=[1]}")
. The homotopy path has one kink at 
(with corresponding solution ![{[0]}](http://s0.wp.com/latex.php?latex=%7B%5B0%5D%7D&bg=ffffff&fg=000000&s=0 "{[0]}")
) and hence, two linear segments. Now let’s go to the next larger instance:
as we like and choose it equals to 1, i.e. our new 
is
which gives our new matrix
.
giving
.
for the 
-case from 
in each step and one checks easily that this leads to 
which is the worst case! If you are interested in the regularization path: I produced picture for the first three dimensions (well, I could not draw a 4d 
-ball) and here they are:
in terms of 
?
on a Banach space 
, a linear and bounded operator 
from 
and an element 
consider the problem 
, choose step-sizes 
and iterate
is replaced by some 
which fulfills 
(and hence, 
” (or even a true solution to 
) first but then start to diverge from some point on. Then it is natural to ask, if the ALM with 
(depending on 
approach the solution of 
such that for a solution 
of 
goes to zero linearly in 
with 
and some non-negative, strictly increasing and concave function 
. Under this assumption (and special 
) and derive that a weak condition (like 
for some 
already imply the stronger one 
). Hence, interestingly, it seems that for sparse regularization one either gets a linear rate or nothing (in this framework). 
to measure the noise or to penalize the deviation from 
to 
is topological space which comes with an additional sequential convergence structure 
(see e.g. ![{\rho:Y\times Y\rightarrow [0,\infty]}](http://s0.wp.com/latex.php?latex=%7B%5Crho%3AY%5Ctimes+Y%5Crightarrow+%5B0%2C%5Cinfty%5D%7D&bg=ffffff&fg=000000&s=0 "{\rho:Y\times Y\rightarrow [0,\infty]}")
. Then we analyzed the interplay of these three things 
, 
. If you wonder why we use the additional sequential convergence structure, remember that in the (by now classical) setting for Tikhonov regularization in Banach spaces with a functional like
and 
there are also two kinds of convergence on 
: The weak convergence (which is replaced by 
for 
. And since we do not have a normed space 
, 
try to find a solution of
-term goes back to Zou and Hastie from the statistics community. There, the motivation was as follows: They observed that the pure 
under the constraint that certain measurements 
result in certain given values 
. Moreover, they make a thorough analysis of what is “reconstructable” by their ansatz and obtain a lower bound on the distance of two Diracs (in other words, a lower bound in the 
which only has 
non-zero entries and a fat matrix 
(i.e. 
) and consider that we are given measurements 
. Of course, the system 
is underdetermined. However, we may add a little more prior knowledge on the solution and ask: Is is possible to reconstruct 
, 
, 
on a closed interval (which we assume to be ![{I=[-1,1]}](http://s0.wp.com/latex.php?latex=%7BI%3D%5B-1%2C1%5D%7D&bg=ffffff&fg=000000&s=0 "{I=[-1,1]}")
for simplicty). We may embed the 
, 
from the interval 
and build 
with the point-masses (or 
. To a be a bit more precise, we speak about the space 
of 
-algebra of 
which is the closure of the continuous functions with compact support in ![{{]{-1,1}[}}](http://s0.wp.com/latex.php?latex=%7B%7B%5D%7B-1%2C1%7D%5B%7D%7D&bg=ffffff&fg=000000&s=0 "{{]{-1,1}[}}")
with respect to the supremum norm. Hence, Radon measures work on these functions as 
. It is also natural to speak of the support 
of a Radon measure 
that
and a negative part 
, i.e. 
. Finally the 
linear functionals and these can be encoded by 
as
. The generalization of Basis Pursuit is then given by
with some 
and the 
linear measurements should be necessary to reconstruct 
and moreover, we can take fairly simple measurements, namely the monomials: 
(with the convention that 
). This is shown in the following theorem by de Castro and Gamboa.
with 
, 
and let 
, 
be the monomials as above. Define 
. Then 
define
will be used: 
for 
, i.e. 
.
small enough it holds for 
that 
.
. Due to property 2 we know that
is singular with respect to 
and especially 
. This shows that 
. It remains to show uniqueness. We show the following: If there is a 
with support in 
such that 
, then 
. To see this, we build, for any 
, the sets
![\displaystyle \Omega_r = [-1,1]\setminus \bigcup_{i=1}^s ]x_i-r,x_i+r[.](http://s0.wp.com/latex.php?latex=%5Cdisplaystyle++%5COmega_r+%3D+%5B-1%2C1%5D%5Csetminus+%5Cbigcup_%7Bi%3D1%7D%5Es+%5Dx_i-r%2Cx_i%2Br%5B.+&bg=ffffff&fg=000000&s=0 "\displaystyle \Omega_r = [-1,1]\setminus \bigcup_{i=1}^s ]x_i-r,x_i+r[.")
(
denoting the restriction of 
to 
). However, it holds by property 3 of 
for all 
and this implies 
. Hence the support of 
. and since 
and hence 
. This can be written as a Vandermonde system
. 
such that any linear combination of these functions has at most 
is a T-system for 
and 
are in the interior of 
which is non-negative and vanishes exactly the the point 
and let 
be a complete T-system on 
is a T-system on 
). Then it holds: For any distinct reals 
and 
between two set 
and 
play the roles of a similarity measure and regularization terms, respectively. While he also treats the issue of noise in the operator and the multiple regularization terms, I was mostly interested in his approach to the general similarity measure. The category in which he works in that of topological spaces and he writes:
[...], we will completely discard all assumption of a linear structure and instead consider the situation, where both the domain 
are mere topological spaces, with the topology of 
continuous), Markus uses the following family of 
define
if 
for all 
. Moreover, the condition that 
iff 
implies that 
-penalties (which I usually call 
-penalty as a replacement for the usual quadratic (
not be underestimated.”
![{\psi_i(x) = h^{-1/2}\chi_{[ih,(i+1)h]}(x)}](http://s0.wp.com/latex.php?latex=%7B%5Cpsi_i%28x%29+%3D+h%5E%7B-1%2F2%7D%5Cchi_%7B%5Bih%2C%28i%2B1%29h%5D%7D%28x%29%7D&bg=ffffff&fg=000000&s=0 "{\psi_i(x) = h^{-1/2}\chi_{[ih,(i+1)h]}(x)}")
. Thus, I work with matrices 
and vectors 
and 
. 
in the interval ![{[0,1]}](http://s0.wp.com/latex.php?latex=%7B%5B0%2C1%5D%7D&bg=ffffff&fg=000000&s=0 "{[0,1]}")
, namely 
, and a value 
. Now I consider the data 
and 
. Now I aim at solving
). In the numerics, I have to scale 
, i.e. I solve
:
: 
: 
: 
:
penalty term
be linear, bounded and injective and let 
have finite support. Moreover let 
and 
. Furthermore, denote with 
the minimizer of
it holds that
)
. I scale 
and plot it doubly logarithmically against 
”)Now we repeat Experiment 
; moreover, it is slightly smaller. Then, this peak moves towards the right position and is also getting larger. Finally, the peak arrives at the exact position and remains there while approaching the correct height.
-penalties, that is, studying the Tikhonov functional 
.
penalty term
we get 
.
leads to 
instead of 
.
since the growth of the 
. Then, 
to the upper branch of the (multivalued) inverse of 
is not at the place at which the second local minimum occurs. It is a little bit larger: In “
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 
). Aiming at an iteration, we fix some of the 
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 
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.
