December  2017, 10(6): 1329-1350. doi: 10.3934/dcdss.2017071

Inverse truss design as a conic mathematical program with equilibrium constraints

1. 

School of Mathematics, University of Birmingham, Birmingham B15 2TT, United Kingdom

2. 

Institute of Information Theory and Automation, Academy of Sciences of the Czech Republic, Pod vodárenskou věží 4, 18208 Praha 8, Czech Republic

* Corresponding author

Dedicated to Tomáš Roubíček on the occasion of his 60th birthday

Received  July 2016 Revised  December 2016 Published  June 2017

Fund Project: The second author is supported by the Grant Agency of the Czech Republic project 15-00735S.

We formulate an inverse optimal design problem as a Mathematical Programming problem with Equilibrium Constraints (MPEC). The equilibrium constraints are in the form of a second-order conic optimization problem. Using the so-called Implicit Programming technique, we reformulate the bilevel optimization problem as a single-level nonsmooth nonconvex problem. The major part of the article is devoted to the computation of a subgradient of the resulting composite objective function. The article is concluded by numerical examples demonstrating, for the first time, that the Implicit Programming technique can be efficiently used in the numerical solution of MPECs with conic constraints on the lower level.

Citation: Michal Kočvara, Jiří V. Outrata. Inverse truss design as a conic mathematical program with equilibrium constraints. Discrete & Continuous Dynamical Systems - S, 2017, 10 (6) : 1329-1350. doi: 10.3934/dcdss.2017071
References:
[1]

W. AchtzigerM. BendsoeA. Ben-Tal and J. Zowe, Equivalent displacement based formulations for maximum strength truss topology design, IMPACT of Computing in Science and Engineering, 4 (1992), 315-345.  doi: 10.1016/0899-8248(92)90005-S.  Google Scholar

[2] M. Bendsoe and O. Sigmund, Topology Optimization. Theory, Methods and Applications, Springer-Verlag, Berlin, 2003.   Google Scholar
[3]

P. BeremlijskiJ. HaslingerM. KocvaraR. Kucera and J. V. Outrata, Shape optimization in three-dimensional contact problems with coulomb friction, SIAM Journal on Optimization, 20 (2009), 416-444.  doi: 10.1137/080714427.  Google Scholar

[4]

P. BeremlijskiJ. HaslingerJ. V. Outrata and R. Pathó, Shape optimization in contact problems with coulomb friction and a solution-dependent friction coefficient, SIAM Journal on Control and Optimization, 52 (2014), 3371-3400.  doi: 10.1137/130948070.  Google Scholar

[5]

J. -F. Bonnans and A. Shapiro, Perturbation Analysis of Optimization Problems, Springer Series in Operations Research. Springer-Verlag, New York, 2000. doi: 10.1007/978-1-4612-1394-9.  Google Scholar

[6]

J. F. Bonnans and H. Ramírez, Perturbation analysis of second-order cone programming problems, Mathematical Programming, 104 (2005), 205-227.  doi: 10.1007/s10107-005-0613-4.  Google Scholar

[7]

J. -F. Bonnans, J. C. Gilbert, C. Lemaréchal and C. A. Sagastizábal, Numerical Optimization: Theoretical and Practical Aspects, Springer Science & Business Media, 2006.  Google Scholar

[8]

A. L. Dontchev and R. T. Rockafellar, Characterizations of strong regularity for variational inequalities over polyhedral convex sets, SIAM Journal on Optimization, 6 (1996), 1087-1105.  doi: 10.1137/S1052623495284029.  Google Scholar

[9]

A. L. Dontchev and R. T. Rockafellar, Implicit Functions and Solution Mappings, Springer Monographs in Mathematics. Springer, Dordrecht, 2009. doi: 10.1007/978-0-387-87821-8.  Google Scholar

[10]

D. DorschW. Gómez and V. Shikhman, Sufficient optimality conditions hold for almost all nonlinear semidefinite programs, Mathematical Programming, 158 (2016), 77-97.  doi: 10.1007/s10107-015-0915-0.  Google Scholar

