Search

Equilibrium problems with equilibrium constraints are appropriate modeling formulations in a number of important areas, such as energy markets, transportation planning, and logistics. These models often correspond to bilevel games, in which certain dual variables, representing the equilibrium price, play a fundamental role. We consider multileader single-follower equilibrium problems having a linear program in the lower level. Because in this setting the lowerlevel response to the leaders' decisions may not be unique, the game formulation becomes ill-posed. We resolve possible ambiguities by considering a sequence of bilevel equilibrium problems, endowed with a special regularization term. We prove convergence of the approximating scheme. Our technique proves useful numerically over several instances related to energy markets. When using PATH to solve the corresponding mixed-complementarity formulations, we exhibit that, in the given context, the regularization approach computes a genuine equilibrium price almost always, while without regularization the outcome is quite the opposite. [ABSTRACT FROM AUTHOR]

The optimal expansion of a power system with reduced carbon footprint entails dealing with uncertainty about the distribution of the random variables involved in the decision process. Optimisation under ambiguity sets provides a mechanism to suitably deal with such a setting. For two-stage stochastic linear programs, we propose a new model that is between the optimistic and pessimistic paradigms in distributionally robust stochastic optimisation. When using Wasserstein balls as ambiguity sets, the resulting optimisation problem has nonsmooth convex constraints depending on the number of scenarios and a bilinear objective function. We propose a decomposition method along scenarios that converges to a solution, provided a global optimisation solver for bilinear programs with polyhedral feasible sets is available. The solution procedure is applied to a case study on expansion of energy generation that takes into account sustainability goals for 2050 in Europe, under uncertain future market conditions. [ABSTRACT FROM AUTHOR]

We present a framework for analyzing convergence and local rates of convergence of a class of descent algorithms, assuming the objective function is weakly convex. The framework is general, in the sense that it combines the possibility of explicit iterations (based on the gradient or a subgradient at the current iterate), implicit iterations (using a subgradient at the next iteration, like in the proximal schemes), as well as iterations when the associated subgradient is specially constructed and does not correspond either to the current or the next point (this is the case of descent steps in bundle methods). Under the subdifferential-based error bound on the distance to critical points, linear rates of convergence are established. Our analysis applies, among other techniques, to prox-descent for decomposable functions, the proximal-gradient method for a sum of functions, redistributed bundle methods, and a class of algorithms that can be cast in the feasible descent framework for constrained optimization. [ABSTRACT FROM AUTHOR]

We present an approach to regularize and approximate solution mappings of parametric convex optimization problems that combines interior penalty (log-barrier) solutions with Tikhonov regularization. Because the regularized mappings are single-valued and smooth under reasonable conditions, they can be used to build a computationally practical smoothing for the associated optimal value function. The value function in question, while resulting from parameterized convex problems, need not be convex. One motivating application of interest is two-stage (possibly nonconvex) stochastic programming. We show that our approach, being computationally implementable, provides locally bounded upper bounds for the subdifferential of the value function of qualified convex problems. As a by-product of our development, we also recover that in the given setting the value function is locally Lipschitz continuous. Numerical experiments are presented for two-stage convex stochastic programming problems, comparing the approach with the bundle method for nonsmooth optimization. [ABSTRACT FROM AUTHOR]

Slower than anticipated, COVID-19 vaccine production and distribution have impaired efforts to curtail the current pandemic. The standard administration schedule for most COVID-19 vaccines currently approved is two doses administered 3 to 4 wk apart. To increase the number of individuals with partial protection, some governments are considering delaying the second vaccine dose. However, the delay duration must take into account crucial factors, such as the degree of protection conferred by a single dose, the anticipated vaccine supply pipeline, and the potential emergence of more virulent COVID-19 variants. To help guide decision-making, we propose here an optimization model based on extended susceptible, exposed, infectious, and removed (SEIR) dynamics that determines the optimal delay duration between the first and second COVID-19 vaccine doses. The model assumes lenient social distancing and uses intensive care unit (ICU) admission as a key metric while selecting the optimal duration between doses vs. the standard 4-wk delay. While epistemic uncertainties apply to the interpretation of simulation outputs, we found that the delay is dependent on the vaccine mechanism of action and first-dose efficacy. For infection-blocking vaccines with firstdose efficacy ≥50%, the model predicts that the second dose can be delayed by ≥8 wk (half of the maximal delay), whereas for symptom-alleviating vaccines, the same delay is recommended only if the first-dose efficacy is ≥70%. Our model predicts that a 12-wk second-dose delay of an infection-blocking vaccine with a first-dose efficacy ≥70% could reduce ICU admissions by 400 people per million over 200 d. [ABSTRACT FROM AUTHOR]

