Search

We give a simple and natural method for computing approximately optimal solutions for minimizing a convex function f over a convex set K given by a separation oracle. Our method utilizes the Frank–Wolfe algorithm over the cone of valid inequalities of K and subgradients of f. Under the assumption that f is L-Lipschitz and that K contains a ball of radius r and is contained inside the origin centered ball of radius R, using O (R L) 2 ε 2 · R 2 r 2 iterations and calls to the oracle, our main method outputs a point x ∈ K satisfying f (x) ≤ ε + min z ∈ K f (z) . Our algorithm is easy to implement, and we believe it can serve as a useful alternative to existing cutting plane methods. As evidence towards this, we show that it compares favorably in terms of iteration counts to the standard LP based cutting plane method and the analytic center cutting plane method, on a testbed of combinatorial, semidefinite and machine learning instances. [ABSTRACT FROM AUTHOR]

With the rapid development of artificial intelligence in recent years, applying various learning techniques to solve mixed-integer linear programming (MILP) problems has emerged as a burgeoning research domain. Apart from constructing end-to-end models directly, integrating learning approaches with some modules in the traditional methods for solving MILPs is also a promising direction. The cutting plane method is one of the fundamental algorithms used in modern MILP solvers, and the selection of appropriate cuts from the candidate cuts subset is crucial for enhancing efficiency. Due to the reliance on expert knowledge and problem-specific heuristics, classical cut selection methods are not always transferable and often limit the scalability and generalizability of the cutting plane method. To provide a more efficient and generalizable strategy, we propose a reinforcement learning (RL) framework to enhance cut selection in the solving process of MILPs. Firstly, we design feature vectors to incorporate the inherent properties of MILP and computational information from the solver and represent MILP instances as bipartite graphs. Secondly, we choose the weighted metrics to approximate the proximity of feasible solutions to the convex hull and utilize the learning method to determine the weights assigned to each metric. Thirdly, a graph convolutional neural network is adopted with a self-attention mechanism to predict the value of weighting factors. Finally, we transform the cut selection process into a Markov decision process and utilize RL method to train the model. Extensive experiments are conducted based on a leading open-source MILP solver SCIP. Results on both general and specific datasets validate the effectiveness and efficiency of our proposed approach. [ABSTRACT FROM AUTHOR]

We study the robust charging station location problem for a large-scale commercial taxi fleet. Vehicles within the fleet coordinate on charging operations but not on customer acquisition. We decide on a set of charging stations to open to ensure operational feasibility. To make this decision, we propose a novel solution method situated between the location routing problems with intraroute facilities and flow refueling location problems. Additionally, we introduce a problem variant that makes a station sizing decision. Using our exact approach, charging stations for a robust operation of citywide taxi fleets can be planned. We develop a deterministic core problem employing a cutting plane method for the strategic problem and a branch-and-price decomposition for the operational problem. We embed this problem into a robust solution framework based on adversarial sampling, which allows for planner-selectable risk tolerance. We solve instances derived from real-world data of the metropolitan area of Munich containing 1,000 vehicles and 60 potential charging station locations. Our investigation of the sensitivity of technological developments shows that increasing battery capacities shows a more favorable impact on vehicle feasibility of up to 10 percentage points compared with increasing charging speeds. Allowing for depot charging dominates both of these options. Finally, we show that allowing just 1% of operational infeasibility risk lowers infrastructure costs by 20%. Funding: This work was partially funded by the Deutsche Forschungsgemeinschaft [Project 277991500]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/trsc.2022.0207. [ABSTRACT FROM AUTHOR]

