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)

4
votes
2answers
3k views

One vs multiple servers - problem

Consider the following problem: We have a simple queueing system with $\lambda%$ - probabilistic intensity of queries per some predefined time interval. Now, we can arrange the system as a single ...
4
votes
0answers
80 views

Quadratic optimisation with quadratic equality constraints

I would like to solve the following optimisation problem: $\min_{x} (x'Ax)$ subject to $x'Bx = x'Cx = 1$. Where A is symmetric and B and C are diagonal. Does anyone have a suggestion for an ...
4
votes
3answers
1k views

Monotonicity of $\ell_p$ norm

Consider a $n$ dimensional space, it is known (Wikipedia) that for $p>r>0$, we have $$ \|x\|_p\leq\|x\|_r\leq n^{(1/r-1/p)}\|x\|_p. $$ I have two questions about the above inequality. $(\bf 1)...
4
votes
2answers
388 views

Sparsest matrix with specified row and column sums

Given a sequence of row sums $r_1, \ldots, r_m$ and column sums $c_1, \ldots, c_n$, all positive, I'd like to find a matrix $A_{m\times n}$ consistent with the given row and column sums that has the ...
3
votes
2answers
4k views

Maximum area of a triangle in a square

For a given square, consider 3 points on the perimeter to form a triangle. How to prove that: The maximum area of triangle is half the square's. The maximum area of triangle occurs if and only if ...
3
votes
2answers
130 views

Mminimize the integral and obtaining the constants $a$ and $b$

Determine the constants $a$ and $b$ for the integral $$ \int\limits _{0}^{1}(ax+b-f(x))^{2} dx$$ take the smallest possible value if $f(x)=(x^{2}+1)^{-1}$ thanks
3
votes
1answer
147 views

Equivalence of following statements about shortest path problem

We formulate the shortest path problem as follows: We have a directed graph $D=(V,A)$ with length $c_{j}$ for each arrow $e_j$ in $A$ and two special points $s,t\in V$. The node-arc incidence ...
3
votes
0answers
111 views

If this problem is not unbounded, what's wrong in this dual derivation?

In a paper with 100 citation, Robust Support Vector Machine Training via Convex outlier Ablation, a convex relaxation is used. In this paper, a form of robust svm proposed: \begin{align} \min_{0\leq \...
3
votes
0answers
331 views

What is the derivation of the derivative of softmax regression (or multinomial logistic regression)?

Consider the training cost for softmax regression (I will use the term multinomial logistic regression): $$ J( \theta ) = - \sum^m_{i=1} \sum^K_{k=1} 1 \{ y^{(i)} = k \} \log p(y^{(i)} = k \mid x^{(...
3
votes
1answer
53 views

Even distribution of roughly 16 dots in a rectangle

I'm about to grow lettuces on a hydroponic system and I was wondering what would be the ideal pattern to provide each lettuce with the max space. Would it be better to plant them according to a grid ...
3
votes
2answers
101 views

Is this “theorem” true in Optimization Theory?

If I have a function $f(x,y)$ subjected to a region $D$ on the xy-plane, then the extreme values of $f(x,y)$ occurs at the extreme "corners" points of $D$? I remember waaaaaaay back in calculus, if ...
3
votes
3answers
206 views

Find out minimize volume (V) of tetrahedral

I have this problem: On space $ (Oxyz)$ given point $M(1,2,3)$. Plane ($\alpha$) contain point $M$ and ($\alpha$) cross $Ox$ at $A(a,0,0)$; $Oy$ at $B(0,b,0)$; $C(0,0,c)$. Where a,b,c>0 Write the ...
3
votes
2answers
75 views

Absolute value and quadratic programming

I would like to solve the following optimization problem using a quadratic programming solver $$\begin{array}{ll} \text{minimize} & \dfrac{1}{2} x^T Q x + f^T x\\ \text{subject to} & \...
3
votes
2answers
292 views

How is $L_{2}$ Minkowski norm different from $L^{2}$ norm?

I am reading the book Multidimensional Particle Swarm Optimization for Machine Learning and Pattern Recognition. They use $L_{2}$ Minkowski norm (Euclidean) as the distance metric in the feature space ...
3
votes
2answers
217 views

SVD and least squares proof

I've seen it claimed that the solution to the minimization problem $$\underset{\textbf{b}}{\text{argmin}} \ ||\textbf{A} \textbf{b}|$$ subject to a constraint $||\textbf{b}||=1$, is given by first ...
3
votes
2answers
630 views

Minima of symmetric functions given a constraint

If $f(x,y,z,\ldots)$ is symmetric in all variables, (i.e $f$ remains the same after interchanging any two variables), and we want to find the extrema of $f$ given a symmetric constraint $g(x,y,z,\...
2
votes
1answer
1k views

Maximum of product of numbers when the sum is fixed

This is the problem I'm working on. $$\begin{array}{rl} \text{maximize} & (n+\ell+x_1)\cdots (n+\ell+x_{k-1})(\ell + x_k) \\ \text{subject to} & 0 \leq x_1, ..., x_k \leq n \\ & x_1 + \...
2
votes
3answers
535 views

Max perimeter of triangle inscribed in a circle

What is the maximum perimeter of a triangle inscibed in a circle of radius $1$? I can't seem to find a proper equation to calculate the derivative.
2
votes
2answers
229 views

Shortest ternary string containing all ternary strings of length 3?

How can we find/construct the shortest ternary string that contains all ternary strings of length 3? For instance, $120011$ contains $120$, $200$, $001$, and $011$. (The shortest such a string could ...
2
votes
1answer
176 views

Question about Geometric-Harmonic Mean.

Define our Harmonic sequence for two numbers such that \begin{equation} a_{n+1} = \frac{2a_nb_n}{a_n + b_n} \end{equation} and our geometric sequence \begin{equation}b_{n+1} = \sqrt{a_nb_n} \end{...
2
votes
1answer
75 views

linear approximation with respect to L1 norm

I am trying to solve this problem: Find the best $L^1$ linear approximation of $e^x$ on [0,1] i.e. minimize $\int_0^1|e^x-\alpha-\beta x| dx$ any hints how to proceed
2
votes
1answer
1k views

Optimization of a function of two variables.

Suppose we have to minimize a function $f(\mathbf x,\mathbf y)$ where $\mathbf x$, $\mathbf y$ are vectors in Euclidean space. The function is convex in $\mathbf y$ when $\mathbf x$ is kept constant ...
2
votes
2answers
84 views

Convexity of a trace of matrices with respect to diagonal elements

Can we prove that $\mbox{trace}({\bf A} ({\bf P}+{\bf Q})^{-1} {\bf A}^T)$ is a jointly convex function of positive variables $[q_1,q_i,...,q_N]$, where ${\bf Q}=\mbox{diag}(q_1,...,q_N)$, $q_i&...
2
votes
3answers
102 views

Minimize : $\sqrt{(1+{1\over a})(1+{1\over b})}$ subject to $a+b=\lambda$.

Given positive real variables $a$ and $b$, find the minimum of $$f(a,b)=\sqrt{\left(1+{1\over a}\right)\left(1+{1\over b}\right)}$$ subject to $a+b=\lambda$ where $\lambda$ is a constant . [ISI ...
2
votes
1answer
77 views

Definition functions, integrals on $\mathbb R^{|N|}, \mathbb R^{\mathbb R}$

Is there a standard/reasonable way of defining functions on the sets $\mathbb R^{|\mathbb N|}, \mathbb R^{\mathbb R} $. How about defining integrals over these sets? I guess a function on $\mathbb R^{|...
2
votes
3answers
168 views

Maximal area of a triangle

What would be the most elementary proof of the following: A triangle has been drawn inside the circle with radius $r$ and its area is as large as possible. Prove that the triangle is equilateral. I ...
2
votes
1answer
371 views

Does the uniqueness of solutions to convex optimization with linear constraints hold in n>3 dimensions?

This is a repost of an earlier question, where I think I was not clear enough in what I was asking: I am examining the following optimization problem, for which I would like to know if, when a ...
2
votes
1answer
666 views

Preconditioning for an LBFGS

I am working on a high dimensional (N ~ 1000-60000) optimization problem which is currently solved with an LBFGS algorithm. I have experimented with different diagonal preconditioners as I know that ...
2
votes
1answer
55 views

How does one use the 'input/hr' column in the table below in setting up the problem?

I have to set up a linear programming problem corresponding to the following scenario: If my understanding of the problem is correct, I use $mod$: Let $i$ be $A$ or $B$. Let $x$ be amount ...
2
votes
1answer
250 views

Proximal mapping of $f(U) = -\log \det(U)$

This is an assignment problem which I failed to solve in a couple of days. Denote the set of all $n \times n$ symmetric matrices and the set of all $n \times n$ symmetric positive definite matrices ...
2
votes
1answer
212 views

Set convergence and lim inf and lim sup

I'm a bit confused with the general concept of convergence of a sequence of sets. I'm well aware that the limit of a sequence $\{C^{\nu}\}$ exists iff $$\liminf_{\nu \rightarrow \infty} C^{\nu} = \...
2
votes
4answers
113 views

Is the opposite of the Second Derivative Test also true?

Given the Second Derivative Test, one case says : If $f(x_0)''<0$, then $f$ has a local maximum at $x_0$. Is it also true that, if $f$ has a local maximum at $x_0$, $f(x_0)'' < 0$ ?
2
votes
1answer
204 views

minimum lines, maximum points

There are $P$ points in the 2-dimensional plane. Through each point, we draw two orthogonal lines: one horizontal (parallel to x axis), one vertical (parallel to y axis). Obviously, some of these ...
2
votes
1answer
3k views

Find all critical points of $f(x,y) = x^3 - 12xy + 8y^3$ and state maximum, minimum, or saddle points.

Find all critical points of $f(x,y) = x^3 - 12xy + 8y^3$ and state whether the function has a relative minimum, relative maximum, or a saddle at the critical points. So I have: $f_x = 3x^2 -12 y$ ...
1
vote
0answers
130 views

Why these two problems lead to same answers?

Suppose these two problems: Problem 1: $$\min_{X,P} \quad\max_{1\leq l\leq L-1} \quad {|\sum_{1\leq i\leq N_p}^{N_p}x_ie^{\frac{2\pi l}{N}p_i}| \over {\sum_{i=1}^{N_p} x_i^2}} \quad \equiv \quad \...
1
vote
1answer
70 views

minimum possible value of a linear function of n variables

Suppose $x_1,x_2,\ldots,x_n$ are unknowons satisfying the constraint $a_1x_1 + \cdots + a_nx_n ≥ b$, where $a_1, \ldots , a_n, b ≥ 0$. Then the minimum possible value of the expression $c_1x_1 + \...
1
vote
1answer
72 views

Distribute small number of points on a disc

Firstly I strongly know how many similar questions there are here. It's about sets of evenly distributed points inside a circle. If we need a big set of such points, good solutions are: Isocell ...
1
vote
0answers
89 views

Warm start of simplex algorithm after update of constraint matrix

Assume we found an optimal solution $\mathbf{x}_1$ of the linear program \begin{gather} \max \mathbf{n}^T\mathbf{x}\mbox{ s.t. }A\mathbf{x} \leq \mathbf{b}\tag{1} \end{gather} using the simplex ...
1
vote
3answers
138 views

Confounding Lagrange multiplier problem

Optimize $f(x,y,z) = 4x^2 + 3y^2 + 5z^2$ over $g(x,y,z) = xy + 2yz + 3xz = 6$ According to the theorem the gradients must be parallell, $\nabla f = \lambda \nabla g$, so their cross product must ...
1
vote
3answers
446 views

Local optimality of a KKT point.

Consider the problem \begin{equation} \min_x f(x)~~~{\rm s.t.}~~~ g_i(x)\leq 0,~~i=1,\dots,I, \end{equation} where $x$ is the optimization parameter vector, $f(x)$ is the objective function and $g_i(...
1
vote
2answers
181 views

Clarification on optimization problem

While reading a combinatorics paper about packing densities in compositions, I encountered the following optimization problem. Maximize $$f(\alpha_1, \dots, \alpha_5) = \sum_{1 \le i < j <...
1
vote
2answers
329 views

How can I infer a result using primal feasibility, dual feasibility, and complementary slackness?

I am trying to find the minimum of $-x_1$ with restrictions $\bar g\leq\bar 0$ so that $$\bar g=\begin{pmatrix} (x_1+2)^2+(x_2-4)^2-20\\ (x_1+2)^2+x_2^2-20\\ -x_1\end{pmatrix}\leq \begin{pmatrix}0\\...
1
vote
0answers
120 views

extreme value of increasing or decreasing function

From the three problems: one, two and three, it seems that if $f(x)$ is decreasing function with $a+b+c=abc$ or $a + b + c + a b + b c + c a = 1 + a b c$ then the maximum value of $f(a)+f(b)+f(c)$ ...
1
vote
2answers
268 views

Projection of a vector onto the null space of a matrix

I have the following optimization problem: $$ \text{minimize}_x \Vert z - x \Vert^2 \\ \text{subject to } Ax = 0, $$ where $x,z\in \mathbb{C}^N$, and $A\in\mathbb{C}^{M \times N}$. $A$ is a wide ...
1
vote
1answer
196 views

Solving a Non-linear Multivariable System of equations

How would I go about solving a system of nonlinear equations where the highest degree is two? For example: $$f_1(x) = f_1(x_1, x_2,\dots, x_n) = 0,$$ $$f_2(x) = f_2(x_1, x_2,\dots, x_n) = 0,$$ $$\...
1
vote
0answers
42 views

The solution of $\min_x \max_{1\leq r \leq N} \left|\frac{\sin rMx}{\sin rx}\right|$

I am looking for the solution of $$\min_x \max_{1\leq r \leq N} \left|\frac{\sin rMx}{ M \sin rx}\right|$$ where $M < N$ are integers and $x \in \mathbb{R}^+$. For $M = 4, N = 6$, $f_{r,M}(x) =\...
1
vote
3answers
1k views

How to find maximum and minimum volumes

I would appreciate if somebody could help me with the following problem: Q: Let $S$ be the region bounded by the curves $y=\sin x \ (0 \leq x \leq \pi)$ and $y=0$. Let $V(c)$ be the volume of the ...
1
vote
1answer
376 views

Minimizing $L_\infty$ norm using gradient descent?

Curve fitting problems are solved by minimizing a cost/error function with respect to the model's parameters. Gradient descent and Newton's method are among many algorithms commonly used to minimize ...
1
vote
0answers
482 views

Notation for limit points of a minimizing sequence: $\arg \inf$

Could you tell me what is the accepted notation for the set of limit points of a minimizing sequence. For example, if I have a function $f(x)$ and a sequence $x_t$ such that $\lim f(x_t) = \inf f(x)$...
1
vote
1answer
82 views

How can we draw $14$ squares to obtain an $8 \times 8$ table divided into $64$ unit squares?

How can we draw $14$ squares to obtain an $8\times8$ table divided into $64$ unit squares? Notes: -The squares to be drawn can be of any size. -There will be no drawings outside the table.