A global Optimization Approach to Non-Convex Problems

Zhaosong Lu, Yingying LanAdvances 2015 · DOI

Abstract

In this paper, a novel approach to find the global optimal solution of the special non-convex problems is proposed. The non-convex objective function is first decomposed into two convex sub-functions. Then a generalized gradient is introduced to determine a search direction and the evolution equation is built to obtain a global minimum point. By the approach, we can prevent the search process from some local minima and search a global minimum point. Two numerical examples are given to prove the approach to be effective.

Introduction

Optimization of non-convex functions presents a significant challenge due to the presence of multiple local minima. Standard deterministic algorithms, such as gradient descent, are prone to becoming trapped in these local "valleys," failing to reach the global optimum. While probabilistic methods like Genetic Algorithms or Simulated Annealing can explore the search space more broadly, they often suffer from high computational costs and sensitivity to parameter tuning. This paper proposes a deterministic strategy for a specific class of non-convex problems that leverages the mathematical structure of the objective function to bypass local traps.

Methodology

The proposed approach consists of three primary components:

1. Function Decomposition

The method targets objective functions $J(X)$ that can be represented as the difference between two convex functions: $$J(X) = f_1(X) - f_2(X)$$ This structure, known as D.C. (Difference of Convex) programming, allows the algorithm to exploit the properties of convex sub-functions to navigate non-convex landscapes.

2. Generalized Gradient

To handle potential discontinuities in the search direction arising from the interaction between sub-functions, the authors employ Clarke’s generalized gradient. This provides a robust mathematical framework for defining search directions where standard derivatives may not be well-defined or continuous.

3. Evolution Equation

The search process is modeled as a dynamic system governed by an evolution equation: $$\frac{dX}{dt} = -\lambda g^* \text{sgn}(f_M(X))$$ Using Lyapunov stability theory from control engineering, the authors demonstrate that this system naturally converges toward the global minimum. The sign function and the projection of the generalized gradient create an "escape mechanism" that allows the search trajectory to traverse local minima.

Numerical Results

The effectiveness of the proposed algorithm was validated using two benchmark optimization problems.

Example 1: One-Dimensional Non-Convex Function

The first test case involves a complex polynomial-exponential function: $$J(x) = 8x^4 + 2x^6 - 16x^2 - 3e^{1.2x}$$ Starting from an initial value of $x = -1.25$, the algorithm successfully navigated the landscape to find the global minimum at $x \approx 1$, with a function value of approximately $-15.999$.

Figure 1: Search trajectory for the 1D non-convex function starting from an initial value of x = -1.25.

Example 2: Two-Dimensional Hump Camel-Bak Function

The second test case utilizes the Hump Camel-Bak function, a standard benchmark featuring six local minima, including two global minima. The algorithm successfully identified the global optima at $X^{(1)} = (-0.008984, 0.712656)^T$ and $X^{(2)} = (0.008984, -0.712656)^T$, reaching the optimal value of $0.9684$.

Figure 2: Search trajectory on the contour plot of the 2D Hump Camel-Bak function.

Discussion and Conclusion

The core innovation of this approach lies in the "escape mechanism" provided by the D.C. decomposition and the dynamic evolution equation. By balancing the competing forces of the two convex sub-functions, the algorithm can ignore minor local dips that would trap standard gradient descent methods.

However, several limitations remain. The requirement for an explicit D.C. decomposition limits the method's applicability to "black box" functions where such a structure is unknown. Additionally, further research is needed to evaluate the computational efficiency and scalability of this approach in high-dimensional spaces, such as those encountered in deep learning optimization. Future work will focus on automating the decomposition process and benchmarking against other state-of-the-art global optimizers.

Summary updated

Abstract

In this paper, a novel approach to find the global optimal solution of the special non-convex problems is proposed. The non-convex objective function is first decomposed into two convex sub-functions. Then a generalized gradient is introduced to determine a search direction and the evolution equation is built to obtain a global minimum point. By the approach, we can prevent the search process from some local minima and search a global minimum point. Two numerical examples are given to prove the approach to be effective.
BibTeX
@inproceedings{lu2015global,
  author = {Zhaosong Lu and Yingying Lan},
  title = {{A global Optimization Approach to Non-Convex Problems}},
  booktitle = {Advances},
  year = {2015},
  doi = {10.2991/aiie-15.2015.122},
}
Figure