2
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ "$f(x)$ is a quadratic function over $g(x)$." How? $f(x) = g^2(x)$ or $f(x) = g^2(x) + cg(x)$? $\endgroup$ – Alex Silva Dec 5 '16 at 7:44
  • $\begingroup$ @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". $\endgroup$ – AlexR Dec 5 '16 at 7:45
  • $\begingroup$ @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. $\endgroup$ – Alex Silva Dec 5 '16 at 7:53
  • $\begingroup$ @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$. $\endgroup$ – lulu Dec 5 '16 at 7:56
  • $\begingroup$ @Alex Silva please assume the functions are of proper dimension. $\endgroup$ – lulu Dec 5 '16 at 7:58
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – lulu Dec 7 '16 at 1:30
  • $\begingroup$ 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? $\endgroup$ – lulu Dec 7 '16 at 1:41
  • $\begingroup$ 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. $\endgroup$ – Alex Silva Dec 7 '16 at 13:45
  • $\begingroup$ 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? $\endgroup$ – lulu Dec 9 '16 at 6:44
  • $\begingroup$ 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. $\endgroup$ – Alex Silva Dec 10 '16 at 17:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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