MARC

 008260126s2025        us                              c    eng  d
■001000017359445
■00520260202105120
■006m          o    d                
■007cr#unu||||||||
■020    ▼a9798291548028
■035    ▼a(MiAaPQ)AAI32238220
■040    ▼aMiAaPQ▼cMiAaPQ
■0820  ▼a620
■1001  ▼aZhou,  Dekun.
■24510▼aAlgorithms  for  Sparsity-Constrained  Optimization  Problems  -  On  Polynomial  Solvability  and  Approximability
■260    ▼a[Sl]▼bThe  University  of  Wisconsin  -  Madison▼c2025
■260  1▼aAnn  Arbor▼bProQuest  Dissertations  &  Theses▼c2025
■300    ▼a161  p
■500    ▼aSource:  Dissertations  Abstracts  International,  Volume:  87-02,  Section:  B.
■500    ▼aAdvisor:  Del  Pia,  Alberto.
■5021  ▼aThesis  (Ph.D.)--The  University  of  Wisconsin  -  Madison,  2025.
■520    ▼aThe  optimization  problem  of  finding  a  solution  with  a  limited  number  of  nonzero  entries,  known  as  a  sparsity-constrained  optimization  problem,  has  garnered  considerable  attention;  however,  it  is  generally  regarded  as  an  NP-hard  problem.  This  thesis  investigates  various  types  of  sparsity-constrained  optimization  problems,  such  as  the  Sparse  Integer  Least  Square  problem  (SILS)  and  the  Sparse  PCA  problem  (SPCA).  Due  to  their  computational  complexity,  it  is  not  feasible  to  efficiently  solve  these  problems  with  arbitrary  inputs.  Nevertheless,  we  present  relaxation  techniques  that  can  be  solved  in  polynomial  time,  providing  provable  approximation  bounds  to  the  original  problems.  Furthermore,  we  demonstrate  that  our  proposed  relaxations  are  sufficiently  tight  to  solve  the  original  problems  for  several  input  classes,  and  hence  our  results  shed  light  on  the  applicability  of  these  methods  in  real-world  scenarios.  In  the  first  part  of  the  thesis,  we  study  SILS.  Our  study  involves  the  derivation  of  an  l1-based  semidefinite  programming  (SDP)  relaxation,  along  with  a  randomized  algorithm  that  can  handle  a  broader  class  of  binary  quadratic  programs  with  cardinality  constraint.  We  also  establish  sufficient  conditions  under  which  our  SDP  relaxation  can  successfully  solve  SILS,  which  we  demonstrate  through  the  analysis  of  two  important  special  cases:  the  feature  extraction  problem  and  the  integer  sparse  recovery  problem.  In  the  second  part,  we  study  SPCA.  We  introduce  a  randomized  algorithm  based  on  the  basic  SDP  relaxation  of  SPCA,  provide  provable  approximation  bounds,  and  demonstrate  that  the  basic  SDP  relaxation  is  resilient  to  adversarial  perturbations  in  certain  statistical  models,  and  so  do  our  algorithm.  In  the  third  part,  we  further  our  investigation  into  SPCA.  We  introduce  a  plug-and-play  framework  that  accelerates  most  existing  SPCA  algorithms  while  incurring  only  a  negligible  loss  in  accuracy.  The  framework  leverages  a  key  structural  property  of  SPCA:  when  the  covariance  matrix  is  block-diagonal,  the  global  SPCA  problem  splits  into  independent  SPCA  sub-problems,  allowing  substantial  speed-ups.
■590    ▼aSchool  code:  0262.
■650  4▼aEngineering
■650  4▼aSystems  science
■653    ▼aApproximation  algorithm
■653    ▼aMixed-integer  optimization
■653    ▼aRandomized  algorithm
■653    ▼aSparse  optimization
■690    ▼a0796
■690    ▼a0537
■690    ▼a0790
■71020▼aThe  University  of  Wisconsin  -  Madison▼bIndustrial  Engineering.
■7730  ▼tDissertations  Abstracts  International▼g87-02B.
■790    ▼a0262
■791    ▼aPh.D.
■792    ▼a2025
■793    ▼aEnglish
■85640▼uhttp://www.riss.kr/pdu/ddodLink.do?id=T17359445▼nKERIS▼z이  자료의  원문은  한국교육학술정보원에서  제공합니다.

미리보기

내보내기

chatGPT토론

Ai 추천 관련 도서