We examine how different pricing frameworks deal with non-convex features typical of day-ahead energy prices when the power system is hydro-dominated, like in Brazil. For the system operator, requirements of minimum generation translate into feasibility issues that are fundamental to carry the generated power through the network. When utilities are remunerated at a price depending on Lagrange multipliers computed for a system with fixed commitment, the corresponding values sometimes fail to capture a signal that recovers costs. Keeping in mind recent discussions for the Brazilian power system, we analyse mechanisms that provide a compromise between the needs of the generators and those of the system operator. After characterizing when a price supports a generation plan, we explain in simple terms dual prices and related concepts, such as minimal uplifts and bi-dual problems. We present a new pricing mechanism that guarantees cost recovery to all agents, without over-compensations. Instead of using Lagrange multipliers, the price is defined as the solution to an optimization problem. The behaviour of the new rule is compared to two other proposals in the literature on illustrative examples, including a small, yet representative, hydro-thermal system. [ABSTRACT FROM AUTHOR]

In many mathematical optimization applications, dual variables are an important output of the solving process, due to their role as price signals. When dual solutions are not unique, different solvers or different computers, even different runs in the same computer if the problem is stochastic, often end up with different optimal multipliers. From the perspective of a decision maker, this variability makes the price signals less reliable and, hence, less useful. We address this issue for a particular family of linear and quadratic programs by proposing a solution procedure that, among all possible optimal multipliers, systematically yields the one with the smallest norm. The approach, based on penalization techniques of nonlinear programming, amounts to a regularization in the dual of the original problem. As the penalty parameter tends to zero, convergence of the primal sequence and, more critically, of the dual is shown under natural assumptions. The methodology is illustrated on a battery of two-stage stochastic linear programs. [ABSTRACT FROM AUTHOR]

We consider two models for stochastic equilibrium: one based on the variational equilibrium of a generalized Nash game, and the other on the mixed complementarity formulation. Each agent in the market solves a single-stage risk-averse optimization problem with both here-and-now (investment) variables and (production) wait-and-see variables. A shared constraint couples almost surely the wait-and-see decisions of all the agents. An important characteristic of our approach is that the agents hedge risk in the objective functions (on costs or profits) of their optimization problems, which has a clear economic interpretation. This feature is obviously desirable, but in the risk-averse case it leads to variational inequalities with set-valued operators-a class of problems for which no established software is currently available. To overcome this difficulty, we define a sequence of approximating differentiable variational inequalities based on smoothing the nonsmooth risk measure in the agents' problems, such as average or conditional value-at-risk. The smoothed variational inequalities can be tackled by the PATH solver, for example. The approximation scheme is shown to converge, including the case when smoothed problems are solved approximately. An interesting by-product of our proposal is that the smoothing approach allows us to show existence of an equilibrium for the original problem. To assess the proposed technique, numerical results are presented. The first set of experiments is on randomly generated equilibrium problems, for which we compare the proposed methodology with the standard smooth reformulation of average value-at-risk minimization (using additional variables to rewrite the associated max-function). The second set of experiments deals with a part of the real-life European gas network, for which Dantzig-Wolfe decomposition can be combined with the smoothing approach. [ABSTRACT FROM AUTHOR]

Joint chance constrained problems give rise to many algorithmic challenges. Even in the convex case, i.e., when an appropriate transformation of the probabilistic constraint is a convex function, its cutting-plane linearization is just an approximation, produced by an oracle providing subgradient and function values that can only be evaluated inexactly. As a result, the cutting-plane model may lie above the true constraint. For dealing with such upper inexact oracles, and still solving the problem up to certain precision, a special numerical algorithm must be put in place. We introduce a family of constrained bundle methods, based on the so-called improvement functions, that is shown to be convergent and encompasses many previous approaches as well as new algorithms. Depending on the oracle accuracy, we analyze to what extent the considered methods solve the joint chance constrained program. The approach is assessed on real-life energy problems, arising when dealing with stochastic hydroreservoir management. [ABSTRACT FROM AUTHOR]

