Consider DC programming problems as the form below<\/p>\n
minimize ![\"{](\"https:\/\/s0.wp.com\/latex.php?latex=%7B+f+%7D_%7B+0+%7D%28x%29-%7B+g+%7D_%7B+0+%7D%28x%29+&bg=ffffff&fg=000&s=0&c=20201002\")
subject to ![\"{](\"https:\/\/s0.wp.com\/latex.php?latex=%7B+f+%7D_%7B+1+%7D%28x%29-%7B+g+%7D_%7B+1+%7D%28x%29+%5Cle%C2%A0+0%2C%5Cquad+i%3D1%2C...m%2C%C2%A0&bg=ffffff&fg=000&s=0&c=20201002\")
where ![\"x\in](\"https:\/\/s0.wp.com\/latex.php?latex=x%5Cin+%7B+R+%7D%5E%7B+n+%7D+&bg=ffffff&fg=000&s=0&c=20201002\")
![\"{](\"https:\/\/s0.wp.com\/latex.php?latex=%7B+f+%7D_%7B+i+%7D%3A%7B+R+%7D%5E%7B+n+%7D%5Crightarrow+R+&bg=ffffff&fg=000&s=0&c=20201002\")
![\"{](\"https:\/\/s0.wp.com\/latex.php?latex=%7B+g+%7D_%7B+i+%7D%3A%7B+R+%7D%5E%7B+n+%7D%5Crightarrow+R+&bg=ffffff&fg=000&s=0&c=20201002\")
![\"i=0,...,m](\"https:\/\/s0.wp.com\/latex.php?latex=i%3D0%2C...%2Cm+&bg=ffffff&fg=000&s=0&c=20201002\")
![\"{](\"https:\/\/s0.wp.com\/latex.php?latex=%7B+f+%7D_%7B+0+%7D%28x%29+&bg=ffffff&fg=000&s=0&c=20201002\")
![\"{](\"https:\/\/s0.wp.com\/latex.php?latex=%7B+g+%7D_%7B+0+%7D%28x%29+&bg=ffffff&fg=000&s=0&c=20201002\")
What if the objective and contraint fuctions are not convex? For example, the Boolean LP probem proposed in this section and the traveling salesman probelm, no polynomial time algorithm is known and are hard to solve. So here convex-concave procedure (CCP) is presented for finding a local optimum to solve convex-optimization problems.<\/p>\n
Assuming that all of the\u00a0![\"{](\"https:\/\/s0.wp.com\/latex.php?latex=%7B+f+%7D_%7B+i+%7D+&bg=ffffff&fg=000&s=0&c=20201002\")
![\"{](\"https:\/\/s0.wp.com\/latex.php?latex=%7B+g+%7D_%7B+i+%7D+&bg=ffffff&fg=000&s=0&c=20201002\")
- \n
- Convexify:
<\/li>\n
- Solve: Set
to the solution of the original problem<\/li>\n
- k=k+1<\/li>\n<\/ul>\n
In the paper, one reasonal stopping criterion is proposed as
, where
is threshold. Here as we discussed in the class, the stop criterion can be further improved.<\/p>\n
The paper proves that each iteration of the algorithm produces a feasible point. It also shows that the convex-concave procedure is indeed a descent algorithm. However, the proof of convergence is ambiguous as negative infinity does not exist.\u00a0The section 1 provides us an idea to generally convert problem with non-convex contraints to one that can be solved using convex optimzation. The basic idea is to minimize a function, usually use linear approximations to the contraints.<\/p>\n
Then the authors go on to show the advantages of CCP which are retaining more information in each of the iterates and are global wihout requiring trust regionswhich limit progress at an iteration to a region where the approximation is valid. The proof of this is shown<\/p>\n
convexification at
: replace\u00a0
with<\/p>\n
<\/p>\n
Since\u00a0
for all x, no trust region is needed.<\/p>\n
- \n
- true objective at\u00a0
is better than convexified objective<\/li>\n
- true feasible set contains feasible set for convexified problem<\/li>\n<\/ul>\n
<\/p>\n
<\/p>\n
<\/p>\n
<\/p>\n","protected":false},"excerpt":{"rendered":"
The section 1 of paper “Variations and extension of the convex\u2013concave procedure” provides an overview of convex-concave problem . The convex-concave procedure (CCP) is a heuristic method used to find local optimum solutions to difference of covex (DC) programming problems. Difference of convex programming Consider DC programming problems as the form below minimize subject to … Continue reading Convex-Concave Procedure<\/span><\/a><\/p>\n","protected":false},"author":123,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[1],"tags":[],"class_list":["post-246","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/p9CQAE-3Y","_links":{"self":[{"href":"https:\/\/wordpress.cs.vt.edu\/optml\/wp-json\/wp\/v2\/posts\/246","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/wordpress.cs.vt.edu\/optml\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/wordpress.cs.vt.edu\/optml\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/wordpress.cs.vt.edu\/optml\/wp-json\/wp\/v2\/users\/123"}],"replies":[{"embeddable":true,"href":"https:\/\/wordpress.cs.vt.edu\/optml\/wp-json\/wp\/v2\/comments?post=246"}],"version-history":[{"count":42,"href":"https:\/\/wordpress.cs.vt.edu\/optml\/wp-json\/wp\/v2\/posts\/246\/revisions"}],"predecessor-version":[{"id":291,"href":"https:\/\/wordpress.cs.vt.edu\/optml\/wp-json\/wp\/v2\/posts\/246\/revisions\/291"}],"wp:attachment":[{"href":"https:\/\/wordpress.cs.vt.edu\/optml\/wp-json\/wp\/v2\/media?parent=246"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/wordpress.cs.vt.edu\/optml\/wp-json\/wp\/v2\/categories?post=246"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/wordpress.cs.vt.edu\/optml\/wp-json\/wp\/v2\/tags?post=246"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
- true objective at\u00a0