3
$\begingroup$

We have a continuous and differentiable function $f(\cdot)$ that maps from $R^n$ to $R^n$. We are trying to solve a nonlinear least square problem:

Minimize $J(x)=\Vert f(x)-z\Vert^2$

subject to box constraints: $l_i \leq x_i \leq u_i$.

This function $f(\cdot)$ has a beautiful property that

$\forall x_1, x_2 \in R^n, x_1\neq x_2$, $(x_1-x_2)^T(f(x_1)-f(x_2))>0$.

If $n=1$, we say $f(\cdot)$ is monotonically increasing. This nonlinear least square problem can be easily solved to global minimum.

But in our real case, $n=10$. Using standard quasi-Newton method together with gradient projection, we are able to solve this problem to local minimum. And usually, they appear to be global minimum. That's why we are into investigating whether they are indeed global optimum.

Global optimality usually requires the objective function $J(x)$ to be convex, or pseudo-convex, even still valid when it's quasi-convex. Since the function $f(\cdot)$ is $10\times 10$ and complicated, we did numerical verifications based on random sampling and discover: $J(x)$ is neither convex nor pseudo-convex, but quasi-convex.

So the questions are: 1) Can we prove from the previously stated property of $f(\cdot)$ that $J(x)$ is quasi-convex? 2) If not, can we solve this problem to global optimality via non-global optimization techniques?

Thanks!!!

$\endgroup$
1
$\begingroup$

Any function $f$ that satisfies $(x-y)^T(f(x)-f(y)) \ge 0$ is a monotone function, and has the interpretation of a subgradient for a certain convex function. If $f$ is continuous and monotone, then the solution set $S=\{x:f(x)=0\}$ is convex.

The global solution of monotone equations is a well-studied problem that admits very specialized algorithms. One such algorithm is described by Solodov & Svaiter, and is guaranteed to converge to a solution $x\in S$, assuming that one does exist. Moreover, if $f$ is differentiable, then convergence is super-linear. More recent algorithms are closer to the nonlinear least-squares procedure that you have described, and allow the system of equations to be solved without an explicit merit function search, see Zhou & Li.

References

Solodov, Michael V., and Benav F. Svaiter. "A globally convergent inexact Newton method for systems of monotone equations." Reformulation: Nonsmooth, Piecewise Smooth, Semismooth and Smoothing Methods. Springer US, 1998. 355-369.

Zhou, Wei-Jun, and Dong-Hui Li. "A globally convergent BFGS method for nonlinear monotone equations without any merit functions." Mathematics of Computation 77.264 (2008): 2231-2240.

$\endgroup$
  • $\begingroup$ Hi Richard, thanks a lot for providing the detailed answer. From the papers that you provided and those subsequently citing publications, we have global convergence to the solution set $x \in S$, even when the problem is subject to convex constraints. This conclusion solves my problem when we are able to find a solution $x \in S$. However, if $z$ is not in the solution set, how can we find the best projection of $z$ onto the attainable set of $f(x)$, i.e. still solving for the least square problem? $\endgroup$ – CJ Zheng Mar 28 '16 at 21:42
  • $\begingroup$ Hi CJ, if $f(x)$ is differentiable strictly monotone, as indicated, then $f(x)=y$ is bijective, i.e. there exists a unique solution $x$ for each $y$. Proof: let the Lipschitz constant of $f$ be $L$. Then $g(x) = x - (1/L) f(x)$ is strictly contractive. $\endgroup$ – Richard Zhang Mar 30 '16 at 2:23
  • $\begingroup$ Sorry, I just reread your question and realized that I didn't really answer it. I believe strict monotonicity and Lipschitz are enough to prove quasiconvexity, but I'm not 100% sure. $\endgroup$ – Richard Zhang Mar 30 '16 at 3:30

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.