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.

learn more… | top users | synonyms (5)

5
votes
1answer
261 views

Complexity of a quadratic program

I have a quadratic program: $$\displaystyle\min_{\mathbf{X}} (\mathbf{X^TQX +C^TX}) \quad{} \text{subject to} \quad{} \mathbf{A X \leq Y}$$ $\mathbf{Q}$ is positive definite and is $N \times N$, ...
0
votes
1answer
325 views

extremum values of a function in three variables

Consider the function $f:\mathbb{R}^3\rightarrow \mathbb{R}$ is given by $$f(x,y,z)=y^2+xyz+x^6$$ Does the function have a local maximum or a minimum at the origin? My question is is there a ...
2
votes
1answer
99 views

Approximating a function with a convex function

Let $f:\mathbb{R} \rightarrow \mathbb{R}$ be a continuous, differentiable function. Is there a known algorithm that fits $f$ with $g$, which is an order-$n$ polynomial that is convex, in the least ...
2
votes
2answers
137 views

How to derive function for least square?

i want to use least square to find x and y that minimize the result of the following function for a series of points (xi,yi) -> (x1,y1), (x2,y2),...: note: y = f(x) ...
6
votes
0answers
199 views

Subgradient of convex minimization duality

$$\min(f_0(x))$$ $$\text{s.t. }f_i(x) \le y_i \forall i, i = 1 ,\ldots, m$$ $$f_i : \text{convex};\quad x : \text{variable}$$ It is also considered that $g(y)$ is the optimal value of the problem ...
3
votes
0answers
42 views

Show that maximisers are in corners

Let $\Pi$ be a rectangle $[a,b] \times [c,d]$ containing $0$: $a < 0 < b$, $c < 0 < d$, let $f(x)$ be a convex continuous function on $\Pi$. Define a functional $$ J(x_1,x_2,x_3) = p_1 ...
3
votes
1answer
147 views

Is it possible to replace function by its concave envelope

Let $f(x) \in C[-1,2]$. Consider an optimization problem $$ J[\mu] = \int\limits_{-1}^{2}f(x) \, \mu(dx) \to \max\limits_{\mu - \text{Borel probability measure}} $$ with restriction $$ ...
1
vote
1answer
118 views

Creating a model

Here's a seemingly simple pondering. If one item is more valuable the higher it is (i.e., $a=5$ is worth more than $a=2$) and another item is more valuable the lower it is (i.e., $b=2$ is worth more ...
10
votes
3answers
303 views

Find the maximum and minimum of $\sum_{i=1}^{n-1}x_ix_{i+1}$ subject to $\sum_{i=1}^nx_i^2=1$.

Find the maximum and minimum of $$ \sum_{i=1}^{n-1}x_ix_{i+1} $$ subject to $$ \sum_{i=1}^nx_i^2=1 $$ for all $n\in\mathbb{N}-\{1,0\}$.
1
vote
1answer
47 views

maximize $-\sum_{i=1}^n \log \left( \lambda_i + \kappa \right) - \sum_{i=1}^n \frac{c_i}{\lambda_i + \kappa}$

Trying to find the maximum of a log-likelihood, for a parameter in a covariance function. I end up with the following problem, that should be concave if my calculations are correct, \begin{align} ...
4
votes
0answers
81 views

Find optimal measure

Let $\Omega$ be a convex compact set in $\mathbb{R}^n$, $f\colon \Omega \to \mathbb{R}$ be a convex function. Consider an optimization problem $$ \int\limits_{\Omega}f(x)\,\mu(dx) \to ...
1
vote
1answer
51 views

Minima of a function

Let $F:\mathbb{R}\times \mathbb{R} \rightarrow \mathbb{R}.$ Is $\inf_{x,y} F(x,y)$ always equal to $\inf_{x} \inf_{y} F(x,y)$?
3
votes
0answers
120 views

Gradient descent for the Thomson problem

I'm trying to solve the Thomson Problem, i.e we have $N$ repelling point charges on a (hyper)sphere of dimension $m$ and we want to determine which configuration gives the lowest energy. We thus want ...
1
vote
0answers
240 views

Gradient Descent for Primal Kernel SVM with Soft-Margin(Hinge) Loss

