Solving nonlinear optimization problems with bipolar fuzzy relational equation constraints

Jian Zhou, Ying Yu, Yuhan Liu, Yuanyuan ZhangJournal of Inequalities and Applications 2016 · DOI

Abstract

This paper considers the problem of minimizing a nonlinear objective function subject to a system of bipolar fuzzy relational equations with max-$T_{L}$ composition, where $T_{L}$ is the Łukasiewicz triangular norm. It shows that the feasible domain, i.e., the solution set of a system of bipolar fuzzy relational equations, can be reformulated as a system of 0-1 mixed integer inequalities. Consequently, such a type of optimization problems can be handled within the framework of 0-1 mixed integer optimization requiring no particular solving techniques.

Introduction

Fuzzy relational equations (FREs) are a cornerstone of fuzzy modeling and approximate reasoning. While standard FREs are well-understood, "bipolar" FREs are more complex because they involve both a variable ($x$) and its logical negation ($\neg x$). This duality makes the equations much more expressive for real-world modeling but significantly harder to solve. Specifically, determining if a solution even exists for these equations is an NP-complete problem, analogous to the Boolean satisfiability problem.

Published in the Journal of Inequalities and Applications, this research addresses the challenge of nonlinear objective functions constrained by bipolar equations using the Łukasiewicz triangular norm ($T_L$). Previous research had largely focused on linear objective functions or specific types of fuzzy compositions, such as max-min.

Methodology

The core of the paper is a mathematical reformulation that bridges fuzzy logic and classical optimization. The authors focus on the system: $$A^+ \circ \mathbf{x} \lor A^- \circ \neg \mathbf{x} = \mathbf{b}$$ where $T_L(x, y) = \max(x + y - 1, 0)$.

Key steps in their approach include:

  1. Bounding the Solution Space: Deriving analytical lower bounds ($\check{x}$) and upper bounds ($\hat{x}$) for the feasible solutions.
  2. Characteristic Matrices: Introducing 0-1 matrices ($Q^+$ and $Q^-$) that identify which variables, when at their bounds, satisfy the equality constraints.
  3. Integer Reformulation (Theorem 1): Proving that a vector $\mathbf{x}$ is a solution if and only if there exist auxiliary binary vectors ($\mathbf{u}^+, \mathbf{u}^-$) that satisfy a specific set of linear inequalities.
  4. Optimization Mapping: Applying this theorem to convert a nonlinear problem with fuzzy constraints into a 0-1 Mixed Integer Nonlinear Programming (MINLP) problem.

Key Insights and Ideas

The most significant insight is that the non-linear, "fuzzy" nature of the Łukasiewicz composition can be perfectly captured by binary (0-1) logic. By introducing binary variables to represent whether a variable is "hitting" its upper or lower bound, the fuzzy constraints become linear.

The authors also note that the Archimedean property of the Łukasiewicz t-norm actually makes the solution structure simpler than the more common "max-min" composition, which often requires more combinatorial effort to solve. By reducing the problem to a standard form, researchers can benefit from decades of optimization research embedded in commercial solvers like CPLEX, bypassing the need for specialized fuzzy algorithms.

Key Results

The theoretical framework was validated through numerical examples. In one instance, the authors successfully solved a quadratic problem: $$\min f(\mathbf{x}) = 2x_1^2 - (x_2 - x_3)^2$$ subject to bipolar fuzzy constraints. They found the optimal solution $\mathbf{x}^* = (0.2, 0.3, 0.8)^T$ with an objective value of $-0.17$. This demonstration confirms that the reformulation successfully removes the nonlinear structure of the constraints, leaving only the nonlinearity of the objective function to be handled by the solver.

Limitations and Future Work

While the reformulation is elegant, 0-1 mixed integer programming is still NP-hard. For very large-scale systems, the number of binary variables introduced might lead to significant computational overhead. Furthermore, the current work is strictly limited to the Łukasiewicz t-norm. Extending this 0-1 integer framework to other continuous t-norms remains an open challenge. Future work could apply this framework to specific engineering problems, such as fuzzy control systems or supply chain optimization under fuzzy uncertainty, to test its performance against heuristic methods.

Summary updated

Abstract

This paper considers the problem of minimizing a nonlinear objective function subject to a system of bipolar fuzzy relational equations with max- $T_{L}$ composition, where $T_{L}$ is the Łukasiewicz triangular norm. It shows that the feasible domain, i.e., the solution set of a system of bipolar fuzzy relational equations, can be reformulated as a system of 0-1 mixed integer inequalities. Consequently, such a type of optimization problems can be handled within the framework of 0-1 mixed integer optimization requiring no particular solving techniques.
BibTeX
@article{zhou2016solving,
  author = {Jian Zhou and Ying Yu and Yuhan Liu and Yuanyuan Zhang},
  title = {{Solving nonlinear optimization problems with bipolar fuzzy relational equation constraints}},
  journal = {Journal of Inequalities and Applications},
  year = {2016},
  doi = {10.1186/s13660-016-1056-6},
}
Figure