# any better approach to solve a nonlinear programming with a nearly convex structure?

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!

• "$f(x)$ is a quadratic function over $g(x)$." How? $f(x) = g^2(x)$ or $f(x) = g^2(x) + cg(x)$? Dec 5, 2016 at 7:44
• @AlexSilva From context it appears to me that $f$ is a quadratic function, i.e. $f(x) = x^TAx + c^Tx ( + d)$ cf. OP paragraph 3: "Considering that if $g$ is linear the problem is convex". Dec 5, 2016 at 7:45
• @AlexR, Are you sure that $f$ is a multivariate function? If it is, $g(x)$ cannot be a scalar function on $x$. It is not clear to me. Dec 5, 2016 at 7:53
• @Alex Silva Let's take a simple case as an exmple, $g(x)=x_1^3$, then $f(g(x))=(g(x)+c)^2=(x_1^3+c)^2$.
– lulu
Dec 5, 2016 at 7:56
• @Alex Silva please assume the functions are of proper dimension.
– lulu
Dec 5, 2016 at 7:58

@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).

• Thanks a lot. The algorithm is nice. One problem is that in each iteration, the nonlinear equality has to be solved, I am not sure the computation complexity can be reduced or not.
– lulu
Dec 7, 2016 at 1:30
• another problem is that the solution in the third step may not be unique. (I notice that we should select the solution $x_{k+1}$ nearest to $x_{k}$, but there is still some possibility that the solution is not unique. ) If this is the case, how to conduct the fourth step?
– lulu
Dec 7, 2016 at 1:41
• You should have some information about $g(x)$, otherwise the problem is very hard to solve. I have supposed that $g(x) = cte$ can be solved by some inexpensive-computational method, but it is true that if it is a complicated function, the complexity of the problem can be compromised. If you find more than one solution at some iteration, pick randomily one of them. For next iterations, it is expected in general that it does not happen often. Dec 7, 2016 at 13:45
• May I know what is 'cte' short for? By the way, it seems there is a typo in the fourth step. I guess the objective function should be $x_{k+2}^TQx_{k+2}$, instead of $x_{k+1}^TQx_{k+2}$. Right?
– lulu
Dec 9, 2016 at 6:44
• 1) cte = constant. 2) No, it is not a typo, but $x^{T}_{k+2}Qx_{k+2}$ can be another option. I prefer $x^{T}_{k+1}Qx_{k+2}$ because is a linear term. You can test both. Dec 10, 2016 at 17:13