Talk:Convex optimization

The layout and presentation could be much better. I know it's a stub, but what little there is could at least be readable. 163.1.159.21 16:48, 14 May 2005 (UTC)

Convex functions

I see "convex optimization" applied to nonlinear functions with multiple minima. In that context are people really talking just about some convex portion of the domain around a local minimum? Similarly, is it still convex optimization if you are looking for the minimum of a Y-shaped valley where the minimum is at the bottom of the Y? What if it wasn't Y-shaped but more V-shaped so that you could draw an ellipse over either valley in which the function is convex? —Ben FrantzDale 19:50, 31 January 2007 (UTC)

For convex optimization the function to be optimized has to be convex. But then any local minimum is global minimum, so local optimization is the same as global optimization. At least that's how I know it. Oleg Alexandrov (talk) 02:38, 1 February 2007 (UTC)

Perhaps some edge-case examples would be helpful. For example, is Rosenbrock's banana function a convex function? I tend to think not (since the valley curves). —Ben FrantzDale 20:56, 5 February 2007 (UTC)

Well, if a function is not convex, then you can't do convex optimization. But you can still do optimization however, it is just you are not guaranteed a global minimum. I fail to see what your point is, with the above. Sorry. :) Oleg Alexandrov (talk) 04:42, 6 February 2007 (UTC)

My point is I think I understand what it means for a function to be convex, but I'm not 100% sure. For that reason I'd like to see some edge-cases explained. Is a curving valley such as the banana function convex? (I think it is not.) My sense is that a convex function is one that has an n-dimensional valley that doesn't curve too much so that if you keep heading down hill you'll be moving closer to the minimum. (Whereas in a curved valley you might be heading downhill but away from the actual minimum.) Is that right? —Ben FrantzDale 13:37, 6 February 2007 (UTC)

There is no graph on the "banana function" page, so I can't tell. Here is a convex function, Image:Convex-function-graph-1.png, and here is a function which is not convex, Image:Quasiconvex function.png. A greater help would be to read the convex function article rather than this one. Oleg Alexandrov (talk) 02:15, 7 February 2007 (UTC)

I've read up on convex function. The thing I want to understand is what makes convex optimization special. It feels like it's because, with a convex function, moving by ε downhill always moves you closer to the minimum. (Intuitively it seems like that property would make an optimization problem much more tractable.) Alternately, I'd like to understand what goes wrong in optimizing a function that isn't quite convex. —Ben FrantzDale 04:28, 7 February 2007 (UTC)

Not much goes wrong if the function to optimize is not convex. You may just have more than one local minimum. Try to see how your "ε downhill" intuition would work for Image:Nonquasiconvex function.png which is not convex. Oleg Alexandrov (talk) 04:47, 7 February 2007 (UTC)

Actually that picture is not a very good example since the function in question is not convex in general, but it is convex around the local minima. See again Image:Quasiconvex function.png which is not convex at all but for which your "ε downhill" argument seems to still work. Oleg Alexandrov (talk) 04:55, 7 February 2007 (UTC)

Both of those pictures obviously satisfy my "ε downhill" argument around their minima. I folloed the external links to a full-length PDF textbook. On page 16 of that (p. 30 of the PDF) it says

In this context Rockafellar stated, in his 1993 SIAM Review survey paper [Roc93],

In fact the great watershed in optimization isn’t between linearity and nonlinearity, but convexity and nonconvexity.

