• Previous Article
    An optimized direction statistics for detecting and removing random-valued impulse noise
  • JIMO Home
  • This Issue
  • Next Article
    Globally solving quadratic programs with convex objective and complementarity constraints via completely positive programming
April 2018, 14(2): 613-623. doi: 10.3934/jimo.2017063

D.C. programming approach for solving an applied ore-processing problem

1. 

Matrosov Institute for System Dynamics and Control Theory of SB RAS, Irkutsk, Russia

2. 

National University of Mongolia, Ulaanbaatar, Mongolia

* Corresponding author:renkhbat46@yahoo.com

Received  April 2016 Revised  December 2016 Published  June 2017

Fund Project: This work has been supported by the Russian Science Foundation, Project N15-11-2001

This paper was motivated by a practical optimization problem formulated at the Erdenet Mining Corporation (Mongolia). By solving an identification problem for a chosen design of experiment we developed a quadratic model that quite adequately represents the experimental data. The problem obtained turned out to be the indefinite quadratic program, which we solved by applying the global search theory for a d.c. programming developed by A.S. Strekalovsky [13]-[15]. According to this d.c. optimization theory, we performed a local search that takes into account the structure of the problem in question, and constructed procedures of escaping critical points provided by the local search. The algorithms proposed for d.c. programming were verified using a set of test problems as well as a copper content maximization problem arising at the mining factory.

Citation: R. Enkhbat, T. V. Gruzdeva, M. V. Barkova. D.C. programming approach for solving an applied ore-processing problem. Journal of Industrial & Management Optimization, 2018, 14 (2) : 613-623. doi: 10.3934/jimo.2017063
References:
[1]

R. Enkhbat and Ya. Bazarsad, General quadratic programming and its applications, in Optimization and optimal control (eds. A. Chinchuluun, P. M. Pardalos, R. Enkhbat and I. Tseveendorj), Springer-Verlag New York, (2010), 121-139.

[2]

R. Enkhbat and T. Ibaraki, Global optimization algorithms for general quadratic programming, J. Mong. Math. Soc., 5 (2001), 22-56.

[3]

T. V. Gruzdeva and A. S. Strekalovsky, Local search in problems with nonconvex constraints, Comput. Math. Math. Phys., 47 (2007), 381-396. doi: 10.1134/S0965542507030049.

[4]

R. HorstP. Pardalos and N. V. Thoai, Introduction to Global Optimization, Introduction to Global Optimization, (1995).

[5]

V. JeyakumarG. M. Lee and N. T. H. Linh, Generalized Farkas lemma and gap-free duality for minimax dc optimization with polynomials and robust quadratic optimization, J. Global Optim., 64 (2016), 679-702. doi: 10.1007/s10898-015-0277-4.

[6]

V. JeyakumarA. M. Rubinov and Z. Y. Wu, Non-convex quadratic minimization problems with quadratic constraints: Global optimality conditions, Math. Program., 110 (2007), 521-541. doi: 10.1007/s10107-006-0012-5.

[7]

R. Horst and N. V. Thoai, D.C.programming: Overview, J. Optim. Theory Appl., 103 (1999), 1-43. doi: 10.1023/A:1021765131316.

[8]

R. H. Myers, Response Surface Methodology, Allyn and Bacon, Boston, MA, 1971.

[9]

J. Nocedal and S. J. Wright, Numerical Optimization, Springer-Verlag, New York, 1999. doi: 10.1007/b98874.

[10]

A. Rubinov, Abstract Convexity and Global Optimization, Springer US, Dordrecht, 2000.

[11]

A. M. Rubinov and Z. Y. Wu, Optimality conditions in global optimization and their applications, Math. Program., 120 (2009), 101-123. doi: 10.1007/s10107-007-0142-4.

[12]

A. S. Strekalovsky, On local search in d.c. optimization problems, Appl. Math. Comput., 255 (2015), 73-83. doi: 10.1016/j.amc.2014.08.092.

[13]

A. S. Strekalovsky, On solving optimization problems with hidden nonconvex structures, in Optimization in science and engineering (eds. T. M. Rassias, C. A. Floudas and S. Butenko), Springer, New York, (2014), 465-502. doi: 10.1007/978-1-4939-0808-0_23.

[14]

A. S. Strekalovsky, Elementy Nevypukloi Optimizatsii, (Russian) [Elements of nonconvex optimization], Nauka Publ., Novosibirsk, 2003.

