Mathematics Stack Exchange
Mathematics Stack Exchange

Questions tagged [optimization]

Optimization is the process of choosing the "best" value among possible values. They are often formulated as questions on the minimization/maximization of functions, with or without constraints.

In mathematics, computer science, economics, or management science, mathematical optimization (alternatively, optimization or mathematical programming) is the selection of a best element (with regard to some criteria) from some set of available alternatives.

An optimization problem can be represented in the following way: given a function $f:A\to\mathbb{R}$ from some set $A$ to the real numbers, we want to find an element $x_0\in A$ such that $f(x_0)\le f(x)$ for all $x \in A$ ("minimization") or such that $f(x_0)\ge f(x)$ for all $x \in A$ ("maximization").

22512 questions
1
vote
1 answer

Can this integer programming problem be converted into another with nonnegative cost coefficients?

Suppose there is an integer programming problem: $$\min_{x_i \in \{0,1 \}, i=1,\cdots,k} \sum_{i=1}^k c_i x_i$$ subject to $$ \sum_{i=1}^k a_i x_i \leq W. $$ Suppose the cost coefficients are negative, i.e., $c_i < 0, i=1, \cdots, k$. I was…
Tim
  • 47,382
1
vote
2 answers

Maximizing the Sum of Cubes

I have ten variables, $x_1$ through $x_{10}$. $-1 \leq x_i \leq 1$, and $\sum x_i = 0$. What is the maximum of $\sum x_i^3$? I've tried to use Lagrange multipliers, but writing the restricted domain as a constraint seems, if not impossible, then…
Duncan Ramage
  • 6,928
  • 1
  • 20
  • 38
1
vote
2 answers

Find a point that minimizes the sum squared difference of the distances to a set of other points

I have n points in Euclidean space $\{\mathbf{a_1}, \mathbf{a_2}, ... , \mathbf{a_n}\}$, and the desired distances to them $\{d_1, d_2, ..., d_n\}$. How can I find the optimal point $\mathbf{x}$ that minimizes $\sum_{i=1}^n [\lVert \mathbf{x} -…
Chaoping
  • 11
1
vote
0 answers

Optimize integration volume under integral constraint

I am trying to solve an optimization problem and I am almost sure there exist some theorem which already does it: Let there be two probability density functions: $f_1(x_1,x_2...x_d),f_2(x_1,x_2...x_d)$ The d dimension space V can be is divided…
etamar
  • 11
1
vote
0 answers

Gradient of L 2,1 norm w.r.t a matrix

I have previously asked this question but did not get a response. Maybe it was because tag was wrong. I deleted the previous one and asking this again. I have this cost function: $$f(X)=||AX||_{2,1}$$ I want to derive $$\nabla_X f(X)$$ I have done…
strahd
  • 111
  • 1
  • 7
1
vote
1 answer

Minimizing L2 norm of a vector

This will be more of a verbal question. What does finding the vector that minimizes L2 norm of that vector mean, logically? (which is bounded by another condition). Do I find the vector with numerically closest entries? This question is actually…
strahd
  • 111
  • 1
  • 7
1
vote
1 answer

Convex sets and algebraic operations

If $A$ is convex set and $\alpha,\beta>0$, show that $(\alpha+\beta)Α=\alpha Α+\beta Α$. I tried to show that, but I am not sure if it was so simple. This is how I did it: $$(\alpha+\beta)Α := \left\{z:z=(\alpha+\beta)x,\,x\in A\right\}$$ $\alpha Α…
gorica
  • 15
  • 2
1
vote
4 answers

Finding Local Minimizers using KKT points (in a degenerate case)

Consider the problem $$ \begin{split} \min_{x\in \mathbb{R}^2}\ & x_1^4 -2x_2^2-x_2 \\ \text{subject to }\ & x_1^2+x_2^2+x_2\leq 0 \end{split} $$ I have found that the point $x$ with $x_1 = 0, x_2 = -0.25$ is a KKT point with corresponding…
Dman
  • 345
  • 1
  • 6
1
vote
1 answer

Minimize a function in two variables with constraint

I have to minimize this: \begin{align*} \min&\quad{ (x-3)^2+(y-1)^2} \\ s.t.& \quad 2x+y \leq 2 \\ &\quad x^2 + 2y = 3\\ &\quad x, y \geq 0 \end{align*} Can I isolate $y$ in the second constraint and substitute it in the first?
Valentina Sau
  • 57
1
vote
0 answers

Confusion related to complexity of least squares problem

I have this confusion about the time complexity of least squares problem. Suppose minimize $||Ax-b||^2$ Analytical solution = $x^* = (A^TA)^{-1}A^Tb$ computational time proportional to $n^2k$, $A \in \mathbb{R}^{k\times n}$ I didn't get how the…
user34790
  • 4,192
1
vote
0 answers

Find values that minimize weighted ratio errors

Let's say I am given $\left \{ \phi_{ij}, \mu_{ij} \mid 0 < \phi_{ij}, \mu_{ij} \in \mathbb{Q} \wedge i,j \in \{1,..,n\} \right \}$ and I want to find or approximate $\alpha_{1},..,\alpha_{n}$ such that $\left | \sum_{\forall i,j} (\phi_{ij} -…
user1588931
  • 11
1
vote
2 answers

Minimize $z=3x_1+2x_2$

Minimize $z=3x_1+2x_2$ s.t $2x_1+x_2\geq 10$ $-3x_1+2x_2\leq 6$ $x_1+x_2\geq 6$ $x_1,x_2 \geq 0$ The feasible area is : link how can I find graphically that the answer is $(4,2)$?
newhere
  • 3,115
1
vote
0 answers

Limit and minimization

For a given coefficient $\alpha \in \mathbb{R}$, I have to find a minimizer of $$ \min_{x \in \mathbb{R}, y \in \mathbb{R}} f(x,y) + \alpha [x \not= y], $$ where $[.]$ is the Iverson bracket, returning $1$ if its argument is true and $0$ otherwise.…
user153330
  • 11
1
vote
0 answers

Pontryagin's maximum principle with state constraints at specific points but they are not initial and final points

i am solving Pontryagin's Maximum Principle (PMP) but in my case x(t0) are fixed instead of x(tf), it is x(t1) is fixed where as t1 is some point which lies between t0 and tf. How can i solve such a problem..should i first solve from to to t1 and…
yasir naeem
  • 11
1
vote
2 answers

can not find root of the equation

$(0,0)$ with semi-major axis a and semi-minor axis $b$"> I want find out for each point $(x,y)$ in the white region, the nearest point $(a \cos \theta, b \sin \theta )$ on the ellipse curve.I tried with the following approach. $$ \text {distance} =…
cseju19
  • 71
  • 6
1 2 3
…
97 98