Presumably there is something special about convex functions that I am missing. (Or else, the analisys doesn't work for non-convex functions but actual algorithms might work reasonably well for "almost convex" functions.) Thanks. —Ben FrantzDale 05:39, 7 February 2007 (UTC)

OK, I don't know convex optimization so well. What I know is that convexity is profoundly important in the sense that if the function is convex, you are guaranteed to have a global minimum, and if it is strictly convex, that minimum is unique. This is immensely important, since then you will arrive at the minimum starting from anywhere. If your function is not convex, you always need to worry, especially in problems involving millions of variables, that the solution you found is only a lousy local minimum, and there are many other solutions in the search space which are much more optimal but which can't be easily found. There are many algorithms which can help in that case, which search for a solution randomly, etc, but the problem of finding the global minimum of a non-convex function is (I think!) NP-hard, meaning that it is impossible to do in practice. Oleg Alexandrov (talk) 16:30, 7 February 2007 (UTC)

Thanks. Perhaps someone with more background on the subject can comment. What you said sounds right, although as I understand convexity, there are plenty of non-convex functions for which there is exactly one minimum and that is the only point with a zero derivative, which seems naively like it would be just as easy to minimize. Like I said, I'm trying to grock what makes convexity special, hence the "what goes wrong if..." questions. Thanks agian. —Ben FrantzDale 16:50, 7 February 2007 (UTC)

It is just very hard to prove in general that a given non-convex function has a unique minimum. And most non-convex functions have many local minima. So practically speaking, non-convex function == no unique minimum, then what I said above applies. Oleg Alexandrov (talk) 04:17, 8 February 2007 (UTC)

After thinking about it more, it looks like gradient descent solvers can work on nonconvex functions, but e.g., the simplex method does not because the real minimum could "leak" out of the simplex as the simplex shrinks. —Ben FrantzDale 20:43, 10 April 2007 (UTC)

Gradient descent works for non-convex problems, but one end up only with local minima only. Now, the simplex method works only for linear problems as far as I know, so even more particular than convex problems. Oleg Alexandrov (talk) 03:03, 11 April 2007 (UTC)

Hmm. There are non-convex nonlinear functions with a single global minimum (e.g., a bowl with an extra dent at the bottom). Basically I'm trying to figure out why convexity is important. If it is important rather than just "functions with a single global minimum, then there has to be a case for which nonconvex functions that may still have a single global minimum cause an algorithm to fail. It could be that I don't understand the simplex method exactly. —Ben FrantzDale 04:42, 11 April 2007 (UTC)

"Convex minimization" would be better for this article

The theory of convex optimization pertains to convex minimization, not maximization (apart from a maximum boundary principle). Maximizing (even quadratic QP) convex functions (on convex subsets) is NP hard. Shouldn't the title of the article be clarified to "Convex Minimization"? Kiefer.Wolfowitz (talk) 14:32, 7 June 2009 (UTC) I updated the discussion to specific "convex minimization" where appropriate.Kiefer.Wolfowitz (talk) 15:49, 7 June 2009 (UTC)

Problem Hierarchy: QP covers LP (not shown in the illustration)

Would somebody improve the illustration of the "problem hierarchy", please?

Hierarchical representation of common convex minimization problems

Convex quadratic programming (QP) (with linear constraints) is more general than linear programming.

I would not object to somebody changing the QP with Q constraints to simply QP (with linear constraints). Thanks. Kiefer.Wolfowitz (talk) 19:47, 7 January 2010 (UTC)

I removed the still wrong diagram. Kiefer.Wolfowitz (talk) 16:39, 21 July 2010 (UTC)

Grammar

The first sentence is gramatically wrong: "is focuses" -> "focuses" —Preceding unsigned comment added by 139.179.161.17 (talk) 12:36, 28 February 2010 (UTC)

Abstract convex programming

Does anyone know where I can find some information about "abstract convex programming"? By this I mean minimising a convex function over a convex feasible set. That is, there are no explicit constraints, all you know is that the feasible set is convex. —Preceding unsigned comment added by 203.167.251.186 (talk) 04:48, 19 July 2010 (UTC)

The best theoretical and computational work is very challenging. Start with Dimitri Bertsekas's books or his on-line lecture notes. Some current research is described in Claude Lemaréchal's lectures on "Lagrangian Relaxation" at a summer school, which was published in Springer's lecture notes in computer science (Combinatorial Optimization).

(Such questions are better reserved for your professor or for on-line lists: Look at Optimization Online.)

Avoid the term "Abstract convex programming", which is established for a very mathematical approach to more general problems (Rolewicz & Pallaschke, Ivan Singer, the late Rubinov, etc.). Thanks! Best regards, Kiefer.Wolfowitz (talk) 16:37, 21 July 2010 (UTC)

Thanks. Much appreciated. —Preceding unsigned comment added by 203.167.251.186 (talk) 21:35, 26 July 2010 (UTC)

Convex Optimization in practice

In the introductory section it is mentioned that

With recent improvements in computing and in optimization theory, convex minimization is nearly as straightforward as linear programming.

While that is certainly true in theory (existence of a rich duality theory and polynomial-time algorithms), I am not so sure to which extent this is true in practice. For linear programs, simplex and interior-point methods can solve problems with input size (nonzero entries on constraint matrix) on the order of millions on a desktop computer. But even for a well studied and highly structured class of convex optimization problems, namely, semidefinite optimization, current solvers do not fare very well even for problems with input size on the order of a few thousand nonzeroes. See the benchmarks at http://plato.asu.edu/bench.html.

It is obvious that this is not a fair comparison, given that the codes for LPs are obviously much more mature. However, semidefinite optimization solvers (as well as general convex optimization software) faces an apparently intrinsic problem of numerical stability.

If anybody else can confirm that I am not completely outdated about this, could you please add these remarks to the page, or let me know so that I can write the remarks myself? Thanks.

--Marcelkcs (talk) 15:20, 4 June 2011 (UTC)

Factual accuracy

I would like to raise concerns about the recent edits to the article. Specifically, I find the claim that "the field of convex optimization also considers the far more difficult problem of maximizing convex functions" questionable. According to Boyd/Vandenberge, which is considered a standard reference, a convex optimization problem has three additional requirements as compared to a general optimization problem, namely 1) the objective function must be convex (in the case of minimization), 2) the inequality constraint functions must be convex, and 3) the equality constraint functions must be affine (Section 4.2.1, pp. 136-). In a concave maximization problem, requirements 2) and 3) are fulfilled but the negative of the objective function (which is concave) is maximized. Since they are equivalent, both these problems are referred to as convex optimization problems (p. 137). A problem that does not fulfil these requirements, for example the problem of minimizing a convex function subject to an equality constraint that is not affine, is referred to as a nonlinear optimization problem and is treated with global optimization methods. The term "convex minimization" seems to focus only on requirement 1) above, therefore a reference would be needed to show that this is standard terminology. Isheden (talk) 19:36, 26 October 2011 (UTC)

