Search

A technique for developing convex dual variational principles for the governing PDE of nonlinear elastostatics and elastodynamics is presented. This allows the definition of notions of a variational dual solution and a dual solution corresponding to the PDEs of nonlinear elasticity, even when the latter arise as formal Euler–Lagrange equations corresponding to non-quasiconvex elastic energy functionals whose energy minimizers do not exist. This is demonstrated rigorously in the case of elastostatics for the Saint-Venant Kirchhoff material (in all dimensions), where the existence of variational dual solutions is also proven. The existence of a variational dual solution for the incompressible neo-Hookean material in 2-d is also shown. Stressed and unstressed elastostatic and elastodynamic solutions in 1 space dimension corresponding to a non-convex, double-well energy are computed using the dual methodology. In particular, we show the stability of a dual elastodynamic equilibrium solution for which there are regions of non-vanishing length with negative elastic stiffness, i.e. non-hyperbolic regions, for which the corresponding primal problem is ill-posed and demonstrates an explosive 'Hadamard instability;' this appears to have implications for the modeling of physically observed softening behavior in macroscopic mechanical response. [ABSTRACT FROM AUTHOR]

The generalized trace ratio problem (GTRP) is to maximize the quotient t r (G V T B V) / t r (G V T A V) over the Stiefel manifold. We establish the first-order necessary and sufficient optimality conditions for the global maximizer. Based on the classical second-order necessary optimality condition, we prove that GTRP has no local non-global maximizer. Finally we reveal the hidden convexity property of GTRP by applying the convex hull representation of the orthogonal similarity set. [ABSTRACT FROM AUTHOR]

We extend the Calabi-Polyak theorem on the convexity of joint numerical range from three to any number of matrices on condition that each of them is a linear combination of three matrices having a positive definite linear combination. Our new result covers the fundamental Dines's theorem. As applications, the further extended Yuan's lemma and S-lemma are presented. The former is used to establish a more generalized assumption under which the standard second-order necessary optimality condition holds at the local minimizer in nonlinear programming, and the latter reveals hidden convexity of the homogeneous quadratic optimization problem with two bilateral quadratic constraints and its fractional extension. [ABSTRACT FROM AUTHOR]

We consider the sharp Sobolev-Poincaré constant for the embedding of $ W^{1, 2}_0(\Omega) $ into $ L^q(\Omega) $. We show that such a constant exhibits an unexpected dual variational formulation, in the range $ 1 < q < 2 $. Namely, this can be written as a convex minimization problem, under a divergence–type constraint. This is particularly useful in order to prove lower bounds. The result generalizes what happens for the torsional rigidity (corresponding to $ q = 1 $) and extends up to the case of the first eigenvalue of the Dirichlet-Laplacian (i.e., to $ q = 2 $).

We consider the speed planning problem for a vehicle moving along an assigned trajectory, under maximum speed, tangential and lateral acceleration, and jerk constraints. The problem is a nonconvex one, where nonconvexity is due to jerk constraints. We propose a convex relaxation, and we present various theoretical properties. In particular, we show that the relaxation is exact under some assumptions. Also, we rewrite the relaxation as a Second Order Cone Programming (SOCP) problem. This has a relevant practical impact, since solvers for SOCP problems are quite efficient and allow solving large instances within tenths of a second. We performed many numerical tests, and in all of them the relaxation turned out to be exact. For this reason, we conjecture that the convex relaxation is always exact, although we could not give a formal proof of this fact. [ABSTRACT FROM AUTHOR]