[15]

A. S. Strekalovsky, On the minimization of the difference of convex functions on a feasible set, Comput. Math. Math. Phys., 43 (2003), 380-390.

[16]

A. S. StrekalovskyA. A. Kuznetsova and T. V. Yakovleva, Numerical solution of nonconvex optimization problems, Numer. Anal. Appl., 4 (2001), 185-199.

[17]

A. S. Strekalovsky and T. V. Yakovleva, On a local and global search involved in nonconvex optimization problems, Autom. and Remote Control, 65 (2004), 375-387. doi: 10.1023/B:AURC.0000019368.45522.7a.

[18]

P. D. Tao and L. T. Hoai An, The DC (difference of convex functions) programming and DCA revisited with DC models of real world nonconvex optimization problems, Ann. Oper. Res., 133 (2005), 23-46. doi: 10.1007/s10479-004-5022-1.

[19]

Z. Y. WuV. Jeyakumar and A. M. Rubinov, Sufficient conditions for global optimality of bivalent nonconvex quadratic programs with inequality constraints, J. Optim. Theory Appl., 133 (2007), 123-130. doi: 10.1007/s10957-007-9177-1.

[20]

Z. Y. Wu and A. M. Rubinov, Global optimality conditions for some classes of optimization problems, J. Optim. Theory Appl., 145 (2010), 164-185. doi: 10.1007/s10957-009-9616-2.

show all references

References:
[1]

R. Enkhbat and Ya. Bazarsad, General quadratic programming and its applications, in Optimization and optimal control (eds. A. Chinchuluun, P. M. Pardalos, R. Enkhbat and I. Tseveendorj), Springer-Verlag New York, (2010), 121-139.

[2]

R. Enkhbat and T. Ibaraki, Global optimization algorithms for general quadratic programming, J. Mong. Math. Soc., 5 (2001), 22-56.

[3]

T. V. Gruzdeva and A. S. Strekalovsky, Local search in problems with nonconvex constraints, Comput. Math. Math. Phys., 47 (2007), 381-396. doi: 10.1134/S0965542507030049.

[4]

R. HorstP. Pardalos and N. V. Thoai, Introduction to Global Optimization, Introduction to Global Optimization, (1995).

[5]

V. JeyakumarG. M. Lee and N. T. H. Linh, Generalized Farkas lemma and gap-free duality for minimax dc optimization with polynomials and robust quadratic optimization, J. Global Optim., 64 (2016), 679-702. doi: 10.1007/s10898-015-0277-4.

[6]

V. JeyakumarA. M. Rubinov and Z. Y. Wu, Non-convex quadratic minimization problems with quadratic constraints: Global optimality conditions, Math. Program., 110 (2007), 521-541. doi: 10.1007/s10107-006-0012-5.

[7]

R. Horst and N. V. Thoai, D.C.programming: Overview, J. Optim. Theory Appl., 103 (1999), 1-43. doi: 10.1023/A:1021765131316.

[8]

R. H. Myers, Response Surface Methodology, Allyn and Bacon, Boston, MA, 1971.

[9]

J. Nocedal and S. J. Wright, Numerical Optimization, Springer-Verlag, New York, 1999. doi: 10.1007/b98874.

[10]

A. Rubinov, Abstract Convexity and Global Optimization, Springer US, Dordrecht, 2000.

[11]

A. M. Rubinov and Z. Y. Wu, Optimality conditions in global optimization and their applications, Math. Program., 120 (2009), 101-123. doi: 10.1007/s10107-007-0142-4.

[12]

A. S. Strekalovsky, On local search in d.c. optimization problems, Appl. Math. Comput., 255 (2015), 73-83. doi: 10.1016/j.amc.2014.08.092.

[13]

A. S. Strekalovsky, On solving optimization problems with hidden nonconvex structures, in Optimization in science and engineering (eds. T. M. Rassias, C. A. Floudas and S. Butenko), Springer, New York, (2014), 465-502. doi: 10.1007/978-1-4939-0808-0_23.

[14]

A. S. Strekalovsky, Elementy Nevypukloi Optimizatsii, (Russian) [Elements of nonconvex optimization], Nauka Publ., Novosibirsk, 2003.

[15]