Convex "optimization" is vague. Convex minimization is preferred for minimization problems. Advanced research, following Rockafellar, uses indicator functions or penalty representations of constraints. There is no need to set up a convex subset in the definition (although it has some pedagogical value, and is used by Polyak and Bertsekas's books).

The Boyd Vandenberge book is good, especially for pedagogy and for its engineering applications. It also considers quasi-convex problems, etc. (Don't they mention quasi-convex constraint functions, also?)

There is a theory of convex maximization, which should be covered in an article on convex optimization. I gave a reference to a theoretical result in Rockafellar, and I mentioned classic articles by Sahni and by Vavasis, et alia.

Problems with non-convex constraints are not always solved by global optimization methods. Often they are approximately locally minimized with local methods or by global methods.  Kiefer.Wolfowitz 19:53, 26 October 2011 (UTC)

I beg to differ. In Rockafellar (1997), Section 28 (p. 273), the term "ordinary convex program" is defined in a very similar way to Boyd's definition of a "convex optimization problem". Rockafellar even suggests a more rigorous definition on the same page as a tuple of functions satisfying the conditions given. Indicator functions and penalty representation are discussed in Boyd as well, see 11.2 for the use of the indicator function to make inequality constraints implicit in the objective, and 5.4.4 for the price interpretation of violating an inequality constraint. Perhaps what you mean is that the Lagrangian (see 5.1.1), which includes the constraints, is a convex function, and that "convex minimization" is about finding the minimum of this function (called the Lagrange dual function, see 5.1.2)? I think that what you call the theory of convex maximization would fit better in the convex analysis article, since this is a basic property of a convex function. The section "Generalized convexity" as it is formulated now would fit better in the article convex function. And you're right that local methods are often used when finding the global optimum is difficult, but the point of convex optimization is that it is in a certain sense the broadest class of nonlinear optimization problems for which any local optimum is the global optimum. Isheden (talk) 21:51, 26 October 2011 (UTC)