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
0answers
90 views

Quadratic optimisation with quadratic equality constraints

I would like to solve the following optimisation problem: $$\text{minimize} \quad x'Ax \qquad \qquad \text{subject to} \quad x'Bx = x'Cx = 1$$ Where $A$ is symmetric and $B$ and $C$ are diagonal. ...
5
votes
1answer
1k views

A property of the minimum of a sum of convex functions

Let $g_1(x), \ldots, g_k(x)$ be convex functions from $\mathbb{R}^n$ to $\mathbb{R}$, and lets assume that global minimum of each $g_i$ is unique and is achieved, denoting $$x_i = \arg \min_{x \in \...
5
votes
2answers
456 views

Eleven unit squares inside a larger square

What is the smallest square which contains 11 non-overlapping (except boundary) unit squares? This question is open but I would like to know a method to verify the best known answer at the moment. I'...
5
votes
2answers
613 views

Generalizing Lagrange multipliers to use the subdifferential?

Background: This is a followup to this question: Lagrange multipliers with non-smooth constraints Lagrange multipliers can be used for constrained optimization problems of the form $\min_{\vec x} f(...
5
votes
2answers
257 views

Proving that $\text{ri rge}\,A=\text{ri conv rge}\,A$

"If $A:\mathbb R^n\rightrightarrows\mathbb R^n$ is maximal monotone,then $\text{ri rge}\,A$ is convex". This is a proposition in auslender's book about the asymptotic cones. We can prove that $$\text{...
5
votes
1answer
57 views

Fundamental Optimization question consisting of two parts.

A) Find all extrema of $$f(x)=\sum_{k=1}^{n} x_{k}^{2} $$ subject to the constraint $\sum_{k=1}^{n}\vert x_k\vert^p=1$ B) prove that $$\frac{1}{n^{(2-p)/(2p)}}(\sum \vert x_k\vert^p)^{(1/p)}\le (\sum ...
5
votes
1answer
216 views

dual problem of a Semidefinite programming in a non-standard forme

I have a problem with calculating the dual problem of : $$ \mbox{Minimize } tr(Y) + \frac{1}{\eta} tr(Z) $$ $$ \begin{pmatrix} Y & X \\ X & Z+\varepsilon I \end{pmatrix} \succeq 0 \mbox{,...
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
391 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 ...
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
2answers
1k views

Change-making problem - counterexample for greedy algorithm

Let D be set of denominations and m the largest element of D. We say c is counterexample if greedy algorithm is giving answer different from optimal one. I found statement that if for given set ...
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
3answers
207 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
76 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
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
2answers
648 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,\...
3
votes
2answers
294 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
1answer
54 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
1answer
49 views

Maximizing $\frac{x(1-f(x))}{3-f(x)}$

Let $f:[0,1]\rightarrow[0,1]$ be a nondecreasing function such that $f(0)=0$ and $f(1)=1$. Let $x_1\in[0,1]$ be the value maximizing $x(1-f(x))$. Let $x_2\in[0,1]$ be the value maximizing $\frac{x(...
3
votes
2answers
224 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
0answers
350 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
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
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
131 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
2
votes
1answer
57 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
3answers
170 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
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
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$ ...
2
votes
1answer
677 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
180 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
4answers
114 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
2answers
231 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
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
1answer
214 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
1answer
218 views

What is the difference between projected gradient descent and ordinary gradient descent?

I just read about projected gradient descent but I did not see the intuition to use Projected one instead of normal gradient descent. Would you tell me the reason and preferable situations of ...
2
votes
1answer
255 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
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
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
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
3answers
544 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
1answer
2k 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
1answer
392 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 ...
2
votes
1answer
385 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
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^{|...
1
vote
3answers
464 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
75 views

proving that $\text{aff}C-\text{aff}C\subset\text{aff}\,(C-C)$

In proof of Theorem 6.4.1 of Auslender's book about asymptotic cones, the author assumes that $\text{rge}\,A\subset\text{aff}\,C$ and for $\epsilon>0$ claims that $\epsilon^{-1}(C-\text{rge}\,A)\...
1
vote
1answer
71 views

The Jeep Problem and Nash's Friends

The classical jeep problem is the following. A jeep can carry a maximum load of fuel of 1 gallon, and it travels $l$ miles with $l$ gallons of fuel. The jeep moves along a straight line, and is ...
1
vote
1answer
208 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
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
0answers
490 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)$...