Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Assume that we optimize a convex problem (convex objective and linear constraint) over a set of functions (say $L2$). Consider now the same optimization problem (same objective and same linear constraint) but now we optimize over a subset of $L2$. For example the set of affine functions or the set of polynomials of degree 2.

Is there a geometric relationship between the optimum of the first problem (optimizing over the set L2) and the second problem (optimizing over the subset of affine functions).

For example, can it be that the optimum of the second problem is the projection of the optimum of the first problem on the subset of affine functions in the sense of certain distance.

Does this question make sense and if so was this done in some textbook or perhaps an old paper? Many thanks for your help.

share|improve this question
I don't think it's as simple as projecting the optimum of the first problem onto the subspace used in the second problem. I'm not an expert, but maybe you'll find something useful in the theory of gamma-convergence: en.wikipedia.org/wiki/%CE%93-convergence. This is often used in finite-element theory to show that solutions of the FEM problem converge to solutions of the continuum problem. –  jvkersch Aug 4 '11 at 17:38
Fixed title so that search engines will recognise it. –  David Roberts Sep 2 '11 at 1:13
add comment

1 Answer

It "can be" but usually is not. Think of it in reverse. Start with a problem of minimizing a convex function $f$ over a convex set $S$ in vector space $V$, where the minimum value happens to be positive. Extend $f$ to the cone $C = \{(ts, t) \in V \times {\mathbb R}: t \ge 0, s \in S \}$ by $f(ts,t) = t f(s)$. The new convex function on $C$ has its minimum at $(0,0)$. But that does not help you find the minimizer of $f$ on $S$, which could be any extreme point of $S$.

share|improve this answer
I agree with the counter example. It shows that the statement is not true for the usual norm. But if the norm (and the associated projection) is appropriatly constructed from the form of the objective than maybe (0,0) ca give us information on the minimizer on S. This means that my question was not properly written. Many thanks for your feedback. –  user16953 Aug 5 '11 at 1:02
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.