1,721,909 research outputs found
Is time-optimal speed planning under jerk constraints a convex problem?
Full text linkWe 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. (c) 2024 The Author(s). Published by Elsevier Ltd. This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0/)
Convex envelope of bivariate cubic functions over rectangular regions
No full textIn recent years many papers have derived polyhedral and non-polyhedral convex envelopes for different classes of functions. Except for the univariate cases, all these classes of functions share the property that the generating set of their convex envelope is a subset of the border of the region over which the envelope is computed. In this paper we derive the convex envelope over a rectangular region for a class of functions which does not have this property, namely the class of bivariate cubic functions without univariate third-degree terms
Exact and approximate results for convex envelopes of special structured functions over simplices
No full textIn this paper we describe how to derive the convex envelope of a function f over the n-dimensional unit simplex Δ n at different levels of detail, depending on the properties of function f, by starting from its definition as the supremum of all the affine underestimators of f over Δ n. At the first level we are able to derive the closed-form formula of the convex envelope. At the second level we are able to derive the exact value of the convex envelope at some point x∈ Δ n, and a supporting hyperplane of the convex envelope itself at the same point, by solving a suitable convex optimization problem. Finally, at the third level we are able to derive an underestimating value which differs from the exact value of the convex envelope at some point x∈ Δ n by at most a given threshold δ. The underestimation is obtained by solving a suitable LP problem and may lead also to a convex piecewise linear underestimator of f
A new technique to derive tight convex underestimators (sometimes envelopes)
No full textThe convex envelope value for a given function f over a region X at some point x is an element of X can be derived by searching for the largest value at that point among affine underestimators of f over X. This can be computed by solving a maximin problem, whose exact computation, however, may be a hard task. In this paper we show that by relaxation of the inner minimization problem, duality, and, in particular, by an enlargement of the class of underestimators (thus, not only affine ones) an easier derivation of good convex understimating functions, which can also be proved to be convex envelopes in some cases, is possible. The proposed approach is mainly applied to the derivation of convex underestimators (in fact, in some cases, convex envelopes) in the quadratic case. However, some results are also presented for polynomial, ratio of polynomials, and some other separable functions over regions defined by similarly defined separable functions
A new approach to the multiple obnoxious facility location problem based on combinatorial and continuous tools
No full textIn this paper we address the multiple obnoxious facility location problem. In this problem p facilities need to be spread within the unit square in such a way that they are far enough from each other and that their minimal distance from n communities, with known positions within the unit square, is maximized. The problem has a combinatorial component, related to the key observation made in Drezner (Omega 87:105–116, 2019) about the role played by Voronoi points. We propose a new approach, which exploits both the combinatorial component of the problem and, through continuous local optimizations, also its continuous component. We also propose techniques to limit the impact on computation times of the number n of communities. The approach turns out to be quite competitive and is able to return 24 new best known solutions with respect to the best results reported in Kalczynski (Optim Lett 16:1153–1166, 2022)
KKT-based primal-dual exactness conditions for the Shor relaxation
Full text linkIn this work we present some exactness conditions for the Shor relaxation of diagonal (or, more generally, diagonalizable) QCQPs, which extend the conditions introduced in different recent papers about the same topic. It is shown that the Shor relaxation is equivalent to two convex quadratic relaxations. Then, sufficient conditions for the exactness of the relaxations are derived from their KKT systems. It will be shown that, in some cases, by this derivation previous conditions in the literature, which can be viewed as dual conditions, since they only involve the Lagrange multipliers appearing in the KKT systems, can be extended to primal-dual conditions, which also involve the primal variables appearing in the KKT systems
A new branch-and-bound algorithm for standard quadratic programming problems
Full text linkIn this paper we propose convex and LP bounds for standard quadratic programming (StQP) problems and employ them within a branch-and-bound approach. We first compare different bounding strategies for StQPs in terms both of the quality of the bound and of the computation times. It turns out that the polyhedral bounding strategy is the best one to be used within a branch-and-bound scheme. Indeed, it guarantees a good quality of the bound at the expense of a very limited computation time. The proposed branch-and-bound algorithm performs an implicit enumeration of all the KKT (stationary) points of the problem. We compare different branching strategies exploiting the structure of the problem. Numerical results on randomly generated problems (with varying density of the underlying convexity graph) are reported which show the effectiveness of the proposed approach, in particular in limiting the growth of the number of nodes in the branch-and-bound tree as the density of the underlying graph increases
No significant association between vitamin D and COVID-19. A retrospective study from a northern Italian hospital
No full textThe world is currently overwhelmed by a novel coronavirus disease (COVID-19). Clinically, COVID-19 shows a broad range of manifestations: from asymptomatic to severe and possibly lethal interstitial pneumonia. Several studies suggested the involvement of Vitamin-D (VitD) in reducing the risk of COVID-19 infections/severity. However, most of them are based on circumstantial evidences, like the association between latitude-related sunlight exposure and mortality rate, while studies based on patients' VitD measurements are still scarce. Therefore, we retrospectively analyzed the VitD levels (measured as 25-hydroxyvitamin-D) from a cohort of 347 patients admitted to a northern Italian Hospital as suspected COVID-19s. Of them, 128 were positive (83 males, aged 62.7 ± 14.2 and 45 females, aged 69.3 ± 15.6) and 219 were negative (107 males, aged 62.8 ± 19.5 and 112 females, aged 54.3 ± 20.1). The averaged VitD levels were similar in the two groups: 21.8 ± 16.1 ng/mL and 22.8 ± 14.0 ng/mL for the COVID-19 positive and negative group respectively (p-value: 0.39), as well as the percentage of individuals having VitD levels below 30 ng/mL: 78.9% and 73.5% for the COVID-19 positive and negative group respectively. Because a large portion of patients were below the suggested 30 ng/mL threshold, we can't exclude that VitD supplementation, restoring normal levels, might be beneficial in reducing the risk of infection
- …
