期刊,Journal of global optimization 2025年92卷2期_国家学术搜索

Gaussian Process regression over discrete probability measures: on the non-stationarity relation between Euclidean and Wasserstein Squared Exponential Kernels

Antonio CandelieriAndrea PontiFrancesco Archetti

253-278页

查看更多>>摘要：Gaussian Process regression is a kernel method successfully adopted in many real-life applications. Recently, there is a growing interest on extending this method to non-Euclidean input spaces, like the one considered in this paper, consisting of probability measures. Although a Positive Definite kernel can be defined by using a suitable distance-the Wasserstein distance-the common procedure for learning the Gaussian Process model can fail due to numerical issues, arising earlier and more frequently than in the case of an Euclidean input space and, as demonstrated, impossible to avoid by adding artificial noise (nugget effect) as usually done. This paper uncovers the main reason of these issues, that is a non-stationarity relation between the Wasserstein-based squared exponential kernel and its Euclidean counterpart. As a relevant result, we learn a Gaussian Process model by assuming the input space as Euclidean and then use an algebraic transformation, based on the uncovered relation, to transform it into a non-stationary and Wasserstein-based Gaussian Process model over probability measures. This algebraic transformation is simpler than log-exp maps used on data belonging to Riemannian manifolds and recently extended to consider the pseudo-Riemannian structure of an input space equipped with the Wasserstein distance.

原文链接:

NETL
NSTL
Springer Nature

Gaussian Process regression over discrete probability measures: on the non-stationarity relation between Euclidean and Wasserstein Squared Exponential Kernels

Antonio CandelieriAndrea PontiFrancesco Archetti

253-278页

查看更多>>摘要：Gaussian Process regression is a kernel method successfully adopted in many real-life applications. Recently, there is a growing interest on extending this method to non-Euclidean input spaces, like the one considered in this paper, consisting of probability measures. Although a Positive Definite kernel can be defined by using a suitable distance-the Wasserstein distance-the common procedure for learning the Gaussian Process model can fail due to numerical issues, arising earlier and more frequently than in the case of an Euclidean input space and, as demonstrated, impossible to avoid by adding artificial noise (nugget effect) as usually done. This paper uncovers the main reason of these issues, that is a non-stationarity relation between the Wasserstein-based squared exponential kernel and its Euclidean counterpart. As a relevant result, we learn a Gaussian Process model by assuming the input space as Euclidean and then use an algebraic transformation, based on the uncovered relation, to transform it into a non-stationary and Wasserstein-based Gaussian Process model over probability measures. This algebraic transformation is simpler than log-exp maps used on data belonging to Riemannian manifolds and recently extended to consider the pseudo-Riemannian structure of an input space equipped with the Wasserstein distance.

原文链接:

NETL
NSTL
Springer Nature

Quasiconjugate duality and optimality conditions for quasiconvex optimization

Satoshi Suzuki

279-293页

查看更多>>摘要：In nonlinear optimization, conjugate functions and subdifferentials play an essential role. In particular, Fenchel conjugate is the most well known conjugate function in convex optimization. In quasiconvex optimization, extra parameters for quasiconjugate functions have been introduced in order to show duality theorems, for example λ-quasiconjugate and λ-semiconjugate. By these extra parameters, we can show duality results that hold for general quasiconvex objective functions. On the other hand, extra parameters usually increase the complexity of dual problems. Hence, conjugate functions without extra parameters have also been investigated, for example H-quasiconjugate, R-quasiconjugate, and so on. However, there are some open problems. In this paper, we study quasiconjugate duality and optimality conditions for quasiconvex optimization without extra parameters. We investigate three types of quasiconjugate dual problems, and show sufficient conditions for strong duality. We introduce three types of quasi-subdifferentials, and study optimality conditions and characterizations of the solution set. Additionally, we give a classification of quasiconvex optimization problems in terms of quasiconjugate duality.

原文链接:

NETL
NSTL
Springer Nature

Quasiconjugate duality and optimality conditions for quasiconvex optimization

Satoshi Suzuki

279-293页

