In this paper, we propose a variable sample distributed algorithm for the computation of stochastic Nash equilibrium in which the objective functions are replaced, at each iteration, by sample average approximations. We investigate the contraction mapping properties of the variable sample distributed algorithm and show that the accuracy of estimators yielded in the algorithms to … Read more
Packing problems in discrete geometry can be modeled as finding independent sets in infinite graphs where one is interested in independent sets which are as large as possible. For finite graphs one popular way to compute upper bounds for the maximal size of an independent set is to use Lasserre’s semidefinite programming hierarchy. We generalize … Read more
We consider the natural generalizations of blocking and anti-blocking polyhedra in infinite dimensions, and study issues related to duality and integrality of extreme points for these sets. Using appropriate finite truncations, we give conditions under which complementary slackness holds for primal-dual pairs of the infi nite linear programming problems associated with infi nite blocking and anti-blocking polyhedra. … Read more
In the \emph{incremental knapsack problem} ($\IK$), we are given a knapsack whose capacity grows weakly as a function of time. There is a time horizon of $T$ periods and the capacity of the knapsack is $B_t$ in period $t$ for $t = 1, \ldots, T$. We are also given a set $S$ of $N$ items … Read more
The trust-region subproblem minimizes a general quadratic function over an ellipsoid and can be solved in polynomial time using a semidefinite-programming (SDP) relaxation. Intersecting the feasible set with a second ellipsoid results in the two-trust-region subproblem (TTRS). Even though TTRS can also be solved in polynomial-time, existing algorithms do not use SDP. In this paper, … Read more
We study the {\em Celis-Dennis-Tapia (CDT) problem}: minimize a non-convex quadratic function over the intersection of two ellipsoids. In contrast to the well-studied trust region problem where the feasible set is just one ellipsoid, the CDT problem is not yet fully understood. Our main objective in this paper is to narrow the difficulty gap that … Read more
We study the minimum concave cost flow problem over a two-dimensional grid network (CFG), where one dimension represents time ($1\le t\le T$) and the other dimension represents echelons ($1\le l\le L$). The concave function over each arc is given by a value oracle. We give a polynomial-time algorithm for finding the optimal solution when the … Read more
A new computational algorithm is introduced in the present study to solve multimaterial topology optimization problems. It is based on the penalization of the objective functional by the multiphase volume constrained Cahn-Hilliard energy functional. The update procedure is based on the gradient flow of the objective functional by a fractional step projected steepest descent method. … Read more
Constrained global optimization problems can be tackled by using exact penalty approaches. In a preceding paper, we proposed an exact penalty algorithm for constrained problems which combines an unconstrained global minimization technique for minimizing a non-differentiable exact penalty func- tion for given values of the penalty parameter, and an automatic updating of the penalty parameter … Read more
In this paper, we introduce a framework for derivative-free robust optimization based on the use of an efficient derivative-free optimization routine for mixed integer nonlinear problems. The proposed framework is employed to find a robust optimal design of a particular integrated circuit (namely a DC-DC converter commonly used in portable electronic devices). The proposed robust … Read more