Explore the vast range of titles available.

Following the breakthrough work of Tardos (Oper Res 34:250–256, 1986) in the bit-complexity model, Vavasis and Ye (Math Program 74(1):79–120, 1996) gave the first exact algorithm for linear programming in the real model of computation with running time depending only on the constraint matrix. For solving a linear program (LP) max c ⊤ x , A x = b , x ≥ 0 , A ∈ R m × n , Vavasis and Ye developed a primal-dual interior point method using a ‘layered least squares’ (LLS) step, and showed that O ( n 3.5 log ( χ ¯ A + n ) ) iterations suffice to solve (LP) exactly, where χ ¯ A is a condition measure controlling the size of solutions to linear systems related to A . Monteiro and Tsuchiya (SIAM J Optim 13(4):1054–1079, 2003), noting that the central path is invariant under rescalings of the columns of A and c , asked whether there exists an LP algorithm depending instead on the measure χ ¯ A ∗ , defined as the minimum χ ¯ AD value achievable by a column rescaling AD of A , and gave strong evidence that this should be the case. We resolve this open question affirmatively. Our first main contribution is an O ( m 2 n 2 + n 3 ) time algorithm which works on the linear matroid of A to compute a nearly optimal diagonal rescaling D satisfying χ ¯ AD ≤ n ( χ ¯ A ∗ ) 3 . This algorithm also allows us to approximate the value of χ ¯ A up to a factor n ( χ ¯ A ∗ ) 2 . This result is in surprising contrast to that of Tunçel (Math Program 86(1):219–223, 1999), who showed NP-hardness for approximating χ ¯ A to within 2 poly ( rank ( A ) ) . The key insight for our algorithm is to work with ratios g i / g j of circuits of A —i.e., minimal linear dependencies A g = 0 —which allow us to approximate the value of χ ¯ A ∗ by a maximum geometric mean cycle computation in what we call the ‘circuit ratio digraph’ of A . While this resolves Monteiro and Tsuchiya’s question by appropriate preprocessing, it falls short of providing either a truly scaling invariant algorithm or an improvement upon the base LLS analysis. In this vein, as our second main contribution we develop a scaling invariant LLS algorithm, which uses and dynamically maintains improving estimates of the circuit ratio digraph, together with a refined potential function based analysis for LLS algorithms in general. With this analysis, we derive an improved O ( n 2.5 log ( n ) log ( χ ¯ A ∗ + n ) ) iteration bound for optimally solving (LP) using our algorithm. The same argument also yields a factor n / log n improvement on the iteration complexity bound of the original Vavasis–Ye algorithm.

We present a Markov chain, \"Dikin walk,\" for sampling from a convex body equipped with a self-concordant barrier. This Markov chain corresponds to a natural random walk with respect to a Riemannian metric defined using the Hessian of the barrier function. For every convex set of dimension n, there exists a self-concordant barrier whose self-concordance parameter is O(n). Consequently, a rapidly mixing Markov chain of the kind we describe can be defined (but not always be efficiently implemented) on any convex set. We use these results to design an algorithm consisting of a single random walk for optimizing a linear function on a convex set. Using results of Barthe [Geom. Fund. Anal. 12 (2002) 32-55] and Bobkov and Houdré [Ann. Probab. 25 (1997) 184-205], on the isoperimetry of products of weighted Riemannian manifolds, we obtain sharper upper bounds on the mixing time of a Dikin walk on products of convex sets than the bounds obtained from a direct application of the localization lemma. The results in this paper generalize previous results of Kannan and Narayanan [In STOC'09—Proceedings of the 2009 ACM International Symposium on Theory of Computing (2009) 561-570 ACM] from poly topes to spectrahedra and beyond, and improve upon those results in a special case when the convex set is a direct product of lower-dimensional convex sets. This Markov chain like the chain described in [In STOC'09—Proceedings of the 2009 ACM International Symposium on Theory of Computing (2009) 561-570 ACM] is affine-invariant.

