# Questions tagged [optimization]

Questions about problems that entail selecting the best element from some set of available alternatives, and methods to solve them.

1,254 questions
Filter by
Sorted by
Tagged with
25 views

### Proof of Fundamental Lower Bound on Regret

Online Convex Optimization sees optimization as a continuous process in which the algorithm learns new aspects of the problem and improves upon. Every iteration consists of the player making a ...
28 views

### Does Warnsdorff’s algorithm for Knight’s tour problem always gives complete tour

I have implemented the basic algorithm. easily available but I am not getting the complete tour. The visited square never equals N * N;
25 views

### Rectangle Packing with Constraints

I am aware that the general rectangle packing problem is NP-hard. I am trying to form an estimate for a version of the problem with constraints. Consider fitting rectangles of smaller size into a ...
19 views

### How to maximize the number of filled grid squares in a partially filled grid with Tetris shapes

So here's the problem: -You are given a partially filled grid of size mxn (represented by a matrix of 1s and 0s where a 1 signifies that grid square is occupied by a block and a 0 signifies that grid ...
16 views

### How do i code Steepest Descent in python? [closed]

I am very confused and really need help to code with Steepest Descent method. I have a pseudo code for it( see picture).
55 views

15 views

### Is there a high-level framework from which all known search and optimization algorithms can be derived?

The fields of applied math and computer science are inundated with optimization algorithms, variations on those optimization algorithms, and variations on those variations. I'm mainly talking about ...
23 views

### Modifying the genetic algorithm

I have a multi-objective optimization problem (NP-complete). To solve it, I've decided to use the genetic algorithm. I have 3 "areas" of optimization, say parameters ...
37 views

### Is Newton's algorithm really this much better than conjugate gradient descent?

I have a function I'm minimizing. I'm using conjugate gradient descent and the Newton algorithm. I am experiencing that the Newton algorithm is absurdly faster. Like, it finishes it 5-6 iterations, ...
27 views

### Select certain number of column elements of a stochastic matrix, maximum one element per row

Consider a $m \times n$ Matrix. Every column represents a class and every row an observation. Every row/observation is a probability distribution, hence every row sums up to 1. We now want to choose ...
31 views

### Sorting algorithm for set of elements, when I have comparison of just some pairs not all of them

Is there some kind of algorithm for sorting of set, when there is comparison of just some pairs? Example 1: set(a, b, c, d, e) pairs(a>b, ce) Example 2: set(a, b, c, d, e) pairs(a>b, d>b, c>d, d>e)...
36 views

### About Steiner tree problem in graphs

In the paper (p. 3) and the slides presents the formulation of the Steiner problem on graphs via so called Steiner cuts. But according to the definition, the number of Steiner cuts and so the ...
48 views

### How to partition disagreeable people into compatible groups

We have a number of people that must be partitioned into groups, but there may be people that dislike other individuals. Partition the people into the minimum number of groups such that no person is ...
27 views

### How to effectively represent and generate 2D cellular automaton rules that are invariant under rotation and reflection of the input matrix?

Consider cellular automaton rules for a two-dimensional universe with two states, where a cell's new state can depend on its previous state and the states of the cells in its Moore neighborhood. Such ...
193 views

### If a convex optimization problem can be NP-Hard, in what sense are convex problems easier than non-convex problems?

Being new to the OR and Optimization world, I've always assumed that a problem being convex meant that it can be solved in polynomial time. Now I am learning that a convex optimization problem can ...
38 views

### Algorithm Design: Efficient O(n) algorithm to get the ith to jth largest elements in an array

I am trying to design an efficient algorithm that retrieves the ith to jth largest elements in an array. For example, if the following array is the input: ...
The question is: given an array of size $n$ and a number $m$, now our goal is to find AT MOST $m$ contiguous subarrays such that the sum of all these subarrays is the largest. It is also required that ...
I am looking for an algorithm in $O(N^2)$ that finds the maximum value that be obtained from a sequence of real numbers greater than 0 (e.g. $\{ 1, 2, 3 , 4\}$) by inserting a plus ($+$) or ...