查看更多>>摘要：In nonlinear optimization, conjugate functions and subdifferentials play an essential role. In particular, Fenchel conjugate is the most well known conjugate function in convex optimization. In quasiconvex optimization, extra parameters for quasiconjugate functions have been introduced in order to show duality theorems, for example λ-quasiconjugate and λ-semiconjugate. By these extra parameters, we can show duality results that hold for general quasiconvex objective functions. On the other hand, extra parameters usually increase the complexity of dual problems. Hence, conjugate functions without extra parameters have also been investigated, for example H-quasiconjugate, R-quasiconjugate, and so on. However, there are some open problems. In this paper, we study quasiconjugate duality and optimality conditions for quasiconvex optimization without extra parameters. We investigate three types of quasiconjugate dual problems, and show sufficient conditions for strong duality. We introduce three types of quasi-subdifferentials, and study optimality conditions and characterizations of the solution set. Additionally, we give a classification of quasiconvex optimization problems in terms of quasiconjugate duality.

原文链接:

NETL
NSTL
Springer Nature

Extending interval branch-and-bound from two to few objectives in nonlinear multiobjective optimization

Ignacio ArayaVictor ReyesJavier Montero

295-320页

查看更多>>摘要：Nonlinear multiobjective optimization presents significant challenges, particularly when addressing problems with three or more objectives. Building on our previous work using Interval Branch and Bound (B&B) techniques for biobjective optimization, we extend these methods to handle the increased complexity of multiobjective scenarios. Interval B&B methods involve dividing the original problem into smaller subproblems and solving them recursively to achieve a desired level of accuracy. These methods offer the advantage of guaranteeing global optimality and providing rigorous bounds on solution quality. We introduce a refined representation of non-dominated regions using two sets of vectors: the non dominated feasible vectors found so far and its associated set of extreme vectors. To accurately define the feasible non-dominated region within each subspace, we adapt an "envelope constraint" from biobjective solvers. Additionally, we propose a novel method for computing the distance from a subspace to the dominated region, and enhance a peeling technique for contracting the subspace based on the dominated region and the envelope constraint. Our approach is evaluated on a set of benchmark problems, and our results show a significant improvement in solution quality and convergence speed compared to a basic approach. Specifically, our enhanced strategy achieves a 42% reduction in relative CPU time, with a remarkable average time reduction of 63% in problems with three objectives. The code of our solver can be found in our git repository.

原文链接:

NETL
NSTL
Springer Nature

Extending interval branch-and-bound from two to few objectives in nonlinear multiobjective optimization

Ignacio ArayaVictor ReyesJavier Montero

295-320页

查看更多>>摘要：Nonlinear multiobjective optimization presents significant challenges, particularly when addressing problems with three or more objectives. Building on our previous work using Interval Branch and Bound (B&B) techniques for biobjective optimization, we extend these methods to handle the increased complexity of multiobjective scenarios. Interval B&B methods involve dividing the original problem into smaller subproblems and solving them recursively to achieve a desired level of accuracy. These methods offer the advantage of guaranteeing global optimality and providing rigorous bounds on solution quality. We introduce a refined representation of non-dominated regions using two sets of vectors: the non dominated feasible vectors found so far and its associated set of extreme vectors. To accurately define the feasible non-dominated region within each subspace, we adapt an "envelope constraint" from biobjective solvers. Additionally, we propose a novel method for computing the distance from a subspace to the dominated region, and enhance a peeling technique for contracting the subspace based on the dominated region and the envelope constraint. Our approach is evaluated on a set of benchmark problems, and our results show a significant improvement in solution quality and convergence speed compared to a basic approach. Specifically, our enhanced strategy achieves a 42% reduction in relative CPU time, with a remarkable average time reduction of 63% in problems with three objectives. The code of our solver can be found in our git repository.

原文链接:

NETL
NSTL
Springer Nature

Rank-one matrix completion via high-rank matrices in sum-of-squares relaxations

Godai AzumaSunyoung KimMakoto Yamashita

321-343页

