Search

We consider the convergence rate of the alternating projection method for the nontransversal intersection of a semialgebraic set and a linear subspace. For such an intersection, the convergence rate is known as sublinear in the worst case. We study the exact convergence rate for a given semialgebraic set and an initial point, and investigate when the convergence rate is linear or sublinear. As a consequence, we show that the exact rates are expressed by multiplicities of the defining polynomials of the semialgebraic set, or related power series in the case that the linear subspace is a line, and we also decide the convergence rate for given data by using elimination theory. Our methods are also applied to give upper bounds for the case that the linear subspace has the dimension more than one. The upper bounds are shown to be tight by obtaining exact convergence rates for a specific semialgebraic set, which depend on the initial points., 22 pages, 1 figure

International audience; This paper is concerned with the analysis of the L2 induced norm of continuous-time LTI systems where the input signals are restricted to be nonnegative. This induced norm is referred to as the L2+ induced norm in this paper. It has been shown very recently that the L2+ induced norm is particularly useful for the stability analysis of nonlinear feedback systems constructed from linear systems and static nonlinearities where the nonlinear elements only provide nonnegative signals. For the upper bound computation of the L2+ induced norm, an approach with copositive programming has also been proposed. It is nonetheless true that this approach becomes effective only for multi-input systems, and for single-input systems this approach does not bring any improvement over the trivial upper bound, the standard L2 norm. To overcome this difficulty, we newly introduce positive filters to increase the number of positive signals. This enables us to enlarge the size of the copositive multipliers so that we can obtain better (smaller) upper bounds with copositive programming.

This paper deals with the minimization of $$H_\infty $$ H ∞ output feedback control. This minimization can be formulated as a linear matrix inequality (LMI) problem via a result of Iwasaki and Skelton 1994. The strict feasibility of the dual problem of such an LMI problem is a valuable property to guarantee the existence of an optimal solution of the LMI problem. If this property fails, then the LMI problem may not have any optimal solutions. Even if one can compute parameters of controllers from a computed solution of the LMI problem, then the computed $$H_\infty $$ H ∞ norm may be very sensitive to a small change of parameters in the controller. In other words, the non-strict feasibility of the dual tells us that the considered design problem may be poorly formulated. We reveal that the strict feasibility of the dual is closely related to invariant zeros of the given generalized plant. The facial reduction is useful in analyzing the relationship. The facial reduction is an iterative algorithm to convert a non-strictly feasible problem into a strictly feasible one. We also show that facial reduction spends only one iteration for so-called regular $$H_\infty $$ H ∞ output feedback control. In particular, we can obtain a strictly feasible problem by using null vectors associated with some invariant zeros. This reduction is more straightforward than the direct application of facial reduction.

One often encounters numerical difficulties in solving linear matrix inequality (LMI) problems obtained from $H_\infty$ control problems. We discuss the reason from the viewpoint of optimization, and provide necessary and sufficient conditions for LMI problem and its dual not to be strongly feasible. Moreover, we interpret them in terms of control system. In this analysis, facial reduction, which was proposed by Borwein and Wolkowicz, plays an important role. We show that a necessary and sufficient condition closely related to the existence of invariant zeros in the closed left-half plane in the system, and present a way to remove the numerical difficulty with the null vectors associated with invariant zeros in the closed left-half plane. Numerical results show that the numerical stability is improved by applying it.

We consider the linear matrix inequality (LMI) problem of $H_\infty$ output feedback control problem for a generalized plant whose control input, measured output, disturbance input, and controlled output are scalar. We provide an explicit form of the optimal value. This form is the unification of some results in the literature of $H_\infty$ performance limitation analysis. To obtain the form of the optimal value, we focus on the non-uniqueness of perpendicular matrices, which appear in the LMI problem. We use the null vectors of invariant zeros associated with the dynamical system for the expression of the perpendicular matrices. This expression enables us to reduce and simplify the LMI problem. Our approach uses some well-known fundamental tools, e.g., the Schur complement, Lyapunov equation, Sylvester equation, and matrix completion. We use these techniques for the simplification of the LMI problem. Also, we investigate the structure of dual feasible solutions and reduce the size of the dual. This reduction is called a facial reduction in the literature of convex optimization., Submitted to a journal

