Continuous and Multiobjective optimization I

Contributed Session

Time Slot: Thursday Morning

Room: AUD_B

Chair: Sara Mattia

A decomposition method for lasso problems with zero-sum constraint

Time: 9:00

Andrea Cristofari (Univ di Roma Tor Vergata)

In this talk, an algorithm is presented to solve lasso problems with a constraint imposing that the sum of all variables is zero.Models of this type are commonly required for the analysis of compositional data in high-dimensional spaces.The proposed method uses a tailored active-set technique to estimate the zero variables in the optimal solution and a 2-coordinate descent scheme to update the variables.At each iteration, the algorithm chooses between two different strategies by a simple test based on the progress in the objective function.In particular, the first strategy requires to compute the whole gradient of the smooth term of the objective function and is more accurate in the active-set estimate,while the second strategy only needs to compute partial derivatives and is computationally more efficient.Global convergence of the algorithm to optimal solutions is proved.Finally, numerical results are presented on synthetic and real datasets, showing the effectiveness of the proposed method.

A conic optimization approach for solving Procrustes problems with quadratic constraints

Time: 9:20

Terézia Fulová (Faculty of Mathematics, Physics and Informatics, Comenius University in Bratislava), Trnovská Mária

A Procrustes problem (PP) is a matrix approximation problem that searches for a transformation matrix of the given dataset to fit another dataset. Since their first appearance in psychometrics, PPs have arisen in many applications such as factor analysis, multivariate analysis, computer vision, multidimensional scaling, or global positioning systems. However, there are still subclasses of PPs lacking an effective solving algorithm. In this contribution, we introduce a rank-constrained semidefinite reformulation of the PP with quadratic constraints representing a specific transformation matrix. To solve rank constrained semidefinite problems, we apply a semidefinite relaxation and a modified rank reduction algorithm based on solving semidefinite programs. Unlike other methods, our approach can be applied to a wider class of PPs, including PPs with different types of transformation matrices, weighted PPs, PPs with partially specified targets, or PPs with additional affine constraints. We demonstrate our approach’s performance while solving orthogonal Procrustes problems.

Enhancing online combinatorial optimization with linear profits using mathematical programming

Time: 9:40

Rosario Messana (Università degli Studi di Milano)

We consider the following class of online optimization problems: the decision maker chooses a vector in and then observes a linear profit whose parameters are unknown until the decision maker’s choice is made. The goal is to maximize the cumulative profit up to T iterations with respect to the best cumulative profit in hindsight.The problem and some of its variants have been addressed in several works, including Freund & Shapire 1997, Koolen et al. 2010, and Pasteris et al. 2019. It is in fact suitable to model combinatorial optimization problems such as online facility location, online 0-1 knapsack and many others. A common strategy to address it is to relax the integrality constraints on the decision variables and to interpret the profit as the expected value of the same profit with binary variables. This step is key to enable the use of analytical methods like e.g. online convex optimization algorithms, and to obtain good regret bounds, i.e. sub-linear with respect to T. In fact, previous attempts introduce frameworks that alternate an online optimization step for the update of the relaxed variables with a randomized decision step for the choice of the binary-valued decision vector based on probabilistic interpretation of the updated relaxed variables. These frameworks lack in the capability of being together efficient and open to the insertion of arbitrary constraints on the decision vector.We investigate both theoretically and experimentally the introduction of methods involving mixed integer programming resolution to address sub-problems of the problem described above. We are indeed motivated by the idea of estimating the applicability and flexibility in similar online settings. The aim of our work is to provide methods that improve on the generality of the existent approaches and that ensure good empirical efficiency.

Lipschitz global optimization using space-filling curves

Time: 10:00

Maria Chiara Nasso (University of Calabria), Sergeyev Yaroslav D., Lera Daniela

A wide variety of applications inengineering, machine learning, electronics, optimal control are interested in Lipshitz global optimization problems (see [1, 3]). In this work, we consider a multidimensional Lipshitz global optimization problem where the objective function is a black-box function which is supposed to be multiextremal and hard to evaluate.It is known that this optimization problem can be reduced to an equivalent univariate Holder one through space-filling curves, (see [2, 4]). In this talk, two different approximations of Peano-Hilbert curve are employed. The first one is broadly used in global optimization whereas the second one, the non-univalent approximation, is less known.Each method is tested on 900 randomly generated test functionstaken from the literature. Numerical experiments confirm advantages of the presented algorithms with respect to their direct competitors.

[1] Lera D. and Sergeyev Y. D. Deterministic global optimization using space-filling curves and multiple estimates of Lipschitz and Hölder constants. Communications in Nonlinear Science and Numerical Simulation., 23(1):328-342, 2015.
[2] Sergeyev Y. D. An information global optimization algorithm with local tuning. SIAM J. Optim., 5(4):858-870, 1995.
[3] Sergeyev Y. D. and Kvasov. D. E. Deterministic Global Optimization: An Introduction to the Diagonal Approach. Springer, New York, 2017.
[4] Sergeyev Y. D., Strongin R. G. and Lera D. Introduction to GlobalOptimization Exploiting Space-Filling Curves. Springer, New York,2013.
[5] Strongin R. G., Sergeyev Y. D. Global optimization with non-convex constraints. Sequential and parallel algorithms. Kluwer Academic Publishers,Dordrecht, 2000.

Optimistic vs Pessimistic Policy in Bilevel Programming

Time: 10:20

Sara Mattia (IASI-CNR)

Bilevel programming problems models situations where two stakeholders hierarchically ordered, known as leader and follower, are involved in a decision process.This leads to a mathematical model with a nested structure.Depending on the cooperation between the leader and the follower, there exists two versions of the same bilevel problem: an optimistic version, where the leader and the follower cooperate, and a pessimistic version, where there is no cooperation.These two policies correspond, in general, to different solutions of the problem.We consider mixed integer linear bilevel programming problems and describe necessary and sufficient conditions ensuring that the policy can be neglected, as the optimistic and the pessimistic problem produce the same solution.We also analyze a simple situation where, contrary to what one may expect, this is not the case.