More Like this

1. Deterministic Guarantees for Burer‐Monteiro Factorizations of Smooth Semidefinite Programs

   Boumal, Nicolas; Voroninski, Vladislav; Bandeira, Alfonso S. (January 2019, Communications on pure and applied mathematics)

   We consider semidefinite programs (SDPs) with equality constraints. The variable to be optimized is a positive semidefinite matrix X of size n. Following the Burer‐Monteiro approach, we optimize a factor Y of size n × p instead, such that X = YYT. This ensures positive semidefiniteness at no cost and can reduce the dimension of the problem if p is small, but results in a nonconvex optimization problem with a quadratic cost function and quadratic equality constraints in Y. In this paper, we show that if the set of constraints on Y regularly defines a smooth manifold, then, despite nonconvexity, first‐ and second‐order necessary optimality conditions are also sufficient, provided p is large enough. For smaller values of p, we show a similar result holds for almost all (linear) cost functions. Under those conditions, a global optimum Y maps to a global optimum X = YYT of the SDP. We deduce old and new consequences for SDP relaxations of the generalized eigenvector problem, the trust‐region subproblem, and quadratic optimization over several spheres, as well as for the Max‐Cut and Orthogonal‐Cut SDPs, which are common relaxations in stochastic block modeling and synchronization of rotations. © 2018 Wiley Periodicals, Inc. 

   more » « less
2. Feedback control of transitional flows: A framework for controller verification using quadratic constraints

   https://doi.org/10.2514/6.2021-2825  

   Mushtaq, Talha; Seiler, Peter; Hemati, Maziar (July 2021, AIAA AVIATION 2021 FORUM)

   The dynamics of incompressible fluid flows are governed by a non-normal linear dynamical system in feedback with a static energy-conserving nonlinearity. These dynamics can be altered using feedback control but verifying performance of a given control law can be challenging. The conventional approach is to perform a campaign of high-fidelity direct numerical simulations to assess performance over a wide range of parameters and disturbance scenarios. In this paper, we propose an alternative simulation-free approach for controller verification. The incompressible Navier-Stokes equations are modeled as a linear system in feedback with a static and quadratic nonlinearity. The energy conserving property of this nonlinearity can be expressed as a set of quadratic constraints on the system, which allows us to perform a nonlinear stability analysis of the fluid dynamics with minimal complexity. In addition, the Reynolds number variations only influence the linear dynamics in the Navier-Stokes equations. Therefore, the fluid flow can be modeled as a parameter-varying linear system (with Reynolds number as the parameter) in feedback with a quadratic nonlinearity. The quadratic constraint framework is used to determine the range of Reynolds numbers over which a given flow will be stable, without resorting to numerical simulations. We demonstrate the framework on a reduced-order model of plane Couette flow. We show that our proposed method allows us to determine the critical Reynolds number, largest initial disturbance, and a range of parameter variations over which a given controller will stabilize the nonlinear dynamics. 

   more » « less
3. On the convex hull of convex quadratic optimization problems with indicators

   https://doi.org/10.1007/s10107-023-01982-0  

   Wei, Linchuan; Atamtürk, Alper; Gómez, Andrés; Küçükyavuz, Simge (June 2023, Mathematical Programming)

   Abstract We consider the convex quadratic optimization problem in$$\mathbb {R}^{n}$$ $R^n$with indicator variables and arbitrary constraints on the indicators. We show that a convex hull description of the associated mixed-integer set in an extended space with a quadratic number of additional variables consists of an$$(n+1) \times (n+1)$$ $(n+1)\times (n+1)$positive semidefinite constraint (explicitly stated) and linear constraints. In particular, convexification of this class of problems reduces to describing a polyhedral set in an extended formulation. While the vertex representation of this polyhedral set is exponential and an explicit linear inequality description may not be readily available in general, we derive a compact mixed-integer linear formulation whose solutions coincide with the vertices of the polyhedral set. We also give descriptions in the original space of variables: we provide a description based on an infinite number of conic-quadratic inequalities, which are “finitely generated.” In particular, it is possible to characterize whether a given inequality is necessary to describe the convex hull. The new theory presented here unifies several previously established results, and paves the way toward utilizing polyhedral methods to analyze the convex hull of mixed-integer nonlinear sets. 

   more » « less