We consider a class of decomposition methods for variational inequalities, which is related to the classical Dantzig-Wolfe decomposition of linear programs. Our approach is rather general, in that it can be used with certain types of set-valued or nonmonotone operators, as well as with various kinds of approximations in the subproblems of the functions and derivatives in the single-valued case. Also, subproblems may be solved approximately. Convergence is established under reasonable assumptions. We also report numerical experiments for computing variational equilibria of the game-theoretic models of electricity markets. Our numerical results illustrate that the decomposition approach allows to solve large-scale problem instances otherwise intractable if the widely used PATH solver is applied directly, without decomposition. [ABSTRACT FROM AUTHOR]

We consider minimization of nonsmooth functions which can be represented as the composition of a positively homogeneous convex function and a smooth mapping. This is a sufficiently rich class that includes max-functions, largest eigenvalue functions, and norm-1 regularized functions. The bundle method uses an oracle that is able to compute separately the function and subgradient information for the convex function, and the function and derivatives for the smooth mapping. With this information, it is possible to solve approximately certain proximal linearized subproblems in which the smooth mapping is replaced by its Taylor-series linearization around the current serious step. Our numerical results show the good performance of the Composite Bundle method for a large class of problems. [ABSTRACT FROM AUTHOR]

We consider risk-averse formulations of stochastic linear programs having a structure that is common in real-life applications. Specifically, the optimization problem corresponds to controlling over a certain horizon a system whose dynamics is given by a transition equation depending affinely on an interstage dependent stochastic process. We put in place a rolling-horizon time consistent policy. For each time step, a risk-averse problem with constraints that are deterministic for the current time step and uncertain for future times is solved. To each uncertain constraint corresponds both a chance and a Conditional Value-at-Risk constraint. We show that the resulting risk-averse problems are numerically tractable, being at worst conic quadratic programs. For the particular case in which uncertainty appears only on the right-hand side of the constraints, such risk-averse problems are linear programs. We show how to write dynamic programming equations for these problems and define robust recourse functions that can be approximated recursively by cutting planes. The methodology is assessed and favourably compared with Stochastic Dual Dynamic Programming on a real size water-resource planning problem. [ABSTRACT FROM AUTHOR]

Stochastic programming problems arise in many practical situations, hi general, the deterministic equivalents of these problems can be very large and may not be solvable directly by general-purpose optimization approaches. For the particular case of two-stage stochastic programs, we consider decomposition approaches akin to a regularized L-shaped method that can handle inexactness ill the subproblem solution. From a nonsmooth optimization perspective, these variants amount to applying a proximal bundle method to an oracle that gives inaccurate values for the objective function and a subgradient. Rather than forcing early termination of the subproblem optimization to define inexact oracles, we select a small subset of scenarios for which the subproblem solution is exact, and we replace the information for the remaining scenarios by a fast procedure that does not involve solving an optimization problem. The inaccurate oracle information creates inexact cuts in the master program, which are well handled by the recently introduced inexact bundle methods. The proposed approaches are validated by encouraging numerical results on several two-stage stochastic linear programs found in the literature. [ABSTRACT FROM AUTHOR]

The mid-term operation planning of hydro-thermal power systems needs a large number of synthetic sequences to represent accurately stochastic streamflows. These sequences are generated by a periodic autoregressive model. If the number of synthetic sequences is too big, the optimization planning problem may be too difficult to solve. To select a small set of sequences representing the stochastic process well enough, this work employs two variants of the Scenario Optimal Reduction technique. The first variant applies such a technique at the last stage of a tree defined a priori for the whole planning horizon while the second variant combines a stage-wise reduction, preserving the periodic autoregressive structure, with resampling. Both approaches are assessed numerically on hydrological sequences generated for real configurations of the Brazilian power system. [ABSTRACT FROM AUTHOR]

