# establish that a minimization problem is indeed a convex minimization problem and then solve it

I have a minimization problem of the following form : $$\underset{\lambda (x) \in [0,1]}{min} \int_\Omega (1- \lambda(x))C_s(x)dx + \int_\Omega \lambda(x)C_t(x)dx + \alpha\int_\Omega |\nabla\lambda(x)|dx$$

$\Omega$ is a region in $\mathbb{R}^2$ ( for example a rectangular region )

$C_s, C_t$ are some kind of cost functions.

First I want to be able to establish that this problem is indeed a convex minimization problem. Having done that I want to find out various methods that can be used to minimize. I have gone through the artice on wikipedia about convex optimization and I don't find it much helpful to my cause. I would like to know what are the various methods I should read that could help me solve this kind of a minimization problem. I have with me a book on convex optimization by Stephen Boyd. But the book seems large and I don't know where to start.

-

## 1 Answer

Your problem looks convex to me. But if you are talking about Convex Optimization by Boyd and Vandenberghe, it only seems useful if you want to consider approximations of $\lambda$ with a finite number of variables. Otherwise you may want to look into calculus of variations. However, as the problem stands, it may not have an optimum in the space of continuously differentiable functions, or even in the continuous, almost everywhere differentiable functions. In fact, for many choices of $\Omega, C_s, C_t$ I think the solutions will tend to an infeasible functions of the form $\lambda(x) = 1$ if $C_s > C_t$, $\lambda(x) = 0$ otherwise. If you change $|\nabla \lambda(x)|$ to something differentiable and strictly convex like $|\nabla \lambda(x)|^2$ it might be a different story.

From a quick look at the article you mention, I gather that this variational problem is just an intermediate step in turning a non-convex discrete problem into a convex numerical problem. The "degenerate" solutions I warned about are in fact precisely what is ultimately wanted. So, to apply the techniques developed there you would definitely need to understand convex (numerical) optimization problems, but I doubt that that will be enough. A degree in physics would probably be useful.

Maybe someone else can recommend literature about variational calculus. For a quick introduction you might take a look at this PDF.

-
In the paper "A study on continuous max flow and min cut approaches" by boykov et al., the authors claim that the problem is a convex minimization problem. " More specifically solving (it) leads to a sequence of global binary optimums through thresholds of its optimum $\lambda^*(x) \in [0,1]$ by any value $t \in (0,1]$." I have little familiarity with this field of mathematics.I understand that I have infinite number of variables because I am in the continuous domain? What difference does changing $|\nabla\lambda(x)|$ to $|\nabla\lambda(x)|^2$ make?Book for calculus of variations ? – AnkurVijay Jun 11 '11 at 7:47