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)

1
vote
0answers
93 views

KKT: Explain visually the optimality condition $F_0\cap G_0\cap H_0=\emptyset$

I am trying to understand visually what this condition actually mean. It is the optimality condition in KKT. It means something like that constraint -set, objective -set and hyperplane -set has no ...
1
vote
2answers
319 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 ...
1
vote
1answer
850 views

Need help with Lagrange Multipliers

I need to maximize $U = BM$ with constraits: $6B +3M = 60$, $B>0$ and $M>0$. The Lagrange function is $L=U + \lambda (6B+3M-60) + KB + HM$. So $$\partial_{\lambda}L= 6B+3M-60=0$$ ...
0
votes
1answer
25 views

Optimization involving integrals with varying limits

What are the common methods and tools to tackle optimization problemsinvolving integrals. To be precise lets consider the following optimization problem that I came across with: ...
0
votes
4answers
260 views

Maximizing the Magnitude of the Resultant Vector

Given a set of $n$ two-dimensional unit vectors: $\left\{ \mathbf{v}_1, \dots, \mathbf{v}_n \right\}$, I want to find the coefficients $\left\{ \alpha_1, \dots, \alpha_n \right\}$, $0 \leq \alpha_i ...
0
votes
2answers
114 views

Help finding local extrema of $f(x)=\frac{x}{\sqrt{2}}-3\sin\frac{x}{2}$

Find the local extrema of $f(x)=\dfrac{x}{\sqrt{2}}-3\sin\dfrac{x}{2}$ on the interval $0 \leq x \leq 2\pi$ $f^{\prime}=\dfrac{1}{\sqrt{2}}-3\cos \left(\dfrac{x}{2}\right) \left ( ...
0
votes
2answers
556 views

How to prove equality from poincare inequality?

Let $$D = \{y \in C^1(0,1) : y(0) = y(1) = 0\}$$ Suppose there exists a $C_0$ such that $$\int_{0}^{1} y^2 \ dx \leq C_0 \int_{0}^{1} (y')^2 \ dx$$ for all $y \in D$, and for all $C < C_0$ ...
0
votes
1answer
148 views

Explain Complementary Slackness $\mu_i g_i(x^*)=0\forall i$

Wikipedia here explains it like this: I understand it so that either $\mu_i=0$ or $g_i=0$ but this answer here: "If μ1≠0 and μ2≠0, then x is one of the two points at the intersection of the two ...
16
votes
4answers
840 views

Gerrymandering/Optimization of electoral districts for one particular party

I'm asking this on behalf of Zach Weiner (actually it's my own initiative in order to promote this site). Original text is here, and is as follows: Hey-- This is Zach from SMBC, and I have a math ...
9
votes
2answers
271 views

Maximising determinant problem

The problem is to maximise the determinant of a 3x3 matrix with elements from 1 to 9. Is there a method to do this without resorting to brute force?
8
votes
6answers
2k views

Optimization problem (in linear algebra course!)

Let $a_1, a_2, \ldots, a_n$ be real numbers such that $a_1 + \cdots + a_n = 0$ and $a_1^2 + \cdots +a_n^2 = 1$. What is the maximum value of $a_1a_2 + a_2a_3 + \cdots + a_{n - 1}a_n + a_na_1$? I'd ...
8
votes
1answer
2k views

On problems of coins totaling to a given amount

I don't know the proper terms to type into Google, so please pardon me for asking here first. While jingling around a few coins, I realized that one nice puzzle might be to figure out which $n$ or so ...
7
votes
1answer
11k views

How to compute the Pareto Frontier, intuitively speaking?

I'm working on a multi-objective optimization problem and we have 'alternatives' that are quantified on two dimensions - value and cost. Now the question is 'how does one compute a pareto frontier'? ...
6
votes
1answer
182 views

What is the minimal isoperimetric ratio of a polyhedron with $5$ vertices?

I'm asking and answering this question to provide a partial answer to this question and a comment on this answer at MO. The isoperimetric ratio $\mu$ of a solid is the ratio $A^3/V^2$, where $A$ is ...
5
votes
1answer
185 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 ...
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
909 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
1answer
529 views

Optimizing a functional with a differential equation as a constraint

I am working on solving the following optimization problem. I think it is well-poised but, if not, please give me some pointers that could make the question make more sense. We have a parametric ...
5
votes
0answers
304 views

(easier version)What is a working example for finding the maximum of a algebraic function $f(a,b,c,d,e)$ with 4 equality …

edit 2: If you are founding an answer would be interesting to you, please upvote this question, because i may use those point in order to start a new bounty. Edit 3: Can somebody answer? Edit 4:I ...
5
votes
2answers
2k views

Minimize a matrix function with constraints

Let $A, X\in\mathbb{R}^{n\times n}$. The scalar objective function is $$J=\mathrm{tr}(AX)$$ If no constraints, let the derivative of $J$ with respect to $X$ be zeros, then we have $$A=0$$ Suppose $A$ ...
5
votes
2answers
580 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} ...
5
votes
2answers
449 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. ...
4
votes
0answers
71 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
1answer
69 views

What exactly are the curves that are a best fit to the Harmonic Cantilever?

