Generalized Reduced Jacobian Method

Basic Information

• Paper ID: 2510.14785
• Title: Generalized Reduced Jacobian Method
• Authors: M. El Maghri, Y. Elboulqe
• Classification: math.OC (Optimization and Control)
• Publication Date: October 17, 2025
• Paper Link: https://arxiv.org/abs/2510.14785

Abstract

This paper proposes the Generalized Reduced Jacobian (GRJ) method, extending the authors' previous Reduced Jacobian Method (RJM) for linear-constrained multiobjective optimization problems to handle nonlinear constraints. The method employs a global reduction strategy based on the implicit function theorem, computing a common reduced descent direction for all criteria by solving simple convex programming problems. After establishing Armijo-type line search conditions that guarantee feasibility, the authors prove global convergence to Pareto critical (KKT-stationary) points under mild assumptions. Experimental results include comparisons with other deterministic and evolutionary methods.

Research Background and Motivation

Problem Description

Multiobjective optimization problems (MOP) frequently arise in economics, medicine, design, transportation, and other fields, requiring simultaneous optimization of multiple potentially conflicting objective functions. Due to conflicts among objectives, it is rare that a single point simultaneously minimizes or maximizes all objectives; therefore, the concept of Pareto optimality must be considered.

Research Motivation

1. Limitations of Traditional Methods: Existing multiobjective optimization methods often require scalarization, introducing artificial parameters that may be sensitive to the original problem
2. Linear Constraint Restrictions: The authors' previous RJM method only applies to linearly constrained problems
3. Practical Application Needs: Real-world multiobjective optimization problems typically contain nonlinear constraints

Technical Challenges

• How to maintain the effectiveness of multiobjective descent directions under nonlinear constraints
• How to ensure global convergence of the algorithm
• How to conduct effective line searches while maintaining feasibility

Core Contributions

1. Method Extension: Successfully extends the RJM method to handle multiobjective optimization problems with nonlinear constraints
2. Theoretical Foundation: Establishes a complete theoretical framework based on the implicit function theorem
3. Algorithm Design: Proposes a complete GRJ algorithm incorporating feasible Armijo line search
4. Convergence Proof: Proves global convergence of the algorithm under mild assumptions
5. Experimental Verification: Validates the method's effectiveness through 30 test problems, including comparisons with other methods

Methodology Details

Problem Formulation

Consider the following nonlinearly constrained multiobjective optimization problem:

(MOP) Min F(x) subject to G(x) = 0, a ≤ x ≤ b

where:

• $F: \mathbb{R}^n \to \mathbb{R}^r$ is the objective function vector
• $G: \mathbb{R}^n \to \mathbb{R}^m$ is the constraint function vector
• $a, b \in \mathbb{R}^n$ are variable bounds

Core Concepts

Efficiency Definitions

The paper defines three efficiency concepts:

1. Weak Efficiency: There does not exist $x \in S$ such that $F(x) < F(x^*)$
2. Efficiency (Pareto Optimality): There does not exist $x \in S$ such that $F(x) \preceq F(x^*)$
3. Proper Efficiency: Proper efficiency in the Henig sense

Multiobjective Descent Direction

A vector $d \in \mathbb{R}^n$ is called a multiobjective descent direction if it satisfies: $J_F(x)d < 0$

GRJ Strategy

Reduction Technique

Let $A(x) = J_G(x) \in \mathbb{R}^{m \times n}$ be the constraint Jacobian matrix, assuming it has full rank. Select a basis $B$ such that the submatrix $A_B(x)$ is invertible, partitioning variables into basic variables $x_B$ and nonbasic variables $x_N$.

By the implicit function theorem, there exists a function $\psi: W \to V$ such that: $G(\psi(x_N), x_N) = 0$$\frac{\partial \psi}{\partial x_N}(x_N) = -A_B^{-1}(x')A_N(x')$

Generalized Reduced Jacobian Matrix

Define the generalized reduced Jacobian matrix: $U_N(x) := J_{F_N}(x) - J_{F_B}(x)A_B^{-1}(x)A_N(x)$

