ORIE 6326: Projects
Project description
The class will culminate in a final project. These projects will be completed in groups of 1–3 students. We encourage students to work in groups of 3. Undergraduate or masters students who wish to work alone will require special permission from the instructor, as will groups of 4 or more students.
The project can take a number of different forms:
Application. Identify an interesting optimization problem. Explain why it matters. Do you care about speed? accuracy? robustness? Experiment with different formulations and see how well they achieve your goal.
Model. Design a new modeling language to target a new class of problems. Explain how to identify problems of the correct form and parse them for the solver.
Algorithm. Design a new, fast algorithm for a particular problem class, or implement one that has no existing implementation. Compare with previous methods numerically, and analyze convergence.
Software. Contribute code, documentation, examples, and/or tests to an existing open source optimization project. Fixing a substantial issue (on the project's GitHub) or a few minor ones would count as a project.
Project timeline
March 3. Form project groups
March 17. Submit project proposal
March 24. Peer reviews of project proposals due
April 14. Project midterm reports due
April 21. Peer reviews of project midterm reports due
May 10. Project reports due
May 12. Peer reviews of project reports due
Detailed requirements
Project groups. Follow these instructions: 1. Every team member should create an account at https:github.coecis.cornell.edu 2. Submit this form listing your accounts so we can add you to the ORIE 6326 organization 3. Wait 4. Create a repository in the ORIE 6326 organization; give all your team members pull/push permissions. The name of your repository will function as a unique ID for your team; keep it short, memorable, and unchanged for the duration of the course. 5. Write a README for the repository that lists your team members and their NetIDs. It is your responsibility to keep this updated if your team changes. We will use this for grading. (See the “TAs” repository for an example.) 6. (Optional) You can easily work on a public git repo as well; just add a second remote!
To submit a project proposal, midterm report, etc, you'll simply push a file named project_proposal.pdf, project_midterm_report.pdf, etc, to (the root directory of) your repository.
If you're unfamiliar with Github, see these tutorials:
Project proposal. The project proposal should be no more than 2 pages, written in LaTeX. It should identify a problem, and describe an approach (or two) that you plan to use to solve the problem. Justify why the problem is important, and why you think your approach will be successful. As a template, consider answering the questions of the Heilmeyer Catechism, in order.
Proposal Peer review. Do you understand the problem the team proposes to solve? Does it seem important or interesting? Do you think their approach is likely to succeed? What other approaches do you think the group should consider? What do you like about the proposal? What concerns you?
Submit a grade for the proposal via google forms, and submit comments on the proposal by opening an issue on the group's github repo.
We expect your reviews to be at least two paragraphs, and expect that you will provide critical and useful feedback to the team you're reviewing. Concretely, your comments should begin with a two or three sentence summary of the project you're reviewing. Then answer the questions above, describing at least three things you like about the proposal, and three areas for improvement. Make sure to back up your subjective assessments with reasoned, detailed explanations so readers can understand what improvements you're suggesting and how to make them.
Project midterm report. By this time, you should have made some progress in addressing your problem, and should have some idea whether your solution method is likely to be effective. Your project midterm report should be no more than 4 pages, written in LaTeX, and posted in your project repository with the filename “midterm_report.pdf”.
In the report, you should describe your problem in greater detail. Describe the progress you've made towards solving it, and the roadblocks you've encountered. Describe the metrics you will use to quantify the effectiveness of your solution. These might include numerical experiments on real data (for an application), a proof of convergence or numerical experiments (for an algorithm), or unit tests (for software). Finally, explain what remains to be done, and which solution strategies you plan to try during the next month.
Midterm Peer review. Instructions are the same as the first peer review assignment. Submit a grade for the proposal via google forms, and submit comments on the proposal by opening an issue on the group's github repo.
Project final report. The final report should be no more than 8 pages long, include figures and tables. (A bibliography of references you used may be listed on a final 9th page.) In your report, you should describe the problem, why it's important, and describe your solution (if you solved it), or solution strategies that failed (if you didn't) and why they failed. Describe the theory and algorithms you used, and the results you obtained. Do you think they could be improved on? How?
If you used techniques not discussed in class, be sure to describe how they work and provide references so that anyone from the class who reads your paper has the tools to understand it.
Final Peer review. Instructions are the same as the previous peer review assignment.
Submit a grade for (and answer a few more specific questions about) the project here, and submit comments on the proposal by opening an issue on the group's github repo.
Project ideas
Application
Nearly any application is ok, so long as you
analyze its structure (convexity, concavity, sparsity,..), and exploit the structure to solve the problem
write a demo illustrating how to model and solve the problem in your favorite modeling language (or using your own custom package), and contribute it as an example to the appropriate project (eg on Github)
Model
Combining structured and differentiable objectives
parse objectives composed of some differentiable, non-convex parts together with some structured, non-differentiable parts
use automatic differentiation in Jump to compute gradients of non-smooth part and (approximately) solve the composite problem.
Graph form problems (targeting solvers like POGS)
Gradient calculus
can you compute gradients using composition rules?
can you compute the Lipshitz constant using composition rules?
for use with (accelerated) gradient solvers like FISTA
Subgradient calculus
like above, but for subgradients
Prox calculus
like above, but for the prox operator
useful for proximal algorithms and splitting algorithms
Fenchel calculus
like above, but for the fenchel operator
useful for the Frank-Wolfe method and accelerated variants
Convex envelope calculus
can you automatically compute (a lower bound on) the convex envelope of a nonconvex function using composition rules?
useful for global optimization via branch-and-bound
Algorithm
Distributed optimization
Compare consensus algorithms vs diffusion algorithms
First order methods for conic optimization
Implement eg a generalization of the Chambolle Pock method in place of ADMM to solve conic optimization problems (as in, eg, SCS)
Implement Renegar's subgradient method for conic optimization via a fast subgradient method
Homotopy methods for solving optimization problems with nonconvex regularizers
Accelerate a previously unaccelerated method eg using ideas from Allen-Zhu and Hazan
Implement Abernethy and Hazan's method for convex optimization via simulated annealing. Can you use it to beat interior point methods?
Software
Implement a CVX* extension in a different CVX* language
Fix one or two major issues on any open source optimization package
(see any package's Github issue tracker for ideas)