[11]

G. Inc, Gurobi Optimizer Reference Manual. Version 6.5, 2016. Google Scholar

[12]

R. HenrionA. Jourani and J. Outrata, On the calmness of a class of multifunctions, SIAM Journal on Optimization, 13 (2002), 603-618.  doi: 10.1137/S1052623401395553.  Google Scholar

[13]

N. J. Higham, Optimization by direct search in matrix computations, SIAM J. Matrix Anal. Appl., 14 (1993), 317-333.  doi: 10.1137/0614023.  Google Scholar

[14] R. A. Horn and C. R. Johnson, Matrix Analysis, Cambridge University Press, Cambridge, 2013.   Google Scholar
[15]

F. Jarre, Elementary optimality conditions for nonlinear SDPs, in Handbook on Semidefinite, Conic and Polynomial Optimization (eds. M. Anjos and J. Lasserre), Springer, 166 (2012), 455-470. doi: 10.1007/978-1-4614-0769-0_16.  Google Scholar

[16]

C. Kanzow and A. Schwartz, Mathematical programs with equilibrium constraints: Enhanced fritz john-conditions, new constraint qualifications, and improved exact penalty results, SIAM Journal on Optimization, 20 (2010), 2730-2753.  doi: 10.1137/090774975.  Google Scholar

[17]

M. KočvaraM. Zibulevsky and J. Zowe, Mechanical design problems with unilateral contact, M2AN Mathematical Modelling and Numerical Analysis, 32 (1998), 255-281.  doi: 10.1051/m2an/1998320302551.  Google Scholar

[18]

M. Kočvara, M. Kružík and J. V. Outrata, On the control of an evolutionary equilibrium in micromagnetics, in Optimization with multivalued mappings, Springer, 2 (2006), 143-168. doi: 10.1007/0-387-34221-4_8.  Google Scholar

[19]

M. Kočvara and J. V. Outrata, Optimization problems with equilibrium constraints and their numerical solution, Mathematical Programming, 101 (2004), 119-149.  doi: 10.1007/s10107-004-0539-2.  Google Scholar

[20]

A. Korányi, Monotone functions on formally real Jordan algebras, Mathematische Annalen, 269 (1984), 73-76.  doi: 10.1007/BF01455996.  Google Scholar

[21]

J. Löfberg, YALMIP : A toolbox for modeling and optimization in MATLAB, in Proceedings of the 2004 IEEE International Symposium on Computer Aided Control Systems Design, Taipei, Taiwan, 2004,284-289. Google Scholar

[22] Z.-Q. LuoJ.-S. Pang and D. Ralph, Mathematical Programs with Equilibrium Constraints, Cambridge University Press, 1996.  doi: 10.1017/CBO9780511983658.  Google Scholar
[23]

B. S. Mordukhovich, Variational Analysis and Generalized Differentiation Ⅰ: Basic Theory, vol. 330, Springer Science & Business Media, 2006.  Google Scholar

[24]

B. S. MordukhovichN. M. Nam and N. T. Yen Nhi, Partial second-order subdifferentials in variational analysis and optimization, Numerical Functional Analysis and Optimization, 35 (2014), 1113-1151.  doi: 10.1080/01630563.2014.895747.  Google Scholar

[25]

B. S. Mordukhovich and J. V. Outrata, Coderivative analysis of quasi-variational inequalities with applications to stability and optimization, SIAM Journal on Optimization, 18 (2007), 389-412.  doi: 10.1137/060665609.  Google Scholar

[26]

B. S. Mordukhovich and R. T. Rockafellar, Second-order subdifferential calculus with applications to tilt stability in optimization, SIAM Journal on Optimization, 22 (2012), 953-986.  doi: 10.1137/110852528.  Google Scholar

[27]

MOSEK ApS, The MOSEK Optimization Toolbox for MATLAB Manual. Version 7. 1 (Revision 28), 2015, URL http://docs.mosek.com/7.1/toolbox/index.html. Google Scholar

