Optimization Problems With Solutions Pdf

[Astryd Boschee]

Althoughwe endeavor to make our web sites work with a wide variety of browsers, we can only support browsers that provide sufficiently modern support for web standards. Thus, this site requires the use of reasonably up-to-date versions of Google Chrome, FireFox, Internet Explorer (IE 9 or greater), or Safari (5 or greater). If you are experiencing trouble with the web site, please try one of these alternative browsers. If you need further assistance, you may write to he...@aps.org.

We show how the localization landscape, originally introduced to bound low-energy eigenstates of disordered wave media and many-body quantum systems, can form the basis for hardware-efficient quantum algorithms for solving binary optimization problems. Many binary optimization problems can be cast as finding low-energy eigenstates of Ising Hamiltonians. First, we apply specific perturbations to the Ising Hamiltonian such that the low-energy modes are bounded by the localization landscape. Next, we demonstrate how a variational method can be used to prepare and sample from the peaks of the localization landscape. Numerical simulations of problems of up to ten binary variables show that the localization landscape-based sampling can outperform quantum approximate optimization algorithm (QAOA) circuits of similar depth, as measured in terms of the probability of sampling the exact ground state.

Localization landscape, u, of Ĥ for N=10 qubits as constructed in Eq. (9), compared with the four lowest-energy states of ĤIsing for (a) a randomly generated QUBO instance (nondegenerate case) and (b) a randomly generated three-regular MaxCut problem (degenerate case). The peaks of the landscape function correspond to the low-energy eigenstates of ĤIsing.

There are many optimization problems in which the variables are symmetric in the objective and the constraints; i.e., you can swap any two variables, and the problem remains the same. Let's call such problems symmetric optimization problems. The optimal solution for a symmetric optimization problem - like many of the ones that show up in calculus texts - frequently has all variables equal. To take some simple examples,

However, it is not true that every symmetric optimization problem has all variables equal at optimality. For example, the problem of minimizing $x +y$ subject to $x^2 + y^2 \geq 1$ and $x, y \geq 0$ has $(0,1)$ and $(1,0)$ as the optimal solutions.

The Monthly article "Do symmetric problems have symmetric solutions?" by William Waterhouse discusses this issue. For global optimality one really needs strong global constraints on the objective function, such as convexity (as in Igor's answer), and there's nothing one can say otherwise. However, local results hold in considerably greater generality. Waterhouse calls this the Purkiss Principle: in a symmetric optimization problem, symmetric points tend to be either local maxima or local minima.

This is one of those results where finding the right statement is the real issue, and once the statement has been found it takes just a few lines to prove it. In his article, Waterhouse builds up to this formulation in several steps, and he shows how it encompasses various more concrete cases and applications. He also gives a wonderful historical overview.

If the representation on the tangent space is reducible, then the Purkiss Principle can fail. If we break the representation into a direct sum of irreducible subrepresentations, then the Hessian matrix for $f$ will have an eigenvalue for each irreducible (with multiplicity equal to the dimension of the irreducible), and there's no reason why they should all have the same sign. However, this decomposition is nevertheless very useful for doing local calculations, because even if $M$ is high-dimensional, $T_x M$ may decompose into just a few irreducibles.

So the upshot is this: if you are applying the second derivative test to a symmetric optimization problem, then representation theory will tell you what the symmetry implies, and irreducibility leads to the simplest possible answer.

The most common condition for symmetry in my experience is convexity: if the feasible region is symmetric and convex, and the objective function is convex, it is immediate that argmin has all variables equal (or invariant by whatever your symmetry group is).

There are many optimization problems that are known to be NP-hard, such as the traveling salesman problem, MAX-SAT, or finding the minimum chromatic number of a graph. Given a problem of this sort, I'm curious about the complexity of the following problem:

Intuitively, it seems like this might be co-NP hard, since it's easy to refute an answer to an optimization problem by guessing a better solution and using it as a witness, but I have no idea how to show this. In fact, I don't really know how to reason about the complexity of this problem.

For instance, I can't see what precludes decision problems from being considered NP-hard optimization problems - if you consider, say, the MAX-CNF-SAT problem with the solutions being scored as floor(k/N), where k is the number of satisfied clauses and N is the total number of clauses in the instance (which is clearly computable in polynomial time), then any valuation which yields a 1 in this formula will have to satisfy the whole formula. So let's assume that we are maximizing floor(k/N) and call this the FLOOR-CNF-SAT optimization problem:)

