Tell me more ×
Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. It's 100% free, no registration required.
up vote 1 down vote favorite

I want to solve a nonlinear optimization problem $$\underset{\mathbf{x}\in \mathbb{R}^n}{\operatorname{argmin}} f(\mathbf{x})$$ subject to a support constraint $$\mathbf{x}=[x_1,\cdots,x_n]^T, \quad x_1=x_2=\cdots=x_i=0,\quad x_j=x_{j+1}=\cdots=x_n=0 \quad (1<i<j<n)$$

Is there any algorithm or library able to solve this kind of problem?

share|improve this question

1 Answer

up vote 1 down vote

If $i$ and $j$ are known, then the resulting constraints on $x_{1}, \ldots, x_{i}$ and $x_{j}, \ldots, x_{n}$ are all linear, and easy to implement in nonlinear programming solvers.

However, if $i$ and $j$ are actually decision variables, then the problem should be formulated as a mixed-integer nonlinear program (MINLP) and solved using an MINLP solver.

Perhaps I'm misunderstanding the question?

share|improve this answer
Hi Geoff, you're right, i and j are known in my case. Could you elaborate how to incorporate the constrain? Right now, I'm using nonlinear conjugate gradient method, and I include the constraint by set $x_1, \cdots, x_i$ and $x_j,\cdots,x_n$ to be zero right after each update of $\mathbf{x}$. But I am not sure if this is reasonable. – chaohuang Feb 23 at 3:34
I haven't programmed nonlinear CG; I tend to use high-level nonlinear optimization libraries that accept nonlinear programs as arguments, in which case these constraints are just additional arguments to a solver call. In terms of matrix operations, the simplest way to implement your constraints is to treat $f$ as a function of the variables $x_{i+1}, \ldots, x_{j-1}$ only, and set the remaining variables to zero. The resulting function can be treated as an unconstrained problem (because in those variables, it is). Using nonlinear CG on this problem will make matrix operations more efficient. – Geoff Oxberry♦ Feb 23 at 8:45
It would be overkill (and perhaps harmful) to consider your problem as a constrained optimization problem. Simply eliminate the variables $x_1, \ldots, x_i$ and $x_j, \ldots, x_n$. You are left with an unconstrained problem in the variables $x_{i+1}, \ldots, x_{j-1}$. You can use any unconstrained method (Newton if you have second derivatives, (L-)BFGS, nonlinear CG, etc.) – Dominique Feb 23 at 21:17
@Dominique: I just said that. – Geoff Oxberry♦ Feb 23 at 22:17
@GeoffOxberry Sorry I must have missed your comment, but it's worth stressing that the OP's problem is inherently unconstrained. – Dominique Feb 24 at 4:09

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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