Search

This paper considers the relaxed Peaceman-Rachford (PR) splitting method for finding an approximate solution of a monotone inclusion whose underlying operator consists of the sum of two maximal strongly monotone operators. Using general results obtained in the setting of a non-Euclidean hybrid proximal extragradient framework, we extend a previous convergence result on the iterates generated by the relaxed PR splitting method, as well as establish new pointwise and ergodic convergence rate results for the method whenever an associated relaxation parameter is within a certain interval. An example is also discussed to demonstrate that the iterates may not converge when the relaxation parameter is outside this interval. [ABSTRACT FROM AUTHOR]

This paper concerns exact linesearch quasi-Newton methods for minimizing a quadratic function whose Hessian is positive definite. We show that by interpreting the method of conjugate gradients as a particular exact linesearch quasi-Newton method, necessary and sufficient conditions can be given for an exact linesearch quasi-Newton method to generate a search direction which is parallel to that of the method of conjugate gradients. We also analyze update matrices and give a complete description of the rank-one update matrices that give search direction parallel to those of the method of conjugate gradients. In particular, we characterize the family of such symmetric rank-one update matrices that preserve positive definiteness of the quasi-Newton matrix. This is in contrast to the classical symmetric-rank-one update where there is no freedom in choosing the matrix, and positive definiteness cannot be preserved. The analysis is extended to search directions that are parallel to those of the preconditioned method of conjugate gradients in a straightforward manner. [ABSTRACT FROM AUTHOR]

In this paper we consider the problem of minimizing the product of two affine functions over a polyhedral set. An approximation algorithm is proposed and it is proved that it is a Fully Polynomial Time Approximation Scheme. We will also present and computationally investigate an exact version of the algorithm. [ABSTRACT FROM AUTHOR]

This paper concerns a method of selecting a subset of features for a logistic regression model. Information criteria, such as the Akaike information criterion and Bayesian information criterion, are employed as a goodness-of-fit measure. The purpose of our work is to establish a computational framework for selecting a subset of features with an optimality guarantee. For this purpose, we devise mixed integer optimization formulations for feature subset selection in logistic regression. Specifically, we pose the problem as a mixed integer linear optimization problem, which can be solved with standard mixed integer optimization software, by making a piecewise linear approximation of the logistic loss function. The computational results demonstrate that when the number of candidate features was less than 40, our method successfully provided a feature subset that was sufficiently close to an optimal one in a reasonable amount of time. Furthermore, even if there were more candidate features, our method often found a better subset of features than the stepwise methods did in terms of information criteria. [ABSTRACT FROM AUTHOR]

One main task in evolutionary multiobjective optimization (EMO) is to obtain a suitable finite size approximation of the Pareto front which is the image of the solution set, termed the Pareto set, of a given multiobjective optimization problem. In the technical literature, the characteristic of the desired approximation is commonly expressed by closeness to the Pareto front and a sufficient spread of the solutions obtained. In this paper, we first make an effort to show by theoretical and empirical findings that the recently proposed Averaged Hausdorff (or $$\Delta _p$$ -) indicator indeed aims at fulfilling both performance criteria for bi-objective optimization problems. In the second part of this paper, standard EMO algorithms combined with a specialized archiver and a postprocessing step based on the $$\Delta _p$$ indicator are introduced which sufficiently approximate the $$\Delta _p$$ -optimal archives and generate solutions evenly spread along the Pareto front. [ABSTRACT FROM AUTHOR]

This paper proposes an algorithm for the unconstrained minimization of a class of nonsmooth and nonconvex functions that can be written as finite-max functions. A gradient and function-based sampling method is proposed which, under special circumstances, either moves superlinearly to a minimizer of the problem of interest or improves the optimality certificate. Global and local convergence analysis are presented, as well as examples that illustrate the obtained theoretical results. [ABSTRACT FROM AUTHOR]

The projected Levenberg-Marquardt method for the solution of a system of equations with convex constraints is known to converge locally quadratically to a possibly nonisolated solution if a certain error bound condition holds. This condition turns out to be quite strong since it implies that the solution sets of the constrained and of the unconstrained system are locally the same. Under a pair of more reasonable error bound conditions this paper proves R-linear convergence of a Levenberg-Marquardt method with approximate projections. In this way, computationally expensive projections can be avoided. The new method is also applicable if there are nonsmooth constraints having subgradients. Moreover, the projected Levenberg-Marquardt method is a special case of the new method and shares its R-linear convergence. [ABSTRACT FROM AUTHOR]