Lagrangian relaxation is a popular technique to solve difficult optimization problems. However, the applicability of this technique depends on having a relatively low number of hard constraints to dualize. When there are many hard constraints, it may be preferable to relax them dynamically, according to some rule depending on which multipliers are active. From the dual point of view, this approach yields multipliers with varying dimensions and a dual objective function that changes along iterations. We discuss how to apply a bundle methodology to solve this kind of dual problems. Our framework covers many separation procedures to generate inequalities that can be found in the literature, including (but not limited to) the most violated inequality. We analyze the resulting dynamic bundle method giving a positive answer for its primal-dual convergence properties, and, under suitable conditions, show finite termination for polyhedral problems. [ABSTRACT FROM AUTHOR]

We consider the problem of minimizing nonsmooth convex functions, defined piecewise by a finite number of functions each of which is either convex quadratic or twice continuously differentiable with positive definite Hessian on the set of interest. This is a particular case of functions with primal-dual gradient structure, a notion closely related to the so-called VU space decomposition: At a given point, nonsmoothness is locally restricted to the directions of the subspace V, while along the subspace U the behavior of the function is twice differentiable. Constructive identification of the two subspaces is important, because it opens the way to devising fast algorithms for nonsmooth optimization (by following iteratively the manifold of smoothness on which superlinear U-Newton steps can be computed). In this work we show that, for the class of functions in consideration, the information needed for this identification can be obtained from the output of a standard bundle method for computing proximal points, provided a minimizer satisfies the nondegeneracy and strong transversality conditions. [ABSTRACT FROM AUTHOR]

The proximal point mapping is the basis of many optimization techniques for convex functions. By means of variational analysis, the concept of proximal mapping was recently extended to nonconvex functions that are prox-regular and prox-bounded. In such a setting, the proximal point mapping is locally Lipschitz continuous and its set of fixed points coincide with the critical points of the original function. This suggests that the many uses of proximal points, and their corresponding proximal envelopes (Moreau envelopes), will have a natural extension from convex optimization to nonconvex optimization. For example, the inexact proximal point methods for convex optimization might be redesigned to work for nonconvex functions. In order to begin the practical implementation of proximal points in a nonconvex setting, a first crucial step would be to design efficient methods of approximating nonconvex proximal points. This would provide a solid foundation on which future design and analysis for nonconvex proximal point methods could flourish. In this paper we present a methodology based on the computation of proximal points of piecewise affine models of the nonconvex function. These models can be built with only the knowledge obtained from a black box providing, for each point, the function value and one subgradient. Convergence of the method is proved for the class of nonconvex functions that are prox-bounded and lower- $${\mathcal{C}}^2$$ and encouraging preliminary numerical testing is reported. [ABSTRACT FROM AUTHOR]

Generation expansion planning problems should take into account not only satisfaction of future demand but also environmental constraints, such as government imposed limits on pollution produced by coal-based power plants. For a vertically integrated system of power plants, we model those features as a two-stage stochastic programming problem with recourse that can be solved by decomposition methods. We present results for different demand scenarios, corresponding to low, medium, and high economic future growth, as well as different environmental cases, with stringent and non-stringent emission limits for the thermal plants composing the electric mix. Copyright © 2006 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

For a maximal monotone operator T on a Hilbert space H and a closed subspace A of H , we consider the problem of finding ( x , y ? T ( x )) satisfying x ? A and y ? A ? . An equivalent formulation of this problem makes use of the partial inverse operator of Spingarn. The resulting generalized equation can be solved by using the proximal point algorithm. We consider instead the use of hybrid proximal methods. Hybrid methods use enlargements of operators, close in spirit to the concept of e-subdifferentials. We characterize the enlargement of the partial inverse operator in terms of the enlargement of T itself. We present a new algorithm of resolution that combines Spingarn and hybrid methods, we prove for this method global convergence only assuming existence of solutions and maximal monotonicity of T . We also show that, under standard assumptions, the method has a linear rate of convergence. For the important problem of finding a zero of a sum of maximal monotone operators T 1 , ..., T m , we present a highly parallelizable scheme. Finally, we derive a parallel bundle method for minimizing the sum of polyhedral functions. [ABSTRACT FROM AUTHOR]

For convex minimization we introduce an algorithm based on -space decomposition. The method uses a bundle subroutine to generate a sequence of approximate proximal points. When a primal-dual track leading to a solution and zero subgradient pair exists, these points approximate the primal track points and give the algorithm's , or corrector, steps. The subroutine also approximates dual track points that are -gradients needed for the method's -Newton predictor steps. With the inclusion of a simple line search the resulting algorithm is proved to be globally convergent. The convergence is superlinear if the primal-dual track points and the objective's -Hessian are approximated well enough. [ABSTRACT FROM AUTHOR]

