Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. It only takes a minute to sign up.
Sign up to join this community
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?
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?
As Geoff Oxberry points out in his comment, if you know a priori that $x_k=0$ for $k\leq i$ and $k\geq j$, then there's nothing to optimize with respect to these variables and you can just solve the (smaller) reduced unconstrained problem $\min_{x\in\mathbb{R}^{j-i-1}}\hat f(x)$, where $\hat f$ takes only the nonzero variables as input.
If this is not feasible for some reason, you might want to update your question to include this in order to get concrete advice. But to address the question in your comment: One possible approach to solve a constrained optimization problem of the form $\min_{x\in C} f(x)$ for some (convex) set $C\subset\mathbb{R}^n$ (in your case, $C=\{x\in\mathbb{R}^n: x_k=0,\ k\leq i \text{ or }k\geq j\}$) is projected gradient descent (which is a special instance of proximal gradient methods), defined by the iteration $$x^{k+1} = P_C \left(x^k - \alpha_k f'(x^k)\right)$$ where $P_C$ is the projection onto the convex set $C$ (in your case, simply setting the corresponding $x_k$ to zero) and $\alpha_k$ is a suitable step size (e.g., of Armijo type). If $f$ is smooth, this iteration converges to a stationary point (which is a minimizer if $f$ is convex); see, e.g., PH Calamai, JJ Moré: Projected gradient methods for linearly constrained problems, Mathematical Programming 39, 93-116.
In principle, this is what you are doing, except you are using the conjugate gradient as a search direction instead of the gradient. I haven't checked the proofs, but I'd assume that your version should still work as long as you have a descent direction. Whether it is reasonable, though, depends on your definition (it is a bit of a sledgehammer approach...)
Even if $i$ and $j$ are known, this is hard if the object function is nonconvex. Therefore, if only the object function is convex or concave, you find exact solution of this problem. if the object function is nonconvex, you will find approximate solution of this problem by DC Programming.
$).
$\endgroup$
Jun 21, 2013 at 11:57