Strong feasibility (a.k.a. strict feasibility) of the dual problem of a given linear matrix inequality (LMI) is an important property to guarantee the existence of an optimal solution of the LMI problem. In particular, the LMI problem may not have any optimal solutions if the dual is not strongly feasible. This implies that the computed solutions by SDP solvers may be meaningless and useless for designing the controllers of H ∞ output feedback control problems. The facial reduction is a tool to analyze and reduce such non-strongly feasible problems. We introduce the strong feasibility of the dual and facial reduction and provide the necessary and sufficient condition on the strong feasibility. Furthermore, we reveal that the condition is closely related to invariant zeros in the plant.

In the field of automotive engines calibration, generating a boundary model of an admissible operation domain, for instance, a convex hull, is a step often required when solving constrained optimization problems addressed by Model-Based Calibration (MBC) software suites, such as Model-Based Calibration Toolbox from MathWorks. However, depending on the amount of data modeled, generating a convex hull might become a computationally intensive process. This is due to the fact that the half-space representation of the convex hull is used. We discuss here an alternative representation of the convex hull, the vertex representation, which proves capable to reduce the computational cost for specific conditions. Numerical comparisons in this article are executed in MATLAB using MBC Toolbox commands and show that for a representative optimization problem, the vertex representation outperforms the half-space representation.

One often encounters numerical difficulties in solving linear matrix inequality (LMI) problems obtained from H ∞ control problems. We discuss the reason from the viewpoint of optimization. It is empirically known that a numerical difficulty occurs if the resulting LMI problem or its dual is not strongly feasible. In this paper, we provide necessary and sufficient conditions for LMI problem and its dual not to be strongly feasible, and interpret them in terms of control system. For this, facial reduction, which was proposed by Borwein and Wolkowicz, plays an important role. We show that a necessary and sufficient condition closely related to the existence of invariant zeros in the closed left-half plane in the system, and present a way to remove the numerical difficulty with the null vectors associated with invariant zeros in the closed left-half plane. Numerical results show that the numerical stability is improved by applying it.

Lattice-based cryptography is based on the hardness of the lattice problems, e.g., the shortest vector problem and the closed vector problem. In fact, these mathematical optimization problems are known to be NP-hard. Our interest is to know how large-scale shortest vector problems can be solved. For this, we provide a mixed integer quadratic programming formulation for the shortest vector problem and propose a technique to restrict the search space of the shortest vector problem. This approach is a potential technique to improve the performance of the state-of-the-art software for mixed integer programming problems. In fact, we observe that this technique improves the numerical performance for TU Darmstadt’s benchmark instances with the dimension up to 49.

The semi definite programming (SDP) problem is one of the central problems in mathematical optimization. The primal-dual interior-point method (PDIPM) is one of the most powerful algorithms for solving SDP problems, and many research groups have employed it for developing software packages. However, two well-known major bottlenecks, i.e., the generation of the Schur complement matrix (SCM) and its Cholesky factorization, exist in the algorithmic framework of the PDIPM. We have developed a new version of the semi definite programming algorithm parallel version (SDPARA), which is a parallel implementation on multiple CPUs and GPUs for solving extremely large-scale SDP problems with over a million constraints. SDPARA can automatically extract the unique characteristics from an SDP problem and identify the bottleneck. When the generation of the SCM becomes a bottleneck, SDPARA can attain high scalability using a large quantity of CPU cores and some processor affinity and memory interleaving techniques. SDPARA can also perform parallel Cholesky factorization using thousands of GPUs and techniques for overlapping computation and communication if an SDP problem has over two million constraints and Cholesky factorization constitutes a bottleneck. We demonstrate that SDPARA is a high-performance general solver for SDPs in various application fields through numerical experiments conducted on the TSUBAME 2.5 supercomputer, and we solved the largest SDP problem (which has over 2.33 million constraints), thereby creating a new world record. Our implementation also achieved 1.713 PFlops in double precision for large-scale Cholesky factorization using 2,720 CPUs and 4,080 GPUs.

When using the convex hull approach in the boundary modeling process, Model-Based Calibration (MBC) software suites -- such as Model-Based Calibration Toolbox from MathWorks -- can be computationally intensive depending on the amount of data modeled. The reason for this is that the half-space representation of the convex hull is used. We discuss here another representation of the convex hull, the vertex representation, which proves capable to reduce the computational cost. Numerical comparisons in this article are executed in MATLAB by using MBC Toolbox commands, and show that for certain conditions, the vertex representation outperforms the half-space representation., We change only the license statement from the first version, MI Preprint Series MI 2016-6