Let's start with a few references to get an idea: Daniel Goldwater: Harmonic Cantilever Book Stacking Problem Block-stacking problem Harmonic Series and Bricks Interesting related issues: Maximum ...
4
votes
2answers
91 views

How do I maximize $|t-e^z|$, for $z\in D$, the unit disk?

I guess this question doesn't have a closed form solution for all $t\in \Bbb C$, but I know one for $t=1$ provided by Daniel Fischer in a question I asked. $$\begin{align} \left\lvert ...
4
votes
1answer
113 views

How find this minimum $\sum_{i=1}^{n}a^2_{i}-2\sum_{i=1}^{n}a_{i}a_{i+1},a_{n+1}=a_{1}$

let $a_{1},a_{2},\cdots,a_{n}\ge 0$,and such $a_{1}+a_{2}+\cdots+a_{n}=1$. Find this follow minimum $$I=a^2_{1}+a^2_{2}+\cdots+a^2_{n}-2a_{1}a_{2}-2a_{2}a_{3}-\cdots-2a_{n-1}a_{n}-2a_{n}a_{1}$$ My ...
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 ...
4
votes
2answers
970 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 ...
4
votes
0answers
313 views

Extremal curve passing through a set of points

I'm having trouble recasting the following question in a form amenable to the calculus of variations. Question: Given a set of $n$ points $P=\{(x_1,y_1),..(x_n,y_n)\}$ what is the curve passing ...
4
votes
1answer
1k views

Dynamic programming - A type of balanced 0-1 matrix

I was reading the Wikipedia article of Dynamic programming, however, I'm having a hard time understanding the explanation given in the example for a type of balanced 0-1 matrix. The problem is stated ...
3
votes
0answers
98 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
1answer
74 views

Spacing of fence posts with minimal distance to other fence posts

Definition 1: A "fence" is a set of "fence post positions", where each pair of adjacent positions has the same difference (the spacing), e.g. $\{1,2, 3, 4\}$. A fence is described by three values ...
3
votes
3answers
180 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
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
2answers
173 views

Optimization for constrained problem

I'm reading about Lagrange multipliers from a Pattern recognition book appendix and on one point the following is stated: $\begin{align} ...
3
votes
3answers
1k views

How to find the minimum value of the expression?

Let $x$, $y$, $z$ be three nonegative real numbers and $x^2 + y^2 + z^2 = 5.$ Find the minimum of the expression $$E=\dfrac{1}{2}(x^2 y^2 + y^2 z^2 + z^2 x^2) + \dfrac{96}{x + y + z + 1}.$$ What ...
3
votes
3answers
76 views

Minimize $\| ACE \|$ by geometrical means

I have the following figure Where $AB=10$m, $BD=12$m and $DE=12$m. The point C can slide along the segment BD. Now the problem is to minimize the distance from A to D going along the dashed line. ...
3
votes
1answer
126 views

Maximizing a quadratic subject to $\lVert x\rVert_2 \le 1$

Consider the $n$-dimensional quadratically constrained quadratic optimization problem $$\max \frac12 x^TAx + b^Tx \\ \text{s.t. } \lVert x\rVert_2 \le 1,$$ where $A$ is a symmetric $n\times n$ matrix ...
3
votes
2answers
2k 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 ...
3
votes
2answers
94 views

a plausible maximum or minimum

Is the following statement true? Let $a_1\ge a_2\ge \cdots \ge a_n>0$, $b_1\ge b_2\ge \cdots \ge b_n>0$, then $$\max\limits_{\sigma\in S_n}\;\;\prod\limits_{i=1}^n(a_i+b_{\sigma ...
3
votes
6answers
397 views

Optimizing $a+b+c$ subject to $a^2 + b^2 + c^2 = 27$

If $a,b,c \gt 0$ and $a^2+b^2+c^2=27$, find the maximum and minimum values of $a+b+c$. How to solve this one? (Here's the source of inspiration for the problem.)
3
votes
1answer
557 views

Construct dual network for conversion of min-cut problem to shortest path problem

I was wondering if there is some typo in the following description from Section 8.4 p263 of Network Flows: Theory, Algorithms, and Applications by Ravindra K. Ahuja, Thomas L. Magnanti, and James B. ...
3
votes
1answer
336 views

Classifying singular points as local min, max or saddle points

I want to determine if a singular point is a local min, max or saddle point. We are dealing with singular points so we cannot use the hessian matrix. What I have written, and I think I must of missed ...
2
votes
1answer
16 views

Algebraic Riccati equation (DARE) stabilazability condition

I'm Trying to help in this question which involves Algebraic Ricatti equation. Honestly to say I never met this equation before. I'm struggling to understand the conditions stated in the limitations ...
2
votes
2answers
73 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)$, ...
2
votes
0answers
189 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 ...
2
votes
1answer
65 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
3answers
96 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
123 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} ...
2
votes
3answers
145 views

Is this optimization problem solvable?

I have the following optimization problem: $$ \min_\mathbf{x}\|\mathbf{a+Bx}\|^2 ~~\text{s.t}~~ \|\mathbf{y+Ax}\|_\infty \leq \beta\|\mathbf{y}\|_\infty ~~,~~ \|\mathbf{x}\|^2 \leq \alpha^2$$ where ...