Source-linked AI summary
Combining Convex-Concave Decompositions and Linearization Approaches for solving BMIs, with application to Static Output Feedback
Quoc Tran Dinh, Suat Gumussoy, Wim Michiels, Moritz Diehl
TL;DR
BMI-constrained optimization is difficult because the constraints are nonconvex and potentially nonsmooth. The paper decomposes bilinear mappings into differences of psd-convex mappings, linearizes the concave parts, and applies the resulting method to static output feedback design. The algorithm is benchmarked on COMPleib data, while its Phase 1 is heuristic and depends on finding an appropriate decomposition and feasible starting point.
Problem
BMI-constrained control optimization is difficult because BMI constraints are nonconvex and possibly nonsmooth, with BMI optimization shown to be NP-hard.
Method
The method decomposes BMI constraints into differences of psd-convex mappings, linearizes the concave parts, and solves convex SDP subproblems that can become LMIs in control applications.
Results
The method applies to static feedback controller design and is benchmarked on control problems using data from the COMPleib library.
Takeaways & Limitations
The algorithm provides a practical local optimization method for several BMI-constrained static feedback controller synthesis problems using available SDP software.
Takeaways & Limitations
Phase 1 is heuristic, and the method depends crucially on selecting an appropriate psd-convex-concave decomposition and finding a strictly feasible starting point.
Abstract
from arXiv · showhide
A novel optimization method is proposed to minimize a convex function subject to bilinear matrix inequality (BMI) constraints. The key idea is to decompose the bilinear mapping as a difference between two positive semidefinite convex mappings. At each iteration of the algorithm the concave part is linearized, leading to a convex subproblem.Applications to various output feedback controller synthesis problems are presented. In these applications the subproblem in each iteration step can be turned into a convex optimization problem with linear matrix inequality (LMI) constraints. The performance of the algorithm has been benchmarked on the data from COMPleib library.
1 Introduction
The paper addresses BMI-constrained optimization, which is nonconvex and potentially nonsmooth, by proposing a local method based on convex-concave matrix decompositions. It applies the method to static feedback controller design and benchmarks the resulting control solutions on COMPleib data.
- BMI-constrained optimization is difficult because BMI constraints are nonconvex and possibly nonsmooth, and such problems have been shown to be NP-hard.
- The resulting algorithm solves a sequence of convex semidefinite programming problems and targets local optima.
- The approach is designed for static state and output feedback controller synthesis, including stabilization, H2, and H∞ optimization.
- The method reformulates BMI constraints as differences of two positive semidefinite convex mappings and linearizes the concave parts.
- The numerical results are benchmarked using data from the COMPleib library.
2 Preliminaries
This section introduces positive semidefinite convexity for matrix-valued mappings and the convex-concave decompositions used to represent them. It also states differentiability assumptions and notes that multiple decompositions may exist.
- A matrix-valued mapping is psd-convex when it satisfies the matrix analogue of convexity under the semidefinite order.
- PsD-convexity can be characterized through scalar quadratic forms and a first-order matrix inequality.
- The paper assumes twice differentiability for simplicity, while noting that subdifferentiability can suffice for the objective and concave mapping parts.
- A psd-convex-concave mapping is represented as the difference G(x)−H(x) of two psd-convex mappings.
- A given psd-convex-concave mapping can have multiple valid psd-convex-concave decompositions.
3 Optimization of convex-concave matrix inequality constraints
The paper formulates BMI-related matrix constraints through psd-convex-concave decompositions and develops their optimization framework. Bilinear forms admit explicit decompositions, while Schur-complement transformations connect suitable constraints to LMIs under a strict-feasibility assumption.
- Matrix variables can be vectorized without losing psd-convexity because vectorization and its inverse are linear operators.
- The bilinear form X^T Y + Y^T X can be represented as a difference of two psd-convex mappings.
- At least three explicit decompositions are available, with different curvature assigned to the second term.
- Schur-complement transformations convert suitable psd-convex matrix inequalities into LMI constraints.
- The optimization model minimizes a convex objective over constraints Gi(x)−Hi(x) ⪯ 0, where Gi and Hi are psd-convex mappings.
- The method assumes a nonempty relative interior of the feasible set, requiring a strictly feasible starting point that can be difficult to find.
4 The algorithm and its convergence
The method repeatedly linearizes the concave part of psd-convex-concave BMI constraints, producing convex semidefinite subproblems that can be solved directly or as LMIs. Starting from a strictly feasible relative-interior point, the iterates remain feasible and, under stated assumptions, converge to KKT points.
- The algorithm: Each iteration linearizes the nonconvex concave part of the matrix constraints and solves a convex semidefinite subproblem.The subproblem can be solved by interior-point methods or transformed into a quadratic problem with LMI constraints.
- The algorithm: Algorithm 1 initializes ρ0, Q0, and x0 ∈ ri(D), then repeatedly solves the convex program and updates ρk and Qk until successive iterates differ by at most ε.The stopping test is ∥xk+1 − xk∥ ≤ ε.
- Feasibility: If x0 ∈ ri(D), every generated iterate remains feasible, so no line-search procedure is needed for global convergence.This follows because the linearized concave part is an upper approximation, making each solved subproblem an inner approximation of the original feasible set.
- Assumptions and implementation: The implementation requires a strictly feasible starting point, whose construction is difficult in principle because D is nonconvex, although problem structure can help.The twice-differentiability assumption can be weakened to subdifferentiability, while Schur psd-convex mappings allow direct LMI transformation.
- Convergence: A solution of the linearized subproblem is a stationary point of the original problem, and under the theorem’s assumptions every accumulation point is a KKT point.If the KKT-point set is finite, the whole sequence converges to a KKT point.
- Convergence: When ρk > 0 and Qk has full row rank, the step is a sufficiently descent direction; strict feasibility of one constraint yields strict objective decrease.The descent result is part of the convergence analysis under the stated regularization and rank conditions.
5 Applications to robust controller design
The paper applies its BMI-solving method to several static feedback controller design problems, converting decomposed constraints into iterative LMI subproblems and benchmarking them on COMPleib. The applications include sparse output feedback, spectral-abscissa optimization, H2, H∞, and mixed H2/H∞ synthesis.
- The applications cover sparse linear static output-feedback design, spectral and pseudo-spectral abscissa optimization, H2 synthesis, H∞ synthesis, and mixed H2/H∞ synthesis.
- The unified scheme decomposes BMI constraints as G(x) − H(x) ⪯ 0, finds a starting point, linearizes H at each iterate, and solves the resulting LMI-constrained subproblem with an SDP solver.The implementation reformulates the convex constraint as an LMI before applying Algorithm 1.
- 5.1 Sparse linear constant output-feedback design: For sparse output feedback, the objective combines decay-rate maximization with gain-matrix sparsity through the terms σα and a sparsity penalty.The weighting parameter σ controls the trade-off between stabilization and sparsity.
- 5.1 Sparse linear constant output-feedback design: After 15 iterations, the sparse-design example produced a gain with three nonzero elements and decay rate α = 1.17316, compared with α = 0.3543 reported in.The algorithm stopped because the objective was no longer significantly improved.
- 5.2 Spectral abscissa and pseudo-spectral abscissa optimization: The method also solved pseudo-spectral-abscissa static feedback problems and was reported applicable to mixed H2/H∞ synthesis on COMPleib benchmarks.For mixed H2/H∞ synthesis, the goal is to minimize the closed-loop H2 norm subject to an H∞ bound.
- 5.4 H∞ optimization: BMI formulation: For H∞ synthesis, Algorithm 1 and HIFOO reported almost similar optimal values for many problems, while PENBMI generally had difficulty finding feasible solutions.
6 Concluding remarks
The paper proposes and analyzes a local algorithm for BMI-constrained optimization in static feedback controller design, with applications to robust control benchmarks. Its applicability depends on finding suitable psd-convex-concave decompositions, while broader controller classes remain future work.
- The proposed algorithm solves BMI-constrained optimization problems arising in static feedback controller design.Its convergence is proved under standard assumptions.
- The method has been applied to static feedback controller synthesis for various robust control problems and benchmarked on COMPleib data.
- The algorithm is easy to implement using existing semidefinite programming software tools.
- Algorithm 1 depends crucially on obtaining an appropriate psd-convex-concave decomposition of the BMI constraints.The paper emphasizes examining each problem's specific structure to find such a decomposition.
- Extensions to general nonlinear semidefinite programming, more general reduced-order controller synthesis, and linear parameter-varying or time-varying systems are identified as future directions.
Proof of Lemma 4.2.
The proof uses the convex subproblem's optimality conditions, psd-convexity, and constraint linearization to establish the key inequality and its consequences. Under the stated assumptions, the iteration yields descent when a strict-feasibility and multiplier condition holds.
- The convex subproblem solution and its multiplier satisfy a generalized Kuhn-Tucker condition under the stated assumption.
- The proof uses the derivative identity DGi(xk+1)−DHi(xk) for the linearized constraint mappings.
- Applying psd-convexity and combining the resulting inequalities establishes inequality (4.3).
- The next iterate xk+1 satisfies the convex subproblem linearized at xk, so Gi(xk)−Hi(xk) ⪯0.
- The proof also uses the proximal quadratic terms involving ∥xk−xk+1∥2^2 and ρk∥Qk(xk+1−xk)∥2^2.
- If a constraint is strictly feasible at xk and its corresponding multiplier is negative, then f(xk+1) < f(xk).The proof derives descent by substituting the strict-feasibility and multiplier condition into the established inequality.