In SDP-based H ∞ control, we often encounter numerical difficulties when solving SDPs by various pieces of software. It is empirically known that such numerical difficulty occurs if an SDP at hand or its dual has no interior point feasible solutions, and this is indeed the case of some SDPs in H ∞ control. To conceive a way for getting around such numerical difficulties in a concrete problem setting, in this paper, we focus on the dual SDP for the H ∞ control problem of the transfer function (1 + PK)-1P and simplify it. More precisely, by actively using the information of unstable zeros (non-minimum phase zeros) of the plant P, we reduce the original dual SDP into a set of simplified SDPs each of which and its dual have interior point feasible solutions. In this way, we show by numerical experiments that reliable numerical computation can be done by SDP software. On the other hand, once we have obtained simplified SDPs, it becomes possible to further reduce them into the computation of maximum singular values of matrices determined by unstable zeros. In this way, if the number of unstable zeros is moderate, we can obtain analytical expressions of the best achievable H ∞ performance or its lower bounds in terms of the unstable zeros. Keywords: H ∞ control, SDP, numerical reliability, best achievable performance.

In this paper, we study a dual-LMI-based approach to H ∞ performance limitation analysis of SISO systems. The scope includes the analysis of the sensitivity function S = (1 + PK)−1 and the complementary sensitivity function T = (1 + PK)−1 PK where P and K stand for the plant and the controller, respectively. The H ∞ performance limitations for these transfer functions are well investigated, and exact closed-form performance bounds are already known for the cases where the plant has the sole unstable zero (i.e., non-minimum phase zero) of degree one or the sole unstable pole of degree one. The goal of this paper is to show that such exact bounds can be reproduced by a dual LMI approach. To this end, we study a Lagrange dual of the standard SDP that is usually used to design H ∞ optimal controllers by numerical computation. By characterizing the structure of dual feasible solutions in terms of unstable zeros and unstable poles of the plant, we clarify that we can construct an optimal solution for the dual SDP analytically. It follows that we obtain exact H ∞ performance bounds that are consistent with the known results.

In the conic optimization problems, it is well-known that a positive duality gap may occur, and that solving such a problem is numerically difficult or unstable. For such a case, we propose a facial reduction algorithm to find a primal–dual pair of conic optimization problems having the zero duality gap and the optimal value equal to one of the original primal or dual problems. The conic expansion approach is also known as a method to find such a primal–dual pair, and in this paper we clarify the relationship between our facial reduction algorithm and the conic expansion approach. Our analysis shows that, although they can be regarded as dual to each other, our facial reduction algorithm has ability to produce a finer sequence of faces of the cone including the feasible region. A simple proof of the convergence of our facial reduction algorithm for the conic optimization is presented. We also observe that our facial reduction algorithm has a practical impact by showing numerical experiments for graph partition problems; our facial reduction algorithm in fact enhances the numerical stability in those problems.

We observe that in a simple one-dimensional polynomial optimization problem (POP), the `optimal' values of semidefinite programming (SDP) relaxation problems reported by the standard SDP solvers converge to the optimal value of the POP, while the true optimal values of SDP relaxation problems are strictly and significantly less than that value. Some pieces of circumstantial evidences for the strange behaviors of the SDP solvers are given. This result gives a warning to users of the SDP relaxation method for POPs to be careful in believing the results of the SDP solvers. We also demonstrate how SDPA-GMP, a multiple precision SDP solver developed by one of the authors, can deal with this situation correctly.

Examples of weakly infeasible semidefinite programs are useful to test whether semidefinite solvers can detect infeasibility. However, finding non trivial such examples is notoriously dificult. This note shows how to use Lasserre's semidefinite programming relaxations for polynomial optimization in order to generate examples of weakly infeasible semidefinite programs. Such examples could be used to test whether a semidefinite solver can detect weak infeasibility. In addition, in this note, we generate weakly infeasible semidefinite programs from an instance of polynomial optimization with nonempty feasible region and solve them by semidefinite solvers. Although all semidefinite programming relaxation problems are infeasible, we observe that semidefinite solvers do not detect the infeasibility and that values returned by semidefinite solvers are equal to the optimal value of the instance due to numerical round-off errors.