In all instances of convex optimization I know of, the dimension of the vector space is defined beforehand. Is there any work on convex optimization over a vector space of varying dimension?
For example,
$$\begin{array}{ll} \text{minimize} & k\\ \text{subject to} & x_1 + \cdots + x_k = 10\\ & 1 \leq x_i \leq 2\end{array}$$
This reminds me of the compressed sensing literature. Suppose that you know some upper bound for k, let that be K. Then, you can try to solve $\min||{\bf x}||_0$ subject to ${\bf 1}^T_K{\bf x}=10$ and ${\bf x}_i\in[1,2], \; \forall i\in\{1,\ldots,K\}$. The 0-norm counts the number of nonzero elements in ${\bf x}$.
This is by no means a convex problem, but there exist strong approximation schemes such as the $\ell_1$ minimization for the more general problem $\min||{\bf x}||_0, \;{\bf A}{\bf x}={\bf b},\; {\bf x}\in\mathbb{R}^{K\times 1}$, where ${\bf A}$ is fat. If you googlescholar compressed sensing you might find some interesting references.
Dimension minimization problems are notoriously hard (a standard example is: given a graph $G,$ what is the minimal dimension Euclidean space where the graph can be embedded with unit edge lengths? (minimum is finite since every graph with N vertices can be realized with unit edge lengths in dimension $N(N-1)/2 -1.$)) Or, more generally, finding the minimal realization dimension of a metric space. All of these questions are NP-hard. There is a large literature on the subject (look under Maryam Fazel, or Stephen Boyd), but most of the work is purely heuristic. Candes and Tao's work on compressed sensing is one of the few bright spots where rigorous results are known.
You may be interested in some of the recent work of Bill Helton and his collaborators. The idea (very roughly) is to study convex problems which can be defined in some intrinsic way without reference to the dimension of the problem, usually in terms of matrix equations and inequalities (semidefiniteness constraints). For example the existence of a quadratic Lyapunov function for a linear system reduces to such a form: the matrix equations and inequalities you write down look the same regardless of the dimension of the system if you're representing each of these matrices with a symbol rather than an $n\times n$ array. This means there is some "uniformity" to the problem.
They study this by viewing the matrices involved as noncommuting indeterminates. They go on to define convexity and related ideas for noncommutative polynomials. The algebraic structure of this "noncommutative geometry" is very rigid (much more than the commutative case), so you can say a lot about how these polynomials must look. This in turn tells you things about which problems can be cast in such a uniform way, and perhaps why so many of them are semidefinite programs.
I don't know enough to even call myself a novice in this area, let alone an expert, so I'm sure I am not doing this work justice. I was hoping someone more qualified might come along and give a better explanation, but no one has mentioned it so far and it may be what you are looking for, so I gave it a shot.
A lot of convex optimization theory carries over to infinite dimensions. The $\mathbb{R}^{\infty}$ space is the injective limit of $\mathbb{R}^1 \subset \mathbb{R}^2 \subset \cdots$ and its elements are finite sequences of real numbers, so you should be able to investigate finite-dimensional questions of varying dimension by working with such a space. But I can't say I've seen any applications along these specific lines. If you could go into more detail about what you are trying to accomplish, people would be able to give more pertinent answers.
If $x_j$ are integers, maybe you could pose and solve this as a knapsack problem?
You can think of $x_1, x_2, \ldots, x_k$ (for some large enough $k$) as all the possible items (i.e. numbers) that you want to place into your knapsack and then solve $$ \begin{align} \min &\sum_{j=1}^k I_j\\ \text{s.t.}&\sum_{j=1}^k x_j I_j = 10 \end{align} $$ where $I_j=1$ if $x_j$ is put in your knapsack, otherwise $I_j=0$.
If $x_j$ are not integers, then maybe there is a nice way to extend the knapsack approach?
