Showing 1 to 10 of 719 matching Articles
Results per page:
Export (CSV)
By
John, Reinhard
14 Citations
Some notions of generalized monotonicity for multivalued mappings are characterized in terms of properties of the associated Minty variational inequalities. In particular, it is shown that the Minty variational inequality problem derived from a map F defined on a convex domain is solvable on any nonempty, compact, and convex subdomain if and only if F is properly quasimonotone.
more …
By
Sojoudi, Somayeh; Fattahi, Salar; Lavaei, Javad
This paper is concerned with the minimumcost flow problem over an arbitrary flow network. In this problem, each node is associated with some possibly unknown injection and each line has two unknown flows at its ends that are related to each other via a nonlinear function. Moreover, all injections and flows must satisfy certain box constraints. This problem, named generalized network flow (GNF), is highly nonconvex due to its nonlinear equality constraints. Under the assumption of monotonicity and convexity of the flow and cost functions, a convex relaxation is proposed, which is shown to always obtain globally optimal injections. This relaxation may fail to find optimal flows because the mapping from injections to flows is not unique in general. We show that the proposed relaxation, named convexified GNF (CGNF), obtains a globally optimal flow vector if the optimal injection vector is a Pareto point. More generally, the network can be decomposed into two subgraphs such that the lines between the subgraphs are congested at optimality and that CGNF finds correct optimal flows over all lines of one of these subgraphs. We also fully characterize the set of all globally optimal flow vectors, based on the optimal injection vector found via CGNF. In particular, we show that this solution set is a subset of the boundary of a convex set, and may include an exponential number of disconnected components. A primary application of this work is in optimization over electrical power networks.
more …
By
Draisma, Jan; Horobeţ, Emil; Ottaviani, Giorgio; Sturmfels, Bernd; Thomas, Rekha R.
Show all (5)
40 Citations
The nearest point map of a real algebraic variety with respect to Euclidean distance is an algebraic function. For instance, for varieties of lowrank matrices, the Eckart–Young Theorem states that this map is given by the singular value decomposition. This article develops a theory of such nearest point maps from the perspective of computational algebraic geometry. The Euclidean distance degree of a variety is the number of critical points of the squared distance to a general point outside the variety. Focusing on varieties seen in applications, we present numerous tools for exact computations.
more …
By
Li, YuFan; Huang, ZhengHai; Zhang, Min
1 Citations
Recently, the
$$l_p$$
minimization problem (
$$p\in (0,\,1)$$
) for sparse signal recovery has been studied a lot because of its efficiency. In this paper, we propose a general smoothing algorithmic framework based on the entropy function for solving a class of
$$l_p$$
minimization problems, which includes the wellknown unconstrained
$$l_2$$
–
$$l_p$$
problem as a special case. We show that any accumulation point of the sequence generated by the proposed algorithm is a stationary point of the
$$l_p$$
minimization problem, and derive a lower bound for the nonzero entries of the stationary point of the smoothing problem. We implement a specific version of the proposed algorithm which indicates that the entropy functionbased algorithm is effective.
more …
By
Merzifonluoğlu, Yasemin; Geunes, Joseph; Romeijn, H. Edwin
17 Citations
This paper develops exact and heuristic algorithms for a stochastic knapsack problem where items with random sizes may be assigned to a knapsack. An item’s value is given by the realization of the product of a random unit revenue and the random item size. When the realization of the sum of selected item sizes exceeds the knapsack capacity, a penalty cost is incurred for each unit of overflow, while our model allows for a salvage value for each unit of capacity that remains unused. We seek to maximize the expected net profit resulting from the assignment of items to the knapsack. Although the capacity is fixed in our core model, we show that problems with random capacity, as well as problems in which capacity is a decision variable subject to unit costs, fall within this class of problems as well. We focus on the case where item sizes are independent and normally distributed random variables, and provide an exact solution method for a continuous relaxation of the problem. We show that an optimal solution to this relaxation exists containing no more than two fractionally selected items, and develop a customized branchandbound algorithm for obtaining an optimal binary solution. In addition, we present an efficient heuristic solution method based on our algorithm for solving the relaxation and empirically show that it provides highquality solutions.
more …
By
Nie, Jiawang
55 Citations
Lasserre’s hierarchy is a sequence of semidefinite relaxations for solving polynomial optimization problems globally. This paper studies the relationship between optimality conditions in nonlinear programming theory and finite convergence of Lasserre’s hierarchy. Our main results are: (i) Lasserre’s hierarchy has finite convergence when the constraint qualification, strict complementarity and second order sufficiency conditions hold at every global minimizer, under the standard archimedean condition; the proof uses a result of Marshall on boundary hessian conditions. (ii) These optimality conditions are all satisfied at every local minimizer if a finite set of polynomials, which are in the coefficients of input polynomials, do not vanish at the input data (i.e., they hold in a Zariski open set). This implies that, under archimedeanness, Lasserre’s hierarchy has finite convergence generically.
more …
By
Chen, Xin; Peng, Jiming; Zhang, Shuzhong
9 Citations
The standard quadratic optimization problem (StQP) refers to the problem of minimizing a quadratic form over the standard simplex. Such a problem arises from numerous applications and is known to be NPhard. In this paper we focus on a special scenario of the StQP where all the elements of the data matrix Q are independently identically distributed and follow a certain distribution such as uniform or exponential distribution. We show that the probability that such a random StQP has a global optimal solution with k nonzero elements decays exponentially in k. Numerical evaluation of our theoretical finding is discussed as well.
more …
By
Scitovski, Rudolf ; Sabo, Kristian
In this paper, we propose an efficient method for searching for a globally optimal kpartition of the set
$$\mathcal {A}\subset \mathbb {R}^n$$
. Due to the property of the DIRECT global optimization algorithm to usually quickly arrive close to a point of global minimum, after which it slowly attains the desired accuracy, the proposed method uses the wellknown kmeans algorithm with a initial approximation chosen on the basis of only a few iterations of the DIRECT algorithm. In case of searching for an optimal kpartition of spherical clusters, the method is not worse than other known methods, but in case of solving the multiple circle detection problem, the proposed method shows remarkable superiority.
more …
By
Li, Guoyin; Pong, Ting Kei
22 Citations
We adapt the Douglas–Rachford (DR) splitting method to solve nonconvex feasibility problems by studying this method for a class of nonconvex optimization problem. While the convergence properties of the method for convex problems have been well studied, far less is known in the nonconvex setting. In this paper, for the direct adaptation of the method to minimize the sum of a proper closed function g and a smooth function f with a Lipschitz continuous gradient, we show that if the stepsize parameter is smaller than a computable threshold and the sequence generated has a cluster point, then it gives a stationary point of the optimization problem. Convergence of the whole sequence and a local convergence rate are also established under the additional assumption that f and g are semialgebraic. We also give simple sufficient conditions guaranteeing the boundedness of the sequence generated. We then apply our nonconvex DR splitting method to finding a point in the intersection of a closed convex set C and a general closed set D by minimizing the squared distance to C subject to D. We show that if either set is bounded and the stepsize parameter is smaller than a computable threshold, then the sequence generated from the DR splitting method is actually bounded. Consequently, the sequence generated will have cluster points that are stationary for an optimization problem, and the whole sequence is convergent under an additional assumption that C and D are semialgebraic. We achieve these results based on a new merit function constructed particularly for the DR splitting method. Our preliminary numerical results indicate that our DR splitting method usually outperforms the alternating projection method in finding a sparse solution of a linear system, in terms of both the solution quality and the number of iterations taken.
more …
By
Beck, Amir; Hallak, Nadav
This paper studies a general form problem in which a lower bounded continuously differentiable function is minimized over a block separable set incorporating a group sparsity expression as a constraint or a penalty (or both) in the group sparsity setting. This class of problems is generally hard to solve, yet highly applicable in numerous practical settings. Particularly, we study the proximal mapping that includes groupsparsity terms, and derive an efficient method to compute it. Necessary optimality conditions for the problem are devised, and a hierarchy between stationarybased and coordinatewised based conditions is established. Methods that obtain points satisfying the optimality conditions are presented, analyzed and tested in applications from the fields of investment and graph theory.
more …