In this paper, a novel technique for tight outer-approximation of the intersection region of a finite number of ellipses in 2-dimensional space is proposed. First, the vertices of a tight polygon that contains the convex intersection of the ellipses are found in an efficient manner. To do so, the intersection points of the ellipses that fall on the boundary of the intersection region are determined, and a set of points is generated on the elliptic arcs connecting every two neighbouring intersection points. By finding the tangent lines to the ellipses at the extended set of points, a set of half-planes is obtained, whose intersection forms a polygon. To find the polygon more efficiently, the points are given an order and the intersection of the half-planes corresponding to every two neighbouring points is calculated. If the polygon is convex and bounded, these calculated points together with the initially obtained intersection points will form its vertices. If the polygon is non-convex or unbounded, we can detect this situation and then generate additional discrete points only on the elliptical arc segment causing the issue, and restart the algorithm to obtain a bounded and convex polygon. Finally, the smallest area ellipse that contains the vertices of the polygon is obtained by solving a convex optimization problem. Through numerical experiments, it is illustrated that the proposed technique returns a tighter outer-approximation of the intersection of multiple ellipses, compared to conventional techniques, with only slightly higher computational cost. [ABSTRACT FROM AUTHOR]

In this paper we present a new iterative projection method for finding the closest point in the intersection of convex sets to any arbitrary point in a Hilbert space. This method, termed AAMR for averaged alternating modified reflections, can be viewed as an adequate modification of the Douglas-Rachford method that yields a solution to the best approximation problem. Under a constraint qualification at the point of interest, we show strong convergence of the method. In fact, the so-called strong CHIP fully characterizes the convergence of the AAMR method for every point in the space. We report some promising numerical experiments where we compare the performance of AAMR against other projection methods for finding the closest point in the intersection of pairs of finite dimensional subspaces. [ABSTRACT FROM AUTHOR]

This paper develops a Bregman operator splitting algorithm with variable stepsize (BOSVS) for solving problems of the form $\min\{\phi(Bu) +1/2\|Au-f\|_{2}^{2}\}$, where ϕ may be nonsmooth. The original Bregman Operator Splitting (BOS) algorithm employed a fixed stepsize, while BOSVS uses a line search to achieve better efficiency. These schemes are applicable to total variation (TV)-based image reconstruction. The stepsize rule starts with a Barzilai-Borwein (BB) step, and increases the nominal step until a termination condition is satisfied. The stepsize rule is related to the scheme used in SpaRSA (Sparse Reconstruction by Separable Approximation). Global convergence of the proposed BOSVS algorithm to a solution of the optimization problem is established. BOSVS is compared with other operator splitting schemes using partially parallel magnetic resonance image reconstruction problems. The experimental results indicate that the proposed BOSVS algorithm is more efficient than the BOS algorithm and another split Bregman Barzilai-Borwein algorithm known as SBB. [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]

This paper is concerned with solving single CVaR and mixed CVaR minimization problems. A CHKS-type smoothing sample average approximation (SAA) method is proposed for solving these two problems, which retains the convexity and smoothness of the original problem and is easy to implement. For any fixed smoothing constant ε, this method produces a sequence whose cluster points are weak stationary points of the CVaR optimization problems with probability one. This framework of combining smoothing technique and SAA scheme can be extended to other smoothing functions as well. Practical numerical examples arising from logistics management are presented to show the usefulness of this method. [ABSTRACT FROM AUTHOR]

In this paper, a new hybrid method is proposed for solving nonlinear complementarity problems (NCP) with P function. In the new method, we combine a smoothing nonmonotone trust region method based on a conic model and line search techniques. We reformulate the NCP as a system of semismooth equations using the Fischer-Burmeister function. Using Kanzow's smooth approximation function to construct the smooth operator, we propose a smoothing nonmonotone trust region algorithm of a conic model for solving the NCP with P functions. This is different from the classical trust region methods, in that when a trial step is not accepted, the method does not resolve the trust region subproblem but generates an iterative point whose steplength is defined by a line search. We prove that every accumulation point of the sequence generated by the algorithm is a solution of the NCP. Under a nonsingularity condition, the superlinear convergence of the algorithm is established without a strict complementarity condition. [ABSTRACT FROM AUTHOR]

