An official website of the United States government
We study robust convex quadratic programs where the uncertain problem parameters can contain both continuous and integer components. Under the natural boundedness assumption on the uncertainty set, we show that the generic problems are amenable to exact copositive programming reformulations of polynomial size. These convex optimization problems are NP-hard but admit a conservative semidefinite programming (SDP) approximation that can be solved efficiently. We prove that the popular approximate S-lemma method—which is valid only in the case of continuous uncertainty—is weaker than our approximation. We also show that all results can be extended to the two-stage robust quadratic optimization setting if the problem has complete recourse. We assess the effectiveness of our proposed SDP reformulations and demonstrate their superiority over the state-of-the-art solution schemes on instances of least squares, project management, and multi-item newsvendor problems.
more »
« less
A Convex Optimization Approach to Compute Trapping Regions for Lossless Quadratic Systems
ABSTRACT Quadratic systems with lossless quadratic terms arise in many applications, including models of atmosphere and incompressible fluid flows. Such systems have a trapping region if all trajectories eventually converge to and stay within a bounded set. Conditions for the existence and characterization of trapping regions have been established in prior work for boundedness analysis. However, prior solutions have used non‐convex optimization methods, resulting in conservative estimates. In this paper, we build on this prior work and provide a convex semidefinite programming condition for the existence of a trapping region. The condition allows for precise verification or falsification of the existence of a trapping region. If a trapping region exists, then we provide a second semidefinite program to compute the least conservative radius of the spherical trapping region. Two low‐dimensional systems are provided as examples to illustrate the results. A third high‐dimensional example is also included to demonstrate that the computation required for the analysis can be scaled to systems of up to states. The proposed method provides a precise and computationally efficient numerical approach for computing trapping regions. We anticipate this work will benefit future studies on modeling and control of lossless quadratic dynamical systems.
more »
« less
- Award ID(s):
- 1943988
- PAR ID:
- 10584569
- Publisher / Repository:
- Wiley
- Date Published:
- Journal Name:
- International Journal of Robust and Nonlinear Control
- Volume:
- 35
- Issue:
- 6
- ISSN:
- 1049-8923
- Page Range / eLocation ID:
- 2425 to 2436
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
While recent work suggests that quantum computers can speed up the solution of semidefinite programs, little is known about the quantum complexity of more general convex optimization. We present a quantum algorithm that can optimize a convex function over an n -dimensional convex body using O ~ ( n ) queries to oracles that evaluate the objective function and determine membership in the convex body. This represents a quadratic improvement over the best-known classical algorithm. We also study limitations on the power of quantum computers for general convex optimization, showing that it requires Ω ~ ( n ) evaluation queries and Ω ( n ) membership queries.more » « less
-
Existing model reduction techniques for high-dimensional models of conservative partial differential equations (PDEs) encounter computational bottlenecks when dealing with systems featuring non-polynomial nonlinearities. This work presents a nonlinear model reduction method that employs lifting variable transformations to derive structure-preserving quadratic reduced-order models for conservative PDEs with general nonlinearities. We present an energy-quadratization strategy that defines the auxiliary variable in terms of the nonlinear term in the energy expression to derive an equivalent quadratic lifted system with quadratic system energy. The proposed strategy combined with proper orthogonal decomposition model reduction yields quadratic reduced-order models that conserve the quadratized lifted energy exactly in high dimensions. We demonstrate the proposed model reduction approach on four nonlinear conservative PDEs: the one-dimensional wave equation with exponential nonlinearity, the two-dimensional sine-Gordon equation, the two-dimensional Klein–Gordon equation with parametric dependence, and the two-dimensional Klein–Gordon–Zakharov equations. The numerical results show that the proposed lifting approach is competitive with the state-of-the-art structure-preserving hyper-reduction method in terms of both accuracy and computational efficiency in the online stage while providing significant computational gains in the offline stage.more » « less
-
We present a dual form of Lyapunov-Krasovskii functional which allows the problem of controller synthesis for multi-delay systems to be formulated and solved in a convex manner. First, we give a generalized version of the dual stability condition formulated in terms of Lyapunov operators which are positive, self-adjoint and preserve the structure of the state-space. Second, we provide a class of such operators and express the stability conditions as positivity and negativity of quadratic Lyapunov-Krasovskii functional forms. Next, we adapt the SOS methodology to express positivity and negativity of these forms as LMIs, describing a new set of polynomial manipulation tools designed for this purpose. We apply the resulting LMIs to a battery of numerical examples and demonstrate that the stability conditions are not significantly conservative. Finally, we formulate a test for controller synthesis for systems with multiple delays, apply the test to a numerical example, and simulate the resulting closed-loop system.more » « less
-
We tackle the problem of recovering a complex signal $$\vx\in\mathbb{C}^n$$ from quadratic measurements of the form $$y_i=\vx^*\vA_i\vx$$, where $$\{\vA_i\}_{i=1}^m$$ is a set of complex iid standard Gaussian matrices. This non-convex problem is related to the well understood phase retrieval problem where $$\vA_i$$ is a rank-1 positive semidefinite matrix. Here we study a general full-rank case which models a number of key applications such as molecular geometry recovery from distance distributions and compound measurements in phaseless diffractive imaging. Most prior work either addresses the rank-1 case or focuses on real measurements. The several papers that address the full-rank complex case adopt the semidefinite relaxation approach and are thus computationally demanding. In this paper we propose a method based on the standard framework comprising a spectral initialization followed by iterative gradient descent updates. We prove that when the number of measurements exceeds the signal's length by some constant factor, a globally optimal solution can be recovered from complex quadratic measurements with high probability. Numerical experiments on simulated data corroborate our theoretical analysis.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript
- Journal Article:
- https://doi.org/10.1002/rnc.7807