[28]

J. V. Outrata, M. Kočvara and J. Zowe, Nonsmooth Approach to Optimization Problems with Equilibrium Constraints: Theory, Applications and Numerical Results, vol. 28, Springer Science & Business Media, 1998. doi: 10.1007/978-1-4757-2825-5.  Google Scholar

[29]

J. V. Outrata and H. Ramírez C, On the Aubin property of critical points to perturbed second-order cone programs, SIAM Journal on Optimization, 21 (2011), 798-823.  doi: 10.1137/100807168.  Google Scholar

[30]

J. V. Outrata and D. Sun, On the coderivative of the projection operator onto the second-order cone, Set-Valued Analysis, 16 (2008), 999-1014.  doi: 10.1007/s11228-008-0092-x.  Google Scholar

[31] R. T. Rockafellar and R. J.-B. Wets, Variational Analysis, Springer, Berlin-Heidelberg, 1998.  doi: 10.1007/978-3-642-02431-3.  Google Scholar
[32]

H. Scheel and S. Scholtes, Mathematical programs with equilibrium constraints: Stationarity, optimality and sensitivity, Mathematics of Operations Research, 25 (2000), 1-22.  doi: 10.1287/moor.25.1.1.15213.  Google Scholar

[33]

H. Schramm and J. Zowe, A version of the bundle idea for minimizing a nonsmooth function: Conceptual idea, convergence analysis, numerical results, SIAM Journal on Optimization, 2 (1992), 121-152.  doi: 10.1137/0802008.  Google Scholar

show all references

References:
[1]

W. AchtzigerM. BendsoeA. Ben-Tal and J. Zowe, Equivalent displacement based formulations for maximum strength truss topology design, IMPACT of Computing in Science and Engineering, 4 (1992), 315-345.  doi: 10.1016/0899-8248(92)90005-S.  Google Scholar

[2] M. Bendsoe and O. Sigmund, Topology Optimization. Theory, Methods and Applications, Springer-Verlag, Berlin, 2003.   Google Scholar
[3]

P. BeremlijskiJ. HaslingerM. KocvaraR. Kucera and J. V. Outrata, Shape optimization in three-dimensional contact problems with coulomb friction, SIAM Journal on Optimization, 20 (2009), 416-444.  doi: 10.1137/080714427.  Google Scholar

[4]

P. BeremlijskiJ. HaslingerJ. V. Outrata and R. Pathó, Shape optimization in contact problems with coulomb friction and a solution-dependent friction coefficient, SIAM Journal on Control and Optimization, 52 (2014), 3371-3400.  doi: 10.1137/130948070.  Google Scholar

[5]

J. -F. Bonnans and A. Shapiro, Perturbation Analysis of Optimization Problems, Springer Series in Operations Research. Springer-Verlag, New York, 2000. doi: 10.1007/978-1-4612-1394-9.  Google Scholar

[6]

J. F. Bonnans and H. Ramírez, Perturbation analysis of second-order cone programming problems, Mathematical Programming, 104 (2005), 205-227.  doi: 10.1007/s10107-005-0613-4.  Google Scholar

[7]

J. -F. Bonnans, J. C. Gilbert, C. Lemaréchal and C. A. Sagastizábal, Numerical Optimization: Theoretical and Practical Aspects, Springer Science & Business Media, 2006.  Google Scholar

[8]

A. L. Dontchev and R. T. Rockafellar, Characterizations of strong regularity for variational inequalities over polyhedral convex sets, SIAM Journal on Optimization, 6 (1996), 1087-1105.  doi: 10.1137/S1052623495284029.  Google Scholar

[9]

A. L. Dontchev and R. T. Rockafellar, Implicit Functions and Solution Mappings, Springer Monographs in Mathematics. Springer, Dordrecht, 2009. doi: 10.1007/978-0-387-87821-8.  Google Scholar

[10]