查看更多>>摘要：The standard semidefinite programming (SDP) relaxation for quadratically constrained quadratic programming (QCQP) problems generally cannot obtain an exact optimal solution. However, if the optimal solution of the SDP relaxation is of rank-1, then that of QCQP can be constructed. Cosse and Demanet (Found Comput Math 21:891-940, 2021) employed this condition for a rank-one matrix completion problem using the sum-of-squares (SOS) relaxation, which is the dual of the Lasserre's relaxation. In this paper, we analyze the conditions under which the SOS relaxation provides an exact solution to the rank-one matrix completion problem. In particular, our focus is on obtaining the rank-(N - 1) dual variable matrix of dimension N, a condition satisfied when the coefficient matrix of the objective function in the SOS relaxation problem exhibits an arrowhead structure. We relax the assumption of the explicit chain structure in Cosse and Demanet (Found Comput Math 21:891-940, 2021), and derive a weaker condition for the SDP relaxation to yield an exact solution compared to the explicit chain structure. We also present a numerical algorithm to find the coefficient matrix with the arrowhead structure, and numerical experiments illustrate the validity of the proposed algorithm.

原文链接:

NETL
NSTL
Springer Nature

Rank-one matrix completion via high-rank matrices in sum-of-squares relaxations

Godai AzumaSunyoung KimMakoto Yamashita

321-343页

查看更多>>摘要：The standard semidefinite programming (SDP) relaxation for quadratically constrained quadratic programming (QCQP) problems generally cannot obtain an exact optimal solution. However, if the optimal solution of the SDP relaxation is of rank-1, then that of QCQP can be constructed. Cosse and Demanet (Found Comput Math 21:891-940, 2021) employed this condition for a rank-one matrix completion problem using the sum-of-squares (SOS) relaxation, which is the dual of the Lasserre's relaxation. In this paper, we analyze the conditions under which the SOS relaxation provides an exact solution to the rank-one matrix completion problem. In particular, our focus is on obtaining the rank-(N - 1) dual variable matrix of dimension N, a condition satisfied when the coefficient matrix of the objective function in the SOS relaxation problem exhibits an arrowhead structure. We relax the assumption of the explicit chain structure in Cosse and Demanet (Found Comput Math 21:891-940, 2021), and derive a weaker condition for the SDP relaxation to yield an exact solution compared to the explicit chain structure. We also present a numerical algorithm to find the coefficient matrix with the arrowhead structure, and numerical experiments illustrate the validity of the proposed algorithm.

原文链接:

NETL
NSTL
Springer Nature

Partial augmented Lagrangian method for non-Lipschitz mathematical programs with complementarity constraints

Gao-Xi LiXin-Min YangXian-Jun Long

345-379页

查看更多>>摘要：In recent years, mathematical programs with complementarity constraints (MPCC) and a non-Lipschitz objective function have been introduced and are now more prevalent than locally Lipschitz MPCC. This paper proposes a smoothing partial augmented Lagrangian (SPAL) method to tackle this problem. However, due to the disruption of the complementary structure's integrity by this method, proving its convergence becomes exceptionally challenging. We have achieved global convergence of the SPAL method. Specifically, we demonstrate that the accumulation point of the sequence generated by the SPAL method can be a strongly stationary point under the Mangasarian-Fromovitz qualification (MPCC-MFQ) and the boundedness of the multiplier corresponding to the orthogonal constraint. Moreover, if the aforementioned multiplier is unbounded, the accumulation point can be a Clarke stationary point under MPCC-MFQ and a suitable assumption. Numerical experiments indicate that the SPAL method surpasses existing methods in terms of the quality of accumulation points and running times.

原文链接:

NETL
NSTL
Springer Nature

Partial augmented Lagrangian method for non-Lipschitz mathematical programs with complementarity constraints

Gao-Xi LiXin-Min YangXian-Jun Long

345-379页

查看更多>>摘要：In recent years, mathematical programs with complementarity constraints (MPCC) and a non-Lipschitz objective function have been introduced and are now more prevalent than locally Lipschitz MPCC. This paper proposes a smoothing partial augmented Lagrangian (SPAL) method to tackle this problem. However, due to the disruption of the complementary structure's integrity by this method, proving its convergence becomes exceptionally challenging. We have achieved global convergence of the SPAL method. Specifically, we demonstrate that the accumulation point of the sequence generated by the SPAL method can be a strongly stationary point under the Mangasarian-Fromovitz qualification (MPCC-MFQ) and the boundedness of the multiplier corresponding to the orthogonal constraint. Moreover, if the aforementioned multiplier is unbounded, the accumulation point can be a Clarke stationary point under MPCC-MFQ and a suitable assumption. Numerical experiments indicate that the SPAL method surpasses existing methods in terms of the quality of accumulation points and running times.

原文链接:

NETL
NSTL
Springer Nature