A. S. Strekalovsky, On the minimization of the difference of convex functions on a feasible set, Comput. Math. Math. Phys., 43 (2003), 380-390.

[16]

A. S. StrekalovskyA. A. Kuznetsova and T. V. Yakovleva, Numerical solution of nonconvex optimization problems, Numer. Anal. Appl., 4 (2001), 185-199.

[17]

A. S. Strekalovsky and T. V. Yakovleva, On a local and global search involved in nonconvex optimization problems, Autom. and Remote Control, 65 (2004), 375-387. doi: 10.1023/B:AURC.0000019368.45522.7a.

[18]

P. D. Tao and L. T. Hoai An, The DC (difference of convex functions) programming and DCA revisited with DC models of real world nonconvex optimization problems, Ann. Oper. Res., 133 (2005), 23-46. doi: 10.1007/s10479-004-5022-1.

[19]

Z. Y. WuV. Jeyakumar and A. M. Rubinov, Sufficient conditions for global optimality of bivalent nonconvex quadratic programs with inequality constraints, J. Optim. Theory Appl., 133 (2007), 123-130. doi: 10.1007/s10957-007-9177-1.

[20]

Z. Y. Wu and A. M. Rubinov, Global optimality conditions for some classes of optimization problems, J. Optim. Theory Appl., 145 (2010), 164-185. doi: 10.1007/s10957-009-9616-2.