D. DorschW. Gómez and V. Shikhman, Sufficient optimality conditions hold for almost all nonlinear semidefinite programs, Mathematical Programming, 158 (2016), 77-97.  doi: 10.1007/s10107-015-0915-0.  Google Scholar

[11]

G. Inc, Gurobi Optimizer Reference Manual. Version 6.5, 2016. Google Scholar

[12]

R. HenrionA. Jourani and J. Outrata, On the calmness of a class of multifunctions, SIAM Journal on Optimization, 13 (2002), 603-618.  doi: 10.1137/S1052623401395553.  Google Scholar

[13]

N. J. Higham, Optimization by direct search in matrix computations, SIAM J. Matrix Anal. Appl., 14 (1993), 317-333.  doi: 10.1137/0614023.  Google Scholar

[14] R. A. Horn and C. R. Johnson, Matrix Analysis, Cambridge University Press, Cambridge, 2013.   Google Scholar
[15]

F. Jarre, Elementary optimality conditions for nonlinear SDPs, in Handbook on Semidefinite, Conic and Polynomial Optimization (eds. M. Anjos and J. Lasserre), Springer, 166 (2012), 455-470. doi: 10.1007/978-1-4614-0769-0_16.  Google Scholar

[16]

C. Kanzow and A. Schwartz, Mathematical programs with equilibrium constraints: Enhanced fritz john-conditions, new constraint qualifications, and improved exact penalty results, SIAM Journal on Optimization, 20 (2010), 2730-2753.  doi: 10.1137/090774975.  Google Scholar

[17]

M. KočvaraM. Zibulevsky and J. Zowe, Mechanical design problems with unilateral contact, M2AN Mathematical Modelling and Numerical Analysis, 32 (1998), 255-281.  doi: 10.1051/m2an/1998320302551.  Google Scholar

[18]

M. Kočvara, M. Kružík and J. V. Outrata, On the control of an evolutionary equilibrium in micromagnetics, in Optimization with multivalued mappings, Springer, 2 (2006), 143-168. doi: 10.1007/0-387-34221-4_8.  Google Scholar

[19]

M. Kočvara and J. V. Outrata, Optimization problems with equilibrium constraints and their numerical solution, Mathematical Programming, 101 (2004), 119-149.  doi: 10.1007/s10107-004-0539-2.  Google Scholar

[20]

A. Korányi, Monotone functions on formally real Jordan algebras, Mathematische Annalen, 269 (1984), 73-76.  doi: 10.1007/BF01455996.  Google Scholar

[21]

J. Löfberg, YALMIP : A toolbox for modeling and optimization in MATLAB, in Proceedings of the 2004 IEEE International Symposium on Computer Aided Control Systems Design, Taipei, Taiwan, 2004,284-289. Google Scholar

[22] Z.-Q. LuoJ.-S. Pang and D. Ralph, Mathematical Programs with Equilibrium Constraints, Cambridge University Press, 1996.  doi: 10.1017/CBO9780511983658.  Google Scholar
[23]

B. S. Mordukhovich, Variational Analysis and Generalized Differentiation Ⅰ: Basic Theory, vol. 330, Springer Science & Business Media, 2006.  Google Scholar

[24]

B. S. MordukhovichN. M. Nam and N. T. Yen Nhi, Partial second-order subdifferentials in variational analysis and optimization, Numerical Functional Analysis and Optimization, 35 (2014), 1113-1151.  doi: 10.1080/01630563.2014.895747.  Google Scholar

[25]

B. S. Mordukhovich and J. V. Outrata, Coderivative analysis of quasi-variational inequalities with applications to stability and optimization, SIAM Journal on Optimization, 18 (2007), 389-412.  doi: 10.1137/060665609.  Google Scholar

[26]

B. S. Mordukhovich and R. T. Rockafellar, Second-order subdifferential calculus with applications to tilt stability in optimization, SIAM Journal on Optimization, 22 (2012), 953-986.  doi: 10.1137/110852528.  Google Scholar

[27]