In this paper, an algorithm for maximizing a convex function over a convex feasible set is proposed. The algorithm, called CoMax, consists of two phases: in phase 1, a feasible starting point is obtained that is used in a gradient ascent algorithm in phase 2. The main contribution of the paper is connected to phase 1; five different methods are used to approximate the original NP-hard problem of maximizing a convex function (MCF) by a tractable convex optimization problem. All the methods use the minimizer of the convex objective function in their construction. In phase 2, the gradient ascent algorithm yields stationary points to the MCF problem. The performance of CoMax is tested on a wide variety of MCF problems, demonstrating its efficiency. History: Accepted by Antonio Frangioni, Area Editor for Design & Analysis of Algorithms–Continuous. Funding: This work was supported by the Nederlandse Organisatie voor Wetenschappelijk Onderzoek [Grant 406.17.511]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplementary Information [https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2022.1238] or is available from the IJOC GitHub software repository (https://github.com/INFORMSJoC) at [http://dx.doi.org/10.5281/zenodo.6884872]. [ABSTRACT FROM AUTHOR]

We establish a generalized alternative theorem for nonquadratic nonconvex system by unifying S-lemma and convex Farkas lemma. As an application, we reveal hidden convexity of a new family of nonconvex optimization problems that combine generalized trust region subproblem with convex optimization. [ABSTRACT FROM AUTHOR]

Given n × n n × n symmetric matrices A A and B , B , Dines in 1941 proved that the joint range set { (x T A x , x T B x) | x ∈ R n } { (x T A x , x T B x) | x ∈ R n } is always convex. Our paper is concerned with non-homogeneous extension of the Dines theorem for the range set R (f , g) = { (f (x) , g (x)) | x ∈ R n } , R (f , g) = { (f (x) , g (x)) | x ∈ R n } , f (x) = x T A x + 2 a T x + a 0 f (x) = x T A x + 2 a T x + a 0 and g (x) = x T B x + 2 b T x + b 0. g (x) = x T B x + 2 b T x + b 0. We show that R (f , g) R (f , g) is convex if, and only if, any pair of level sets, { x ∈ R n | f (x) = α } { x ∈ R n | f (x) = α } and { x ∈ R n | g (x) = β } { x ∈ R n | g (x) = β } , do not separate each other. With the novel geometric concept about separation, we provide a polynomial-time procedure to practically check whether a given R (f , g) R (f , g) is convex or not. [ABSTRACT FROM AUTHOR]

Many formulations of quadratic allocation problems, portfolio optimization problems, the maximum weight clique problem, among others, take the form as the well-known standard quadratic optimization problem, which consists in minimizing a homogeneous quadratic function on the usual simplex in the non negative orthant. We propose to analyze the same problem when the simplex is substituted by a convex and compact base of any pointed, closed, convex cone (so, the cone of positive semidefinite matrices or the cone of copositive matrices are particular instances). Three main duals (for which a semi-infinite formulation of the primal problem is required) are associated, and we establish some characterizations of strong duality with respect to each of the three duals in terms of copositivity of the Hessian of the quadratic objective function on suitable cones. Such a problem reveals a hidden convexity and the validity of S-lemma. In case of bidimensional quadratic optimization problems, copositivity of the Hessian of the objective function is characterized, and the case when every local solution is global. [ABSTRACT FROM AUTHOR]

The paper proposes a method for finding the minimum value of a functional in nonlinear nonconvex optimal control problems. The method takes advantage of the hidden convexity property of the controlled differential equations systems. Application of the multistart idea with extrema selection procedures makes it possible to create software that does not strongly depend on the problem size and supplies additional information about the object under investigation. Three test problems are considered to show specific properties of using the stochastic multistart algorithm and extension numerical technology. [ABSTRACT FROM AUTHOR]

Some topological and geometric characterizations of strong duality for a non convex optimization problem under a single equality and geometric constraints are established. In particular, a hidden convexity of the conic hull of joint-range of the pair of functions associated to the original problem, is obtained. Applications to derive (a characterization of the validity of) KKT conditions without standard constraints qualification, are also discussed. It goes beyond the exact penalization technique. Several examples showing our results provide much more information than those appearing elsewhere, are given. Finally, the standard quadratic problem involving a non necessarily polyhedral cone is analyzed in detail. [ABSTRACT FROM AUTHOR]

The performance of synthetic aperture radar (SAR) reconstruction is significantly deteriorated by the random phase noises arising from the atmospheric turbulence or frequency jitter of the transmit signal. Recently, the emerging phase retrieval (PR) technique is gradually extended to the SAR reconstruction problem via the phase-corrupted data attributing to its alluring potential for phase noise mitigation. In this paper, a novel PR-based SAR reconstruction algorithm for phase noise mitigation is proposed by jointing alternating direction method of multipliers (ADMM) and Kolmogorov spectral factorization (KoSF). Owing to the exploiting of the hidden convexity of PR-based SAR reconstruction problem and the structure advantage of the quadratic magnitude measurement, the proposed algorithm acquires better robustness for the complex-valued Gaussian white noises and the random phase noises than the existing PR-based SAR reconstruction algorithms. In the experiments, the synthetic scene data and the moving and stationary target recognition Sandia laboratories implementation of cylinders (MSTAR SLICY) target data are provided to verify the validity of the proposed algorithm. [ABSTRACT FROM AUTHOR]

We present a linear-time approximation scheme for solving the trust region subproblem (TRS). It employs Nesterov's accelerated gradient descent algorithm to solve a convex programming reformulation of (TRS). The total time complexity is less than that of the recent linear-time algorithm. The algorithm is further extended to the two-sided trust region subproblem. [ABSTRACT FROM AUTHOR]

Velocity planning on a path to be followed by a wheeled autonomous vehicle may be difficult when high curvatures and velocities are allowed. A fast, straightforward algorithm to address this problem is presented. It has linear-time computational complexity and provides an optimal minimum-time velocity profile. The algorithm is based on a curvilinear discretization that makes easy to take into account the constraint on the vehicle’s maximal normal acceleration. A generalized problem is also addressed with formal results on feasibility, complexity, and solution characterization. Three examples illustrate the proposed approach. [ABSTRACT FROM AUTHOR]

Let $$f(x)=x^TAx+2a^Tx+c$$ and $$h(x)=x^TBx+2b^Tx+d$$ be two quadratic functions having symmetric matrices $$A$$ and $$B$$ . The S-lemma with equality asks when the unsolvability of the system $$f(x)<0, h(x)=0$$ implies the existence of a real number $$\mu $$ such that $$f(x) + \mu h(x)\ge 0, ~\forall x\in \mathbb {R}^n$$ . The problem is much harder than the inequality version which asserts that, under Slater condition, $$f(x)<0, h(x)\le 0$$ is unsolvable if and only if $$f(x) + \mu h(x)\ge 0, ~\forall x\in \mathbb {R}^n$$ for some $$\mu \ge 0$$ . In this paper, we show that the S-lemma with equality does not hold only when the matrix $$A$$ has exactly one negative eigenvalue and $$h(x)$$ is a non-constant linear function ( $$B=0, b\not =0$$ ). As an application, we can globally solve $$\inf \{f(x): h(x)=0\}$$ as well as the two-sided generalized trust region subproblem $$\inf \{f(x): l\le h(x)\le u\}$$ without any condition. Moreover, the convexity of the joint numerical range $$\{(f(x), h_1(x),\ldots , h_p(x)):x\in \mathbb R^n\}$$ where $$f$$ is a (possibly non-convex) quadratic function and $$h_1(x),\ldots ,h_p(x)$$ are affine functions can be characterized using the newly developed S-lemma with equality. [ABSTRACT FROM AUTHOR]

We study the convexity properties of Dynamic Integrated Model of Climate and the Economy (DICE), which is a nonlinear optimization problem. Through some optima-preserving transformations and convex function analysis, we conclude that the DICE model is a hidden convex optimization problem when using the standard parameter values. This result implies that the solutions obtained from the model under these settings are globally optimal and are accurately reflective of the complex economic relationships modeled. We also provide sufficient conditions on the parameter space that assure this property. [ABSTRACT FROM AUTHOR]

In this paper we establish a basic theory on the connectivity of quadratic hypersurfaces. In addition, we examine how both the connectivity and the hidden convexity of quadratic functions are related to each other and prove several connectivity theorems on quadratic functions that combine and generalize Dines's and Brickman's results on the hidden convexity of quadratic mappings in real field. Many classical results in quadratic optimization are reproved by the unified approach, and more properties involving the matrix pencils are given. [ABSTRACT FROM AUTHOR]

In this paper we analyze the Fritz John and Karush--Kuhn--Tucker (KKT) conditions for a (Gâteaux) differentiable nonconvex optimization problem with inequality constraints and a geometric constraint set. The Fritz John condition is characterized in terms of an alternative theorem which covers beyond standard situations, while characterizations of KKT conditions, without assuming constraints qualifications, are related to strong duality of a suitable linear approximation of the given problem and the properties of its associated image mapping. Such characterizations are suitable for dealing with some problems in structural optimization, where most of the known constraint qualifications fail. In particular, several examples are given showing the usefulness and optimality, in a certain sense, of our results, which provide much more information than those (including the Mordukhovich normal cone or Clarke's) appearing elsewhere. The case with a single inequality constraint is discussed in detail by establishing a hidden convexity in the validity of the KKT conditions. We outline possible applications to a class of mathematical programs with equilibrium constraints as well as to vector equilibrium or quasi-variational inequality problems. [ABSTRACT FROM AUTHOR]

The problem of minimizing a quadratic objective function subject to one or two quadratic constraints is known to have a hidden convexity property, even when the quadratic forms are indefinite. The equivalent convex problem is a semidefinite one, and the equivalence is based on the celebrated S-lemma. In this paper, we show that when the quadratic forms are simultaneously diagonalizable (SD), it is possible to derive an equivalent convex problem, which is a conic quadratic (CQ) one, and as such is significantly more tractable than a semidefinite problem. The SD condition holds for free for many problems arising in applications, in particular, when deriving robust counterparts of quadratic, or conic quadratic, constraints affected by implementation error. The proof of the hidden CQ property is constructive and does not rely on the S-lemma. This fact may be significant in discovering hidden convexity in some nonquadratic problems. [ABSTRACT FROM AUTHOR]

This paper considers reliable communications over a multiple-input multiple-output (MIMO) Gaussian channel, where the channel matrix is within a bounded channel uncertainty region around a nominal channel matrix, i.e., an instance of the compound MIMO Gaussian channel. We study the optimal transmit covariance matrix design to achieve the capacity of compound MIMO Gaussian channels, where the channel uncertainty region is characterized by the spectral norm. This design problem is a challenging nonconvex optimization problem. However, in this paper, we reveal that this problem has a hidden convexity property, which can be exploited to map the problem into a convex optimization problem. We first prove that the optimal transmit design is to diagonalize the nominal channel, and then show that the duality gap between the capacity of the compound MIMO Gaussian channel and the min-max channel capacity is zero, which proves and generalizes a conjecture of Loyka and Charalambous. The key tools for showing these results are a new matrix determinant inequality and some unitarily invariant properties. [ABSTRACT FROM PUBLISHER]

In a recent paper, Georgiev and Venkov establish first radial symmetry and then uniqueness of minimizers to a certain functional. In the present paper we prove first the uniqueness of possible positive minimizers by revealing a hidden convexity property of the underlying functional. Then symmetry follows from the simple observation that uniqueness fails if there is a nonradial minimizer, because it could be rotated and give rise to a second minimizer. [ABSTRACT FROM AUTHOR]

This paper extends and completes the discussion by Xing et al. (Canonical dual solutions to the quadratic programming over a quadratic constraint, submitted) about the quadratic programming over one quadratic constraint (QP1QC). In particular, we relax the assumption to cover more general cases when the two matrices from the objective and the constraint functions can be simultaneously diagonalizable via congruence. Under such an assumption, the nonconvex (QP1QC) problem can be solved through a dual approach with no duality gap. This is unusual for general nonconvex programming but we can explain by showing that (QP1QC) is indeed equivalent to a linearly constrained convex problem, which happens to be dual of the dual of itself. Another type of hidden convexity can be also found in the boundarification technique developed in Xing et al. (Canonical dual solutions to the quadratic programming over a quadratic constraint, submitted). [ABSTRACT FROM AUTHOR]

We consider regularized covariance estimation in scaled Gaussian settings, e.g., elliptical distributions, compound-Gaussian processes and spherically invariant random vectors. Asymptotically in the number of samples, the classical maximum likelihood (ML) estimate is optimal under different criteria and can be efficiently computed even though the optimization is nonconvex. We propose a unified framework for regularizing this estimate in order to improve its finite sample performance. Our approach is based on the discovery of hidden convexity within the ML objective. We begin by restricting the attention to diagonal covariance matrices. Using a simple change of variables, we transform the problem into a convex optimization that can be efficiently solved. We then extend this idea to nondiagonal matrices using convexity on the manifold of positive definite matrices. We regularize the problem using appropriately convex penalties. These allow for shrinkage towards the identity matrix, shrinkage towards a diagonal matrix, shrinkage towards a given positive definite matrix, and regularization of the condition number. We demonstrate the advantages of these estimators using numerical simulations. [ABSTRACT FROM PUBLISHER]

Convexity is, without a doubt, one of the most desirable features in optimization. Many optimization problems that are nonconvex in their original settings may become convex after performing certain equivalent transformations. This paper studies the conditions for such hidden convexity. More specifically, some transformation-independent sufficient conditions have been derived for identifying hidden convexity. The derived sufficient conditions axe readily verifiable for quadratic optimization problems. The global minimizer of a hidden convex programming problem can be identified using a local search algorithm. [ABSTRACT FROM AUTHOR]