We consider derivatives written on multiple underlyings in a one-period financial market, and we are interested in the computation of model-free upper and lower bounds for their arbitrage-free prices. We work in a completely realistic setting, in that we only assume the knowledge of traded prices for other single- and multi-asset derivatives and even allow for the presence of bid–ask spread in these prices. We provide a fundamental theorem of asset pricing for this market model, as well as a superhedging duality result, that allows to transform the abstract maximization problem over probability measures into a more tractable minimization problem over vectors, subject to certain constraints. Then, we recast this problem into a linear semi-infinite optimization problem and provide two algorithms for its solution. These algorithms provide upper and lower bounds for the prices that are ε-optimal, as well as a characterization of the optimal pricing measures. These algorithms are efficient and allow the computation of bounds in high-dimensional scenarios (e.g., when d = 60). Moreover, these algorithms can be used to detect arbitrage opportunities and identify the corresponding arbitrage strategies. Numerical experiments using both synthetic and real market data showcase the efficiency of these algorithms, and they also allow understanding of the reduction of model risk by including additional information in the form of known derivative prices. This paper was accepted by Chung Piaw Teo, optimization. Funding: This work was supported by the Nanyang Technological University [NAP Grant] and the Hellenic Foundation for Research and Innovation [Grant HFRI-FM17-2152]. Supplemental Material: The data files and online appendices are available at https://doi.org/10.1287/mnsc.2022.4456. [ABSTRACT FROM AUTHOR]

