Minimizing under argmin constraint

Question

I have a problem in the form

$$\begin{aligned} \min_a f(a,b)\\ \text{s.t.}\ b =\ & \arg\min_c g(a,c)\\ & \text{s.t.}\ H(a,c) \leq \vec{0} \end{aligned}$$

where $f, g, H$ are all linear functions. Actually, if there are multiple $c$ such that the $\arg\min$ is optimal, then any of them is ok as a choice for $b$.

I want to solve this problem (to optimality) and analyze its behavior. However, I don't know how to modelize that in standard solvers. Is there a way to convert this to a more standard setting?

Actually, I even don't know what is the form of the space formed by the solutions of the argmin problem depending on $a$. I.e., if we pose $$\begin{aligned} p(a) & = & \arg\min_c g(a,c)\\ & &\text{s.t.}\ H(a,c) \leq \vec{0} \end{aligned}$$

(let's assume $c$ is unique here)

Are there known properties of $p(a)$?

Answer 1

Presuming all variables are continuous, and given that the inner and outer level problems are both Linear, this is the simplest type of Bilevel optimization problem.

A standard formulation is to replace the argmin with the inner LP KKT (optimality) conditions. Because of the complementarity constraint in the KKT conditions, this gives rise to a (non-convex) Linear Complementarity Problem (LCP).

There are LCP solvers which can be used.

Alternatively, the complementarity constraint can be linearized by introduction of binary variables and use of Big M to convert this into a MLIP. This requires however a priori bounds on the Lagrange Multipliers, which can be problematic. However, use of indicator constraints in a MILP solver could avoid this. Or you could provide the LCP directly to a non-convex quadratic(ally-constrained) solver, such as Gurobi, which can handle all that tricky stuff itself under the hood, likely better than you would on your own. Or use any other solver having built-in special handling for complementarity constraints, of which there are several.

Answer 2

If you are willing to roll the dice and use numerical methods to find a good, hopefully maybe possibly optimal solution, there are definitely ways to do that. The mission is to solve $$\min_a q(a)$$ where $q(a) = f(a, p(a))$ and evaluation of $q(a)$ for a given value of $a$ involves solving a linear program. I would be inclined to use dual simplex, or to solve the dual LP, since at each iteration you will be altering the right-hand side of the original LP.

For the outer problem, you could try any of a variety of derivative-free optimization methods. Some of them (genetic algorithms and particle swarm optimization) require large numbers of function evaluations (meaning here solving lots of LPs), so I think I would try something like Nelder-Mead first. Assuming your chosen algorithm converges reasonably quickly, you could consider running it multiple times with different starting points, possibly in parallel.

Addendum: Another possibility is gradient descent. Start with a feasible value $\hat{a}$ for $a$ and solve the LP for $p(a).$ Using the inverse of the basis matrix, you can express $p(a)$ as a linear function of $a$ (locally). Substitute that linear function into the second argument of $f()$ to get $q(a)$ as a (locally) linear function of $a.$ Calculate the gradient of that function and negate it to get a search direction in the $a$ space. Go back to the LP and calculate how far from $\hat{a}$ you can go in that direction before either the problem becomes infeasible or a pivot is required. Go that far to get a new value $\tilde{a}$ for $a$ and, depending on what stopped you from going further, either project the negative gradient on the constraint(s) that you were about to violate to see if you can descend further with that basis or pivot as indicated and see if you can descend with the next basis. I suspect this will require fewer LP solutions than something like Nelder-Mead, and you will typically be able to update the LP solution using a small (?) number of dual simplex pivots.