Does the projection of a vector $X$ in $\mathbb{R}^k$ onto a closed convex cone (positively homogenous set) $C$ in $\mathbb{R}^k$ with respect to a positve definite projection matrix $V$ always exist? i.e.
$\inf_{w\in C}\left(X-w\right)^TV\left(X-w\right)=\min_{w\in C}\left(X-w\right)^TV\left(X-w\right)$
Specifically I am interested in cone $C$ with linear constraints over its elements (of course these must not violate the properties of a cone).
Many thanks
I should think that the answer indeed is "Yes". The problem at hand is that of minimizing a strictly (here in fact even strongly) convex and weakly coercive (here even coercive) function over a non-empty, closed and convex (here even polyhedral) set. Such problems have a unique optimal solution: combine the two results from convex programming which state that (a) if the objective function is strictly convex and the feasible set is closed and convex, then there can be at most one optimal solution, with (b) a version of Weierstrass' Theorem applied to the problem at hand, and which ensures that there is at least one optimal solution. (The original formulation of Weierstrass' Theorem is in R^1 and concerns continuous functions over a closed and bounded interval, but it extends to weakly coercive functions over any non-empty, closed and convex set in R^n.
I think that, additionally to Michael's quote, the solution is unique.
I don't remember where is exactly the specific proof, you can download and look the next book:
http://web.stanford.edu/~boyd/cvxbook/
Yes, indeed, and that was also stated above: "there can be at most one optimal solution". :-) Combined with the fact that there is at least one I think one can draw the conclusion that there is precisely one. ;-)
Thank you all ! This is indeed what I thought (hoped). I need this for the continuity of the $\inf ... $ function in variables other than $w$ which in turn is used to invoke the continuous mapping theorem.
But why should people keep using $\inf$ instead of $\min$?. Or could there be some specific $C$ where $\inf$ is needed?
Michael, yes, indeed!:)
(I wanted to share with Anh the existence of the book, if he didn't know it)
Oh, well, having about 500 optimization-related books on my shelves, I can hardly miss that one.
Anh: as long as the objective function is strongly convex and the feasible set is non-empty, closed and convex there is an optimal solution, and indeed a unique one. But replace strong convexity with strict convexity, and you may have to replace "min" by "inf", such as in the problem of minimizing f(x) = 1/x over, say, the set of all x greater than or equal to 1. (There is then an optimal value of 0, but it is not attained anywhere.)
So, Michael, after such a collection, what is the proposed by you book on convex optimization field?
Well, Demetris, that would depend on any factors: the purpose of the course, the background of the students, etcetera. So tell me about the objectives and scope of the course you have in mind, and the kind of students that would take it.
Michael, the question was for my personal book collection, since I have already collected many books about convex optimization (theory+algorithms), some of them are good, but some others are really a disaster...
(My focus is mainly in Algorithm Development.)
Since I like nice expositions, I would more often prefer the older ones, as the modern ones tend to be very technical. This is to some degree by necessity, but the balance between exposition and technical arguments now more often is lost, with a too strong focus on the technical development, and too little energy is put on constructing links between subjects, illustrations of results and their utilization. Further, I find that more often books today lack enough good graphical illustrations, examples, and good basic as well as advanced exercises (with answers/hints). I think this is because too often a book is written based on a series of very good technical papers, and the author tends to forget that a book should have a very different style of writing than a technical paper.
Among the best books in terms of style, layout, and sheer reading pleasure, are:
1. Lasdon - Optimization Theory for Large Systems. Classical, and focusing on problems and algorithms for large-scale problems and how to iteratively turn them into problems that are manageable so that the original problem can be solved after some coordinating steps.
2. Bazaraa, Sherali, Shetty - Nonlinear Optimization. The layout in the first edition, 1979, I think, is much nicer than the later ones from 1993 and 2005 (or is it 2006?). The layout matters a lot to me, by the way.
3. Bertsekas - Nonlinear Programming. There is a new edition every few years. Very good, accessible and nicely structured.
These three are frequently used in beginner PhD courses on nonlinear optimization. Further books that I like but have not used as much are:
4. Luenberger, Ye - Linear and Nonlinear Programming, 2nd edition.
5. Mangasarian - Nonlinear Programming.
These two are somewhat classical - not as complete as the ones above but written in a nice style, also by masters of the field. And by the way all these five books cover more than convex optimization, so I have somehow answered the wrong question. :-) I think a course on nonlinear stuff needs to cover more than the convex case, anyway.
Thank you Michael for your extensive and valuable response.
I liked Bertsekas (many exercises and graphs), Luenberger, Ye (they use vectors-very important for me, compact notation), Mangasarian (it starts from scratch-very good for beginners I think).
Of course Optimization is an extensive field, I do agree with you on this.
Thanks again!
- Badges
- Science topic
- Similar topics
- Mathematics
- Statistics
- Statistical Software
- R