I have a nonlinear programming problem as \begin{align}\min_x \quad& x^TQx\nonumber\\ \text{s.t.}~~~~&f(g(x))\leq b\nonumber\\ & x\geq 0\end{align} Here $x$ is a vector, $Q$ is a positive semidefinite. $f$ is a quadratic function over $g(x)$. $g(x)$ is a scalar nonlinear function. For example, $g(x)=x_1^3+\sqrt{x_2}$ with $x_1$ the first element of $x$, and $x_2$ is the second element. $f(g(x))=g(x)^2.$
The problem is a non-convex nonlinear programming. Generally, many existing nonlinear programming methods can be adopted here.
I intend to seek some simpler methods which can be applied to this type of problem. Considering that, if $g$ is linear, the problem is convex. Can we just linearize $g(x)$ at each iteration? If yes, how to guarantee the convergence?
I do not know much about optimization, could anyone provide me some suggestions or relevant materials? Thanks!
@lulu, I have an idea to find at least a local solution of this problem. There is no convergence guarantees but I think it is a better approach than the linearization of $g(x)$ (which may introduce errors when the linearization is around a point far from the solution).
The idea is to solve the problem alternately. Assuming that $g(x)$ is a continuous function, the steps are the following:
(1) Solve the convex optimization problem
\begin{align}\min_{x_k} \quad& x_k^TQx_k\nonumber\\ \text{s.t.}~~~~ & x_k\geq 0.\end{align}
(2) Test if $-\sqrt{b} \leq g(x_k) \leq \sqrt{b} $. If it is, the problem is solved. Otherwise, go to the next step.
(3) On one hand, if $g(x_k) < -\sqrt{b}$, find $x_{k+1}$ closest to $x_{k}$ such that $g(x_{k+1}) = -\sqrt{b}$. On the other hand, if $g(x_k) > \sqrt{b}$, then find $x_{k+1}$ closest to $x_{k}$ such that $g(x_{k+1}) = \sqrt{b}$.
(4) Solve the convex optimization problem
\begin{align}\min_{x_{k+2}} \quad& x_{k+1}^TQx_{k+2} + \mu\|x_{k+2}- x_{k+1}\|^2 \nonumber\\ \text{s.t.}~~~~ & x_{k+2}\geq 0,\end{align} for some regularization factor $\mu$.
(4) Go to the step (2).