Table 1.   
$x^1$$x^2$$\ldots$$x^n$$f^1$$f^2$$\ldots$$f^l$
$x_{11}$$x_{12}$$\ldots$$x_{1n}$$f_{11}$$f_{12}$$\ldots$$f_{1l}$
$x_{21}$$x_{22}$$\ldots$$x_{2n}$$f_{21}$$f_{22}$$\ldots$$f_{2l}$
$\ldots$$\ldots$$\ldots$$\ldots$$\ldots$$\ldots$$\ldots$$\ldots$
$x_{m1}$$x_{m2}$$\ldots$$x_{m n}$$f_{m1}$$f_{m2}$$\ldots$$f_{ml}$
$x^1$$x^2$$\ldots$$x^n$$f^1$$f^2$$\ldots$$f^l$
$x_{11}$$x_{12}$$\ldots$$x_{1n}$$f_{11}$$f_{12}$$\ldots$$f_{1l}$
$x_{21}$$x_{22}$$\ldots$$x_{2n}$$f_{21}$$f_{22}$$\ldots$$f_{2l}$
$\ldots$$\ldots$$\ldots$$\ldots$$\ldots$$\ldots$$\ldots$$\ldots$
$x_{m1}$$x_{m2}$$\ldots$$x_{m n}$$f_{m1}$$f_{m2}$$\ldots$$f_{ml}$
Table 1.  Local search method for Problem $(P_1)$
$#$$x^0$$f_1(x^0)$$f_1(z)$$PL$$Time$
$1$$(0.408, 1.000, 0.572, 1.000, 0.628, 1.000, 0.167)$$0.91617$$0.93224$$6$$0.062$
$2$$(0.408, 1.000, 1.000, 1.000, 1.000, 1.000, 1.000 )$$1.10581$$1.28877$$6$$0.076$
$3$$(1.000, 0.000, 1.000, 1.000, 1.000, 1.000, 1.000)$$1.20652$$1.35330$$5$$0.047$
$4$$(0.987, 0.920, 0.852, 0.914, 0.893, 0.796, 0.186)$$0.87444$$1.36455$$7$$0.015$
$5$$(0.658, 0.699, 0.970, 0.783, 0.629, 0.858, 0.847)$$0.83431$${\bf{1.36510}}$$\!10\!$$0.010$
$#$$x^0$$f_1(x^0)$$f_1(z)$$PL$$Time$
$1$$(0.408, 1.000, 0.572, 1.000, 0.628, 1.000, 0.167)$$0.91617$$0.93224$$6$$0.062$
$2$$(0.408, 1.000, 1.000, 1.000, 1.000, 1.000, 1.000 )$$1.10581$$1.28877$$6$$0.076$
$3$$(1.000, 0.000, 1.000, 1.000, 1.000, 1.000, 1.000)$$1.20652$$1.35330$$5$$0.047$
$4$$(0.987, 0.920, 0.852, 0.914, 0.893, 0.796, 0.186)$$0.87444$$1.36455$$7$$0.015$
$5$$(0.658, 0.699, 0.970, 0.783, 0.629, 0.858, 0.847)$$0.83431$${\bf{1.36510}}$$\!10\!$$0.010$
Table 2.  Local search method for Problem $(P_2)$
$#$$x^0$$f_2(x^0)$$f_2(z)$$PL$$Time$
$1$$(1.000, 1.000, 1.000, 1.000, 1.000, 1.000, 1.000)$$0.87224$${\bf{1.10128}}$$9$$ 0.090$
$2$$(0.408, 1.000, 0.572, 1.000, 0.628, 1.000, 0.167) $$1.02257$$1.04541$$5$$0.047 $
$3$$(0.408, 1.000, 1.000, 1.000, 1.000, 1.000, 1.000)$$1.08494$${\bf{1.10126}}$$8$$0.078$
$4$$(0.408, 0.000, 0.572, 0.724, 0.628, 1.000, 0.167)$$0.93835$$1.10021$$\!16\!$$0.031$
$5$ $(1.000, 1.000, 1.000, 1.000, 1.000, 1.000, 0.167) $0.995591.0984780.012
$#$$x^0$$f_2(x^0)$$f_2(z)$$PL$$Time$
$1$$(1.000, 1.000, 1.000, 1.000, 1.000, 1.000, 1.000)$$0.87224$${\bf{1.10128}}$$9$$ 0.090$
$2$$(0.408, 1.000, 0.572, 1.000, 0.628, 1.000, 0.167) $$1.02257$$1.04541$$5$$0.047 $
$3$$(0.408, 1.000, 1.000, 1.000, 1.000, 1.000, 1.000)$$1.08494$${\bf{1.10126}}$$8$$0.078$
$4$$(0.408, 0.000, 0.572, 0.724, 0.628, 1.000, 0.167)$$0.93835$$1.10021$$\!16\!$$0.031$
$5$ $(1.000, 1.000, 1.000, 1.000, 1.000, 1.000, 0.167) $0.995591.0984780.012
Table 3.  Global search method for Problem $(P_1)$
$#$$f_1(x^0)$$f_1^*$$it$$loc$$PL$$Time$
10.916171.3651881613460.260
21.105811.3651891573380.250
31.206521.3651891653530.262
40.874441.3651851473190.234
50.834311.3651811362940.218
$#$$f_1(x^0)$$f_1^*$$it$$loc$$PL$$Time$
10.916171.3651881613460.260
21.105811.3651891573380.250
31.206521.3651891653530.262
40.874441.3651851473190.234
50.834311.3651811362940.218
Table 4.  Global search method for Problem $(P_2)$
$#$$f_2(x^0)$$f_2^*$$it$$loc$$PL$$Time$
10.872241.101281741450.124
21.022571.101288911990.171
31.084941.101281741550.124
40.938351.101286851880.141
50.995591.101288911990.156
$#$$f_2(x^0)$$f_2^*$$it$$loc$$PL$$Time$
10.872241.101281741450.124
21.022571.101288911990.171
31.084941.101281741550.124
40.938351.101286851880.141
50.995591.101288911990.156
[1]

Paul B. Hermanns, Nguyen Van Thoai. Global optimization algorithm for solving bilevel programming problems with quadratic lower levels. Journal of Industrial & Management Optimization, 2010, 6 (1) : 177-196. doi: 10.3934/jimo.2010.6.177

[2]

Ye Tian, Cheng Lu. Nonconvex quadratic reformulations and solvable conditions for mixed integer quadratic programming problems. Journal of Industrial & Management Optimization, 2011, 7 (4) : 1027-1039. doi: 10.3934/jimo.2011.7.1027

[3]

Adil Bagirov, Sona Taheri, Soodabeh Asadi. A difference of convex optimization algorithm for piecewise linear regression. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-24. doi: 10.3934/jimo.2018077

[4]

Fengqiu Liu, Xiaoping Xue. Subgradient-based neural network for nonconvex optimization problems in support vector machines with indefinite kernels. Journal of Industrial & Management Optimization, 2016, 12 (1) : 285-301. doi: 10.3934/jimo.2016.12.285

[5]

Ziye Shi, Qingwei Jin. Second order optimality conditions and reformulations for nonconvex quadratically constrained quadratic programming problems. Journal of Industrial & Management Optimization, 2014, 10 (3) : 871-882. doi: 10.3934/jimo.2014.10.871

