TL;DR
This paper introduces a novel iterative algorithm for solving a class of challenging optimization problems involving Bilinear Matrix Inequalities (BMIs), which are common in control system design. The method reformulates BMIs into a convex-concave form, then iteratively linearizes the concave part to solve a sequence of convex subproblems, guaranteeing convergence to a local optimum.
What Problem Does This Paper Address?
Designing control systems often involves optimizing parameters subject to constraints that are not always linear or convex. Specifically, many problems in static state/output feedback controller design lead to optimization problems with Bilinear Matrix Inequalities (BMIs). Unlike Linear Matrix Inequalities (LMIs), which can be efficiently solved using convex optimization techniques, BMIs are generally NP-hard due to their non-convexity. This makes finding optimal controllers for such systems a significant challenge. Existing methods for BMIs are often computationally expensive or lack guaranteed convergence. This paper aims to provide a practical and reliable method for solving these BMI-constrained optimization problems, particularly in the context of static output feedback controller design.
Methods
The core of the proposed method is a convex-concave decomposition of the BMI constraints. The authors show that a bilinear matrix form, common in BMIs, can be expressed as the difference between two positive semidefinite convex mappings. This allows them to reformulate the BMI optimization problem into a form with convex-concave matrix inequality constraints.
The algorithm then iteratively tackles this problem:
- Linearization: At each iteration, the concave part of the reformulated constraint is linearized around the current solution. This transforms the non-convex subproblem into a convex one.
- Convex Subproblem Solution: The resulting convex subproblem, which can be formulated as a quadratic semidefinite program (SDP) or an LMI problem, is solved using standard SDP solvers.
- Iteration: The solution from the convex subproblem becomes the starting point for the next iteration.
A key advantage highlighted is that if a strictly feasible starting point is chosen, the algorithm generates a sequence of feasible solutions, eliminating the need for complex line-search procedures to ensure convergence. The paper also details specific "Phase 1" procedures to find suitable starting points for various control problems.
Datasets
The paper uses benchmark datasets from the COMPleib library for evaluating the proposed method in various control design applications, including sparse linear static output feedback, spectral abscissa optimization, H2 optimization, H∞ optimization, and mixed H2/H∞ synthesis.
Key Insights and Ideas
- BMI Reformulation: The crucial insight is the decomposition of bilinear matrix terms into a difference of convex mappings, transforming a non-convex BMI into a convex-concave form. This is the foundation for applying iterative linearization.
- Iterative Linearization for BMIs: The paper demonstrates that a sequence of convex subproblems, obtained by linearizing the concave part of the BMI, can effectively approximate the solution to the original non-convex BMI problem.
- Guaranteed Feasible Iterations: The algorithm's property of maintaining feasibility throughout iterations (given a strictly feasible start) simplifies implementation and enhances robustness.
- Practical Applicability: The method is shown to be applicable to a range of important control design problems, demonstrating its practical utility.
Key Results
The paper presents numerical results comparing their algorithm against established methods like HIFOO, PENBMI, and LMIRank on various COMPleib benchmark problems.
- Performance: The proposed algorithm achieves comparable or superior results in terms of the achieved performance metric (e.g., spectral abscissa, H2/H∞ norms) and often requires fewer iterations than some existing methods.
- Efficiency: While not explicitly stating speedups in all cases, the iterative nature and use of standard SDP solvers suggest a practical computational approach. For instance, in the sparse linear static output feedback design, their method achieved a better decay rate (a = 1.17316) than a previous method (a = 0.3543) in fewer iterations.
- Robustness: The algorithm successfully handles various control design problems, including spectral abscissa optimization, H2, H∞, and mixed H2/H∞ synthesis, demonstrating its versatility.
Limitations and Future Work
- Local Optima: The algorithm is a local optimization method, meaning it guarantees convergence to a local optimum, not necessarily the global one. The quality of the solution can depend on the initial starting point.
- Starting Point Dependency: Finding a strictly feasible starting point (x⁰ ∈ ri(D)) is crucial and can be challenging for some problems, although the paper proposes heuristic methods for this.
- Decomposition Dependence: The effectiveness of the algorithm relies on finding an appropriate convex-concave decomposition for the specific BMI constraints.
- Future Work: The authors suggest extending the method to more general nonlinear semidefinite programming, linear parameter-varying (LPV) systems, and time-varying systems. They also aim to apply it to more complex reduced-order controller synthesis problems.
Summary updated