The paper deals with a general problem of convex stochastic optimization in a space of small dimension (for example, 100 variables). It is known that for deterministic problems of convex optimization in small dimensions, the methods of centers of gravity type (for example, Vaidya's method) provide the best convergence. For stochastic optimization problems, the question of the possibility of applying Vaidya's method can be reduced to the question of how it accumulates inaccuracies in the subgradient. A recent result of the authors stating that there is no accumulation of inaccuracies at the iterations of Vaidya's method allows the authors to propose its analog for solving stochastic optimization problems. The main technique is to replace the subgradient in Vaidya's method by its batched analogue (the arithmetic mean of stochastic subgradients). In the present paper, this plan is implemented, which results in an efficient method (under conditions of the possibility of parallel calculations with batching) for solving problems of convex stochastic optimization in spaces of small dimensions. The work of the algorithm is illustrated by a numerical experiment. [ABSTRACT FROM AUTHOR]

In this paper, we present a sequential sampling-based algorithm for the two-stage distributionally robust linear programming (2-DRLP) models. The 2-DRLP models are defined over a general class of ambiguity sets with discrete or continuous probability distributions. The algorithm is a distributionally robust version of the well-known stochastic decomposition algorithm of Higle and Sen [Math. Oper. Res., 16 (1991), pp. 650-669] for a two-stage stochastic linear program. We refer to the algorithm as the distributionally robust stochastic decomposition (DRSD) method. The key features of the algorithm include (1) it works with data-driven approximations of ambiguity sets that are constructed using samples of increasing size and (2) efficient construction of approximations of the worst-case expectation function that solves only two second-stage subproblems in every iteration. We identify conditions under which the ambiguity set approximations converge to the true ambiguity sets and show that the DRSD method asymptotically identifies an optimal solution, with probability one. We also computationally evaluate the performance of the DRSD method for solving distributionally robust versions of instances considered in stochastic programming literature. The numerical results corroborate the analytical behavior of the DRSD method and illustrate the computational advantage over an external sampling-based decomposition approach (distributionally robust L-shaped method). [ABSTRACT FROM AUTHOR]

As the installation of electronically interconnected renewable energy resources grows rapidly in power systems, system frequency maintenance and control become challenging problems to maintain the system reliability in bulk power systems. As two of the most important frequency control actions in the control centers of independent system operators (ISOs) and utilities, the interaction between Economic Dispatch (ED) and Automatic Generation Control (AGC) attracts more and more attention. In this paper, we propose a robust optimization based framework to measure the system flexibility by considering the interaction between two hierarchical processes (i.e., ED and AGC). We propose a cutting plane algorithm with the reformulation technique to obtain seven different indices of the system. In addition, we study the impacts of several system factors (i.e., the budget of operational cost, ramping capability, and transmission line capacity) and show numerically how these factors can influence the system flexibility. [ABSTRACT FROM AUTHOR]

Integer Linear Programming is a special form of linear programming which the decision variables are in integer form. Berkah Rasa is a home industry business in the form of Jenang Ayu and Jenang Krasikan processed food. The daily production that carried out by Berkah Rasa is based on the availability of raw materials and the number of requests. So far, Berkah Rasa has not had the right strategy in producing Jenang to get maximum profit. The purpose of this research is to apply integer linear programming to the optimization of Jenang Ayu and Jenang Krasikan production. The method used to solve this problem is the cutting plane method. The results of the research obtained is the optimal solution for Berkah Rasa, that is by producing 25 kg of Jenang Ayu and 22 kg of Jenang Krasikan every day. So that the benefits obtained by Berkah Rasa every day are IDR 727,000.00.

We consider the integer points in a unimodular cone K ordered by a lexicographic rule defined by a lattice basis. To each integer point x in K we associate a family of inequalities (lex-inequalities) that define the convex hull of the integer points in K that are not lexicographically smaller than x. The family of lex-inequalities contains the Chvátal–Gomory cuts, but does not contain and is not contained in the family of split cuts. This provides a finite cutting plane method to solve the integer program min { c x : x ∈ S ∩ Z n } , where S ⊂ R n is a compact set and c ∈ Z n . We analyze the number of iterations of our algorithm. [ABSTRACT FROM AUTHOR]

The article deals with some approaches to solving convex problems of the min-min type with smoothness and strong convexity in only one of the two groups of variables. It is shown that the proposed approaches based on Vaidya's method, the fast gradient method, and the accelerated gradient method with variance reduction have linear convergence. It is proposed to use Vaidya's method to solve the exterior problem and the fast gradient method to solve the interior (smooth and strongly convex) one. Due to its importance for applications in machine learning, the case where the objective function is the sum of a large number of functions is considered separately. In this case, the accelerated gradient method with variance reduction is used instead of the fast gradient method. The results of numerical experiments are presented that illustrate the advantages of the proposed procedures for a logistic regression problem in which the a priori distribution for one of the two groups of variables is available. [ABSTRACT FROM AUTHOR]

This study aims to determine the minimum spanning tree of a complete graph K_n with weight constraints and completion using the cutting plane method. The cutting plane method is one of the algorithms included in the exact method. This algorithm works by reducing the solution area so that it becomes narrower. As a result, the feasible solutions that will be investigated become less and less. This is because the cutting plane method works based on the optimal linear programming solution of relaxation solved by the simplex method. In this paper we give illustration of the algorithm applied for two cases, one for K_4 and one for K_5.

A tiny subclass of minimum-type functions, called G n + 1 , is introduced. We show that abstract convex functions generated by G n + 1 and those generated by the whole class of minimum-type functions coincide. Other concepts from abstract convex analysis such as support set, subdifferential and conjugate function with respect to G n + 1 are investigated. We will use these results to establish a stochastic version of generalized cutting plane method (SGCPM) to solve two-stage nonconvex programming problems. Under mild conditions, we will show that every limit point of the sequence generated by SGCPM is an optimal solution. [ABSTRACT FROM AUTHOR]

Although concern has been recently expressed with regard to the solution to the non-convex problem, convex optimization is still important in machine learning, especially when the situation requires an interpretable model. Solution to the convex problem is a global minimum, and the final model can be explained mathematically. Typically, the convex problem is re-casted as a regularized risk minimization problem to prevent overfitting. The cutting plane method (CPM) is one of the best solvers for the convex problem, irrespective of whether the objective function is differentiable or not. However, CPM and its variants fail to adequately address large-scale dataintensive cases because these algorithms access the entire dataset in each iteration, which substantially increases the computational burden and memory cost. To alleviate this problem, we propose a novel algorithm named the mini-batch cutting plane method (MBCPM), which iterates with estimated cutting planes calculated on a small batch of sampled data and is capable of handling large-scale problems. Furthermore, the proposed MBCPM adopts a "sink" operation that detects and adjusts noisy estimations to guarantee convergence. Numerical experiments on extensive real-world datasets demonstrate the effectiveness of MBCPM, which is superior to the bundle methods for regularized risk minimization as well as popular stochastic gradient descent methods in terms of convergence speed. [ABSTRACT FROM AUTHOR]

Although several classes of cutting plane methods for deterministically solving disjoint bilinear programming (DBLP) have been proposed, the frequently encountered computational issue regarding the generation of a suitable cut from a degenerate vertex in a pseudo-global minimizer (PGM) still remains. Among the approaches to dealing with degeneracy, the most recent one is to generate a conservative cut. Nevertheless, the computational performance of the corresponding distance-following algorithm for its location seems far from satisfactory. This paper proposes several approaches that can be utilized to efficiently locate a conservative hyperplane from a degenerate vertex in a PGM. Extensive experiments are conducted to evaluate their performance from the dimensionality as well as the degree of degeneracy. From the computational viewpoint, these new approaches can outperform the earlier developed distance-following algorithm, and thereby can be incorporated into cutting plane methods for solving DBLP. [ABSTRACT FROM AUTHOR]

The paper deals with modelling a specifc problem called the Optimal Seating Arrangement (OSA) as an Integer Linear Program and demonstrated that the problem can be efficiently solved by combining branch-and-bound and cutting plane methods. OSA refers to a specific scenario that could possibly happen in a corporative environment, i.e. when a company endeavors to minimize travel costs when employees travel to an organized event. Each employee is free to choose the time to travel to and from an event and it depends on personal reasons. The paper differentiates between using different travel possibilities in the OSA problem, such as using company assigned or a company owned vehicles, private vehicles or using public transport, if needed. Also, a user-friendly web application was made and is available to the public for testing purposes.

Cutting plane methods are an important component in solving the mixed integer programming (MIP). By carefully studying the coefficient strengthening method, which is originally a presolving method, we are able to generalize this method to generate a family of valid inequalities called generalized coefficient strengthening (GCS) inequalities. The invariant property of the GCS inequalities is established under bound substitutions. Furthermore, we develop a separation algorithm for finding the violated GCS inequalities for a general mixed integer set. The separation algorithm is proved to have the polynomial time complexity. Extensive numerical experiments are made on standard MIP test sets, which demonstrate the usefulness of the resulting GCS separator. [ABSTRACT FROM AUTHOR]

We focus on nonconvex multi-agent optimization where a large number of participants collaboratively optimize some social cost function and their individual preferences. We focus on the semidecentralized multi-agent best response setting where a central planner attempts to coordinate the agents and each participant pursues self-interest. By studying the duality framework, we provide geometric and analytic characterizations of the duality gap and the price of decentralization. We prove that the nonconvex problem becomes increasingly convex as the problem scales up in dimension. Upon appropriate coordination, the price of decentralization asymptotically vanishes to zero as the number of participants grows. We develop a duality-based coordination procedure for the central planner to adapt the price vector and select a particular best response for each participant. The coordination algorithm is able to induce individual best responses to dynamically converge to an approximate global optimum, regardless of the initial solution. A convergence rate and complexity analysis as well as numerical results are provided. In the case without any coordination, we provide counterexamples showing that the price of decentralization can be disastrously high. [ABSTRACT FROM AUTHOR]

Wavelength division multiplexing (WDM) technology transmits multiple optical communication channels in an optical fiber. Routing and wavelength assignment (RWA) problems on WDM network have widely attracted interest of many researchers. Recently, so called sub-wavelength paths which are smaller granular paths than the wavelength-paths are discussed. In this paper, we deal with the RWA problem with considering sub-wavelength assignment on optical networks. One of the purpose of our study is to investigate active rates for optical networks. We formulate a sub-wavelength path assignment problem maximizing accommodated traffic demands by integer programming and solve it by a cutting plane algorithm. Since, in actuality, RWA is done individually for each demand on the time when the demand occurs, we consider a greedy type on-line algorithm. Numerical experiments show the efficiency of our algorithms and give some observation for active rates. Moreover, we verify the efficiency of our greedy-type algorithm on realistic situations which follow 10/40/100 Gbps system used for the current communication on optical networks. Our experimental results conclude that the active rates are depending on the configurations of the underlying graphs, and that our greedy-type algorithm is efficient for several kinds of instances.

This work deals with a new method for solving Integer Linear Programming Problems depending on a previous methods for solving these problems such that Branch and Bound method and Cutting Planes method where this new method is a combination between them and we called it Cut and Branch method, The reasons which led to this combination between Cutting Planes method and Branch and Bound method are to defeat from the drawbacks of both methods and especially the big number of iterations and the long time for the solving and getting of a results between the results of these methods where the Cut and Branch method took the good properties from the both methods. And this work deals with solving a one problem of Integer Linear Programming Problems by Branch and Bound method and Cutting Planes method and the new method, and we made a programs on the computer for solving ten problems of Integer Linear Programming Problems by these methods then we got a good results and by that, the new method (Cut and Branch) became a good method for solving Integer Linear Programming Problems. The combination method which we doing in this research opened a big and wide field in solving Integer Linear Programming Problems and finding the best solutions for them where we did the combination method again between the new method (Cut and Branch) and the Cutting Planes method then we got a new method with a very good results and solutions.

Temporary haul road plays a pivotal part in achieving cost-efficiency and successful project delivery in heavy civil and industrial construction. Temporary haul road layout design has been empirically performed by field managers, superintendents or even truck drivers largely based on experience instead of science. Previous research endeavors in earthmoving research devised analytical algorithms to minimize the total earthmoving cost and developed simulation models to optimize earthmoving resources and processes. In the same domain, this research introduces an optimization methodology for temporary haul road layout design in order to facilitate mass earthmoving operations and improve construction performances on a typical rough-grading site. A Mixed-Integer Linear Programming model, integrated with a cutting plane method, is established for the identified problem. In particular, the cutting plane method is introduced to refine the optimization formulation by maintaining field accessibility and haul road continuity, thus ensuring practical feasibility of the analytical solution. Performances of the newly devised algorithms were benchmarked against genetic algorithms in solving ten test cases. Further, feasibility of the proposed methodology was evaluated based on a real-world case study. In conclusion, the proposed methodology is capable of tackling the temporary haul road layout design problem with high computing efficiency and delivering optimal results that are ready for field implementation. [ABSTRACT FROM AUTHOR]

The primal-dual column generation method (PDCGM) is a general-purpose column generation technique that relies on the primal-dual interior point method to solve the restricted master problems. The use of this interior point method variant allows to obtain suboptimal and well-centered dual solutions which naturally stabilizes the column generation process. As recently presented in the literature, reductions in the number of calls to the oracle and in the CPU times are typically observed when compared to the standard column generation, which relies on extreme optimal dual solutions. However, these results are based on relatively small problems obtained from linear relaxations of combinatorial applications. In this paper, we investigate the behaviour of the PDCGM in a broader context, namely when solving large-scale convex optimization problems. We have selected applications that arise in important real-life contexts such as data analysis (multiple kernel learning problem), decision-making under uncertainty (two-stage stochastic programming problems) and telecommunication and transportation networks (multicommodity network flow problem). In the numerical experiments, we use publicly available benchmark instances to compare the performance of the PDCGM against recent results for different methods presented in the literature, which were the best available results to date. The analysis of these results suggests that the PDCGM offers an attractive alternative over specialized methods since it remains competitive in terms of number of iterations and CPU times even for large-scale optimization problems. [ABSTRACT FROM AUTHOR]

Preventive healthcare (PH) programs and services aim at reducing the likelihood and severity of potentially life-threatening illness by early detection and prevention. The effectiveness of these programs depends on the participation level and the accessibility of the users to the facilities providing the services. Factors that impact the accessibility include the number, type, and location of the facilities as well as the assignment of the clients to these facilities. In this paper, we study the impact of system-optimal (i.e., directed) choice on the design of the preventive healthcare facility network under congestion. We present a model that simultaneously determines the location and the size of the facilities as well as the allocation of clients to these facilities so as to minimize the weighted sum of the total travel time and the congestion associated with waiting and service delay at the facilities. The problem is set up as a network of spatially distributed M/G/1 queues and formulated as a nonlinear mixed integer program. Using simple transformation of the nonlinear objective function and piecewise linear approximation, we reformulate the problem as a linear model. We present a cutting plane algorithm based exact (휖-optimal) solution approach. We analyze the tradeoff between travel time and queuing time and its impact on the location and capacity of the facilities as well as the allocation of clients to these facilities under a directed choice policy. We present a case study that deals with locating mammography clinics in Montreal, Canada. The results show that incorporating congestion in the PH facility network design substantially reduces the total time spent by clients. The proposed model allows policy makers to direct clients to facilities in an equitable manner resulting in better accessibility. [ABSTRACT FROM AUTHOR]

A robust congestion pricing (ROPRICE) of signal-controlled road network is considered for equilibrium network flow with uncertain travel demand. A min–max bi-level program is presented to mitigate vulnerability of area traffic control road network against growing travel demand and reduce traffic congestion. A cutting plane projection approach (CPP) is proposed to effectively solve the ROPRICE problem with global convergence. Numerical computations are performed using various test road networks and comparisons are made with recently proposed heuristics. Computational results indicate that the proposed solution scheme can substantially achieve greater system performance as compared to other alternatives. [ABSTRACT FROM AUTHOR]

A solution algorithm is proposed for problems of nondifferentiable optimization of a family of separating plane methods with additional clippings generated by the solution of an auxiliary problem of the cutting plane method. The convergence of this algorithm is proved, and the results of computational experiments are given that demonstrate its overall computational efficiency compared to that of well-known leaders in this field. Transportation-type problems with constraints on flows are reduced to problems of projection of a sufficiently remote point onto an admissible set. [ABSTRACT FROM AUTHOR]

In this article, we address the problem of synthesizing communication networks for unmanned aerial vehicles (UAVs) in the presence of resource constraints. UAVs can be deployed as backbone nodes in ad hoc networks that can be central to civilian and military applications. The cost of operation of the network depends on the resources that are used such as the total power consumption associated with the network and the number of communication links in the network. The objective of the problem is to synthesize a communication network that maximizes connectivity subject to the cost of operation being within the specified budget for the resources. It is known that algebraic connectivity is a measure of robust connectivity and hence, it is chosen as an objective for optimization. We pose the network synthesis problem as a mixed-integer semidefinite program (MISDP): (1) provide an algorithm for computing optimal solutions using cutting plane methods; (2) develop lower bounds by posing the problem as a binaty semidefinite program; and (3) construct feasible solutions using heuristics and estimate their quality. The network synthesis problem is a nondeterministic polynomial-time (NP)-hard problem. We provide some computational results to corroborate the performance of the proposed algorithms. [ABSTRACT FROM AUTHOR]

We found an interesting relation between convex optimization and sorting problem. We present a parallel algorithm to compute multiple order statistics of the data by minimizing a number of related convex functions. The computed order statistics serve as splitters that group the data into buckets suitable for parallel bitonic sorting. This led us to a parallel bucket sort algorithm, which we implemented for many-core architecture of graphics processing units (GPUs). The proposed sorting method is competitive to the state-of-the-art GPU sorting algorithms and is superior to most of them for long sorting keys. [ABSTRACT FROM PUBLISHER]

Transmit beamforming is used to steer radiated power towards a receiver of interest and to limit interference to unintended receivers, thereby facilitating coexistence. Transmit beamforming requires accurate channel state information (CSI) at the transmitter, which is often difficult to acquire, particularly in cognitive underlay settings, where the primary receiver cannot be expected to cooperate with the secondary system to enable it to learn the secondary to primary crosstalk channel. This paper considers cases where it is not realistic to assume channel reciprocity, or that the receivers are capable of accurate CSI estimation and feedback—because they are legacy systems, or have limited computation/energy resources. Transmit beamforming from binary and infrequent CSI is first considered for an isolated link. An online beamforming and learning algorithm is developed using the analytic center cutting plane method and is shown to asymptotically attain optimal performance. A robust maximum-likelihood formulation is next developed to handle feedback errors and correlation drift. The setup is then generalized to a cognitive underlay setting, also exploiting the standard acknowledgement/negative-acknowledgement feedback on the reverse primary link. This is the first solution to jointly tackle secondary signal-to-noise ratio maximization and primary interference mitigation from only rudimentary CSI, without assuming channel reciprocity. [ABSTRACT FROM PUBLISHER]

This article considers the bilevel linear programming problem with interval coefficients in both objective functions. We propose a cutting plane method to solve such a problem. In order to obtain the best and worst optimal solutions, two types of cutting plane methods are developed based on the fact that the best and worst optimal solutions of this kind of problem occur at extreme points of its constraint region. The main idea of the proposed methods is to solve a sequence of linear programming problems with cutting planes that are successively introduced until the best and worst optimal solutions are found. Finally, we extend the two algorithms proposed to compute the best and worst optimal solutions of the general bilevel linear programming problem with interval coefficients in the objective functions as well as in the constraints. [ABSTRACT FROM AUTHOR]

In this paper, we present an algorithm to solve nonlinear semi-infinite programming (NSIP) problems. To deal with the nonlinear constraint, Floudas and Stein (SIAM J. Optim. 18:1187-1208, ) suggest an adaptive convexification relaxation to approximate the nonlinear constraint function. The αBB method, used widely in global optimization, is applied to construct the convexification relaxation. We then combine the idea of the cutting plane method with the convexification relaxation to propose a new algorithm to solve NSIP problems. With some given tolerances, our algorithm terminates in a finite number of iterations and obtains an approximate stationary point of the NSIP problems. In addition, some NSIP application examples are implemented by the method proposed in this paper, such as the proportional-integral-derivative controller design problem and the nonlinear finite impulse response filter design problem. Based on our numerical experience, we demonstrate that our algorithm enhances the computational speed for solving NSIP problems. [ABSTRACT FROM AUTHOR]

In this paper, we investigate the gate sizing problem and develop techniques for improving the runtime by effectively exploiting the graphics processing unit (GPU) resources. Theoretically, we investigate a randomized cutting plane-based convex optimization technique which is highly parallelizable and can effectively exploit the single instruction multiple data structure imposed by GPUs. In order to further improve the runtime, we also develop GPU-oriented implementation guidelines that exploit the specific structure that convex gate sizing formulations impose. We implemented our method on NVIDIA Tesla 10 GPU and obtain 21\times to 400\times speedup compared to the MOSEK optimization tool implemented on conventional CPU. The quality of solution of our method is very close to that achieved by MOSEK, since both are optimal. [ABSTRACT FROM PUBLISHER]

Abstract: We introduce an efficient method for training the linear ranking support vector machine. The method combines cutting plane optimization with red–black tree based approach to subgradient calculations, and has O(ms + mlog (m)) time complexity, where m is the number of training examples, and s the average number of non-zero features per example. Best previously known training algorithms achieve the same efficiency only for restricted special cases, whereas the proposed approach allows any real valued utility scores in the training data. Experiments demonstrate the superior scalability of the proposed approach, when compared to the fastest existing RankSVM implementations. [Copyright &y& Elsevier]