咨询内点法（Mehrotra预测校正）中奇异雅可比矩阵的处理方案

Great question—dealing with singular or semi-definite KKT systems (the core linear system you solve for the affine direction) in interior-point methods (IPMs) for QP is a super common pain point, especially when rolling your own implementation. Let’s break down your questions and practical, industry-standard solutions:

First, Why Does This Happen? #

The KKT coefficient matrix can turn semi-definite or singular when:

• Your QP is degenerate: Think redundant constraints, variables sitting exactly on active bounds, or multiple constraints activating simultaneously in a way that reduces the system’s rank.
• The iteration gets too close to the feasible region boundary, where complementarity conditions push the system toward singularity.

Is Using the Pseudo-Inverse a Valid Fix? #

Technically, yes—but it’s rarely the best choice, especially for larger problems:

• Computational cost: Moore-Penrose pseudo-inverses (pinv in MATLAB) are way slower than standard LU/Cholesky decompositions, which are the workhorses of IPMs.
• Convergence risk: The pseudo-inverse gives a least-squares solution, but this might not be a feasible descent direction. It could even push the iteration away from the central path, leading to divergence.
• Complementarity violations: The pseudo-inverse solution doesn’t guarantee the critical complementarity conditions (x·s = μ) are maintained, which breaks IPM convergence logic.

If you’re working on a tiny problem and need a quick hack, lsqminnorm (MATLAB’s optimized least-squares solver) is a better pick than pinv—it’s faster and more stable. But for any serious implementation, you’ll want a more robust approach.

General Strategies for Singular/Semi-Definite KKT Systems #

Here are the go-to fixes, ordered by practicality:

1. Dynamic Regularization #

This is the most widely used method. Add a small positive perturbation to the KKT matrix’s diagonal to make it strictly positive definite:

epsilon = 1e-10; % Start small, adjust dynamically
regularized_matrix = kkt_matrix + epsilon * eye(size(kkt_matrix));

• Dynamic adjustment: Track the matrix’s condition number (using condest for faster estimates on large matrices). If it exceeds a threshold (e.g., 1e10), bump up epsilon; if it’s well-behaved, shrink epsilon to minimize direction bias.
• Avoid over-regularization: Too large an epsilon will distort the search direction, so use the smallest value that stabilizes the decomposition.

2. Robust Linear Solvers #

Swap standard LU decomposition for solvers that handle ill-conditioned matrices better:

• QR Decomposition: QR is inherently more stable for singular/semi-definite systems than LU. MATLAB’s qr works here, though it’s slightly slower.
• Modified Cholesky Decomposition: For symmetric semi-definite matrices (common in QP KKT systems), modified Cholesky only perturbs diagonal entries that would cause decomposition failure, minimizing bias while ensuring positive definiteness.

3. Preprocess to Remove Redundant Constraints #

Singularity often stems from redundant constraints. Before starting IPM iterations:

• Use a rank-revealing QR decomposition to find linearly dependent constraints.
• Remove these redundant constraints to reduce the KKT system’s size and eliminate rank deficiency.
• Note: Dynamic redundancy removal during iteration is possible but adds complexity—stick to preprocessing for most cases.

4. Projected Search Directions #

If you detect a singular system, solve the homogeneous system KKT * dx = 0 to find the matrix’s null space. Then project your candidate search direction onto the intersection of this null space and feasible descent directions. This ensures the direction is both feasible and doesn’t increase the objective function.

• Implementation note: This requires computing the null space (e.g., with null in MATLAB) and projection calculations, which adds complexity but works well for degenerate problems.

Mehrotra-Specific Adjustments #

Since you’re using the Mehrotra predictor-corrector variant, here are tweaks tailored to this algorithm:

• Adjust the Central Parameter (μ): When the KKT system is singular, temporarily increase μ to pull the iteration back toward the central path. Points closer to the central path usually have better-conditioned KKT matrices.
• Shrink Predictor Step Length: If the affine direction is unreliable, use a smaller step size (e.g., 0.5 instead of the usual 0.99) for the predictor step to avoid moving too far into a problematic region.
• Weighted Residuals: In the predictor-corrector system, prioritize feasibility residuals over complementarity residuals when the system is ill-conditioned.

Practical MATLAB Tips #

• Wrap your linear solver in a try-catch block: If LU decomposition fails (throws a warning/error), automatically switch to a regularized version or QR decomposition.
• Test your solver on degenerate QP test cases (e.g., problems with redundant equality constraints) to validate your handling logic.

内容的提问来源于stack exchange，提问作者user112758