In this paper, we consider an extend-valued nonsmooth multiobjective optimization problem of finding weak Pareto optimal solutions. We propose a class of vector-valued generalized viscosity approximation method for solving the problem. Under some conditions, we prove that any sequence generated by this method converges to a weak Pareto optimal solution of the multiobjective optimization problem. [ABSTRACT FROM AUTHOR]

The Krasnoselskii-Mann iteration plays an important role in the approximation of fixed points of nonexpansive operators; it is known to be weakly convergent in the infinite dimensional setting. In this present paper, we provide a new inexact Krasnoselskii-Mann iteration and prove weak convergence under certain accuracy criteria on the error resulting from the inexactness. We also show strong convergence for a modified inexact Krasnoselskii-Mann iteration under suitable assumptions. The convergence results generalize existing ones from the literature. Applications are given to the Douglas-Rachford splitting method, the Fermat-Weber location problem as well as the alternating projection method by John von Neumann. [ABSTRACT FROM AUTHOR]

The affine rank minimization problem is to minimize the rank of a matrix under linear constraints. It has many applications in various areas such as statistics, control, system identification and machine learning. Unlike the literatures which use the nuclear norm or the general Schatten $$q~ (0

This paper proposes a conic approximation algorithm for solving quadratic optimization problems with linear complementarity constraints.We provide a conic reformulation and its dual for the original problem such that these three problems share the same optimal objective value. Moreover, we show that the conic reformulation problem is attainable when the original problem has a nonempty and bounded feasible domain. Since the conic reformulation is in general a hard problem, some conic relaxations are further considered. We offer a condition under which both the semidefinite relaxation and its dual problem become strictly feasible for finding a lower bound in polynomial time. For more general cases, by adaptively refining the outer approximation of the feasible set, we propose a conic approximation algorithm to identify an optimal solution or an $$\epsilon $$ -optimal solution of the original problem. A convergence proof is given under simple assumptions. Some computational results are included to illustrate the effectiveness of the proposed algorithm. [ABSTRACT FROM AUTHOR]

In this paper we study a class of derivative-free unconstrained minimization algorithms employing nonmonotone inexact linesearch techniques along a set of suitable search directions. In particular, we define globally convergent nonmonotone versions of some well-known derivative-free methods and we propose a new linesearch-based nonmonotone algorithm, where search directions are constructed by combining coordinate rotations with simplex gradients. Through extensive numerical experimentation, we show that the proposed algorithm is highly competitive in comparison with some of the most efficient direct search methods and model based methods on a large set of test problems. [ABSTRACT FROM AUTHOR]

In this paper, we study a semi-infinite programming (SIP) problem with a convex set constraint. Using the value function of the lower level problem, we reformulate SIP problem as a nonsmooth optimization problem. Using the theory of nonsmooth Lagrange multiplier rules and Danskin's theorem, we present constraint qualifications and necessary optimality conditions. We propose a new numerical method for solving the problem. The novelty of our numerical method is to use the integral entropy function to approximate the value function and then solve SIP by the smoothing projected gradient method. Moreover we study the relationships between the approximating problems and the original SIP problem. We derive error bounds between the integral entropy function and the value function, and between locally optimal solutions of the smoothing problem and those for the original problem. Using certain second order sufficient conditions, we derive some estimates for locally optimal solutions of problem. Numerical experiments show that the algorithm is efficient for solving SIP. [ABSTRACT FROM AUTHOR]

In this paper we consider cardinality-constrained convex programs that minimize a convex function subject to a cardinality constraint and other linear constraints. This class of problems has found many applications, including portfolio selection, subset selection and compressed sensing. We propose a successive convex approximation method for this class of problems in which the cardinality function is first approximated by a piecewise linear DC function (difference of two convex functions) and a sequence of convex subproblems is then constructed by successively linearizing the concave terms of the DC function. Under some mild assumptions, we establish that any accumulation point of the sequence generated by the method is a KKT point of the DC approximation problem. We show that the basic algorithm can be refined by adding strengthening cuts in the subproblems. Finally, we report some preliminary computational results on cardinality-constrained portfolio selection problems. [ABSTRACT FROM AUTHOR]

The problem of finding the best rank-one approximation to higher-order tensors has extensive engineering and statistical applications. It is well-known that this problem is equivalent to a homogeneous polynomial optimization problem. In this paper, we study theoretical results and numerical methods of this problem, particularly focusing on the 4-th order symmetric tensor case. First, we reformulate the polynomial optimization problem to a matrix programming, and show the equivalence between these two problems. Then, we prove that there is no duality gap between the reformulation and its Lagrangian dual problem. Concerning the approaches to deal with the problem, we propose two relaxed models. The first one is a convex quadratic matrix optimization problem regularized by the nuclear norm, while the second one is a quadratic matrix programming regularized by a truncated nuclear norm, which is a D.C. function and therefore is nonconvex. To overcome the difficulty of solving this nonconvex problem, we approximate the nonconvex penalty by a convex term. We propose to use the proximal augmented Lagrangian method to solve these two relaxed models. In order to obtain a global solution, we propose an alternating least eigenvalue method after solving the relaxed models and prove its convergence. Numerical results presented in the last demonstrate, especially for nonpositive tensors, the effectiveness and efficiency of our proposed methods. [ABSTRACT FROM AUTHOR]

This paper presents a Nash equilibrium model where the underlying objective functions involve uncertainty and nonsmoothness. The well-known sample average approximation method is applied to solve the problem and the first order equilibrium conditions are characterized in terms of Clarke generalized gradients. Under some moderate conditions, it is shown that with probability one, a statistical estimator (a Nash equilibrium or a Nash-C-stationary point) obtained from sample average approximate equilibrium problem converges to its true counterpart. Moreover, under some calmness conditions of the Clarke generalized derivatives, it is shown that with probability approaching one exponentially fast by increasing sample size, the Nash-C-stationary point converges to a weak Nash-C-stationary point of the true problem. Finally, the model is applied to stochastic Nash equilibrium problem in the wholesale electricity market. [ABSTRACT FROM AUTHOR]

In this paper we investigate the relationship between the nearest point problem in a polyhedral cone and the nearest point problem in a polyhedral set, and use this relationship to devise an effective method for solving the latter using an existing algorithm for the former. We then show that this approach can be employed to minimize any strictly convex quadratic function over a polyhedral set. Through a computational experiment we evaluate the effectiveness of this approach and show that for a collection of randomly generated instances this approach is more effective than other existing methods for solving these problems. [ABSTRACT FROM AUTHOR]

Deterministic sample average approximations of stochastic programming problems with recourse are suitable for a scenario-based parallelization. In this paper the parallelization is obtained by using an interior-point method and a Schur complement mechanism for the interior-point linear systems. However, the direct linear solves involving the dense Schur complement matrix are expensive, and adversely affect the scalability of this approach. We address this issue by proposing a stochastic preconditioner for the Schur complement matrix and by using Krylov iterative methods for the solution of the dense linear systems. The stochastic preconditioner is built based on a subset of existing scenarios and can be assembled and factorized on a separate process before the computation of the Schur complement matrix finishes on the remaining processes. The expensive factorization of the Schur complement is removed from the parallel execution flow and the scaling of the optimization solver is considerably improved with this approach. The spectral analysis indicates an exponentially fast convergence in probability to 1 of the eigenvalues of the preconditioned matrix with the number of scenarios incorporated in the preconditioner. Numerical experiments performed on the relaxation of a unit commitment problem show good performance, in terms of both the accuracy of the solution and the execution time. [ABSTRACT FROM AUTHOR]

Large scale stochastic linear programs are typically solved using a combination of mathematical programming techniques and sample-based approximations. Some methods are designed to permit sample sizes to adapt to information obtained during the solution process, while others are not. In this paper, we experimentally examine the relative merits and challenges of approximations based on adaptive samples and those based on non-adaptive samples. We focus our attention on Stochastic Decomposition (SD) as an adaptive technique and Sample Average Approximation (SAA) as a non-adaptive technique. Our results indicate that there can be minimal difference in the quality of the solutions provided by these methods, although comparing their computational requirements would be more challenging. [ABSTRACT FROM AUTHOR]

The bidomain equations, a continuum approximation of cardiac tissue based on the idea of a functional syncytium, are widely accepted as one of the most complete descriptions of cardiac bioelectric activity at the tissue and organ level. Numerous studies employed bidomain simulations to investigate the formation of cardiac arrhythmias and their therapeutical treatment. They consist of a linear elliptic partial differential equation and a non-linear parabolic partial differential equation of reaction-diffusion type, where the reaction term is described by a set of ordinary differential equations. The monodomain equations, although not explicitly accounting for current flow in the extracellular domain and its feedback onto the electrical activity inside the tissue, are popular since they approximate, under many circumstances of practical interest, the bidomain equations quite well at a much lower computational expense, owing to the fact that the elliptic equation can be eliminated when assuming that conductivity tensors of intracellular and extracellular space are related to each other. Optimal control problems suggest themselves quite naturally for this important class of modelling problems and the present paper is a first attempt in this direction. Specifically, we present an optimal control formulation for the monodomain equations with an extra-cellular current, I, as the control variable. I must be determined such that electrical activity in the tissue is damped in an optimal manner. The derivation of the optimality system is given and a method for its numerical realization is proposed. The solution of the optimization problem is based on a non-linear conjugate gradient (NCG) method. The main goals of this work are to demonstrate that optimal control techniques can be employed successfully to this class of highly nonlinear models and that the influence of I judiciously applied can in fact serve as a successful control for the dampening of propagating wavefronts. [ABSTRACT FROM AUTHOR]

Problems with significant input-data uncertainty are very common in practical situations. One approach to dealing with this uncertainty is called scenario planning, where the data uncertainty is represented with scenarios. A scenario represents a potential realization of the important parameters of the problem. In this paper we present a new approach to coping with data uncertainty, called the flexibility approach. Here a problem is described as a set of interconnected simple scenarios. The idea is to find a solution for each scenario such that, after a change in scenario, transforming from one solution to the other one is not expensive. We define two versions of flexibility and hence two versions of the problem, which are called the sum-flexible-attribute problem and the max-flexible-attribute problem. For both problems we prove the $\ensuremath{\mathcal{NP}}$ -hardness as well as the non-approximability. We present polynomial time algorithms for solving the two problems to optimality on trees. Finally, we discuss the possible applications and generalizations of the new approach. [ABSTRACT FROM AUTHOR]

In this paper, we address an approximate solution of a probabilistically constrained convex program (PCCP), where a convex objective function is minimized over solutions satisfying, with a given probability, convex constraints that are parameterized by random variables. In order to approach to a solution, we set forth a conservative approximation problem by introducing a parameter α which indicates an approximate accuracy, and formulate it as a D.C. optimization problem. As an example of the PCCP, the Value-at-Risk (VaR) minimization is considered under the assumption that the support of the probability of the associated random loss is given by a finitely large number of scenarios. It is advantageous in solving the D.C. optimization that the numbers of variables and constraints are independent of the number of scenarios, and a simplicial branch-and-bound algorithm is posed to find a solution of the D.C. optimization. Numerical experiments demonstrate the following: (i) by adjusting a parameter α, the proposed problem can achieve a smaller VaR than the other convex approximation approaches; (ii) when the number of scenarios is large, a typical 0-1 mixed integer formulation for the VaR minimization cannot be solved in a reasonable time and the improvement of the incumbent values is slow, whereas the proposed method can achieve a good solution at an early stage of the algorithm. [ABSTRACT FROM AUTHOR]

It is well-known that a greedy approximation with an integer-valued polymatroid potential function f is H( γ)-approximation of the minimum submodular cover problem with linear cost where γ is the maximum value of f over all singletons and H( γ) is the γ-th harmonic number. In this paper, we establish similar results for the minimum submodular cover problem with a submodular cost (possibly nonlinear) and/or fractional submodular potential function f. [ABSTRACT FROM AUTHOR]

In this paper several parameter dependent scalarization approaches for solving nonlinear multi-objective optimization problems are discussed. It is shown that they can be considered as special cases of a scalarization problem by Pascoletti and Serafini (or a modification of this problem). Based on these connections theoretical results as well as a new algorithm for adaptively controlling the choice of the parameters for generating almost equidistant approximations of the efficient set, lately developed for the Pascoletti-Serafini scalarization, can be applied to these problems. For instance for such well-known scalarizations as the ε-constraint or the normal boundary intersection problem algorithms for adaptively generating high quality approximations are derived. [ABSTRACT FROM AUTHOR]

A state-constrained optimal control problem with nonlocal radiation interface conditions arising from the modeling of crystal growth processes is considered. The problem is approximated by a Moreau-Yosida type regularization. Optimality conditions for the regularized problem are derived and the convergence of the regularized problems is shown. In the last part of the paper, some numerical results are presented. [ABSTRACT FROM AUTHOR]

In this paper, we propose approximate and exact algorithms for the double constrained two-dimensional guillotine cutting stock problem (DCTDC). The approximate algorithm is a two-stage procedure. The first stage attempts to produce a starting feasible solution to DCTDC by solving a single constrained two dimensional cutting problem, CDTC. If the solution to CTDC is not feasible to DCTDC, the second stage is used to eliminate non-feasibility. The exact algorithm is a branch-and-bound that uses efficient lower and upper bounding schemes. It starts with a lower bound reached by the approximate two-stage algorithm. At each internal node of the branching tree, a tailored upper bound is obtained by solving (relaxed) knapsack problems. To speed up the branch and bound, we implement, in addition to ordered data structures of lists, symmetry, duplicate, and non-feasibility detection strategies which fathom some unnecessary branches. We evaluate the performance of the algorithm on different problem instances which can become benchmark problems for the cutting and packing literature. [ABSTRACT FROM AUTHOR]

It is well-known that the conjugate gradient method is widely used for solving large scale optimization problems. In this paper a modified trust-region method with Beale's Preconditioned Conjugate Gradient (BPCG) technique is developed for solving unconstrained optimization problems. The modified version adopts an adaptive rule and retains some useful information when an unsuccessful iteration occurs, and therefore improves the efficiency of the method. The behavior and the convergence properties are discussed. Some numerical experiments are reported. [ABSTRACT FROM AUTHOR]

This paper is concerned with the numerical solution of a Karush-Kuhn-Tucker system. Such symmetric indefinite system arises when we solve a nonlinear programming problem by an Interior-Point (IP) approach. In this framework, we discuss the effectiveness of two inner iterative solvers: the method of multipliers and the preconditioned conjugate gradient method. We discuss the implementation details of these algorithms in an IP scheme and we report the results of a numerical comparison on a set of large scale test-problems arising from the discretization of elliptic control problems. [ABSTRACT FROM AUTHOR]

A mathematical model of portfolio optimization is usually quantified with mean-risk models offering a lucid form of two criteria with possible trade-off analysis. In the classical Markowitz model the risk is measured by a variance, thus resulting in a quadratic programming model. Following Sharpe's work on linear approximation to the mean-variance model, many attempts have been made to linearize the portfolio optimization problem. There were introduced several alternative risk measures which are computationally attractive as (for discrete random variables) they result in solving linear programming (LP) problems. Typical LP computable risk measures, like the mean absolute deviation (MAD) or the Gini's mean absolute difference (GMD) are symmetric with respect to the below-mean and over-mean performances. The paper shows how the measures can he further combined to extend their modeling capabilities with respect to enhancement of the below-mean downside risk aversion. The relations of the below-mean downside stochastic dominance are formally introduced and the corresponding techniques to enhance risk measures ale derived. The resulting mean-risk models generate efficient solutions with respect to second degree stochastic dominance, while at the same time preserving simplicity and LP computability of the original models. The models are tested on real-life historical data. [ABSTRACT FROM AUTHOR]

In this part of the two-part series of papers, algorithms for solving some variable programming (VP) problems proposed in Part I are investigated. It is demonstrated that the non-differentiability and the discontinuity of the maximum objective function, as well as the summation objective function in the VP problems constitute difficulty in finding their solutions, Based on the principle of statistical mechanics, we derive smooth functions to approximate these non-smooth objective functions with specific activated feasible sets. By transforming the minimax problem and the corresponding variable programming problems into their smooth versions we can solve the resulting problems by some efficient algorithms for smooth functions. Relevant theoretical underpinnings about the smoothing techniques are established. The algorithms, in which the minimization of the smooth functions is carried out by the standard quasi-Newton method with BFGS formula, are tested on some standard minimax and variable programming problems. The numerical results show that the smoothing techniques yield accurate optimal solutions and that the algorithms proposed are feasible and efficient. [ABSTRACT FROM AUTHOR]

In this two-part series of papers, a new generalized minimax optimization model, termed variable programming (VP), is developed to solve dynamically a class of multi-objective optimization problems with non-decomposable structure. It is demonstrated that such type of problems is more general than existing optimization models. In this part, the VP model is proposed first, and the relationship between variable programming and the general constrained nonlinear programming is established. To illustrate its practicality, problems on investment and the low-side-lobe conformal antenna array pattern synthesis to which VP can be appropriately applied are discussed for substantiation. Then, theoretical underpinnings of the VP problems are established. Difficulties in dealing with the VP problems are discussed. With some mild assumptions, the necessary conditions for the unconstrained VP problems with arbitrary and specific activated feasible sets are derived respectively. The necessary conditions for the corresponding constrained VP problems with the mild hypotheses are also examined. Whilst discussion in this part is concentrated on the formulation of the VP model and its theoretical underpinnings, construction of solution algorithms is discussed in Part II. [ABSTRACT FROM AUTHOR]

In this paper, we first consider a network improvement problem, called vertex-to-vertices distance reduction problem. The problem is how to use a minimum cost to reduce lengths of the edges in a network so that the distances from a given vertex to all other vertices are within a given upper bound. We use l, l and l norms to measure the total modification cost respectively. Under l norm, we present a strongly polynomial algorithm to solve the problem, and under l or weighted l norm, we show that achieving an approximation ratio O(log(| V|)) is NP-hard. We also extend the results to the vertex-to-points distance reduction problem, which is to reduce the lengths of edges most economically so that the distances from a given vertex to all points on the edges of the network are within a given upper bound. [ABSTRACT FROM AUTHOR]

Usually, local search methods are considered to be slow. In our paper, we present a simulated annealing-based local search algorithm for the approximation of Boolean functions with a proven time complexity that behaves relatively fast on randomly generated functions. The functions are represented by disjunctive normal forms (DNFs). Given a set of m uniformly distributed positive and negative examples of length n generated by a target function F( x,..., x), where the DNF consists of conjunctions with at most ℓ literals only, the algorithm computes with high probability a hypothesis H of length m · ℓ such that the error is zero on all examples. Our algorithm can be implemented easily and we obtained a relatively high percentage of correct classifications on test examples that were not presented in the learning phase. For example, for randomly generated F with n = 64 variables and a training set of m = 16384 examples, the error on the same number of test examples was about 19% on positive and 29% on negative examples, respectively. The proven complexity bound provides the basis for further studies on the average case complexity. [ABSTRACT FROM AUTHOR]

In this paper we propose new globalization strategies for the Barzilai and Borwein gradient method, based on suitable relaxations of the monotonicity requirements. In particular, we define a class of algorithms that combine nonmonotone watchdog techniques with nonmonotone linesearch rules and we prove the global convergence of these schemes. Then we perform an extensive computational study, which shows the effectiveness of the proposed approach in the solution of large dimensional unconstrained optimization problems. [ABSTRACT FROM AUTHOR]

The properties of multilevel optimization problems defined on a hierarchy of discretization grids can be used to define approximate secant equations, which describe the second-order behavior of the objective function. Following earlier work by Gratton and Toint (2009) we introduce a quasi-Newton method (with a linesearch) and a nonlinear conjugate gradient method that both take advantage of this new second-order information. We then present numerical experiments with these methods and formulate recommendations for their practical use. [ABSTRACT FROM AUTHOR]

We consider the approximation of nonlinear bilevel mathematical programs by solvable programs of the same type, i.e., bilevel programs involving linear approximations of the upper-level objective and all constraint- defining functions, as well as a quadratic approximation of the lower-level objective. We describe the main features of the algorithm and the resulting software. Numerical experiments tend to confirm the promising behavior of the method. [ABSTRACT FROM AUTHOR]

Given two disjoint convex polyhedra, we look for a best approximation pair relative to them, i.e., a pair of points, one in each polyhedron, attaining the minimum distance between the sets. Cheney and Goldstein showed that alternating projections onto the two sets, starting from an arbitrary point, generate a sequence whose two interlaced subsequences converge to a best approximation pair. We propose a process based on projections onto the half-spaces defining the two polyhedra, which are more negotiable than projections on the polyhedra themselves. A central component in the proposed process is the Halpern-Lions-Wittmann-Bauschke algorithm for approaching the projection of a given point onto a convex set. [ABSTRACT FROM AUTHOR]

We present a novel randomized block coordinate descent method for the minimization of a convex composite objective function. The method uses (approximate) partial second-order (curvature) information, so that the algorithm performance is more robust when applied to highly nonseparable or ill conditioned problems. We call the method Flexible Coordinate Descent (FCD). At each iteration of FCD, a block of coordinates is sampled randomly, a quadratic model is formed about that block and the model is minimized approximately/inexactly to determine the search direction. An inexpensive line search is then employed to ensure a monotonic decrease in the objective function and acceptance of large step sizes. We present several high probability iteration complexity results to show that convergence of FCD is guaranteed theoretically. Finally, we present numerical results on large-scale problems to demonstrate the practical performance of the method. [ABSTRACT FROM AUTHOR]

Increasing penetration levels of renewables have transformed how power systems are operated. High levels of uncertainty in production make it increasingly difficulty to guarantee operational feasibility; instead, constraints may only be satisfied with high probability. We present a chance-constrained economic dispatch model that efficiently integrates energy storage and high renewable penetration to satisfy renewable portfolio requirements. Specifically, we require that wind energy contribute at least a prespecified proportion of the total demand and that the scheduled wind energy is deliverable with high probability. We develop an approximate partial sample average approximation (PSAA) framework to enable efficient solution of large-scale chance-constrained economic dispatch problems. Computational experiments on the IEEE-24 bus system show that the proposed PSAA approach is more accurate, closer to the prescribed satisfaction tolerance, and approximately 100 times faster than standard sample average approximation. Finally, the improved efficiency of our PSAA approach enables solution of a larger WECC-240 test system in minutes. [ABSTRACT FROM AUTHOR]

In the recent years, there has been an intensive research of absolute value equations $$Ax-b=B|x|$$ . Various methods were developed, but less attention has been paid to approximating or bounding the solutions. We start filling this gap by proposing several outer approximations of the solution set. We present conditions for unsolvability and for existence of exponentially many solutions, too, and compare them with the known conditions. Eventually, we carried out numerical experiments to compare the methods with respect to computational time and quality of estimation. This helps in identifying the cases, in which the bounds are tight enough to determine the signs of the solution, and therefore also the solution itself. [ABSTRACT FROM AUTHOR]

We investigate projected scaled gradient (PSG) methods for convex minimization problems. These methods perform a descent step along a diagonally scaled gradient direction followed by a feasibility regaining step via orthogonal projection onto the constraint set. This constitutes a generalized algorithmic structure that encompasses as special cases the gradient projection method, the projected Newton method, the projected Landweber-type methods and the generalized expectation-maximization (EM)-type methods. We prove the convergence of the PSG methods in the presence of bounded perturbations. This resilience to bounded perturbations is relevant to the ability to apply the recently developed superiorization methodology to PSG methods, in particular to the EM algorithm. [ABSTRACT FROM AUTHOR]

For an optimization problem with general equality and inequality constraints, we propose an algorithm which uses subproblems of the stabilized SQP (sSQP) type for approximately solving subproblems of the augmented Lagrangian method. The motivation is to take advantage of the well-known robust behavior of the augmented Lagrangian algorithm, including on problems with degenerate constraints, and at the same time try to reduce the overall algorithm locally to sSQP (which gives fast local convergence rate under weak assumptions). Specifically, the algorithm first verifies whether the primal-dual sSQP step (with unit stepsize) makes good progress towards decreasing the violation of optimality conditions for the original problem, and if so, makes this step. Otherwise, the primal part of the sSQP direction is used for linesearch that decreases the augmented Lagrangian, keeping the multiplier estimate fixed for the time being. The overall algorithm has reasonable global convergence guarantees, and inherits strong local convergence rate properties of sSQP under the same weak assumptions. Numerical results on degenerate problems and comparisons with some alternatives are reported. [ABSTRACT FROM AUTHOR]

Solving power flow problems is essential for the reliable and efficient operation of an electric power network. However, current software for solving these problems have questionable robustness due to the limitations of the solution methods used. These methods are typically based on the Newton-Raphson method combined with switching heuristics for handling generator reactive power limits and voltage regulation. Among the limitations are the requirement of a good initial solution estimate, the inability to handle near rank-deficient Jacobian matrices, and the convergence issues that may arise due to conflicts between the switching heuristics and the Newton-Raphson process. These limitations are addressed by reformulating the power flow problem and using robust optimization techniques. In particular, the problem is formulated as a constrained optimization problem in which the objective function incorporates prior knowledge about power flow solutions, and solved using an augmented Lagrangian algorithm. The prior information included in the objective adds convexity to the problem, guiding iterates towards physically meaningful solutions, and helps the algorithm handle near rank-deficient Jacobian matrices as well as poor initial solution estimates. To eliminate the negative effects of using switching heuristics, generator reactive power limits and voltage regulation are modeled with complementarity constraints, and these are handled using smooth approximations of the Fischer-Burmeister function. Furthermore, when no solution exists, the new method is able to provide sensitivity information that aids an operator on how best to alter the system. The proposed method has been extensively tested on real power flow networks of up to 58k buses. [ABSTRACT FROM AUTHOR]