4. An Efficient Active-Set method With Applications to Sparse Approximations and Risk Minimization

   https://doi.org/10.1007/s10915-025-02933-x  

   Pougkakiotis, Spyridon; Gondzio, Jacek; Kalogerias, Dionysis (August 2025, Journal of Scientific Computing)

   Abstract In this paper we present an efficient active-set method for the solution of convex quadratic programming problems with general piecewise-linear terms in the objective, with applications to sparse approximations and risk-minimization. The algorithm is derived by combining a proximal method of multipliers (PMM) with a standard semismooth Newton method (SSN), and is shown to be globally convergent under minimal assumptions. Further local linear (and potentially superlinear) convergence is shown under standard additional conditions. The major computational bottleneck of the proposed approach arises from the solution of the associated SSN linear systems. These are solved using a Krylov-subspace method, accelerated by certain novel general-purpose preconditioners which are shown to be optimal with respect to the proximal penalty parameters. The preconditioners are easy to store and invert, since they exploit the structure of the nonsmooth terms appearing in the problem’s objective to significantly reduce their memory requirements. We showcase the efficiency, robustness, and scalability of the proposed solver on a variety of problems arising in risk-averse portfolio selection,$$L^1$$ $L^1$-regularized partial differential equation constrained optimization, quantile regression, and binary classification via linear support vector machines. We provide computational evidence, on real-world datasets, to demonstrate the ability of the solver to efficiently and competitively handle a diverse set of medium- and large-scale optimization instances. 

   more » « less
5. Highly accurate operator factorization methods for the integral fractional Laplacian and its generalization

   https://doi.org/10.3934/dcdss.2022016  

   Wu, Yixuan; Zhang, Yanzhi (January 2022, Discrete & Continuous Dynamical Systems - S)

   In this paper, we propose a new class of operator factorization methods to discretize the integral fractional Laplacian \begin{document}$$ (- \Delta)^\frac{{ \alpha}}{{2}} $$\end{document} for \begin{document}$$ \alpha \in (0, 2) $$\end{document}. One main advantage is that our method can easily increase numerical accuracy by using high-degree Lagrange basis functions, but remain its scheme structure and computer implementation unchanged. Moreover, it results in a symmetric (multilevel) Toeplitz differentiation matrix, enabling efficient computation via the fast Fourier transforms. If constant or linear basis functions are used, our method has an accuracy of \begin{document}$$ {\mathcal O}(h^2) $$\end{document}, while \begin{document}$$ {\mathcal O}(h^4) $$\end{document} for quadratic basis functions with \begin{document}$ h $$\end{document} a small mesh size. This accuracy can be achieved for any \begin{document}$$ \alpha \in (0, 2) $$\end{document} and can be further increased if higher-degree basis functions are chosen. Numerical experiments are provided to approximate the fractional Laplacian and solve the fractional Poisson problems. It shows that if the solution of fractional Poisson problem satisfies \begin{document}$$ u \in C^{m, l}(\bar{ \Omega}) $$\end{document} for \begin{document}$$ m \in {\mathbb N} $$\end{document} and \begin{document}$$ 0 < l < 1 $$\end{document}, our method has an accuracy of \begin{document}$$ {\mathcal O}(h^{\min\{m+l, \, 2\}}) $$\end{document} for constant and linear basis functions, while \begin{document}$$ {\mathcal O}(h^{\min\{m+l, \, 4\}}) $$\end{document}$ for quadratic basis functions. Additionally, our method can be readily applied to approximate the generalized fractional Laplacians with symmetric kernel function, and numerical study on the tempered fractional Poisson problem demonstrates its efficiency. 

   more » « less