Multiobjective Reduced Descent Direction

A nonbasic vector $d_N \in \mathbb{R}^{n-m}$ is called a multiobjective reduced descent direction if it satisfies: $U_N(x)d_N < 0, \quad \forall i \in I_a(x) \cap N, d_i \geq 0, \quad \forall i \in I_b(x) \cap N, d_i \leq 0$

Direction-Finding Subproblem

To compute the reduced descent direction, the following convex optimization subproblem is introduced: $(P_x) \quad \min_{\lambda \in \Lambda} f(\lambda, x) := \frac{1}{2}\sum_{i \in N}\left(\varphi(b_i - x_i)\lfloor(U_N(x)^T\lambda)_i\rfloor_-^2 + \varphi(x_i - a_i)\lfloor(U_N(x)^T\lambda)_i\rfloor_+^2\right)$

where $\Lambda = \{(\lambda_1, \ldots, \lambda_r) \in \mathbb{R}_+^r : \sum_{j=1}^r \lambda_j = 1\}$.

Feasibility and Descent Properties

Proposition 3.1 establishes feasibility along the reduced descent direction:

1. Step size upper bound $t_N > 0$
2. Existence of feasible step length $t_f$ at non-degenerate points
3. Existence of step lengths satisfying Armijo-type inequalities

GRJ Algorithm

Algorithm Flow

Step 0: Initialization
Step 1: Non-degenerate basis selection
Step 2: Compute generalized reduced Jacobian matrix
Step 3: Solve direction-finding subproblem
Step 4: Check stopping criterion
Step 5: Feasible Armijo line search
Step 6: Update iteration point
Step 7: Degeneracy test

Convergence Analysis

Theorem 5.1 Under the following assumptions:

• Non-degeneracy of the feasible set
• Continuity of function $\varphi$ and differentiability at 0
• Basis property assumption (H) holds

The sequence generated by the algorithm satisfies:

1. Feasibility is maintained at each iteration and objective functions strictly decrease
2. Any accumulation point is a Pareto KKT-stationary point

Experimental Setup

Dataset

Thirty constrained multiobjective optimization test problems from the literature are selected, including:

• Linear and nonlinear constraint problems
• 2-3 objective functions
• 2-30 variables
• Practical engineering design problems (disc brake, welded beam design)

Evaluation Metrics

1. Purity (P): Measures the proportion of truly non-dominated solutions in the approximate Pareto front
2. *Spread (Δ)**: Measures solution diversity and dispersion
3. Generational Distance (GD): Measures convergence, i.e., distance from approximate front to true front

Comparison Methods

• ZMO: Zoutendijk-type method
• MOSQP: SQP-type method
• NSGA-II: Classical evolutionary algorithm

Implementation Details

• Armijo constant: β = 0.25
• Stopping criterion: min(P_x) < 10^{-6}
• Initial population: 200 individuals
• Newton method used for solving feasible Armijo line search

Experimental Results

Main Results

Performance Profile Analysis

Performance profile analysis reveals:

1. Purity Metric: The GRJ method performs best in purity, achieving ρ(α)=1 at relatively small thresholds α, while other methods fail to reach this value
2. Spread Metric: All four methods perform comparably in spread, with GRJ and NSGA-II showing slight advantages
3. Convergence Metric: In generational distance, the three deterministic methods show slight advantages over NSGA-II
4. Computational Time: The other three methods are slightly faster than GRJ, primarily due to the computational overhead of basis selection and line search in GRJ

Practical Engineering Problem Analysis

Disc Brake Design Problem

• Objectives: Simultaneously minimize brake mass and stopping time
• Results: GRJ and NSGA-II excel in exploring the Pareto front, while ZMO and MOSQP face serious challenges

Welded Beam Design Problem

• Objectives: Minimize manufacturing cost and beam deflection
• Results: All methods successfully approximate important regions of the Pareto front, but with different dispersion levels; GRJ demonstrates good robustness