In this paper we generalize the Interior Point-Proximal Method of Multipliers (IP-PMM) presented in Pougkakiotis and Gondzio (Comput Optim Appl 78:307–351, 2021. https://doi.org/10.1007/s10589-020-00240-9) for the solution of linear positive Semi-Definite Programming (SDP) problems, allowing inexactness in the solution of the associated Newton systems. In particular, we combine an infeasible Interior Point Method (IPM) with the Proximal Method of Multipliers (PMM) and interpret the algorithm (IP-PMM) as a primal-dual regularized IPM, suitable for solving SDP problems. We apply some iterations of an IPM to each sub-problem of the PMM until a satisfactory solution is found. We then update the PMM parameters, form a new IPM neighbourhood, and repeat this process. Given this framework, we prove polynomial complexity of the algorithm, under mild assumptions, and without requiring exact computations for the Newton directions. We furthermore provide a necessary condition for lack of strong duality, which can be used as a basis for constructing detection mechanisms for identifying pathological cases within IP-PMM.

We propose an efficient primal-dual interior-point relaxation algorithm based on a smoothing barrier augmented Lagrangian, called IPRSDP, for solving semidefinite programming problems in this paper. The IPRSDP algorithm has three advantages over classical interior-point methods. Firstly, IPRSDP does not require the iterative points to be positive definite. Consequently, it can easily be combined with the warm-start technique used for solving many combinatorial optimization problems, which require the solutions of a series of semidefinite programming problems. Secondly, the search direction of IPRSDP is symmetric in itself, and hence the symmetrization procedure is not required any more. Thirdly, with the introduction of the smoothing barrier augmented Lagrangian function, IPRSDP can provide the explicit form of the Schur complement matrix. This enables the complexity of forming this matrix in IPRSDP to be comparable to or lower than that of many existing search directions. The global convergence of IPRSDP is established under suitable assumptions. Numerical experiments are made on the SDPLIB set, which demonstrate the efficiency of IPRSDP.

This paper presents a method to solve the mechanical problems undergoing finite deformations and the contact problems without friction, between an hyperelastic body and an obstacle. The main idea is to formulate the contact problem into a constrained minimization one. The constraints are written in a simple form which makes the interior point method very useful to solve the problem. Finally, the FreeFEM and interior Point OPTimizer (IPOPT) software are used to compute and solve the contact problem. Our method is validated against several benchmarks and used on an industrial application example.

We propose a new method for selecting a common subset of explanatory variables where the aim is to model several response variables. The idea is a natural extension of the LASSO technique proposed by Tibshirani (1996) and is based on the (joint) residual sum of squares while constraining the parameter estimates to lie within a suitable polyhedral region. The properties of the resulting convex programming problem are analyzed for the special case of an orthonormal design. For the general case, we develop an efficient interior point algorithm. The method is illustrated on a dataset with infrared spectrometry measurements on 14 qualitatively different but correlated responses using 770 wavelengths. The aim is to select a subset of the wavelengths suitable for use as predictors for as many of the responses as possible.

Let K be a polytope in n defined by m linear inequalities. We give a new Markov chain algorithm to draw a nearly uniform sample from K . The underlying Markov chain is the first to have a mixing time that is strongly polynomial when started from a \"central\" point. We use this result to design an affine interior point algorithm that does a single random walk to solve linear programs approximately.

The focus in this paper is interior-point methods for bound-constrained nonlinear optimization, where the system of nonlinear equations that arise are solved with Newton’s method. There is a trade-off between solving Newton systems directly, which give high quality solutions, and solving many approximate Newton systems which are computationally less expensive but give lower quality solutions. We propose partial and full approximate solutions to the Newton systems. The specific approximate solution depends on estimates of the active and inactive constraints at the solution. These sets are at each iteration estimated by basic heuristics. The partial approximate solutions are computationally inexpensive, whereas a system of linear equations needs to be solved for the full approximate solution. The size of the system is determined by the estimate of the inactive constraints at the solution. In addition, we motivate and suggest two Newton-like approaches which are based on an intermediate step that consists of the partial approximate solutions. The theoretical setting is introduced and asymptotic error bounds are given. We also give numerical results to investigate the performance of the approximate solutions within and beyond the theoretical framework.

The fast-increasing introduction of renewable energy sources (RESes) leads to some problems in electrical power network due to fluctuating generated power. A power system must be operated with provision of various reserve powers like governor free capacity, load frequency control and spinning reserve. Therefore, the generator’s schedule (unit commitment schedule) should include the consideration of the various power reserves. In addition, it is necessary to calculate the annual operational costs of electric power systems by solving the unit commitment per week of thermal power generators and pumped storages in order to compare and examine the variance of the operational costs and the operating ratio of the generators throughout the year. This study proposes a novel annual analysis for the thermal power generator and pumped storages under a massive introduction of RESes. A weekly unit commitment schedule (start/stop planning) for thermal power generator and pumped storages has been modeled and calculated for one year evaluation. To solve the generator start/stop planning problem, Tabu search and interior point methods are adopted to solve the operation planning for thermal power generators and the output decision for pumped storages, respectively. It is demonstrated that the proposed method can analyze a one-year evaluation within practical time. In addition, by assuming load frequency control (LFC) constraints to cope with photovoltaic (PV) output fluctuations, the impact of the intensity of LFC constraints on the operational cost of the thermal power generator has been elucidated. The increment of the operational cost of the power supply with increasing PV introduction amount has been shown in concrete terms.

Summary The power flow study is an exigency for planning, operation, and optimization of future smart microgrids. In this paper, an interior point‐based power flow solution for balanced microgrids operating in islanded mode is presented. In the proposed method, the power flow problem is set up as a constrained interior‐point optimization problem in which nonlinear power mismatch equations are iteratively solved without defining a slack bus. Unlike conventional power flow problems, the unknown frequency of the microgrid and droop equations for distributed generation units are also taken into account. Moreover, fixed, voltage‐dependent, and frequency‐dependent distributed loads are also considered. The computational efficiency of the proposed method is verified using two tools and tested with various case studies. The proposed method has a good convergence pattern and execution time for all types of distributed generation units and loads in islanded networks that are arbitrarily complex. Copyright © 2015 John Wiley & Sons, Ltd.