Consider the following setting: g(y,V) = minw\in C(y-w)TV(y-w), C is a closed convex cone, V is positive definite and y is in Rn.
Assume an appropriate norm for (y,V), would g(y,V) be continuous in (y,V) ?
I know if C is compact then this is easy to prove. But a cone cannot be compact.
At first glance I thought this should be a trivial problem but whatever strategy I tried I got stuck in the compactness of C. So I turn to the literature and it turns out so far that continuity of such a function like g(y,V) seems to be an active area of research ( I do hope I am wrong!)
I am very naiive to convex optimization in general, particularly conic projection. So I will appreciate any hints or comments on how to tackle this problem as well as solid disproof!
Many thanks in advance
Well, let's look at it this way. If V is a real-valued, symmetric and positive definite matrix, then your objective function is strongly convex on R^n. Such functions have a unique minimum over any non-empty, closed, and convex set in R^n. It appears that your problem fits within this framework. Danskin's Theorem of course talks about a strictly convex objective function over a closed, convex and COMPACT set. So here, you want to replace the compactness with something else, and the uniform strong convexity of your objective function ensures just that.
By the way, here is a link to a revealing note on the issue:
http://www.oyama.e.u-tokyo.ac.jp/papers/nonDiffValFunc.131225.pdf
Well, let's look at it this way. If V is a real-valued, symmetric and positive definite matrix, then your objective function is strongly convex on R^n. Such functions have a unique minimum over any non-empty, closed, and convex set in R^n. It appears that your problem fits within this framework. Danskin's Theorem of course talks about a strictly convex objective function over a closed, convex and COMPACT set. So here, you want to replace the compactness with something else, and the uniform strong convexity of your objective function ensures just that.
By the way, here is a link to a revealing note on the issue:
http://www.oyama.e.u-tokyo.ac.jp/papers/nonDiffValFunc.131225.pdf
Thanks Daniel!
But in your notations, I think the bounded function mentioned in "f(y_j,V_j)(w_j) is within some bounded function of epsilon of f(y_k,V_k)(w_j)" also depends on w_j besides epsilon.
Note that - while I did not see that you in fact asked for proofs on the continuity of the optimal value, what I refer to is the stronger property of the differentiability of the optimal value. :-) So if you need only to establish the continuity of the optimal value, you can reduce the conditions somewhat.
Anh (I hope that is the correct name to use): You are quite right, I did not take into account that the sequence of minimizers might grow arbitrarily large. One can adopt the method I use to get semicontinuity: basically, m_0 (the minimizer of the limit of the sequence of functions) cannot be much smaller than the m_j's for j sufficiently large.
Can it be much larger? I think that provided V_0 (the quadratic operator approached by the sequence V_j) is strictly positive definite, the answer will be "no". I'll give that some more thought. Meanwhile, despite your overly kind upvote, I'm going to delete my prior answer on the grounds that it is simply too careless to stay around.
Okay, let me try that again. We will restrict to the open set of strictly positive definite matrices.
(1) Strict positivity of the operators means the minimizers are unique.
(2) In the class of problems under consideration, the operators are quadratic. This will make life easier below.
(3) For the moment we'll work with C=R^n (rather than a possibly proper cone therein). Item (2) implies the global minimizers, and minimum values, can be found by differentiating and solving for zero. That is, for a pair (y,V), g(y,V) is found by solving a linear system of equations, and it has a unique solution.
(4) So suppose we have a sequence (y_j,V_j) approaching (y_0,V_0). Calling the minimizers w_j (respectively w_0) and the minimal values m_j (resp. m_0), and using continuity of our linear systems, we can show that w_j-->w_0. It follows from this that m_j-->m_0 (a continuity argument).
(5) Now restrict the domain to a cone. If the minimizer w_0 lies in the cone interior then, eventually, so do all w_j for j larger than some N. In this case the above reasoning gives the desired continuity. So suppose w_0 is outside the cone or on the border.
Roughly speaking, the constrainted minimizers w_j will be the "closest" points on the cone border to their respective unconstrained minimizers. In this case "close" is defined by a weighted, rotated Euclidean metric, where the weights arise from eigenvalues of the quadratic operators, and directions from the orthogonal transformations that diagonalize the operators. (Another way to say it is we use the Euclidean metric after rotating and rescaling our coordinates). These weights/rotations exist by assumption of the matrices being symmetric and positive definite (hence diagonalizable with positive elements on the diagonal). Also they vary continuously in the (y,V) parameters. (Note: the diagonalizing matrices need not vary continuously, if there are multiple eigenvalues. But the directions and weights will vary continuously.)
The upshot of all this continuity is that the points of intersection of unconstrained minimizers with "shortest" (weighted and directed) path to C will not grow without bound. This allows one to use the usual arguments that apply when C is compact: just cut out a closed bounded part containing these constrained optimizers w_j. Wil the w_j bounded it is straightforward to show that m_j--> m_0.
Apologies for a somewhat informal, yet still belabored, description. I hope it works out better than the shorter, sleeker, wronger one from yesterday evening.
- Badges
- Science topic
- Similar topics
- Mathematics