Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userKnot Locating in Piecewise Linear Approximation
113
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Many separable nonlinear optimization problems can be approximated by their nonlinear objective functions with piecewise linear functions. A natural question arising from applying this approach is how to break the interval of interest into subintervals (pieces) to achieve a good approximation. We present formulations to optimize the location of the knots. We apply a sequential quadratic programming method and a spectral projected gradient method to solve the problem. We report numerical experiments to show the effectiveness of the proposed approaches.
rate research
Read More
The load pick-up (LPP) problem searches the optimal configuration of the electrical distribution system (EDS), aiming to minimize the power loss or provide maximum power to the load ends. The piecewise linearization (PWL) approximation method can be used to tackle the nonlinearity and nonconvexity in network power flow (PF) constraints, and transform the LPP model into a mixed-integer linear programming model (LPP-MILP model).However, for the PWL approximation based PF constraints, big linear approximation errors will affect the accuracy and feasibility of the LPP-MILP models solving results. And the long modeling and solving time of the direct solution procedure of the LPP-MILP model may affect the applicability of the LPP optimization scheme. This paper proposes a multi-step PWL approximation based solution for the LPP problem in the EDS. In the proposed multi-step solution procedure, the variable upper bounds in the PWL approximation functions are dynamically renewed to reduce the approximation errors effectively. And the multi-step solution procedure can significantly decrease the modeling and solving time of the LPP-MILP model, which ensure the applicability of the LPP optimization scheme. For the two main application schemes for the LPP problem (i.e. network optimization reconfiguration and service restoration), the effectiveness of the proposed method is demonstrated via case studies using a real 13-bus EDS and a real 1066-bus EDS.
Motivated by a growing list of nontraditional statistical estimation problems of the piecewise kind, this paper provides a survey of known results supplemented with new results for the class of piecewise linear-quadratic programs. These are linearly constrained optimization problems with piecewise linear-quadratic (PLQ) objective functions. Starting from a study of the representation of such a function in terms of a family of elementary functions consisting of squared affine functions, squared plus-composite-affine functions, and affine functions themselves, we summarize some local properties of a PLQ function in terms of their first and second-order directional derivatives. We extend some well-known necessary and sufficient second-order conditions for local optimality of a quadratic program to a PLQ program and provide a dozen such equivalent conditions for strong, strict, and isolated local optimality, showing in particular that a PLQ program has the same characterizations for local minimality as a standard quadratic program. As a consequence of one such condition, we show that the number of strong, strict, or isolated local minima of a PLQ program is finite; this result supplements a recent result about the finite number of directional stationary objective values. Interestingly, these finiteness results can be uncovered by invoking a very powerful property of subanalytic functions; our proof is fairly elementary, however. We discuss applications of PLQ programs in some modern statistical estimation problems. These problems lead to a special class of unconstrained composite programs involving the non-differentiable $ell_1$-function, for which we show that the task of verifying the second-order stationary condition can be converted to the problem of checking the copositivity of certain Schur complement on the nonnegative orthant.
Most existing interpretable methods explain a black-box model in a post-hoc manner, which uses simpler models or data analysis techniques to interpret the predictions after the model is learned. However, they (a) may derive contradictory explanations on the same predictions given different methods and data samples, and (b) focus on using simpler models to provide higher descriptive accuracy at the sacrifice of prediction accuracy. To address these issues, we propose a hybrid interpretable model that combines a piecewise linear component and a nonlinear component. The first component describes the explicit feature contributions by piecewise linear approximation to increase the expressiveness of the model. The other component uses a multi-layer perceptron to capture feature interactions and implicit nonlinearity, and increase the prediction performance. Different from the post-hoc approaches, the interpretability is obtained once the model is learned in the form of feature shapes. We also provide a variant to explore higher-order interactions among features to demonstrate that the proposed model is flexible for adaptation. Experiments demonstrate that the proposed model can achieve good interpretability by describing feature shapes while maintaining state-of-the-art accuracy.
Piecewise Linear Approximation (PLA) is a well-established tool to reduce the size of the representation of time series by approximating the series by a sequence of line segments while keeping the error introduced by the approximation within some predetermined threshold. With the recent rise of edge computing, PLA algorithms find a complete new set of applications with the emphasis on reducing the volume of streamed data. In this study, we identify two scenarios set in a data-stream processing context: data reduction in sensor transmissions and datacenter storage. In connection to those scenarios, we identify several streaming metrics and propose streaming protocols as algorithmic implementations of several state of the art PLA techniques. In an experimental evaluation, we measure the quality of the reviewed methods and protocols and evaluate their performance against those streaming statistics. All known methods have deficiencies when it comes to handling streaming-like data, e.g. inflation of the input stream, high latency or poor average error. Our experimental results highlight the challenges raised when transferring those classical methods into the stream processing world and present alternative techniques to overcome them and balance the related trade-offs.
Several techniques were proposed to model the Piecewise linear (PWL) functions, including convex combination, incremental and multiple choice methods. Although the incremental method was proved to be very efficient, the attention of the authors in this field was drawn to the convex combination method, especially for discontinuous PWL functions. In this work, we modify the incremental method to make it suitable for discontinuous functions. The numerical results indicate that the modified incremental method could have considerable reduction in computational time, mainly due to the reduction in the number of the required variables. Further, we propose a tighter formulation for optimization problems over separable univariate PWL functions with binary indicators by using the incremental method.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