MOSEK ApS, The MOSEK Optimization Toolbox for MATLAB Manual. Version 7. 1 (Revision 28), 2015, URL http://docs.mosek.com/7.1/toolbox/index.html. Google Scholar

[28]

J. V. Outrata, M. Kočvara and J. Zowe, Nonsmooth Approach to Optimization Problems with Equilibrium Constraints: Theory, Applications and Numerical Results, vol. 28, Springer Science & Business Media, 1998. doi: 10.1007/978-1-4757-2825-5.  Google Scholar

[29]

J. V. Outrata and H. Ramírez C, On the Aubin property of critical points to perturbed second-order cone programs, SIAM Journal on Optimization, 21 (2011), 798-823.  doi: 10.1137/100807168.  Google Scholar

[30]

J. V. Outrata and D. Sun, On the coderivative of the projection operator onto the second-order cone, Set-Valued Analysis, 16 (2008), 999-1014.  doi: 10.1007/s11228-008-0092-x.  Google Scholar

[31] R. T. Rockafellar and R. J.-B. Wets, Variational Analysis, Springer, Berlin-Heidelberg, 1998.  doi: 10.1007/978-3-642-02431-3.  Google Scholar
[32]

H. Scheel and S. Scholtes, Mathematical programs with equilibrium constraints: Stationarity, optimality and sensitivity, Mathematics of Operations Research, 25 (2000), 1-22.  doi: 10.1287/moor.25.1.1.15213.  Google Scholar

[33]

H. Schramm and J. Zowe, A version of the bundle idea for minimizing a nonsmooth function: Conceptual idea, convergence analysis, numerical results, SIAM Journal on Optimization, 2 (1992), 121-152.  doi: 10.1137/0802008.  Google Scholar

Figure 1.  Two-bar truss
Figure 2.  Two solutions of the $3\times 3$ truss design problem with all nodes connected
Figure 3.  Five-by-three truss (Ex. 2): initial layout and optimal design
Figure 4.  Five-by-five truss (Ex. 3): initial layout and optimal design
Figure 5.  Five-by-five truss (Ex. 3): optimal load and corresponding design as computed by BTNCLC with INI1 (left) and INI3 (right)
Table 1.  Results of Example 2. The last columns show the number of iterations needed to obtain the value of the objective function smaller than $10^{-3}$-$10^{-6}$ and (the last column) to fulfill the stopping criterion
method INI $c^*$number of iterations to reach
$10^{-3}$ $10^{-4}$ $10^{-5}$ $10^{-6}$ $c^*$
BTNCLC 1 $2.4\cdot 10^{-8}$ 23 36 50 63 88
BTNCLC 2 $2.0\cdot 10^{-8}$ 6 15 25 43 64
BTNCLC 3 $7.6\cdot 10^{-8}$ 9 11 16 23 26
NMSMAX 1 $7.7\cdot 10^{-6}$ 547 1018 3631 - 6617
NMSMAX 2 $1.5\cdot 10^{-4}$ 694 - - - 4406
NMSMAX 3 $5.7\cdot 10^{-6}$ 33 66 106 - 192
method INI $c^*$number of iterations to reach
$10^{-3}$ $10^{-4}$ $10^{-5}$ $10^{-6}$ $c^*$
BTNCLC 1 $2.4\cdot 10^{-8}$ 23 36 50 63 88
BTNCLC 2 $2.0\cdot 10^{-8}$ 6 15 25 43 64
BTNCLC 3 $7.6\cdot 10^{-8}$ 9 11 16 23 26
NMSMAX 1 $7.7\cdot 10^{-6}$ 547 1018 3631 - 6617
NMSMAX 2 $1.5\cdot 10^{-4}$ 694 - - - 4406
NMSMAX 3 $5.7\cdot 10^{-6}$ 33 66 106 - 192
Table 2.  Results of Example 3. The last columns show the number of iterations needed to obtain the value of the objective function smaller than $10^{-3}$-$10^{-6}$ and (the last column) to fulfill the stopping criterion
method INI $c^*$number of iterations to reach
$10^{-3}$ $10^{-4}$ $10^{-5}$ $10^{-6}$ $c^*$
BTNCLC 1 $2.6\cdot 10^{-7}$ 67 92 111 313 143
BTNCLC 2 $4.8\cdot 10^{-8}$ 9 29 46 71 99
BTNCLC 3 $4.4\cdot 10^{-1}$ - - - - 11
NMSMAX 1 $5.3\cdot 10^{-3}$ - - - - 13487
NMSMAX 2 $1.7\cdot 10^{-2}$ - - - - 7850
NMSMAX 3 $2.0\cdot 10^{-6}$ 68 157 171 - 207
method INI $c^*$number of iterations to reach
$10^{-3}$ $10^{-4}$ $10^{-5}$ $10^{-6}$ $c^*$
BTNCLC 1 $2.6\cdot 10^{-7}$ 67 92 111 313 143
BTNCLC 2 $4.8\cdot 10^{-8}$ 9 29 46 71 99
BTNCLC 3 $4.4\cdot 10^{-1}$ - - - - 11
NMSMAX 1 $5.3\cdot 10^{-3}$ - - - - 13487
NMSMAX 2 $1.7\cdot 10^{-2}$ - - - - 7850
NMSMAX 3 $2.0\cdot 10^{-6}$ 68 157 171 - 207
[1]