[6]

Radu Ioan Boţ, Anca Grad, Gert Wanka. Sequential characterization of solutions in convex composite programming and applications to vector optimization. Journal of Industrial & Management Optimization, 2008, 4 (4) : 767-782. doi: 10.3934/jimo.2008.4.767

[7]

Lipu Zhang, Yinghong Xu, Zhengjing Jin. An efficient algorithm for convex quadratic semi-definite optimization. Numerical Algebra, Control & Optimization, 2012, 2 (1) : 129-144. doi: 10.3934/naco.2012.2.129

[8]

Huijuan Li, Robert Baier, Lars Grüne, Sigurdur F. Hafstein, Fabian R. Wirth. Computation of local ISS Lyapunov functions with low gains via linear programming. Discrete & Continuous Dynamical Systems - B, 2015, 20 (8) : 2477-2495. doi: 10.3934/dcdsb.2015.20.2477

[9]

Zhenbo Wang, Shu-Cherng Fang, David Y. Gao, Wenxun Xing. Global extremal conditions for multi-integer quadratic programming. Journal of Industrial & Management Optimization, 2008, 4 (2) : 213-225. doi: 10.3934/jimo.2008.4.213

[10]

Ahmet Sahiner, Nurullah Yilmaz, Gulden Kapusuz. A novel modeling and smoothing technique in global optimization. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-18. doi: 10.3934/jimo.2018035

[11]

Zhi-Bin Deng, Ye Tian, Cheng Lu, Wen-Xun Xing. Globally solving quadratic programs with convex objective and complementarity constraints via completely positive programming. Journal of Industrial & Management Optimization, 2018, 14 (2) : 625-636. doi: 10.3934/jimo.2017064

[12]

Ailing Zhang, Shunsuke Hayashi. Celis-Dennis-Tapia based approach to quadratic fractional programming problems with two quadratic constraints. Numerical Algebra, Control & Optimization, 2011, 1 (1) : 83-98. doi: 10.3934/naco.2011.1.83

[13]

Shu-Lin Lyu. On the Hermite--Hadamard inequality for convex functions of two variables. Numerical Algebra, Control & Optimization, 2014, 4 (1) : 1-8. doi: 10.3934/naco.2014.4.1

[14]

Le Thi Hoai An, Tran Duc Quynh, Kondo Hloindo Adjallah. A difference of convex functions algorithm for optimal scheduling and real-time assignment of preventive maintenance jobs on parallel processors. Journal of Industrial & Management Optimization, 2014, 10 (1) : 243-258. doi: 10.3934/jimo.2014.10.243

[15]

Nguyen Thi Bach Kim, Nguyen Canh Nam, Le Quang Thuy. An outcome space algorithm for minimizing the product of two convex functions over a convex set. Journal of Industrial & Management Optimization, 2013, 9 (1) : 243-253. doi: 10.3934/jimo.2013.9.243

[16]

Yanqin Bai, Xuerui Gao, Guoqiang Wang. Primal-dual interior-point algorithms for convex quadratic circular cone optimization. Numerical Algebra, Control & Optimization, 2015, 5 (2) : 211-231. doi: 10.3934/naco.2015.5.211

[17]

Yanqin Bai, Lipu Zhang. A full-Newton step interior-point algorithm for symmetric cone convex quadratic optimization. Journal of Industrial & Management Optimization, 2011, 7 (4) : 891-906. doi: 10.3934/jimo.2011.7.891

[18]

Chunrong Chen, T. C. Edwin Cheng, Shengji Li, Xiaoqi Yang. Nonlinear augmented Lagrangian for nonconvex multiobjective optimization. Journal of Industrial & Management Optimization, 2011, 7 (1) : 157-174. doi: 10.3934/jimo.2011.7.157

[19]

Murat Adivar, Shu-Cherng Fang. Convex optimization on mixed domains. Journal of Industrial & Management Optimization, 2012, 8 (1) : 189-227. doi: 10.3934/jimo.2012.8.189

[20]

S. S. Dragomir, I. Gomm. Some new bounds for two mappings related to the Hermite-Hadamard inequality for convex functions. Numerical Algebra, Control & Optimization, 2012, 2 (2) : 271-278. doi: 10.3934/naco.2012.2.271

2016 Impact Factor: 0.994

Article outline

Figures and Tables

[Back to Top]