We give a novel spectral approximation algorithm for the balanced separator problem that, given a graph G, a constant balance b \in (0,1/2], and a parameter \gamma, either finds an \Omega(b)-balanced cut of conductance O(\sqrt{\gamma}) in G, or outputs a certificate that all b-balanced cuts in G have conductance at least \gamma, and runs in … Read more
This paper adresses the robust counterparts of optimization problems containing sums of maxima of linear functions and proposes several reformulations. These problems include many practical problems, e.g. problems with sums of absolute values, and arise when taking the robust counterpart of a linear inequality that is affine in the decision variables, affine in a parameter … Read more
We call a positive semidefinite matrix whose elements are nonnegative a doubly nonnegative matrix, and the set of those matrices the doubly nonnegative cone (DNN cone). The DNN cone is not symmetric but can be represented as the projection of a symmetric cone embedded in a higher dimension. In \cite{aYOSHISE10}, the authors demonstrated the efficiency … Read more
This paper contributes to a deeper understanding of the link between a now conventional framework in hierarchical optimization spread under the name of the optimistic bilevel problem and its initial more dicult formulation that we call here the original optimistic bilevel optimization problem. It follows from this research that, although the process of deriving necessary … Read more
The paper is concerned with the optimistic formulation of a bilevel optimization problem with multiobjective lower-level problem. Considering the scalarization approach for the multiobjective program, we transform our problem into a scalar-objective optimization problem with inequality constraints by means of the well-known optimal value reformulation. Completely detailed rst-order necessary optimality conditions are then derived in … Read more
This paper presents a methodology for using varying sample sizes in batch-type optimization methods for large scale machine learning problems. The first part of the paper deals with the delicate issue of dynamic sample selection in the evaluation of the function and gradient. We propose a criterion for increasing the sample size based on variance … Read more
The family of optimization problems with value function objectives includes the minmax programming problem and the bilevel optimization problem. In this paper, we derive necessary optimality conditions for this class of problems. The main focus is on the case where the functions involved are nonsmooth and the constraints are the very general operator constraints. CitationsubmittedArticleDownload … Read more
We propose a method to reduce the sizes of SDP relaxation problems for a given polynomial optimization problem (POP). This method is an extension of the elimination method for a sparse SOS polynomial in [Kojima et al., Mathematical Programming] and exploits sparsity of polynomials involved in a given POP. In addition, we show that this … Read more
Tressler’s Theorem states that the long-standing Hadamard conjecture (concerning the existence of n by n orthogonal matrices with elements of the same absolute value, for n=4k, k=1,2,…) will be settled if we find n-2 pairwise orthogonal words in a hyperplane of words. In this paper we will prove the counterpart of Tressler’s Theorem: the existence … Read more
This paper takes a uniform look at the customized applications of proximal point algorithm (PPA) to two classes of problems: the linearly constrained convex minimization problem with a generic or separable objective function and a saddle-point problem. We model these two classes of problems uniformly by a mixed variational inequality, and show how PPA with … Read more