Given the primal objective $$F({\bf a})=L\sum_{i,j}a_{i}a_{j}k(x_i,x_j) + \sum_{i}max(0, 1-y_i \sum_{j}a_jk(x_i,x_j)$$ for the soft margin SVM, where ${\bf a}=(a_1,...,a_N)$, N being the number of ...
2
votes
2answers
177 views

find minimum of a function with abs and squares analytically

maybe someone here can help me. I want to find the analytical minimum '$x_\mathrm{opt} = \arg\min f(x)$' of the following function: $$ f(x) = \alpha |c + x| + \beta x^2 $$ where $x$ is a real number ...
0
votes
2answers
1k views

Questions that can be solved using Excel.

I recently started to realize that Excel is a powerful tool that can solve many problems. What interesting mathematics problems are there can be solved using excel? I am looking for a set of ...
3
votes
0answers
88 views

Dynamic optimization problem.

My starting equations are the following: $V^{e}=w+\beta.((1-s).V^{e}+s.V^{u}(t))\\V^{u}(t)=\begin{matrix} \\max \\a(t) ...
2
votes
1answer
72 views

Optimizing a physician's medical test plan

I have come across the following optimization problem: "A patient presents himself with symptoms to a physician. The physician has a set of $n$ medical tests, where each test $i$ has costs $c_i$ ...
3
votes
0answers
48 views

Optimal way to place a given number of points in a region?

Let $A\subset\mathbb{R}²$ and $n\in\mathbb{N}$ be a given natural number. How to find a finite subset of $A$, $P=${$p_1,...,p_n$} such that $\int_A f_P(x)$ is minimum, where $f_P(x) = ...
1
vote
1answer
160 views

How to Minimize this Function?

Let $f\in C([0,1])$ and $K\subset C([0,1])$ be the set of constant functions on $[0,1]$. Let $\|u\|=\sup\{|u(x)|:\ x\in [0,1]\}$. Define $F:C([0,1])\rightarrow \mathbb{R}$ by $$F(g)=\|f-g\|$$ ...
4
votes
1answer
185 views

Shortest curve that divides circle into two regions of equal area

Of all the curves that divide the circle into two regions with the same area, is the diameter the shortest one?
1
vote
2answers
2k views

Real world well formulated examples of non linear optimization problems

I'm trying to find around the web some real world examples of non linear optimization problems. I currently need examples of: Non restringed optimziation ( $\max$/$\min$ $f(x)$ for ...
3
votes
1answer
107 views

Local Maximum of a function

In a problem, I'm asked to find the local maximum of the function: $$ \rho_v = (\rho^2 - 10^{-4})z\sin(2\phi) $$ over the solid: \begin{align*} 0.005 &\leq \rho \leq 0.02 \\ 0 &\leq \phi \leq ...
5
votes
2answers
173 views

Non-convex optimization: $\min ||y-Ax||_p$ for very small $p$ given that $||x||_2=1$

I need to find $x$ that minimizes the cost function $\|y-Ax\|_p$ when $p$ is close to $0$, subject to the constraint $\|x\|_2=1$ where $x$ and $y$ are vectors in $\mathbb{R}^n$ and $A$ is an $n\times ...
3
votes
1answer
98 views

Optimize a symmetric polynomial on a compact set

This looks like a stupid question, but the obvious answer (if there is one) eludes me … Let $f(x,y)$ be a symmetric polynomial in $x$ and $y$. Then $f$ attains a minimum $m$ on the compact set ...
8
votes
2answers
1k views

Optimization of the area of a cross inscribed in a circle

I've really been scratching my head over this optimization problem. "Consider a symmetric cross inscribed in a circle of radius $r$." The length from the center of the cross to the middle of one of ...
1
vote
0answers
308 views

Linear programming: writing a problem with artificial variables?

Use artificial variables to write a linear programming problem in canonical form with non-negative resource vector whose solution will determine whether there exists (and if so, find) non-negative ...
1
vote
0answers
77 views

Why is primal feasibility for equality constraints a KKT condition?

Given that $h_{i}(x) = 0$ and $g_j(x) \le 0$ are the constraints, observe the gradient of the Lagrangian: $\nabla [f_0(x) + \sum_{i=1}^m\lambda_ih_i(x) + \sum_{j=1}^n\mu_jg_j(x)]$ Each of the ...
1
vote
0answers
128 views

How to represent and handle eigenvalue constraint in optimization

For example consider the problem $\min_X f(X)$ s.t. $\lambda_i(X+A)=\lambda_i(B)$ for $i \in {1,...,N}$ where $A$ and $B$ are full rank N by N matrix, $\lambda_i(X)$ is the i-th eigenvalue of $X$ ...
1
vote
2answers
1k views

derivative of a determinant of a matrix with respect to an element that appears many times in the matrix

I've been trying to find material on matrix calculus but it seems hard to find ones with understandable proofs. I'm doing research work and I am trying to verify some computation. Suppose that I have ...
1
vote
1answer
30 views

My numbers don't feel right on this maximization question.

If Jack is going to construct a rectangular dog pen and divide it into 3 equal subpens (with two fences inside parallel to one side). What is the maximum area of the overall pen if he only has 240 ...
2
votes
3answers
322 views

Applied Optimization of the addition of two positive numbers.

Find the positive number x such that the sum of x and its reciprocal is as small as possible. I'm having a bit of an issue with this one. The answer in my textbook says x=1, but I can't figure ...
3
votes
1answer
158 views

Regularity Conditions for Constrained Optimization

Question: Let $G$ be a convex mapping from $\Omega \subseteq X$ into a normed space $Z$, and assume that $P \subseteq Z$ be a positive cone with nonempty interior. Show that the following two ...
4
votes
1answer
179 views

A variant of assignment problem (different sizes of sets)

I'm given objects divided into two disjoint sets, $A$ and $B$. There's a cost function defined, so that I know a positive cost (or distance) of any assignment $(a,b)\;|\;a \in A,\; b \in B$. It always ...
1
vote
1answer
239 views

Garden optimization problem

I want to build a garden patch and the east and west sides of the fence cost $4\$$ per feet and the the north and south side costs $2\$$ a feet. My budget is $80\$$. What's the largest area that can ...
0
votes
0answers
201 views

Optimization of Light transmission

A window is in the form of a rectangle surmounted by a semicircle. The rectangle is made of clear glass, whereas the semicircle is of tinted glass that transmits only half as much light per ...
2
votes
3answers
307 views

Volume Optimization

The postal service will accept a box for shipment only if the sum of its length and girth (the distance around) does not exceed 108 inches. What dimensions will give a box with a square end the ...
2
votes
1answer
357 views

A variation of the Assignment Problem

In the following Wikipedia article about the Assignment Problem in the Example section, it says: Similar tricks can be played in order to allow more tasks than agents, tasks to which multiple ...
3
votes
2answers
87 views

Quadratic function values through iterative updates

Suppose a function $$f(x)=\frac{1}{2}x^TAx-b^Tx$$ is given, for some symmetric $A\in\mathbb{R}^{n\times n}$ for which all off-diagonal entries of A are nonpositive, and every diagonal entry of A is ...
0
votes
1answer
165 views

Convex optimization problem to quadratic programming problem

Briefly, have the following problem: \begin{equation} \sum_{i = 0}^n a_i \ (max [ F_i( \bar x ), 0 ] )^2 \rightarrow min, \\\\ s.t.\\\\ A \bar x \leq b \end{equation} where $ F( \bar x ) $ is a ...
1
vote
1answer
109 views

Is this use of the simplex method correct?

I am trying to implement a simplex algorithm for solving LP task. I will post the question and my solution as well - what I need to know is whether my solution is correct, thanks in advance! ...
15
votes
4answers
367 views

Maximize $x_1x_2+x_2x_3+\cdots+x_nx_1$

Let $x_1,x_2,\ldots,x_n$ be $n$ non-negative numbers ($n>2$) with a fixed sum $S$. What is the maximum of $x_1x_2+x_2x_3+\cdots+x_nx_1$?
2
votes
1answer
868 views

Optimizing integral functionals using Matlab

I am looking for some bibliography regarding solving integral optimization problems numerically (preferably using Matlab). I want to solve problems of the type $$ \min_{r \in A} \int_a^b ...
3
votes
3answers
189 views

Finding the minimum of $\frac pq + \frac rs$ for distinct integers $p, q, r, s$ from $\{1,2,3,4,5,\ldots,16,17\}$

Here is the question: Four distinct integers $p$, $q$, $r$ and $s$ are chosen from the set $\{1, 2, 3, 4, 5, \ldots, 16, 17\}$. The minimum possible value of $\frac pq + \frac rs$ can be written ...
0
votes
1answer
274 views

Maximizing the Determinant Function

Let $M_{n}$ denote the set of $n\times n$ real matrices. Let $c>0$ be a real number and denote by $X_1,X_2,...,X_n$ the lines of the matrix $X\in M_n$. Let $\|X_i\|$ denote the euclidian norm of ...
1
vote
1answer
287 views

Using Lagrange multipliers for restricted extrema

Consider the function $f(x,y) = x^2 + xy + y^2$ defined on the unit disc $D = \{(x,y) \mid x^2 + y^2 \leq 1\}$. I can not simplify the equations to the point where I find a constant for the lagrange ...
1
vote
0answers
47 views

Optimizing a matrix

input: $b_1,b_2,...,b_n$ positive integers. $a_1<a_2<...a_n$ positive integers output: positive integer I'm given $b_1$ columns of the form ...
0
votes
2answers
113 views

Minimizing The Cost

I have this exercise that I would like anyone to suggest the required steps in order to solve it A cylindrical can is to be made to hold $250 \pi\; cm^3$. Find the dimensions of the can that will ...
1
vote
1answer
40 views

Approximation in $L^2$

Let $G$ be a domain assumed smooth enough. I want to show that the mean value $m$ is minimizing $ m \rightarrow \| f-m\|_{ L^2(G)} $ for $ f \in L^2(G)$. Is it unique? Is it allowed to derive under ...
0
votes
1answer
71 views

Optimize the matrix of “mis-ties” by adding|subtracting a number to|from a whole row|column

Preface: There is a net of $N$ almost-straight paths on an aerial map. Some of them intersect with another. At the points of intersection there are possibly a "mis-tie", which is expressed as a ...