We explore and construct an enlarged subdifferential for weakly convex functions. The resulting object turns out to be continuous with respect to both the function argument and the enlargement parameter. We carefully analyze connections with other constructs in the literature and particularize to the weakly convex setting well-known variational principles. By resorting to the new enlarged subdifferential, we provide an algorithmic pattern of descent for weakly convex minimization. Under minimal assumptions, we show subsequential convergence to a critical point. Links with difference-of-convex functions algorithms and criticality conditions are also discussed. [ABSTRACT FROM AUTHOR]

During the early months of the current COVID-19 pandemic, social distancing measures effectively slowed disease transmission in many countries in Europe and Asia, but the same benefits have not been observed in some developing countries such as Brazil. In part, this is due to a failure to organise systematic testing campaigns at nationwide or even regional levels. To gain effective control of the pandemic, decision-makers in developing countries, particularly those with large populations, must overcome difficulties posed by an unequal distribution of wealth combined with low daily testing capacities. The economic infrastructure of these countries, often concentrated in a few cities, forces workers to travel from commuter cities and rural areas, which induces strong nonlinear effects on disease transmission. In the present study, we develop a smart testing strategy to identify geographic regions where COVID-19 testing could most effectively be deployed to limit further disease transmission. By smart testing we mean the testing protocol that is automatically designed by our optimization platform for a given time period, knowing the available number of tests, the current availability of ICU beds and the initial epidemiological situation. The strategy uses readily available anonymised mobility and demographic data integrated with intensive care unit (ICU) occupancy data and city-specific social distancing measures. Taking into account the heterogeneity of ICU bed occupancy in differing regions and the stages of disease evolution, we use a data-driven study of the Brazilian state of Sao Paulo as an example to show that smart testing strategies can rapidly limit transmission while reducing the need for social distancing measures, even when testing capacity is limited. [ABSTRACT FROM AUTHOR]

Intermittent sources of energy represent a challenge for electrical networks, particularly regarding demand satisfaction at peak times. Energy management tools such as load shaving or storage systems can be used to mitigate intermittency. In this work, the value of different mechanisms to move energy through time is examined through a multi-objective programming approach, that aims at minimizing operating costs as well as carbon emissions. Among main achievements, we mention a sensitivity result that provides a novel three-dimensional Pareto front. The new tool complements the traditional curves of indifference costs with a quantitative measure for assessing the relative value of the conflicting objectives. The methodology is assessed on three instances representing typical configurations in Brazil, Germany and France, respectively corresponding to a system that is hydro-dominated, thermo-dominated, and with a balanced mix of hydro and thermal power. The corresponding Pareto fronts show that lowering carbon emissions can also reduce generation costs if the power mix is sufficiently diversified. [ABSTRACT FROM AUTHOR]

The V U -algorithm is a superlinearly convergent method for minimizing nonsmooth, convex functions. At each iteration, the algorithm works with a certain V -space and its orthogonal U -space, such that the nonsmoothness of the objective function is concentrated on its projection onto the V -space, and on the U -space the projection is smooth. This structure allows for an alternation between a Newton-like step where the function is smooth, and a proximal-point step that is used to find iterates with promising V U -decompositions. We establish a derivative-free variant of the V U -algorithm for convex finite-max objective functions. We show global convergence and provide numerical results from a proof-of-concept implementation, which demonstrates the feasibility and practical value of the approach. We also carry out some tests using nonconvex functions and discuss the results. [ABSTRACT FROM AUTHOR]

For solving nonsmooth convex constrained optimization problems, we propose an algorithm which combines the ideas of the proximal bundle methods with the filter strategy for evaluating candidate points. The resulting algorithm inherits some attractive features from both approaches. On the one hand, it allows effective control of the size of quadratic programming subproblems via the compression and aggregation techniques of proximal bundle methods. On the other hand, the filter criterion for accepting a candidate point as the new iterate is sometimes easier to satisfy than the usual descent condition in bundle methods. Some encouraging preliminary computational results are also reported. [ABSTRACT FROM AUTHOR]