Predrag S. Stanimirović, Branislav Ivanov, Haifeng Ma, Dijana Mosić. A survey of gradient methods for solving nonlinear optimization. Electronic Research Archive, 2020, 28 (4) : 1573-1624. doi: 10.3934/era.2020115

[2]

Alberto Bressan, Sondre Tesdal Galtung. A 2-dimensional shape optimization problem for tree branches. Networks & Heterogeneous Media, 2020  doi: 10.3934/nhm.2020031

[3]

M. S. Lee, H. G. Harno, B. S. Goh, K. H. Lim. On the bang-bang control approach via a component-wise line search strategy for unconstrained optimization. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 45-61. doi: 10.3934/naco.2020014

[4]

Mohammed Abdulrazaq Kahya, Suhaib Abduljabbar Altamir, Zakariya Yahya Algamal. Improving whale optimization algorithm for feature selection with a time-varying transfer function. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 87-98. doi: 10.3934/naco.2020017

[5]

Xuemei Chen, Julia Dobrosotskaya. Inpainting via sparse recovery with directional constraints. Mathematical Foundations of Computing, 2020, 3 (4) : 229-247. doi: 10.3934/mfc.2020025

[6]

Min Chen, Olivier Goubet, Shenghao Li. Mathematical analysis of bump to bucket problem. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5567-5580. doi: 10.3934/cpaa.2020251

[7]

Vieri Benci, Sunra Mosconi, Marco Squassina. Preface: Applications of mathematical analysis to problems in theoretical physics. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020446

[8]

Shasha Hu, Yihong Xu, Yuhan Zhang. Second-Order characterizations for set-valued equilibrium problems with variable ordering structures. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020164

[9]

Yining Cao, Chuck Jia, Roger Temam, Joseph Tribbia. Mathematical analysis of a cloud resolving model including the ice microphysics. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 131-167. doi: 10.3934/dcds.2020219

[10]

Martin Kalousek, Joshua Kortum, Anja Schlömerkemper. Mathematical analysis of weak and strong solutions to an evolutionary model for magnetoviscoelasticity. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 17-39. doi: 10.3934/dcdss.2020331

[11]

Stefan Doboszczak, Manil T. Mohan, Sivaguru S. Sritharan. Pontryagin maximum principle for the optimal control of linearized compressible navier-stokes equations with state constraints. Evolution Equations & Control Theory, 2020  doi: 10.3934/eect.2020110

2019 Impact Factor: 1.233

Metrics

  • PDF downloads (48)
  • HTML views (101)
  • Cited by (0)

Other articles
by authors

[Back to Top]