A counterexample to De Pierro's conjecture on the convergence of under-relaxed cyclic projections
- Authors: Cominetti, Roberto , Roshchina, Vera , Williamson, Andrew
- Date: 2019
- Type: Text , Journal article
- Relation: Optimization Vol. 68, no. 1 (2019), p. 3-12
- Full Text:
- Reviewed:
- Description: The convex feasibility problem consists in finding a point in the intersection of a finite family of closed convex sets. When the intersection is empty, a best compromise is to search for a point that minimizes the sum of the squared distances to the sets. In 2001, de Pierro conjectured that the limit cycles generated by the ε-under-relaxed cyclic projection method converge when ε ↓ 0 towards a least squares solution. While the conjecture has been confirmed under fairly general conditions, we show that it is false in general by constructing a system of three compact convex sets in R3 for which the ε-under-relaxed cycles do not converge. © 2018 Informa UK Limited, trading as Taylor & Francis Group.
A generalization of a theorem of Arrow, Barankin and Blackwell to a nonconvex case
- Authors: Kasimbeyli, Nergiz , Kasimbeyli, Refail , Mammadov, Musa
- Date: 2016
- Type: Text , Journal article
- Relation: Optimization Vol. 65, no. 5 (May 2016), p. 937-945
- Full Text:
- Reviewed:
- Description: The paper presents a generalization of a known density theorem of Arrow, Barankin, and Blackwell for properly efficient points defined as support points of sets with respect to monotonically increasing sublinear functions. This result is shown to hold for nonconvex sets of a partially ordered reflexive Banach space.
A hybrid method combining genetic algorithm and Hooke-Jeeves method for constrained global optimization
- Authors: Long, Qiang , Wu, Changzhi
- Date: 2014
- Type: Text , Journal article
- Relation: Journal of Industrial and Management Optimization Vol. 10, no. 4 (2014), p. 1279-1296
- Full Text:
- Reviewed:
- Description: A new global optimization method combining genetic algorithm and Hooke-Jeeves method to solve a class of constrained optimization problems is studied in this paper. We first introduce the quadratic penalty function method and the exact penalty function method to transform the original constrained optimization problem with general equality and inequality constraints into a sequence of optimization problems only with box constraints. Then, the combination of genetic algorithm and Hooke-Jeeves method is applied to solve the transformed optimization problems. Since Hooke-Jeeves method is good at local search, our proposed method dramatically improves the accuracy and convergence rate of genetic algorithm. In view of the derivative-free of Hooke-Jeeves method, our method only requires information of objective function value which not only can overcome the computational difficulties caused by the ill-condition of the square penalty function, but also can handle the non-diffierentiability by the exact penalty function. Some well-known test problems are investigated. The numerical results show that our proposed method is eficient and robust.
A model for adaptive rescheduling of flights in emergencies (MARFE)
- Authors: Filar, Jerzy , Manyem, Prabhu , Panton, David , White, Kevin
- Date: 2007
- Type: Text , Journal article
- Relation: Journal of Industrial and Management Optimization Vol. 3, no. 2 (May 2007), p. 335-356
- Full Text:
- Reviewed:
- Description: Disruptions to commercial airline schedules are frequent and can inflict significant costs. In this paper we continue a line of research initiated by Vranas, Bertsimas and Odoni [15, 16], that aims to develop techniques facilitating rapid return to normal operations whenever disruptions occur. Ground Holding is a technique that has been successfully employed to combat disruptions at North American airports. However, this alone is insufficient to cope with the problem. We develop an adaptive optimization model that allows the implementation of other tactics, such as flight cancellations, airborne holding and diversions. While the approach is generic, our model incorporates features of Sydney airport in Australia, such as a night curfew from 11:00pm to 6:00am. For an actual day when there was a significant capacity drop, we demonstrate that our model clearly outperforms the actions that were initiated by the air traffic controllers at Sydney.
- Description: C1
- Description: 2003004883
A new auxiliary function method for general constrained global optimization
- Authors: Wu, Zhiyou , Bai, Fusheng , Yang, Yongjian , Mammadov, Musa
- Date: 2013
- Type: Text , Journal article
- Relation: Optimization Vol. 62, no. 2 (2013), p. 193-210
- Full Text:
- Reviewed:
- Description: In this article, we first propose a method to obtain an approximate feasible point for general constrained global optimization problems (with both inequality and equality constraints). Then we propose an auxiliary function method to obtain a global minimizer or an approximate global minimizer with a required precision for general global optimization problems by locally solving some unconstrained programming problems. Some numerical examples are reported to demonstrate the efficiency of the present optimization method. © 2013 Taylor & Francis.
- Description: 2003011103
A new method for solving linear ill-posed problems
- Authors: Zhang, Jianjun , Mammadov, Musa
- Date: 2012
- Type: Text , Journal article
- Relation: Applied Mathematics and Computation Vol. 218, no. 20 (2012), p.10180-10187
- Full Text:
- Reviewed:
- Description: In this paper, we propose a new method for solving large-scale ill-posed problems. This method is based on the Karush-Kuhn-Tucker conditions, Fisher-Burmeister function and the discrepancy principle. The main difference from the majority of existing methods for solving ill-posed problems is that, we do not need to choose a regularization parameter in advance. Experimental results show that the proposed method is effective and promising for many practical problems. © 2012.
A pupil-positioning method based on the starburst model
- Authors: Yu, Pingping , Duan, Wenjie , Sun, Yi , Cao, Ning , Wang, Zhenzhou , Lu, Guojun
- Date: 2020
- Type: Text , Journal article
- Relation: Cmc-Computers Materials & Continua Vol. 64, no. 2 (2020), p. 1199-1217
- Full Text:
- Reviewed:
- Description: Human eye detection has become an area of interest in the field of computer vision with an extensive range of applications in human-computer interaction, disease diagnosis, and psychological and physiological studies. Gaze-tracking systems are an important research topic in the human-computer interaction field. As one of the core modules of the head-mounted gaze-tracking system, pupil positioning affects the accuracy and stability of the system. By tracking eye movements to better locate the center of the pupil, this paper proposes a method for pupil positioning based on the starburst model. The method uses vertical and horizontal coordinate integral projections in the rectangular region of the human eye for accurate positioning and applies a linear interpolation method that is based on a circular model to the reflections in the human eye. In this paper, we propose a method for detecting the feature points of the pupil edge based on the starburst model, which clusters feature points and uses the RANdom SAmple Consensus (RANSAC) algorithm to perform ellipse fitting of the pupil edge to accurately locate the pupil center. Our experimental results show that the algorithm has higher precision, higher efficiency and more robustness than other algorithms and excellent accuracy even when the image of the pupil is incomplete.
- Description: Science and Technology Support Plan Project of Hebei Province (grant numbers 17210803D and 19273703D Science and Technology Spark Project of the Hebei Seismological Bureau (grant number DZ20180402056) Education Department of Hebei Province (grant number QN2018095) Polytechnic College of Hebei University of Science and Technology
A unifying approach to robust convex infinite optimization duality
- Authors: Dinh, Nguyen , Goberna, Miguel , López, Marco , Volle, Michel
- Date: 2017
- Type: Text , Journal article
- Relation: Journal of Optimization Theory and Applications Vol. 174, no. 3 (2017), p. 650-685
- Relation: http://purl.org/au-research/grants/arc/DP160100854
- Full Text:
- Reviewed:
- Description: This paper considers an uncertain convex optimization problem, posed in a locally convex decision space with an arbitrary number of uncertain constraints. To this problem, where the uncertainty only affects the constraints, we associate a robust (pessimistic) counterpart and several dual problems. The paper provides corresponding dual variational principles for the robust counterpart in terms of the closed convexity of different associated cones.
Aggregate subgradient method for nonsmooth DC optimization
- Authors: Bagirov, Adil , Taheri, Sona , Joki, Kaisa , Karmitsa, Napsu , Mäkelä, Marko
- Date: 2021
- Type: Text , Journal article
- Relation: Optimization Letters Vol. 15, no. 1 (2021), p. 83-96
- Relation: http://purl.org/au-research/grants/arc/DP190100580
- Full Text:
- Reviewed:
- Description: The aggregate subgradient method is developed for solving unconstrained nonsmooth difference of convex (DC) optimization problems. The proposed method shares some similarities with both the subgradient and the bundle methods. Aggregate subgradients are defined as a convex combination of subgradients computed at null steps between two serious steps. At each iteration search directions are found using only two subgradients: the aggregate subgradient and a subgradient computed at the current null step. It is proved that the proposed method converges to a critical point of the DC optimization problem and also that the number of null steps between two serious steps is finite. The new method is tested using some academic test problems and compared with several other nonsmooth DC optimization solvers. © 2020, Springer-Verlag GmbH Germany, part of Springer Nature.
An existence result for quasi-equilibrium problems via Ekeland’s variational principle
- Authors: Cotrina, John , Théra, Michel , Zúñiga, Javier
- Date: 2020
- Type: Text , Journal article
- Relation: Journal of Optimization Theory and Applications Vol. 187, no. 2 (2020), p. 336-355
- Full Text:
- Reviewed:
- Description: This paper deals with the existence of solutions to equilibrium and quasi-equilibrium problems without any convexity assumption. Coverage includes some equivalences to the Ekeland variational principle for bifunctions and basic facts about transfer lower continuity. An application is given to systems of quasi-equilibrium problems. © 2020, Springer Science+Business Media, LLC, part of Springer Nature.
- Description: Research of M. Théra is supported by the Australian Research Council (ARC) Grant DP160100854 and benefited from the support of the FMJH Program PGMO and from the support of EDF. http://purl.org/au-research/grants/arc/DP160100854
An extended lifetime measure for telecommunication network
- Authors: Dzalilov, Zari , Ouveysi, Iradj , Rubinov, Alex
- Date: 2008
- Type: Text , Journal article
- Relation: Journal of Industrial and Management Optimization Vol. 4, no. 2 (2008), p. 329-337
- Full Text:
- Reviewed:
- Description: A new measure for network performance evaluation called topology lifetime was introduced in [4, 5]. This measure is based on the notion of unexpected traffic growth and can be used for comparison of topologies. We discuss some advantages and disadvantages of the approach of [4] and suggest some modifications to this approach. In particular we discuss how to evaluate the influence of a subgraph to the lifetime measure and introduce the notion of the order of a path. This notion is useful if we consider a possible extension to the set of working paths in order to support the traffic for the time that is needed for installation of new facilities.
An extended lifetime measure for telecommunications networks : Improvements and implementations
- Authors: Dzalilov, Zari , Ouveysi, Iradj , Bektas, Tolga
- Date: 2012
- Type: Text , Journal article
- Relation: Journal of Industrial and Management Optimization Vol. 8, no. 3 (2012), p. 639-649
- Full Text:
- Reviewed:
- Description: Predicting the lifetime of a network is a stochastic and very hard task. Sensitivity analysis of a network in order to identify the weakest points in the network, provides valuable knowledge to draw an optimum investment strategy for the expansion of the networks for the network carriers. To achieve this goal, a new measure, called topology lifetime, was recently proposed for measuring the performance of a telecommunication network. This measure not only allows to perform a sensitivity analysis of the networks, but also it provides the means to compare the different topologies with respect to the ability of the network in supporting growth in network traffic before new capacity/facility is installed. This paper addresses some improvements upon the previously defined measures and presents the implementation results of the various lifetime measure methodologies. Computational analysis on some commonly used topologies show how the new measure can be utilized in assessing network performance.
- Description: 2003010401
An induction theorem and nonlinear regularity models
- Authors: Khanh, Phan , Kruger, Alexander , Thao, Nguyen
- Date: 2015
- Type: Text , Journal article
- Relation: Siam Journal on Optimization Vol. 25, no. 4 (2015), p. 2561-2588
- Relation: http://purl.org/au-research/grants/arc/DP110102011
- Full Text:
- Reviewed:
- Description: A general nonlinear regularity model for a set-valued mapping F : X x R+ paired right arrows Y, where X and Y are metric spaces, is studied using special iteration procedures, going back to Banach, Schauder, Lyusternik, and Graves. Namely, we revise the induction theorem from Khanh [J. Math. Anal. Appl., 118 (1986), pp. 519-534] and employ it to obtain basic estimates for exploring regularity/openness properties. We also show that it can serve as a substitution for the Ekeland variational principle when establishing other regularity criteria. Then, we apply the induction theorem and the mentioned estimates to establish criteria for both global and local versions of regularity/openness properties for our model and demonstrate how the definitions and criteria translate into the conventional setting of a set-valued mapping F : X paired right arrows Y. An application to second-order necessary optimality conditions for a nonsmooth set-valued optimization problem with mixed constraints is provided.
An update rule and a convergence result for a penalty function method
- Authors: Burachik, Regina , Kaya, Yalcin
- Date: 2007
- Type: Text , Journal article
- Relation: Journal of Industrial & Management Optimization Vol. 3, no. 2 (2007), p. 381-398
- Full Text:
- Reviewed:
- Description: We use a primal-dual scheme to devise a new update rule for a penalty function method applicable to general optimization problems, including nonsmooth and nonconvex ones. The update rule we introduce uses dual information in a simple way. Numerical test problems show that our update rule has certain advantages over the classical one. We study the relationship between exact penalty parameters and dual solutions. Under the differentiability of the dual function at the least exact penalty parameter, we establish convergence of the minimizers of the sequential penalty functions to a solution of the original problem. Numerical experiments are then used to illustrate some of the theoretical results.
- Description: C1
- Description: 2003004886
Calmness modulus of linear semi-infinite programs
- Authors: Cánovas, Maria , Kruger, Alexander , López, Marco , Parra, Juan , Théra, Michel
- Date: 2014
- Type: Text , Journal article
- Relation: SIAM Journal on Optimization Vol. 24, no. 1 (2014), p. 29-48
- Relation: http://purl.org/au-research/grants/arc/DP110102011
- Full Text:
- Reviewed:
- Description: Our main goal is to compute or estimate the calmness modulus of the argmin mapping of linear semi-infinite optimization problems under canonical perturbations, i.e., perturbations of the objective function together with continuous perturbations of the right-hand side of the constraint system (with respect to an index ranging in a compact Hausdorff space). Specifically, we provide a lower bound on the calmness modulus for semi-infinite programs with unique optimal solution which turns out to be the exact modulus when the problem is finitely constrained. The relationship between the calmness of the argmin mapping and the same property for the (sub)level set mapping (with respect to the objective function), for semi-infinite programs and without requiring the uniqueness of the nominal solution, is explored, too, providing an upper bound on the calmness modulus of the argmin mapping. When confined to finitely constrained problems, we also provide a computable upper bound as it only relies on the nominal data and parameters, not involving elements in a neighborhood. Illustrative examples are provided.
Calmness of partially perturbed linear systems with an application to the central path
- Authors: Cánovas, Maria , Hall, Julian , López, Marco , Parra, Juan
- Date: 2019
- Type: Text , Journal article
- Relation: Optimization Vol. 68, no. 2-3 (2019), p. 465-483
- Full Text:
- Reviewed:
- Description: In this paper we develop point-based formulas for the calmness modulus of the feasible set mapping in the context of linear inequality systems with a fixed abstract constraint and (partially) perturbed linear constraints. The case of totally perturbed linear systems was previously analyzed in [Canovas MJ, Lopez MA, Parra J, et al. Calmness of the feasible set mapping for linear inequality systems. Set-Valued Var Anal. 2014;22:375-389, Section 5]. We point out that the presence of such an abstract constraint yields the current paper to appeal to a notable different methodology with respect to previous works on the calmness modulus in linear programming. The interest of this model comes from the fact that partially perturbed systems naturally appear in many applications. As an illustration, the paper includes an example related to the classical central path construction. In this example we consider a certain feasible set mapping whose calmness modulus provides a measure of the convergence of the central path. Finally, we underline the fact that the expression for the calmness modulus obtained in this paper is (conceptually) implementable as far as it only involves the nominal data.
Canonical duality for solving general nonconvex constrained problems
- Authors: Latorre, Vittorio , Gao, David
- Date: 2016
- Type: Text , Journal article
- Relation: Optimization Letters Vol. 10, no. 8 (2016), p. 1763-1779
- Full Text:
- Reviewed:
- Description: This paper presents a canonical duality theory for solving a general nonconvex constrained optimization problem within a unified framework to cover Lagrange multiplier method and KKT theory. It is proved that if both target function and constraints possess certain patterns necessary for modeling real systems, a perfect dual problem (without duality gap) can be obtained in a unified form with global optimality conditions provided.While the popular augmented Lagrangian method may produce more difficult nonconvex problems due to the nonlinearity of constraints. Some fundamental concepts such as the objectivity and Lagrangian in nonlinear programming are addressed.
Characterization theorem for best polynomial spline approximation with free knots, variable degree and fixed tails
- Authors: Crouzeix, Jean-Pierre , Sukhorukova, Nadezda , Ugon, Julien
- Date: 2017
- Type: Text , Journal article
- Relation: Journal of Optimization Theory and Applications Vol. 172, no. 3 (2017), p. 950-964
- Full Text:
- Reviewed:
- Description: In this paper, we derive a necessary condition for a best approximation by piecewise polynomial functions of varying degree from one interval to another. Based on these results, we obtain a characterization theorem for the polynomial splines with fixed tails, that is the value of the spline is fixed in one or more knots (external or internal). We apply nonsmooth nonconvex analysis to obtain this result, which is also a necessary and sufficient condition for inf-stationarity in the sense of Demyanov-Rubinov. This paper is an extension of a paper where similar conditions were obtained for free tails splines. The main results of this paper are essential for the development of a Remez-type algorithm for free knot spline approximation.
Characterizations of nonsmooth robustly quasiconvex functions
- Authors: Bui, Hoa , Khanh, Pham , Tran, Thi
- Date: 2019
- Type: Text , Journal article
- Relation: Journal of Optimization Theory and Applications Vol. 180, no. 3 (2019), p. 775-786
- Full Text:
- Reviewed:
- Description: Two criteria for the robust quasiconvexity of lower semicontinuous functions are established in terms of Fréchet subdifferentials in Asplund spaces. The first criterion extends to such spaces a result established by Barron et al. (Discrete Contin Dyn Syst Ser B 17:1693–1706, 2012). The second criterion is totally new even if it is applied to lower semicontinuous functions on finite-dimensional spaces. © 2018, Springer Science+Business Media, LLC, part of Springer Nature.
Chebyshev multivariate polynomial approximation and point reduction procedure
- Authors: Sukhorukova, Nadezda , Ugon, Julien , Yost, David
- Date: 2021
- Type: Text , Journal article
- Relation: Constructive Approximation Vol. 53, no. 3 (2021), p. 529-544
- Relation: http://purl.org/au-research/grants/arc/DP180100602
- Full Text:
- Reviewed:
- Description: We apply the methods of nonsmooth and convex analysis to extend the study of Chebyshev (uniform) approximation for univariate polynomial functions to the case of general multivariate functions (not just polynomials). First of all, we give new necessary and sufficient optimality conditions for multivariate approximation, and a geometrical interpretation of them which reduces to the classical alternating sequence condition in the univariate case. Then, we present a procedure for verification of necessary and sufficient optimality conditions that is based on our generalization of the notion of alternating sequence to the case of multivariate polynomials. Finally, we develop an algorithm for fast verification of necessary optimality conditions in the multivariate polynomial case. © 2019, Springer Science+Business Media, LLC, part of Springer Nature.