When performing constrained optimization on a smooth, convex function using coordinate descent, for what types of constraints will the algorithm work ? (i.e. converge or reach an approximate optimum within a tolerance of the constraint)

My understanding is that coordinate descent will work for

  • Box constraints: e.g. $x_1 \leq -1$ and $x_2 \leq -1$
  • Linear constraints: e.g. $x_2 \leq -x_1 -1$
  • Any others ?

In other words, how can we know whether or not coordinate descent can be applied to a contrained optimization problem ?

PS: irrespective of whether this is the right algorithm to use

up vote 2 down vote accepted
+50

The bland answer is that to solve constrained optimization problems, you need an algorithm that knows and uses the constraints - simply applying unconstrained optimization algorithms will not work.

Box constraints

Taking the algorithm you described in your answer, it will ''not work'' for box constraints, depending on the value of the step-size $\alpha$;

Take $f(x) = x$, $x \leq 0.9$, start at $x_0 = 0$ with a step-size $\alpha=1$.

The only step available does not satisfy the constraint.

You can decrease $\alpha$ to make it ''work'', but you can always find a function/starting point for which it does not work; the correct step-size depends on the interaction between the function and the constraints and thus require solving a constrained optimization problem to set it.

If you are able to solve the subproblem of finding the minimum along the dimension you are optimizing while respecting the constraint, i.e. taking steps $$x_i^{k+1} = \arg \min_{x_i \in C} f(x_1^{k}, ..., x_{i-1}^{k}, x_i, x_{i+1}^{k}, ..., x_D^{k}),$$ you can solve box constraints, as in your first reference.

Linear constraints

However, this approach will choke on linear constraints.

Take $f(x,y) = x^2 + y^2$, with $x + y < -1$. The minimum is at $(-0.5,-0.5)$, but if you start at $(-1,0)$ you can not make progress on $x$ (not allowed to be bigger than $-1$) nor $y$ (is at the minimum given $x = -1$).

Your second ref. is able to get around that issue by considering block coordinate updates; changing $k$ coordinates at each iteration makes it possible to get around linear constraints involving less than $k$ variable at a time.

Non-linear constraints

Your non-linear constraint is also non convex; start at $(0,-3)$ and the algorithm would converge to $(0, -2.9...)$, not at the minimum.

What to do

You can either use a constrained optimization algorithm (Frank-Wolfe comes to mind) or re-parametrize your problem so that it incorporates the constraints; if you want to find the minimum of $f(x), x \geq 0$, try to find the minimum of $g(y) = f(y^2), y \in \mathbb{R}$

  • Excellent answer thanks a lot - you are right I did have to "cheat" when building the toy examples below - forcing the starting points at specific values. My feeling is that by randomly initializing the starting point within the constraint we could get around some limitations. But of course this is less optimal than alternative methods – Xavier Bourret Sicotte Jul 10 at 10:21

Perhaps this question is more difficult than I thought, or would be better asked on math.stackexchange.com. But since it arose in the context of SVM I will leave it here.

There are some papers discussing coordinate descent and constrained optimization with the following key words.

  • Linear and box constraints and blocks of primal variables here
  • Coupled constraints, Compact convex sets and Polyhedra here
  • A cryptic MIT paper

While the mathematics are beyond me, I will proceed to show visually and experimentally that for the following toy, convex function, coordinate descent works for box, linear and highly non linear constraints.

Consider the function to be minimized:

$$f(x_1,x_2) = .01x_1^2 + 0.03x_2^2$$ $$\nabla f = [2 \times 0.01 x_1, 2 \times .03 x_2]$$

Since the gradient has only terms in $x_1$ and $x_2$ respectively, we can evaluate it at each step $k$ holding the other variable constant. Checking the constraint at each step allows to

  • Do nothing if $x_i^{(k+1)}$ has a value outside the constraint boundary
  • Update $x_i^{(k+1)} = x_i^{(k)} - \alpha \ \nabla_i \ f(x_1, x_2)$ otherwise

A few examples

1) Box and 2) linear constraints

  • $c1: \ x_1 \leq -1 \ \ c2: \ x_2 \leq -1.5 $
  • $c: \ x_1 + x_2 \leq -2$

enter image description here

3) Non linear constraint

  • $c: \ (x_1 + 1.5)^3 + (x_2 + 1.5)^3 \leq 2$

enter image description here

Next steps

Perhaps a function which is convex, but whose gradient has cross terms $x_1x_2$ will prove more difficult or even impossible to optimize using CD

  • In general, it is not possible to make CD work in constrained problems without adapting it for the constraints at hand. Linear constraints don't necessarily work; take $f(x,y) = x^2 + y^2$, $x + y <= -2$ and start at $(-3,-3)$. You will hit a wall (unless using decreasing step-sizes). Non-convex constrained sets won't work either; start your example at $(0,-3)$ and you will converge to $(0,-2.9...)$ – Winks Jul 10 at 8:31
  • thanks for the comment ! Do you think you could expand it a little and post it as an answer ? 1) it will help me better understand your points and 2) I don't want 50 hard earned bounty points to go to waste ! – Xavier Bourret Sicotte Jul 10 at 8:35

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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