Numerical Results Overview

Among 30 test problems, the GRJ method achieves the best purity metric on most problems, particularly demonstrating advantages on complex nonlinearly constrained problems.

Related Work

Classification of Multiobjective Optimization Methods

1. Scalarization Methods: Convert multiobjective problems into single-objective problems
2. Evolutionary Algorithms: Such as NSGA-II, MOEA/D, etc.
3. Direct Methods: Based on multiobjective descent directions

Development of Reduced Gradient Methods

• Wolfe Reduced Gradient Method: Single-objective linear-constrained optimization
• Abadie-Carpentier Generalized Reduced Gradient Method: Single-objective nonlinear-constrained optimization
• Authors' RJM Method: Multiobjective linear-constrained optimization
• Present GRJ Method: Multiobjective nonlinear-constrained optimization

Technical Advantages Compared to Existing Methods

The main advantages of GRJ over existing methods:

1. Avoids scalarization, directly handles multiobjective problems
2. Based on rigorous mathematical theory (implicit function theorem)
3. Guarantees global convergence
4. Applicable to nonlinear constraints

Conclusions and Discussion

Main Conclusions

1. Successfully extends RJM to multiobjective optimization problems with nonlinear constraints
2. Establishes a complete theoretical framework and proves global convergence
3. Experimental validation confirms method effectiveness, particularly on complex problems
4. Demonstrates good practical value in real engineering design problems

Limitations

1. Computational Complexity: Basis selection and line search processes are relatively time-consuming
2. Assumption Conditions: Requires satisfaction of constraint qualification (ACQ) and basis property assumptions
3. Degeneracy Handling: Treatment of degenerate cases may affect algorithm efficiency
4. Parameter Sensitivity: Selection of Armijo parameters and function φ may influence performance

Future Directions

1. Algorithm Acceleration: Improve basis selection strategies and line search efficiency
2. Theoretical Refinement: Relax assumption conditions such as constraint qualifications
3. Application Extension: Apply to more practical engineering problems
4. Hybrid Methods: Combine with evolutionary algorithms to enhance performance

In-Depth Evaluation

Strengths

1. Theoretical Rigor: Solid theoretical foundation based on the implicit function theorem
2. Method Innovation: First successful extension of reduction techniques to nonlinearly constrained multiobjective optimization
3. Convergence Guarantee: Provides rigorous global convergence proof
4. Experimental Sufficiency: Comprehensive validation through 30 test problems
5. Practical Value: Excellent performance on practical engineering design problems

Weaknesses

1. Computational Efficiency: Longer computational time compared to other methods
2. Assumption Limitations: Requires satisfaction of relatively strong theoretical assumptions
3. Parameter Tuning: Lacks detailed guidance for parameter selection
4. Scalability Limitations: Applicability to large-scale problems remains to be verified

Impact

1. Academic Contribution: Provides new research directions for multiobjective optimization theory
2. Methodological Significance: Demonstrates the possibility of extending classical single-objective methods to multiobjective settings
3. Practical Value: Provides effective tools for practical applications such as engineering design
4. Reproducibility: Detailed algorithm description facilitates implementation and reproduction

Applicable Scenarios

1. Engineering Design Optimization: Such as structural design, mechanical design, etc.
2. Economic Management Decisions: Multiobjective resource allocation problems
3. Scientific Computing: Applications requiring strict convergence guarantees
4. Medium-Scale Problems: Problems with moderate numbers of variables and constraints

References

The paper cites 42 related references, primarily including:

• Foundational literature on multiobjective optimization theory
• Research on reduced gradient methods
• Convergence analysis theory
• Test problems and performance evaluation methods
• Evolutionary algorithm benchmarks

Overall Assessment: This is an excellent paper with rigorous theory and innovative methodology, successfully extending the classical reduced gradient technique to multiobjective nonlinearly constrained optimization, with significant theoretical and practical value. Although there is room for improvement in computational efficiency, its solid theoretical foundation and good experimental performance make it an important contribution to the field.