This implies you can reduce TAUTOLOGY to said optimization problem - negate the input and add any solution as S. You can even add a dummy variable to make sure the initial solution is gets a 0 in the FLOOR-CNF-SAT problem. Negation is polynomial in time.

Then if a solver for the proposed problem deems S to not be optimal, there must clearly be a valuation which yields a 1 according to our crafted function and thus satisfies the whole formula - in turn providing a valuation that does not satisfy the original input to TAUTOLOGY.

I don't really feel great about this reduction but I can't easily improve on the problem class. If you require that there be instances which score arbitrarily high and not just 0, 1, I could just use N * floor(k/N). An improvement to the class could be to only consider a problem an NP-hard optimization problem if for each K there exists an instance that has at least K solutions which all score differently.

where S is the negated input. As an initial valuation I choose d1, ..., dN = false, but as a score I give a function that returns 2N - 1 if the first N clauses are all false, otherwise it returns the number of satisfied clauses. Such a function would only return 2N if all the clauses were satisfied but could easily have at least N distinct values.

I am afraid that without some complicated regularity conditions on the scoring function this is the best we can get, unless you consider the definition of an NP-hard optimization problem to be 'a problem for which, given a candidate solution S, we can in polynomial time verify whether S is optimal', in which case 'is-optimal' is clearly P and it's no fun at all:/

Because S is a candidate solution; given that there are no other S in which S can be proven to be greedy or less optimal than any other S. It must be that S is at current the MOST optimal solution for the problem.

I am slightly confused by some terminology I have encountered regarding the complexity of optimization problems. In an algorithms class, I had the large parsimony problem described as NP-complete. However, I am not exactly sure what the term NP-complete means in the context of an optimization problem. Does this just mean that the corresponding decision problem is NP-complete? And does that mean that the optimization problem may in fact be harder (perhaps outside of NP)?

In particular, I am concerned about the fact that while an NP-complete decision problem is polynomial time verifiable, a solution to a corresponding optimization problem does not appear to be polynomial time verifiable. Does that mean that the problem is not really in NP, or is polynomial time verifiability only a characteristic of NP decision problems?

You have to be careful when carrying over the concepts from decision problems. It can be done and a precise notion of NP-completeness for optimization problems can be given. Look at this answer. It is of course different from the NP-completeness for decision problems, but it is based on the sames ideas (reductions).

If you want to verify that a solution is not just feasible, but also optimal, I would say that this is as hard as solving the original optimization problem because, in order to refute a given feasible and possibly optimal solution as non-optimal, you have to give a better solution, which might require you to find the true optimal solution.

For the relation between decision and optimization (search) problems, take a peek at Bellare and Goldwasser's The Complexity of Decision versus Search, SIAM Journal of Computing 23(1), feb 1994. In a nutshell: If the decision problem is NP-complete, the search problem is hard too, and can be solved calling the decision problem's solver a polynomial number of times.

You can easily define NP-hard optimisation problems: We call a decision problem D NP-hard if any decision problem in NP can be reduced to D in polynomial time. And we can use the same definition for any problem P: P is NP-hard if any decision problem in NP can be reduced to P in polynomial time.

The reason most optimization problems can be classed as P, NP, NP-complete, etc., is the Kuhn-Tucker conditions. I'll talk in terms of linear-programming problems, but the KTC apply in many other optimization problems. For each optimization problem there is a dual. If the goal in the original problem is to maximize some function, then the dual (usually) has a function to be minimized.* Feasible, but non-optimal solutions to the original problem will be infeasible/invalid for the dual problem, and vice-versa. If, and only if, a solution is feasible for the primary and dual, it is an optimal solution for both. (Technically, may be one of a large number of optimal solutions which give the same result.)

3a8082e126