Optimization Problem Pdf

[Riley Dyen]

Foreach combinatorial optimization problem, there is a corresponding decision problem that asks whether there is a feasible solution for some particular measure m0. For example, if there is a graph G which contains vertices u and v, an optimization problem might be "find a path from u to v that uses the fewest edges". This problem might have an answer of, say, 4. A corresponding decision problem would be "is there a path from u to v that uses 10 or fewer edges?" This problem can be answered with a simple 'yes' or 'no'.

In the field of approximation algorithms, algorithms are designed to find near-optimal solutions to hard problems. The usual decision version is then an inadequate definition of the problem since it only specifies acceptable solutions. Even though we could introduce suitable decision problems, the problem is more naturally characterized as an optimization problem.[2]

This is mostly a terminological question: Is there a fundamental difference between "optimization problems" and "search problems"? Apologies if this is an obvious question

I think search problem is to search for a solution (or many solutions) that satisfies a condition.Whereas, Optimization problem is to search for the best solution that satisfies a condition.When the search space becomes large, we can't expect to be able to find out the optimal solution, then we turn the search problem into an optimization problem, with the hope that as searching for the best solution we may find some acceptable one. By doing so, we are using the optimization techniques which do not promise to find the optimal solution, instead of using the search techniques, which always do.

On one hand several sources state that convex optimization is easy, because every local minimum is a global minimum. In this video, starting at 27:00, Stephen Boyd from Stanford claims that convex optimization problems are tractable and in polynomial time.

By some definitions, it seems that a convex integer optimization problem is impossible by definition: the very fact of constraining the variables to integer values removes the convexity of the problem, since for a problem to be convex, both the objective function and the feasible set have to be convex.

A first order approximation is that convex programs are tractable, .i.e., most problems you can think of as a layman in the field that are convex, are (probably) tractable to solve. That's why you would be told that in an introductory course on convex optimization. It is not true though.

Tractability of convex problems essentially boils down to being able to decide if an iterate $x$ is feasible, in a computationally tractable way (having a so called oracle available). There are convex sets for which this isn't the case. One such example if the set of co-positive matrices. If you are trying to find a matrix $M(x)$ such that $z^TM(x)z \geq 0$ for all $z\geq 0$, you have problems, as it is very hard to decide if a candidate $M(x)$ satisfies that property. Compare to the simple case of positive-semidefinite where all $z$ should lead to non-negativity, this is simply an eigenvalue test and thus semidefinite programming is tractable. Alas, also this statement is up for debate, as it depends on what you mean with solving a problem. A semidefinite programming problem with size $n$ (what ever we mean with that) can have a solution whose representation grows at an exponential rate $2^n$.

Regarding the second issue whether an integer problem is convex, the answer is no, and that follows directly from geometry (unless there is only 1 solution). However, as shown by Sam Burer, nononvex mixed-binary quadratic programs can be rewritten as convex optimization over the co-positive cone. Remember from the discussion above though, this only implies we've made a convex reformulation, not that the problem has been made tractable.

The reason the optimization community is going against the pure "mathematical" grain lies in the way that MIPs are solved: to find the best combination of binary variables, the problem is relaxed, e.g. $x\in \0,1\ \rightarrow x \in [0,1]$. In other words, the problem is "made" continuous. If then the objective function and constraints are convex, this relaxed version of the problem is also convex and can be solved in polynomial time. This allows e.g. branch-and-bound algorithms to be computationally sensible, as they have to solve these subproblems many, many times to solve a MIP.

In this section we are going to look at optimization problems. In optimization problems we are looking for the largest value or the smallest value that a function can take. We saw how to solve one kind of optimization problem in the Absolute Extrema section where we found the largest and smallest value that a function would take on an interval.

In this problem we want to maximize the area of a field and we know that will use 500 ft of fencing material. So, the area will be the function we are trying to optimize and the amount of fencing is the constraint. The two equations for these are,

Setting this equal to zero and solving gives a lone critical point of \(y = 125\). Plugging this into the area gives an area of \(A\left( 125 \right) = 31250\,\mboxf\mboxt^2\). So according to the method from Absolute Extrema section this must be the largest possible area, since the area at either endpoint is zero.

Next, the vast majority of the examples worked over the course of the next section will only have a single critical point. Problems with more than one critical point are often difficult to know which critical point(s) give the optimal value. There are a couple of examples in the next two sections with more than one critical point including one in the next section mentioned above in which none of the methods discussed above easily work. In that example you can see some of the ideas you might need to do in order to find the optimal value.

We want to minimize the cost of the materials subject to the constraint that the volume must be 50ft3. Note as well that the cost for each side is just the area of that side times the appropriate cost.

Now we need the critical point(s) for the cost function. First, notice that \(w = 0\) is not a critical point. Clearly the derivative does not exist at \(w = 0\) but then neither does the function and remember that values of \(w\) will only be critical points if the function also exists at that point. Note that there is also a physical reason to avoid \(w = 0\). We are constructing a box and it would make no sense to have a zero width of the box.

Note as well here that provided \(w > 0\), which from a physical standpoint we know must be true for the width of the box, then the volume function will be concave down and so if we get a single critical point then we know that it will have to be the value that gives the absolute maximum.

In this case we can exclude the negative critical point since we are dealing with a length of a box and we know that these must be positive. Do not however get into the habit of just excluding any negative critical point. There are problems where negative critical points are perfectly valid possible solutions.

Now, as noted above we got a single critical point, 1.2910, and so this must be the value that gives the maximum volume and since the maximum volume is all that was asked for in the problem statement the answer is then : \[V\left( 1.2910 \right) = 2.1517\,\mboxm^3\].

Also, as seen in the last example we used two different methods of verifying that we did get the optimal value. Do not get too locked into one method of doing this verification that you forget about the other methods.

As an interesting side problem and extension to the above example you might want to show that for a given volume, \(L\), the minimum material will be used if \(h = 2r\) regardless of the volume of the can.

So, knowing that whatever \(h\) is it must be in the range \(0 \le h \le 5\) we can see that the second critical point is outside this range and so the only critical point that we need to worry about is 1.9183.

Finally, since the volume is defined and continuous on \(0 \le h \le 5\) all we need to do is plug in the critical points and endpoints into the volume to determine which gives the largest volume. Here are those function evaluations.

This problem is a little different from the previous problems. Both the constraint and the function we are going to optimize are areas. The constraint is that the overall area of the poster must be 200 in2 while we want to optimize the printed area (i.e. the area of the poster with the margins taken out).

I am solving a minimization problem under equality and inequality constraints. I solve this problem with COSMO and I get a solution which is the vector alpha_opt=[0 0 0]

But I found another vector which is alpha_test=[1 1 0] which also respects the constraints and such that the objective function is equal to -5.5

Attention conservation notice: Over 7800 words about optimal planning for a socialist economy and its intersection with computational complexity theory. This is about as relevant to the world around us as debating whether a devotee of the Olympian gods should approve of transgenic organisms. (Or: centaurs, yes or no?) Contains mathematical symbols (uglified and rendered slightly inexact by HTML) but no actual math, and uses Red Plenty mostly as a launching point for a tangent.

That dream did not come true, but it never even came close to being implemented; strong forces blocked that, forces which Red Plenty describes vividly. But could it even have been tried? Should it have been?

So far as our current knowledge goes, no. Computing optimal prices turns out to have the same complexity as computing the optimal plan itself 3. It is(so far as I know) conceivable that there is some short-cut to computing prices alone, but we have no tractable way of doing that yet. Anyone who wants to advocate this needs to show that it is possible, not just hope piously.

3a8082e126