Computational Methods in Optimization

David Gleich

Purdue University

Spring 2026

Course number CS-52000

Tuesday, Thursday 9:00-10:15

Location Forney B124

Homework 4

Please answer the following questions in complete sentences in a clearly prepared manuscript and submit the solution by the due date on Gradescope.

Remember that this is a graduate class. There may be elements of the problem statements that require you to fill in appropriate assumptions. You are also responsible for determining what evidence to include. An answer alone is rarely sufficient, but neither is an overly verbose description required. Use your judgement to focus your discussion on the most interesting pieces. The answer to "should I include 'something' in my solution?" will almost always be: Yes, if you think it helps support your answer.

Problem 0: Homework checklist

• Please identify anyone, whether or not they are in the class, with whom you discussed your homework. This problem is worth 1 point, but on a multiplicative scale.

• Make sure you have included your source-code and prepared your solution according to the most recent EdStem note on homework submissions.

Problem 1: Log-barrier terms

The basis of a class of methods known as interior point methods is that we can handle non-negativity constraints such as $\vx \ge 0$ by solving a sequence of unconstrained problems where we add the function $b(\vx; \mu) = -\mu \sum_i \log(x_i)$ to the objective. Thus, we convert $$\MINone{}{f(\vx)}{\vx \ge 0}$$ into $$\MIN{}{f(\vx) + b(\vx; \mu).}$$

1. Explain why this idea could work. (Hint: there's a very useful picture you should probably show here!)

2. Write a matrix expression for the gradient and Hessian of $f(\vx) + b(\vx; \mu)$ in terms of the gradient vector $g(\vx)$ and the Hessian matrix $\mH(\vx)$ of $f$.

3. Use an LLM to prepare a report on this idea. Focus on answering the question: is there anything special about $\log$ that makes it especially useful here? For instance, are there other functions that could work and give you the same effect? Would $\log$ be superior? Try and find at least one paper that describes an alternative to log-barrier terms for this purpose and explain what they found.

Problem 2: Inequality constraints

1. Draw a picture of the feasible region for the constraints: $$\bmat{1 - 2 x_1 - x_2 \\ 1 - x_1 + x_2 \\ 1 + x_1 - 3 x_2 \\ 1 + x_1 + x_2} \ge 0.$$

2. Prove that a set of linear inequalities result in a convex feasible set.

Problem 3: Necessary and sufficient conditions

Let $f(\vx) = \frac{1}{2} \vx^T \mQ \vx - \vx^T \vc$.

1. Write down the necessary conditions for the problem: $$\MINone{}{f(\vx)}{\vx \ge 0}.$$

2. Write down the sufficient conditions for the same problem.

3. Consider the two-dimensional case with $$\mQ = \bmat{2 & 3 \\ 3 & 2} \qquad \vc = \bmat{-1.5 \\ 1.5}.$$ Determine the solution to this problem by any means you can, and justify your work.

4. Produce a Julia or hand illustration of the solution showing the function contours, and gradient. What are the active constraints at the solution? What is the value of $\lambda$ in $\mA^T \lambda = \vg$?

5. What changes when we set $\mQ = \bmat{-2 & 3 \\ 3 & -2}$?

Problem 4: Constraints can make a non-smooth problem smooth.

Show that

$$\MIN{}{\sum_i \max (\va_i^T \vx - b_i, 0.5)}$$

can be reformulated as a constrained optimization problem with a continuously differentiable objective function and both linear equality and inequality constraints.

(Optional) Problem 5: Bound constrained least squares

One of the most common variations on least squares and constraints is the non-negative least squares problem: $$\MINone{}{ \normof{\vb - \mA \vx} }{\vx \ge 0.}$$ This is a general instance of a equality and bound-constrained least squares problem $$\MINtwo{}{ \normof{\vb - \mA \vx} }{\mC\vx = \vd}{\vl \le \vx \le \vu.}$$ (Note that $\vl$ could be $-\infty$ and $\vu$ could be $\infty$) Work with an LLM to develop the necessary optimality conditions for this problem, and also a set of sufficient conditions. Develop a finite time algorithm for it as well that would be suitable for problems where $\vx$ only has a few dimensions (e.g. less than 10). Come up and test one idea to make the solver faster. Finally, work with the LLM to explain why we can solve these bound-constrained least squares problems in polynomial time, but cannot solve the problem $$\MAXone{}{\vx^T \mA \vx}{\ve^T \vx = 1, \vx \ge 0}$$ in polynomial time